Packrat Parsing

Every time a program reads source code, a parser turns a flat string of characters into a tree of meaning. Most modern languages are described by Parsing Expression Grammars (PEGs) — a notation that says, for each grammar rule, "try this alternative first; if it fails, try the next one."

That ordered choice is convenient to write and unambiguous to read, but it hides a danger: a parser that simply tries alternatives may end up re-parsing the same fragment of input hundreds or thousands of times — a classic form of exponential backtracking.

The fix, invented by Bryan Ford in 2002, is almost embarrassingly simple: remember every answer. Before applying a grammar rule at a position, check a table. If the result is already there, return it instantly. If not, compute it, store it, and then return it. Because there are only $|G| \times |s|$ possible (rule, position) pairs — where $|G|$ is the number of rules and $|s|$ is the input length — the total work is $O(|G| \times |s|)$, linear in the input size.

This technique is called packrat parsing, and it guarantees that every PEG grammar is parsed in linear time, with no special-casing or grammar restrictions needed. The price is linear extra memory: one table entry per (rule, position) pair.

The demo below parses a simple arithmetic expression using a tiny PEG grammar with two rules. The Naïve mode applies rules repeatedly from scratch; the Packrat mode consults a memo table first. Type any expression and press Parse to watch the call counts diverge.

<!-- {{c_title}} -->
<div class="controls">
  <label for="expr">{{label_expr}}</label>
  <input id="expr" type="text" value="1+2+3" placeholder="{{placeholder_expr}}" />
  <div class="mode-row">
    <label class="mode-label">{{label_mode}}</label>
    <button id="btn-naive" class="mode-btn active" type="button">{{btn_naive}}</button>
    <button id="btn-packrat" class="mode-btn" type="button">{{btn_packrat}}</button>
    <button id="btn-parse" type="button">{{btn_parse}}</button>
  </div>
</div>
<div class="stats" id="stats"></div>
<div class="grid-wrap">
  <div id="legend" class="legend"></div>
  <div id="grid" class="grid"></div>
</div>

/* {{c_reset}} */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; padding: .6rem; }
.controls { display: flex; flex-direction: column; gap: .5rem; margin-bottom: .6rem; }
label { font-size: .85rem; color: #555; }
input { font-size: 1rem; padding: .35rem .5rem; border: 1px solid #ccc; border-radius: 6px; width: 100%; }
.mode-row { display: flex; align-items: center; gap: .4rem; flex-wrap: wrap; }
.mode-label { font-size: .85rem; color: #555; margin-right: .2rem; }
.mode-btn { font: 600 13px system-ui; padding: .3rem .7rem; border: 1px solid #1d3557;
            border-radius: 6px; background: #fff; color: #1d3557; cursor: pointer; }
.mode-btn.active { background: #1d3557; color: #fff; }
#btn-parse { font: 600 13px system-ui; padding: .3rem .9rem; border: 1px solid #1d3557;
             border-radius: 6px; background: #e63946; color: #fff; cursor: pointer; margin-left: auto; }
.stats { font-size: .92rem; font-weight: 600; min-height: 1.4em; margin-bottom: .4rem; }
.stats.ok { color: #0a7d33; }
.stats.warn { color: #b45309; }
.grid-wrap { overflow-x: auto; }
.legend { font-size: .78rem; color: #555; margin-bottom: .3rem; display: flex; gap: .8rem; flex-wrap: wrap; }
.legend span { display: inline-flex; align-items: center; gap: .25rem; }
.swatch { display: inline-block; width: 12px; height: 12px; border-radius: 3px; border: 1px solid #ccc; }
.swatch.hit { background: #a8d8a8; border-color: #5aaa5a; }
.swatch.computed { background: #b8d0e8; border-color: #5a90c8; }
.swatch.fail { background: #f0c0c0; border-color: #d07070; }
.swatch.empty { background: #eee; }
/* {{c_grid_style}} */
.grid { display: grid; gap: 2px; min-width: max-content; }
.cell { width: 34px; height: 28px; border-radius: 4px; font-size: .68rem; display: flex;
        align-items: center; justify-content: center; border: 1px solid #ddd;
        background: #eee; color: #444; text-align: center; overflow: hidden; white-space: nowrap; }
.cell.hit { background: #a8d8a8; border-color: #5aaa5a; color: #1a501a; }
.cell.computed { background: #b8d0e8; border-color: #5a90c8; color: #1a3a5a; }
.cell.fail { background: #f0c0c0; border-color: #d07070; color: #7a1010; }
.row-label { font-size: .75rem; font-weight: 600; color: #555; display: flex;
             align-items: center; padding-right: .3rem; white-space: nowrap; }
.col-header { font-size: .68rem; color: #777; text-align: center; }

// Code not found

Notice that the naïve parser's call count grows rapidly with input length, while the packrat parser's call count stays proportional to the input length. Each cell in the grid represents one (rule, position) pair; a green cell means the memo table was hit — work that was skipped entirely.

How expensive is packrat parsing? The answer is settled — and better than most parsers achieve.

• Naïve recursive descent on a PEG grammar can take $O(2^{n})$ time in the worst case, because the same sub-expression can be re-parsed exponentially many times at overlapping positions.
• Packrat parsing is $O(n)$ time and $O(n)$ space. Bryan Ford proved this in 2002. The key observation is that a grammar $G$ with $|G|$ rules applied to an input of length $n$ has at most $|G| \times n$ distinct (rule, position) pairs. Memoization ensures each pair is computed at most once, so total work is bounded by $|G| \times n$ — linear in $n$ for a fixed grammar.
• The tradeoff is memory. The memo table requires $O(|G| \times n)$ space. For large inputs or grammars with many rules, this can be significant.
• Left recursion is the one caveat. Standard PEGs forbid left-recursive rules (rules that call themselves as their first action), because they cause infinite loops. Extensions exist to handle left recursion in packrat parsers (Warth, Douglass, and Millstein, 2008), but at some added complexity.

The result is striking: unlike context-free grammars, where the best general parsers take $O(n^3)$ time (Earley, CYK), any PEG grammar is parsed in linear time by packrat. The restriction is that PEGs do not describe all context-free languages — but in practice they describe nearly every programming language you would want to parse.

Compare this with the situation in P vs NP: packrat parsing sits firmly in P, and it gets there by a clean application of dynamic programming — the same idea that tames countless other exponential problems.

The linear-time guarantee and the simplicity of PEG notation make packrat parsing a natural fit for tools that need reliable, maintainable parsers:

• Compilers and interpreters: languages like Lua 5.4 and several research languages use PEG-based parsers. The scannerless nature of PEGs — no separate tokenizer needed — simplifies the grammar pipeline.
• Parser generators: tools such as PEG.js, Ohm, and pest (Rust) generate packrat parsers from a grammar description, giving language authors linear-time parsing for free.
• Code editors and IDEs: incremental variants of packrat parsing allow an editor to re-parse only the changed region of a file, keeping highlighting and error detection fast as you type.
• Protocol and data-format parsers: binary and text protocols with complex nested structures benefit from the unambiguous ordered-choice semantics of PEGs, which avoids the shift/reduce conflicts that plague LALR parsers.
• Teaching dynamic programming: packrat parsing is an ideal example of how memoization transforms an exponential recursion into a linear one — the same principle that powers the sequence alignment algorithms used in bioinformatics.

Packrat parsing is a lesson in the power of a single idea applied consistently. Naïve PEG parsing can revisit the same fragment of input exponentially many times. Add one memo table — store every (rule, position) result the first time you compute it, look it up every time after — and the entire grammar is parsed in linear time, with no restrictions on the grammar's structure.

The technique is not magic; it is dynamic programming applied to parsing. But the payoff is unusually clean: a guarantee that a broad, expressive class of grammars is always parsed in $O(n)$ time, making the exponential backtracking of naïve recursive descent a problem you never have to think about again.