Generating Parsers from PEGs

• Recursive-descent parsing

  • Simple & direct, but exponential-time if not careful

• Packrat parsing [Birman '70/'73, Ford '02]

  • Linear-time, but can consume substantial storage

• Classic LL/LR algorithms?

  • Grammar restrictions, but both time- & space-efficient