mogoz

Parsing Expression Grammar (PEG)

tags
Context Free Grammar (CFG) , Programming Languages , Parsers , Production Systems

What

  • Syntactically, PEGs also look similar to context-free grammars (CFGs), but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG.
  • Unlike CFGs, PEGs cannot be ambiguous; a string has exactly one valid parse tree or none
  • Provides unlimited lookahead capability
  • An Alternative to Context Free Grammar (CFG)

About PEG Parsers

  • See Parsers
  • It’s possible to build LL and LR parsers for some PEGs but all PEGs can’t be built using LL/LR because of unlimited lookahead. (NOTE: I don’t understand this properly)
  • PEG can be parsed in linear time by using a packrat parser

Links to this note