| r[notation] | |
| # Notation | |
| r[notation.grammar] | |
| ## Grammar | |
| r[notation.grammar.syntax] | |
| The following notations are used by the *Lexer* and *Syntax* grammar snippets: | |
| | Notation | Examples | Meaning | | |
| |-------------------|-------------------------------|-------------------------------------------| | |
| | CAPITAL | KW_IF, INTEGER_LITERAL | A token produced by the lexer | | |
| | _ItalicCamelCase_ | _LetStatement_, _Item_ | A syntactical production | | |
| | `string` | `x`, `while`, `*` | The exact character(s) | | |
| | x<sup>?</sup> | `pub`<sup>?</sup> | An optional item | | |
| | x<sup>\*</sup> | _OuterAttribute_<sup>\*</sup> | 0 or more of x | | |
| | x<sup>+</sup> | _MacroMatch_<sup>+</sup> | 1 or more of x | | |
| | x<sup>a..b</sup> | HEX_DIGIT<sup>1..6</sup> | a to b repetitions of x, exclusive of b | | |
| | x<sup>a..=b</sup> | HEX_DIGIT<sup>1..=5</sup> | a to b repetitions of x, inclusive of b | | |
| | x<sup>n:a..=b</sup> | `#`<sup>n:1..=255</sup> | a to b repetitions of x (inclusive of b), with the count bound to the name n | | |
| | x<sup>n</sup> | `#`<sup>n</sup> | x repeated the number of times bound to n by a previous labeled repetition | | |
| | Rule1 Rule2 | `fn` _Name_ _Parameters_ | Sequence of rules in order | | |
| | \| | `u8` \| `u16`, Block \| Item | Either one or another | | |
| | ! | !COMMENT | Matches if the expression does not follow, without consuming any input | | |
| | \[ ] | \[`b` `B`] | Any of the characters listed | | |
| | \[ - ] | \[`a`-`z`] | Any of the characters in the range | | |
| | ~\[ ] | ~\[`b` `B`] | Any characters, except those listed | | |
| | ~`string` | ~`\n`, ~`*/` | Any characters, except this sequence | | |
| | ( ) | (`,` _Parameter_)<sup>?</sup> | Groups items | | |
| | ^ | `b'` ^ ASCII_FOR_CHAR | The rest of the sequence must match or parsing fails unconditionally ([hard cut operator]) | | |
| | U+xxxx..xxxxxx | U+0060 | A single Unicode character | | |
| | \<text\> | \<any ASCII char except CR\> | An English description of what should be matched | | |
| | Rule <sub>suffix</sub> | IDENTIFIER_OR_KEYWORD <sub>_except `crate`_</sub> | A modification to the previous rule | | |
| | // Comment. | // Single line comment. | A comment extending to the end of the line. | | |
| Sequences have a higher precedence than `|` alternation. | |
| r[notation.grammar.cut] | |
| ### The hard cut operator | |
| The grammar uses ordered alternation: the parser tries alternatives left to right and takes the first that matches. If an alternative fails partway through a sequence, the parser normally backtracks and tries the next alternative. The cut operator (`^`) prevents this. Once every expression to the left of `^` in a sequence has matched, the rest of the sequence must match or parsing fails unconditionally. | |
| Mizushima et al. introduced [cut operators][cut operator paper] to parsing expression grammars. In the PEG literature, a *soft cut* prevents backtracking only within the immediately enclosing ordered choice --- outer choices can still recover. A *hard cut* prevents all backtracking past the cut point; failure is definitive. The `^` used in this grammar is a hard cut. | |
| The hard cut operator is necessary because some tokens in Rust begin with a prefix that is itself a valid token. For example, `c"` begins a C string literal, but `c` alone is a valid identifier. Without the cut, if `c"\0"` failed to lex as a C string literal (because null bytes are not allowed in C strings), the parser could backtrack and lex it as two tokens: the identifier `c` and the string literal `"\0"`. The [cut after `c"`] prevents this --- once the opening delimiter is recognized, the parser cannot go back. The same reasoning applies to [byte literals], [byte string literals], [raw string literals], and other literals with prefixes that are themselves valid tokens. | |
| r[notation.grammar.string-tables] | |
| ### String table productions | |
| Some rules in the grammar — notably [unary operators], [binary | |
| operators], and [keywords] — are given in a simplified form: as a listing | |
| of printable strings. These cases form a subset of the rules regarding the | |
| [token][tokens] rule, and are assumed to be the result of a lexical-analysis | |
| phase feeding the parser, driven by a <abbr title="Deterministic Finite | |
| Automaton">DFA</abbr>, operating over the disjunction of all such string table | |
| entries. | |
| When such a string in `monospace` font occurs inside the grammar, | |
| it is an implicit reference to a single member of such a string table | |
| production. See [tokens] for more information. | |
| r[notation.grammar.visualizations] | |
| ### Grammar visualizations | |
| Below each grammar block is a button to toggle the display of a [syntax diagram]. A square element is a non-terminal rule, and a rounded rectangle is a terminal. | |
| [binary operators]: expressions/operator-expr.md#arithmetic-and-logical-binary-operators | |
| [byte literals]: tokens.md#r-lex.token.byte.syntax | |
| [byte string literals]: tokens.md#r-lex.token.str-byte.syntax | |
| [cut after `c"`]: tokens.md#r-lex.token.str-c.syntax | |
| [cut operator paper]: https://kmizu.github.io/papers/paste513-mizushima.pdf | |
| [hard cut operator]: notation.md#the-hard-cut-operator | |
| [keywords]: keywords.md | |
| [raw string literals]: tokens.md#r-lex.token.literal.str-raw.syntax | |
| [syntax diagram]: https://en.wikipedia.org/wiki/Syntax_diagram | |
| [tokens]: tokens.md | |
| [unary operators]: expressions/operator-expr.md#borrow-operators |