Parsing Expression Grammar

Parsing expression grammars (PEGs) are an analytic grammar formalism.

They feature the following operators:

• sequencing (e1 e2)
• unambiguous choice (e1/e2)
• (greedy) repetition (e*)
• option (e?)
• one-or-more (e+)
• positive lookahead (&e)
• negative lookahead (!e)

They are:

• fast to parse (O(n) in time and space, where n is the size of the input)
• unambiguous by construction
• closed under composition, which allows modular grammars
• more expressive than context-free grammars (they can parse L="a"^n"b"^n"c"^n)

However, they come with their share of problems:

• PEGs can't directly handle left-recursion (not much of a problem in practice)
• PEGs suffer from so called "prefix capturing": "a*a" will never match any input
  • (this is what you get for defining away ambiguity)
• PEGs are bad for specifying languages: just guess what language "S <- aSa / aa" parses
  • for the lazy: A string of "a"s with a length which is a power of two!
• PEGs can't generate strings, only parse them (due to lookahead operators)
  • it seems to me that one could 'enforce' discovery of whatever one looked ahead to find
  • Generating "(&A)B" would involve finding the intersection of A and B. This is an undecidable problem: If it would be possible to find the intersection of two PEGs we would not have issues detecting prefix capture. Prefix-capture is present in "A/B" iff the language generated by "(&A)B" is not empty. See [1] for more information.

[1] http://charybde.homeunix.org/~schmitz/pub/modular.pdf

---

CategoryCompilers