Packrat parsing

Packrat parsing is a form of recursive descent parsing that employs memoization to ensure that each parsing function is evaluated at most once for a given input position. The technique was formally described by Bryan Ford in 2002, who showed that it can parse any grammar in the class of parsing expression grammars (PEGs) in linear time.¹ The key idea is to store the result of each parsing rule for each position in a memoization table, so that when backtracking occurs, previously computed results are reused rather than recomputed.

This approach eliminates the exponential time complexity that can arise from naive backtracking in recursive descent parsers. However, the memoization table can grow quadratically in the worst case, leading to high memory consumption. For example, a grammar with many rules and a long input can require storing results for every rule at every position, resulting in O(n^2) space.²

Packrat parsing is closely tied to parsing expression grammars (PEGs), a formal grammar formalism introduced by Ford in the same 2002 paper. PEGs are unambiguous and support ordered choice, where the first matching alternative is selected, and unlimited lookahead via syntactic predicates. These features make PEGs expressive but also require careful handling of backtracking.

Because PEGs are deterministic, they avoid the ambiguity of context-free grammars, but they also mean that the order of alternatives matters. Packrat parsing is the natural implementation strategy for PEGs, as it provides the memoization needed to handle the backtracking efficiently. Many modern parser generators, such as PEG.js and Parboiled, use packrat parsing under the hood.

Packrat parsing is used in a variety of practical applications, including programming language compilers, configuration file parsers, and data format parsers. It is particularly popular in the JavaScript ecosystem, where libraries like PEG.js (now Peggy) allow developers to define grammars in a PEG syntax and generate parsers that run in linear time.

Other notable implementations include Packrat for Python, Ratpack for Java, and rust-peg for Rust. These tools often provide additional features such as error reporting and grammar debugging. In addition, packrat parsing has been used in academic research for parsing natural language and for implementing domain-specific languages.³

While packrat parsing guarantees linear time, its space usage can be prohibitive for large inputs. The memoization table stores results for every rule at every position, which can lead to O(n^2) memory consumption. This is a significant drawback for parsing very large files, such as those found in big data applications.

To mitigate this, some implementations use lazy memoization, where results are computed only when needed, or they use heuristics to discard unused entries. Another approach is to use a hybrid strategy that falls back to backtracking when memory is limited. Despite these challenges, packrat parsing remains attractive for grammars that require extensive backtracking, as the time savings often outweigh the memory costs.⁴

One lesser-known aspect of packrat parsing is its connection to chart parsing in natural language processing. Chart parsers also use memoization to avoid redundant work, and packrat parsing can be seen as a top-down variant of chart parsing. This connection has been explored in the literature, with some researchers proposing unified frameworks.

Another edge case is the handling of left recursion in PEGs. Standard packrat parsing cannot handle left-recursive rules directly, as they would cause infinite recursion. However, techniques such as left recursion elimination or seed growing have been developed to extend packrat parsers to support left recursion, as demonstrated in the OMeta language.⁵

Memoization

A technique of storing the results of expensive function calls and reusing them when the same inputs occur again.

Parsing expression grammar (PEG)

A formal grammar formalism that uses ordered choice and unlimited lookahead, designed for unambiguous parsing.

Backtracking

A strategy in parsing where the parser tries alternatives and reverts to a previous state if a choice fails.