Parsing Expression Grammar
Parsing Expression Grammar, or PEG, is a formal parsing language that permits infinite lookahead but runs in linear time.
PEG and Packrat parsing are used in OpenCog's Lojban Framework to parse Lojban utterances into abstract syntax trees. It is possible to use it for parsing other grammars, though no other parsers have been implemented.
A Packrat Parser is an implementation of PEG as a recursive descent parser with infinite lookahead and memoization of intermediate results. It is so widely used to implement parsing expression grammars that it is synonymous with the PEG language itself.
- genturfa'i, a PEG to Scheme compiler.
- Lojban Grammar, which is specified in PEG.
- ratcu, an imaginary friend in the game Where Are Your Keys? inspired by the packrat parsing metaphor.
- Brian Ford's Packrat Parsing and Parsing Expression Grammars Page, an occasionally out-of-date but otherwise authoritative reference on PEG.