Some documentation for the pest_meta crate and the semantics of pest grammars

[Tartasprint]

I'm trying to address the problem of grammars that run indefinitely (by detecting and reporting them) in #851.
For that I need the semantics of pest to be clear to me. So I read slices of the book, didn't find everything I wanted there, then I looked at the docs. There were still question unanswered, such as «what happens when the stack is empty and a POP comes by ?». I expected it to simply fail. Turns out it panics ! My surprise lead me to distrust the docs, and I jumped into the source code.

I started answering all my questions, and I wrote those two recaps about what I read. I guess those might be integrated in the docs. The thing is that I'm not sure where to add them.

The first one is about the precise semantics of Pest, and is yet incomplete. I think this one should be added to the book, but marked as a reference and not a tutorial because of the tone used. Once the TODOs I listed in here are done, including important things: the white space/comment/trivia and the modifiers (atomic, ...) are essential aspects of pest.

The second one is about the inner workings of the pest_meta crate. I think it could go on that crate's documentation. But maybe it's more addressed to a contributor to pest ?

Please give your thoughts about it, whether this could be useful, if this was already said in part somewhere I didn't check and could be adapted to fit there ? Are there things you would add ?

[Tartasprint]

Semantics of Pest

Terminals

Sensitive

Examples: "", "a", "Some text", "Works with Unicode"

• Syntax: string := " inner_str "
• Transformation: escape codes are replaced by what they represent
• Matches:
  • when
    • the next characters in the input are equal the content of the inner_str
    • always when the string is empty.
  • side-effect: advances the input cursor by the length of inner_str.
• Fails
  • when: otherwise
  • side-effect: none
• Examples
  • "":

Insensitive

• Syntax: insensitive_string := ^" inner_str^inner "
• Transformation: escape codes are replaced by what they represent
• Matches:
  • when
    • the next length(inner) characters in the input, if mapping ASCII characters "A"-"Z" to "a"-"z" of both the input and the string, match the full string
    • always when the string is empty.
  • side-effect:
    • advances the input cursor by the length of the string
    • doesn't change input from "A".."Z" to "a".."z" (just to be clear)
• Fails
  • when: otherwise
  • side-effect:
    • none
    • doesn't change input from "A".."Z" to "a".."z" (just to be clear)
• Examples:
  • ^"": always matches, doesn't advance input cursor.
  • ^"a" or ^"A": matches if the next character on input is a or A, and in that case advances the input cursor by 1 character. Fails otherwise.
  • ^"aBc 12": matches if the next 5 characters on input are one of abc 12, abC 12, aBc 12, aBC 12, Abc 12, AbC 12, ABc 12 or ABC 12. In that case advances the input cursor by 5 characters. Fails otherwise.
  • ^"Λλ": matches only if the next 2 characters on input are Λλ, and advances the input cursor by 2 characters. Fails otherwise. ⚠Notice⚠: Doesn't match on any of the following ΛΛ, λΛ or λλ, because pest only supports ASCII insensitive case matching.

Ranges

• Syntax: range := ' (escape | ANY)^lower '..' (escape | ANY)^upper'
• Transformation: escape codes are replaced by what they represent
• Matches:
  • when: the next character's Unicode code point x in the input verifies x_lower≤xand x≤x_upper, where x_lower and x_upper are the Unicode code points of the lower and upper character bounds of the range.
  • side-effect: advances the input cursor by one character.
• Fails:
  • when:
    • otherwise
    • ⚠Notice⚠: A particular case is when x_lower>x_upper, the range expression will always fail.
• Examples:
  • 'a'..'z': matches lower-case ASCII letters
  • '\u{0370}'..'\u{03FF} or 'Ͱ'..'Ͽ: matches the Greek and Coptic letters Unicode range
  • '\u{00}'..'\u{10FFFF}': Matches any Unicode character, same as ANY

Start and End of Input

For SOI and EOI, see Predicates

Stack operations without expression paramater

For POP, PEEK/PEEK[..], POPALL or PEEKALL see Stack operations

Built-in Rules

ANY

• Matches:
  • when there is a next character in the input.
  • side-effect: advances de input cursor by 1 character.
• Fails: otherwise.

Other built-in rules

See the Pest Book's chapter about it.

User defined rules

Syntax: ident^name = modifier? { expr^def }
Defines a new rule identified by name. A name can be assigned only to one rule.

Modifiers

Syntax: _ or @ or $ or !

TODO when thinking about it doesn't give headaches

Sequence operator/expression

• Syntax: expr^left ~ expr^right
• Precendence: over the choice operator, preceeded by unary operators
• Behaviour:
  1. Run the left expression. If it matches go to step 2, if it fails go to step 3.
  2. Run the right expression. If it matches go to step 4. If it fails go to step 4.
  3. The sequence expression failed.
  4. The sequence expression matched.
• Matches: if left followed by right matches.
• Fails: otherwise

Choice operator/expression

• Syntax: expr^left | expr^right
• Precendence: no precedence
• Behaviour:
  1. Capture current state in S.
  2. Run the left expression. If it matches go to step 4, if it fails go to step 3.
  3. Restore the initial state S. Run the right expression. If it matches go to step 4. If it fails go to step 3.
  4. The choice expression failed.
  5. The choice expression matched.
• Matches: if left followed by right matches.
• Fails: otherwise

Repetition operator/expression

• Syntax: expr^pat*
• Semantic equivalence:

  rephand = _{ pat~rephand | ""}
  repsugar = _{ pat{0,} | ""}
  

  For more kinds of repetition see Syntactic sugar: Repetitions
• Precendence: Higher than predicates, sequence and choice operators.
• Matches:
  • when: always: at least an empty input; matches as many times pat with the input as it can.
  • side effect: none if pat didn't match the first time; the cumulated side-effects of matching pat as many times as possible.
• Fails: never

Predicates

Positive predicate operator

• Syntax: &expr^inner
• Precendence: Higher than sequence and choice operators, lower than repetition operators
• Behavior:
  1. the state is saved,
  2. inner is ran against the input,
  3. the state is restored.
• Matches:
  • when: the inner expression matches.
  • side-effect: none.
• Fails:
  • when: the inner expression fails.
  • side-effect: none.

Negative predicate operator

• Syntax: !expr^inner
• Precendence: Higher than sequence and choice operators, lower than repetition operators
• Behavior:
  1. the state is saved,
  2. inner is ran against the input,
  3. the state is restored.
• Matches:
  • when: the inner expression fails.
  • side-effect: none.
• Fails:
  • when: the inner expression matches.
  • side-effect: none.

Start Of Input

• Syntax: SOI
• Precendence: It is seen as terminal
• Matches:
  • when: the input cursor is at the start of the input (0).
  • side-effect: none.
• Fails:
  • when: otherwise
  • side-effect: none.

End Of Input

• Syntax: EOI
• Precendence: It is seen as terminal
• Matches:
  • when: the input cursor is at the end of the input (after the last character in the input, input.len()).
  • side-effect: none.
• Fails:
  • when: otherwise
  • side-effect: none.

Stack

PUSH

• Syntax: PUSH( expr^inner )
• Precendence: It is seen as a "terminal" (with an inner expression)
• Matches:
  • when: the inner expression matches.
  • side-effect: The inner's (match) side-effects, followed by pushing the exact string matched by inner on the stack.
• Fails:
  • when: otherwise
  • side-effect: inner's (match) side-effects

POP

• Syntax: POP
• Precendence: It is seen as a terminal
• Panics: ⚠Notice⚠: if the stack is empty.
• Matches:
  • when: the last string on the stack matches exactly the next input characters
  • side-effect: pops the last string on the stack, advances the input cursor by the length of that last string.
• Fails:
  • when: otherwise
  • side-effect: pops the last string on the stack.

PEEK

• Syntax: PEEK
• Precendence: It is seen as a terminal
• Panics: ⚠Notice⚠: if the stack is empty.
• Matches:
  • when: the last string on the stack matches exactly the next input characters
  • side-effect: advances the input cursor by the length of that last string. Doesn't change the stack.
• Fails:
  • when: otherwise
  • side-effect: none

POPALL

• Syntax: POPALL
• Precendence: It is seen as a terminal
• Matches:
  • when:
    • always if the stack is empty
    • the next characters in input match the concatenation of all the strings on the stack, starting by the last pushed one.
  • side-effect: advances the input cursor by the length of the concatenation all the strings on the stack. Empties the stack.
• Fails:
  • when: otherwise
  • side-effect: Empties the stack.

PEEKALL

• Syntax: PEEKALL
• Precendence: It is seen as a terminal
• Matches:
  • when:
    • always if the stack is empty
    • the next characters in input match the concatenation of all the strings on the stack, starting by the last pushed one.
  • side-effect: advances the input cursor by the length of the concatenation all the strings on the stack. Doesn't change the stack.
• Fails:
  • when: otherwise
  • side-effect: none

Tags

• Syntax: # (_ | a..z | A..Z)+^tag_id= expr^inner
• Precendence: ???
• Behavior: same as the inner expr, except it marks the parsed node with the tag_id.

Syntactic sugar

Sugared repetitions

Exact

• Syntax: expr^inner {numberⁿ}
• Transformation:

($inner)~($inner)...~($inner)
                ▲
    (n times)───╯

Bounded

• Syntax: expr^inner { number^min,number^max} or expr^inner{,number^max}
• Transformation:

($inner)~($inner)...~($inner) ~ ($inner)? ~ ... ~ ($inner)?
                  ▲                         ▲
    (min times)───╯           (max times)───╯

If min is not provided, it is set to zero. max must be positive. ⚠Notice⚠: if min>max it seems to result into inner{max} .

Unbounded

• Syntax: expr^inner { number^min ,}
• Transformation:

($inner)~($inner)...~($inner)    ~ ($inner)*
                  ▲
    (min times)───╯

min must be provided.

One or more

• Syntax: expr^inner +
• Transformation:

($inner) ~ ($inner)*

Text representation

The following syntax rule describes the interior of a string or of an insensitive_string. It supports escape codes, see Escape codes for more information.

inner_str := (NOT(" | \) ANY)* (escape inner_str)?`

By the content/length of a inner_str is meant the the content/length that the inner_str represents after escape code replacement. Here are some examples:

• some text: content: some text; length: 9;
• Smiling face \u{1F600}: content: Smiling face 😀; length: 14;

Escape codes

Pest currently supports the following escape codes:

Escape code	Result	Character Unicode code-point
\"	" (QUOTATION MARK)	U+0022
\r	Carriage Return (CR)	U+000D
\n	Line feed (LF)	U+000A
\t	Horizontal tabulation (HT)	U+0009
\0	Null character (NUL)	U+0000
\'	' (APOSTROPHE)	U+0027
\x ASCII_HEX_DIGITa ASCII_HEX_DIGITb	Unicode code point U+00ab	U+00ab
\u{ ASCII_HEX_DIGIT{2,6}code }	Unicode code point U+code	U+code

escape designates any of the escape codes listed up there.

Some examples of x-escapes are: \x4D or \x4d for letter M.
Some examples of u-escapes are: \u{61} for letter a, \u{03Bc} for letter μ , \u{1F600} for 😀.

x-escapes and u-escapes should always be valid chars.

TODO

• Check operator precendence
• Add rules about whitespace
• Add section about user-defined rules
  • Add explanations for the modifiers
• Complete the examples
• Cover the PEEK[..] syntax
• Investigate how tags actually tag
• Add all the checks from

[Tartasprint]

Pest meta, parsing and preparing a Pest Grammar

There are several stages in the parsing of a *.pest grammar file.
The entry point is at:

fn parse_and_optimize(
    grammar: &str,
) -> Result<UsedBuiltinAndOptimized<'_>, Vec<Error<parser::Rule>>>

in pest/meta/src/lib.rs.

Below are listed the different transformations this function performs. Validation steps were marked by ☑. Every validation step returns either Ok or Err(Vec<Error<parser::Rule>>), and in that case returns immediately. That means that if errors are found at step 2, step 3 (and all the following) is not run. Every validation step returns as many errors as it could find though.

1. Parsing (str -> Pairs<Rule>)
   Done by the parser pest/meta/src/grammar.rs generated by the bootstrap script from the grammar pest/meta/src/grammar.pest

2. ☑ Validation of the pairs, checks for [meta::validator::validate_pairs]:

   1. No overriden built-in rule
   2. All rule used are defined
   3. No rules are defined multiple times.

3. Conversion to an AST (Pairs<Rule> -> Vec<AstRule) [meta::parser::consume_rules]

   1. Construction of the AST in a temporary representation (Pairs<Rule> -> Vec<ParserRule>) [meta::parser::consume_rules_with_spans]

      ☑ Also checks the following properties [meta::parser::consume_expr]:

      • String terminal having custom escape sequences (\x and \u) produce valid UTF-8 chars.
      • On sugar repetitions, if given, the min or max musnt't overflow u32.
      • Sugar repetitions shouldn't specify a number of 0 repetitions
      • ⚠Notice⚠: No checks that in expr{min,max}, min<=max

   2. ☑ Validation of the AST [meta::validator::validate_ast]

      1. Infinite loops (either from repetitions or from left-recursion)
      2. Unreachable choices

   3. Conversion of the temporary representation to a another representation of the AST (Vec<ParserRule> => Vec<AstRule>) [meta::validator::convert_rule]

      The temporary representation kept data about the spans to provide reports (through pest::error::Error) and is removed at this stage. The target enum for expressions meta::ast::Expr also contains one more variant, Expr::Skip(Vec<String>).

4. Optimization (Vec<Rule>=> Vec<OptimizedRule>) [meta::optimizer::optimize]

   1. Rotate - Ensures the lhs of Expr::Choice is never an Expr::Choice, and lhs of Expr::Seq is never an Expr::Seq.
   2. Skip - Transform (!(expr)~ANY)* into Expr::Skip(expr), where expr is of the form "string1" | ... | "stringN" (a choice only Expr::Str)
   3. Unroll - Removes usage of Expr::{RepOnce,RepExact,RepMin,RepMax,RepMinMax}
   4. Concatenate - Concatenates consecutive string or consecutive insensitive strings
   5. Factor - Converts (rule ~ rest) | rule to rule ~ rest? and rule | (rule ~ rest) to rule ~ rest
   6. List - Converts (rule ~ rest)* ~ rule to rule ~ (rest ~ rule)*
   7. Conversion to OptimizedRule (all the steps before used meta::ast::Rule)

   This new representation has no RepOnce,RepExact,RepMin,RepMax,RepMinMax; but has an additional RestoreOnErr(expr) variant to encode the need of ParserState reset when expr fails.

   8. Restore On Err - Annotate branches that need resetting the ParserState

5. Done

[NoahTheDuke]

This is amazing! Would you be interested in putting this into the docs?

[Tartasprint]

Thanks, I am interested:) but where ? In the pest_meta crate's top level documentation ? Because I'm not sure that the users of that crate are interested in knowing what happens behind the scenes. A contributor may be interested.