Packrat parser

A packrat parser is a form of parser similar to a recursive descent parser in construction, except that during the parsing process it memoizes the intermediate results of all invocations of the mutually recursive parsing functions. Because of this memoization, a packrat parser has the ability to parse many context-free grammars and any parsing expression grammar (including some that do not represent context-free languages) in linear time.

See also

• dynamic programming

External link

• The Packrat Parsing and Parsing Expression Grammars Page

See also: Packrat parser, Computer, Context-free grammar, Dynamic programming, Linear time, Memoization, Mutual recursion, Parser, Parsing