Packrat parsing:: simple, powerful, lazy, linear time, functional pearl

By Bryan Ford. ACM SIGPLAN International Conference on Functional Programming, 2002

379 citations recorded by the source corpus.

Packrat parsing is a novel technique for implementing parsers in a lazy functional programming language. A packrat parser provides the power and flexibility of top-down parsing with backtracking and unlimited lookahead, but nevertheless guarantees linear parse time. Any language defined by an LL(k) or LR(k) grammar can be recognized by a packrat parser, in addition to many languages that conventional linear-time algorithms do not support. This additional power simplifies the handling of common syntactic idioms such as the widespread but troublesome longest-match rule, enables the use of sophisticated disambiguation strategies such as syntactic and semantic predicates, provides better grammar composition properties, and allows lexical analysis to be integrated seamlessly into parsing. Yet despite its power, packrat parsing shares the same simplicity and elegance as recursive descent parsing; in fact converting a backtracking recursive descent parser into a linear-time packrat parser often involves only a fairly straightforward structural change. This paper describes packrat parsing informally with emphasis on its use in practical applications, and explores its advantages and disadvantages with respect to the more conventional alternatives.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/6713ff1746e7f1ef12e7231acf6310007079f443

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Paul Hudak
2. Philip Wadler
3. Simon L. Peyton Jones
4. Bryan Ford
5. John Hughes

In Computational Theory and Mathematics

1. Bryan Ford
2. John Hughes
3. Simon L. Peyton Jones
4. Paul Hudak
5. Philip Wadler

In Hardware and Architecture

1. Bryan Ford
2. John Hughes
3. Simon L. Peyton Jones
4. Paul Hudak
5. Philip Wadler

Citations in the corpus

• Parsing expression grammars: a recognition-based syntactic foundation (2004, methodology): “These existing systems generally use “naive” backtracking methods that risk exponential runtime in worst-case scenarios, but the same features can be implemented in strictly linear time using a memoizing “packrat parser” [8, 7].”
• A history of Haskell: being lazy with class (2007, methodology): “Wadler introduced the name “list comprehension” in his paper “How to replace failure by a list of successes” (Wadler, 1985).”