Packrat parser

From Wikipedia, the free encyclopedia

A packrat parser^[1] 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.

[edit] References

1. ^ Ford, Bryan, Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking, Master’s thesis, Massachusetts Institute of Technology, September, 2002.

[edit] See also

• dynamic programming

[edit] External link

• The Packrat Parsing and Parsing Expression Grammars Page