Compilers
Packrat Parsing: Linear-Time PEG Parsing via Memoized Results
A naive recursive-descent parser with backtracking can take exponential time — 2ⁿ steps on a pathological grammar where every rule retries every alternative. Packrat parsing collapses that blowup to a flat, predictable O(n) by remembering: it caches the result of every parsing rule at every input position, so no rule is ever re-run at the same spot twice.
Packrat parsing is a table-driven technique for executing Parsing Expression Grammars (PEGs) in guaranteed linear time. It combines ordinary recursive descent with unlimited backtracking and unlimited lookahead, then makes that combination cheap by memoizing every (rule, position) result in a two-dimensional table. Invented by Bryan Ford at MIT in 2002, it trades memory for time — buying determinism and speed at the cost of O(n) space.
- InventorBryan Ford (MIT, 2002)
- Time complexityO(n) — linear in input length
- Space complexityO(n) — one memo table row per position
- Grammar formalismParsing Expression Grammar (PEG)
- Choice operatorOrdered / prioritized (e /) — no ambiguity
- Key limitationNo direct left recursion; O(n) memory
Interactive visualization
Press play, or step through manually. The visualization is yours to drive — try it before reading on.
Watch the 60-second explainer
A condensed visual walkthrough — narrated, captioned, under a minute.
What It Is and the Problem It Solves
Packrat parsing executes a Parsing Expression Grammar (PEG) — a grammar formalism where alternation is ordered (A / B tries A first, and only tries B if A fails), so a PEG describes a deterministic recognizer rather than an ambiguous language. PEGs also allow syntactic predicates: &e (and-predicate) and !e (not-predicate) provide unlimited lookahead without consuming input.
The catch is backtracking. Ordered choice plus unlimited lookahead means a rule may be attempted, fail deep inside, and be re-attempted from the same position under a different enclosing rule. Naive recursive descent re-does that work every time, and on adversarial grammars the repeated re-parsing compounds into exponential running time. Packrat parsing's insight is that a PEG rule invoked at input position i always yields the same result — success (with an end position and AST) or failure — regardless of context. So each of those results can be computed once and cached, eliminating all redundant re-parsing.
How It Works, Step by Step
The core data structure is a memo table: conceptually a 2-D array indexed by (rule R, position i). Each cell holds one of three states: unknown (not yet computed), failed, or matched — and a matched entry stores the end position and the result value.
- To parse rule
Rat positioni, first look upmemo[R][i]. - If the cell is matched or failed, return it immediately — no work.
- If unknown, run R's body: try each ordered alternative in turn, recursively parsing sub-expressions and consuming input.
- Store the outcome (fail, or match + end position) back into
memo[R][i]before returning.
parse(R, i):
if memo[R][i] is set: return memo[R][i]
res = apply R's ordered choices at i # may recurse
memo[R][i] = res # cache success or failure
return resBecause every cell is filled at most once and reading a cell is O(1), the total work is bounded by the number of cells times the cost per cell.
Complexity and a Worked Trace
Let n be the input length and g the number of grammar rules. The memo table has g·n cells. Each cell is computed exactly once; computing it does constant work plus the cost of its immediate sub-calls, and every sub-call is itself either a table hit (O(1)) or the one-time fill of another cell. With g a fixed constant for a given grammar, the total is O(g·n) = O(n) time and O(g·n) = O(n) space.
Worked trace on Expr <- Term ('+' Term)* against input a+b (positions 0..3):
parse(Term,0) -> match 'a', end=1 memo[Term][0]=match(1)
see '+' at 1, consume
parse(Term,2) -> match 'b', end=3 memo[Term][2]=match(3)
parse(Term,0) requested again later? -> TABLE HIT, returns match(1)
The key invariant: memo[R][i] is a pure function of (R, i) — independent of the call stack — so caching is always sound. If a naive parser would have re-entered Term at position 0 a hundred times during backtracking, packrat does it once and reads the answer ninety-nine times.
Real-System Usage
Packrat and PEG techniques underpin a wide slice of real tooling. Python's CPython switched its production grammar to a PEG parser in version 3.9 (PEP 617), replacing the decades-old LL(1) parser — it uses packrat-style memoization for the reserved backtracking points. The Rust ecosystem has pest and peg; JavaScript/TypeScript has PEG.js / Peggy and Ohm; Java has Parboiled and Rats! (part of the xtc toolkit, an early influential packrat generator). Ford's original reference implementation, Pappy, generated packrat parsers in Haskell.
PEG/packrat tools show up wherever developers want a grammar that is easy to compose and free of the shift/reduce conflicts that plague LALR generators: syntax highlighters, linters, configuration and data-format parsers, template languages, and domain-specific languages embedded in larger applications. The scannerless nature of PEGs (no separate lexer needed) makes them especially convenient for languages with context-sensitive tokenization.
Comparison and the Central Tradeoff
Against LALR(1) generators (yacc/bison): packrat accepts a strictly more convenient grammar class — ordered choice removes ambiguity by construction, so there are no shift/reduce or reduce/reduce conflicts to debug — and it supports unlimited lookahead. LALR needs only O(stack-depth) memory, though, versus packrat's O(n).
Against Earley and GLR: those handle any context-free grammar including ambiguous ones and left recursion, but pay O(n³) in the worst case. Packrat is faster (linear) but restricted to the PEG class and its deterministic-choice semantics.
The central tradeoff is stark: packrat spends O(n) memory to buy guaranteed O(n) time. That is the opposite of a naive backtracking parser, which uses little memory but risks exponential time. For a 10 MB source file this can mean allocating a memo table proportional to the file, an amount many production parsers deem unacceptable — which is exactly why CPython and others memoize selectively rather than every rule at every position.
Pitfalls and Significance
The signature pitfall is left recursion. Because packrat is recursive descent at heart, a rule like Expr <- Expr '+' Term recurses infinitely at the same position before any memo entry is written. Grammars must be rewritten to right recursion or iteration, or use the Warth–Douglass–Millstein technique (PEPM 2008) that seeds the memo cell with a failure and grows the match iteratively — at the cost of the clean linear guarantee.
The second pitfall is the O(n) memory itself. Mitigations include the cut operator (Mizushima et al., PASTE 2010), borrowed from Prolog, which marks points where backtracking is impossible so memo entries can be discarded, letting realistic grammars run in nearly constant space. A subtler trap: PEG's silent ordered choice can mask alternatives (put if after identifier and it never matches), and semantic predicates make error reporting harder than in CFG tools.
Significance: packrat unified backtracking, memoization, and a clean deterministic grammar formalism, proving that unlimited-lookahead parsing need not be slow — and directly inspired a generation of parser generators and even a mainstream language's front end.
| Technique | Time | Space | Grammar class | Left recursion |
|---|---|---|---|---|
| Packrat (PEG) | O(n) | O(n) | PEG (ordered choice) | Not directly |
| Naive recursive descent + backtrack | O(2ⁿ) worst case | O(depth) | PEG / TDPL | Not directly |
| Earley parser | O(n³), O(n²), O(n) | O(n²) | Any CFG (ambiguous OK) | Yes |
| LALR(1) / yacc | O(n) | O(depth) | Deterministic CFG subset | Yes |
| GLR | O(n³) worst case | O(n³) | Any CFG | Yes |
Frequently asked questions
Why can't packrat parsers handle left recursion?
Packrat is recursive descent underneath, so a left-recursive rule like Expr <- Expr '+' Term calls itself at the same input position before writing any memo entry, producing infinite recursion. The standard fix is to rewrite the grammar to right recursion or a repetition operator. Alternatively, the Warth et al. (2008) algorithm seeds the memo cell with failure and grows the match iteratively to support left recursion, but it gives up the clean linear-time guarantee.
Is packrat parsing really always linear time?
Yes, for a fixed grammar. The memo table has g×n cells (g rules, n input characters); each cell is computed at most once and every table lookup is O(1), so total work is O(g×n) = O(n). The linear bound holds despite unlimited backtracking and lookahead precisely because memoization prevents any rule from being re-evaluated at the same position twice.
What does packrat parsing cost in memory, and can I reduce it?
It uses O(n) space — the memo table grows in proportion to input length, not recursion depth, which can be orders of magnitude larger. You can shrink this with the cut operator (Mizushima 2010) that marks non-backtrackable points so entries can be freed, by memoizing only rules that actually benefit, or by sliding a bounded window as parsing advances. Many production PEG parsers memoize selectively for this reason.
How is a PEG different from a context-free grammar?
A CFG's alternation is unordered and can be ambiguous; a PEG's choice operator '/' is ordered, so A / B always tries A first and only falls back to B on failure — the grammar is a deterministic recognizer with no ambiguity. PEGs also add syntactic predicates (&e and !e) for unlimited lookahead. The practical consequence is that a PEG can silently mask an alternative if you order the choices wrong.
Who invented packrat parsing and where is it published?
Bryan Ford invented it in his 2002 MIT master's thesis, 'Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking.' The functional-pearl paper 'Packrat Parsing: Simple, Powerful, Lazy, Linear Time' appeared at ICFP 2002, and the companion PEG formalism paper was published at POPL 2004. His reference implementation, Pappy, generated packrat parsers in Haskell.
Do any real languages use packrat or PEG parsing in production?
Yes. CPython replaced its LL(1) parser with a PEG parser in Python 3.9 (PEP 617), using memoization at its backtracking points. Widely used generators include pest and peg (Rust), Peggy/PEG.js and Ohm (JavaScript), Parboiled and Rats! (Java). PEGs are popular for DSLs, config formats, and syntax highlighting because they avoid the shift/reduce conflicts of LALR tools and need no separate lexer.