Parsing Expression Grammar Definition Interpretation Of Parsing

Each parsing rule in P has the form A ← e, where A is a nonterminal and e is a parsing expression. A parsing expression is a hierarchical expression similar to a regular expression, which is constructed in the following fashion:

Unlike in a context-free grammar or other generative grammars, in a parsing expression grammar there must be exactly one rule in the grammar having a given nonterminal on its left-hand side. That is, rules act as definitions in a PEG, and each nonterminal must have one and only one definition.

1.1 Interpretation of parsing expressions

Each nonterminal in a parsing expression grammar essentially represents a parsing function in a recursive descent parser, and the corresponding parsing expression represents the "code" comprising the function. Each parsing function conceptually takes an input string as its argument, and yields one of the following results:

A nonterminal may succeed without actually consuming any input, and this is considered an outcome distinct from failure.

An atomic parsing expression consisting of a single terminal succeeds if the first character of the input string matches that terminal, and in that case consumes the input character; otherwise the expression yields a failure result. An atomic parsing expression consisting of the empty string always trivially succeeds without consuming any input. An atomic parsing expression consisting of a nonterminal A represents a recursive call to the nonterminal-function A.

The sequence operator e₁ e₂ first invokes e₁, and if e₁ succeeds, subsequently invokes e₂ on the remainder of the input string left unconsumed by e₁, and returns the result. If either e₁ or e₂ fails, then the sequence expression e₁ e₂ fails.

The choice operator e₁ / e₂ first invokes e₁, and if e₁ succeeds, returns its result immediately. Otherwise, if e₁ fails, then the choice operator backtracks to the original input position at which it invoked e₁, but then calls e₂ instead, returning e₂'s result.

The zero-or-more, one-or-more, and optional operators consume zero or more, one or more, or zero or one consecutive repetitions of their sub-expression e, respectively. Unlike in regular expressions or context-free grammars, however, these operators always behave greedily, consuming as much input as possible. For example, the expression a* will always consume as many a's as are consecutively available in the input string, and the expression (a* a) will always fail because the first part (a*) will never leave any a's for the second part to match.

Finally, the and-predicate and not-predicate operators implement syntactic predicate s. The expression &e invokes the sub-expression e, and then succeeds if e succeeds and fails if e fails, but in either case never consumes any input. Conversely, the expression !e succeeds if e fails and fails if e succeeds, again consuming no input in either case. Because these can use an arbitrarily complex sub-expression e to "look ahead" into the input string without actually consuming it, they provide a powerful syntactic lookahead and disambiguation facility.

1.2 Examples

The parsing expression (a/b)* matches and consumes an arbitrary-length sequence of a's and b's. The rule S ← a S b describes the simple context-free "matching language" {aⁿbⁿ}. The following parsing expression grammar describes the classic non-context-free language {aⁿbⁿcⁿ} where n > 0:

S ← &(A b) a* B !c
A ← (a A b)?
B ← (b B c)?

The following recursive rule matches standard C-style if/then/else statements in such a way that the optional "else" clause always binds to the innermost "if", because of the implicit prioritization of the '/' operator. (In a context-free grammar, this construct yields the classic dangling elseThe dangling else is a well-known problem in computer programming in which a seemingly well-defined grammar can become ambiguous. In many programming languages you can write code like this: if a then if b then s1 else s2 which can be understood in two way ambiguity.)

S ← if C then S else S / if C then S

The parsing expression foo &(bar) matches and consumes the text "foo" but only if it is followed by the text "bar". The parsing expression foo !(bar) matches the text "foo" but only if it is not followed by the text "bar". The expression !(a+ b) a matches a single "a" but only if it is not the first in an arbitrarily-long sequence of a's followed by a b.

The following recursive rule matches Pascal-style nested comment syntax, (* which can (* nest *) like this *):

C ← "(*" I* "*)"
I ← C / (!"(*" Z)
Z ← any single character

2 Implementing parsers from parsing expression grammars

Any parsing expression grammar can of course be converted directly into a recursive descent parser. Due to the unlimited lookahead capability that the grammar formalism provides, however, the resulting parser could exhibit exponential time performance in the worst case.

By memoizing the results of intermediate parsing steps and ensuring that each parsing function is only invoked at most once at a given input position, however, it is possible to convert any parsing expression grammar into a packrat parser, which always runs in linear time at the cost of substantially greater storage space requirements.

It is also possible to build LL parsers and LR parsers from parsing expression grammars, but the unlimited lookahead capability of the grammar formalism is lost in this case.

3 See also

4 External link

The Packrat Parsing and Parsing Expression Grammars Page

<Hide>

Home > Parsing expression grammar

1 Definition