Packrat parser

A packrat parser is a kind of top-down parser built much like a recursive descent parser, but taking parsing expression grammars, or PEGs, as its input rather than LL grammars. Its roots lie in Alexander Birman's 1970 work on the TMG recognition scheme, later refined by Aho and Ullman as the Top-Down Parsing Language, which were the first deterministic top-down parsing methods with backtracking. Bryan Ford developed PEGs as an expansion of those schemes and introduced the packrat parser, which adds memoization to a simple PEG parser. Because PEGs allow unlimited lookahead, an unmemoized parser can take exponential time in the worst case. By recording the intermediate result of every parsing function, each function is called only once at a given input position. The price is memory, since packrat parsers need space proportional to the input length, which a cut operator can reduce on average but has not removed. A packrat parser also cannot handle left recursion directly, and rewriting indirect left recursion can be complicated.