Introduction

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∣×∣s∣|G| \times |s| possible (rule, position) pairs — where ∣G∣|G| is the number of rules and ∣s∣|s| is the input length — the total work is O(∣G∣×∣s∣)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.

Try It: Memo vs. No Memo

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.

<!-- Packrat parsing demo: naive recursive descent vs packrat with memoization -->
<div class="controls">
  <label for="expr">Expression to parse:</label>
  <input id="expr" type="text" value="1+2+3" placeholder="e.g. 1+2+3" />
  <div class="mode-row">
    <label class="mode-label">Mode:</label>
    <button id="btn-naive" class="mode-btn active" type="button">Naïve</button>
    <button id="btn-packrat" class="mode-btn" type="button">Packrat</button>
    <button id="btn-parse" type="button">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>

/* global reset / box-sizing */
* { 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; }
/* memo grid cells */
.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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// Packrat demo: compare naïve recursive descent vs memoized (packrat) parsing
// Grammar (simplified, no operator precedence):
//   Expr  <- Term ('+' Term)*
//   Term  <- [0-9]+
// Each rule is applied at every position of the input string
const RULES = ['Expr', 'Term'];

// Naïve parser: no memoization — re-parses the same substrings repeatedly
let naiveCalls = 0;

function naiveExpr(s, pos) {
  naiveCalls++;
  // try to parse Term at this position
  const t0 = naiveTerm(s, pos);
  if (t0 === null) return null;
  let cur = t0;
  while (cur < s.length && s[cur] === '+') {
    const t1 = naiveTerm(s, cur + 1);
    if (t1 === null) break;
    cur = t1;
  }
  return cur;
}

function naiveTerm(s, pos) {
  naiveCalls++;
  if (pos >= s.length || !/[0-9]/.test(s[pos])) return null;
  let i = pos;
  while (i < s.length && /[0-9]/.test(s[i])) i++;
  return i;
}

// Packrat parser: memo table stores (rule, position) -> end position
// memo[rule][pos] = { end, hit } where end is the end position or null on failure
let memo = {};
let packratCalls = 0;
let memoHits = 0;

function packratExpr(s, pos) {
  packratCalls++;
  const key = 'Expr,' + pos;
  if (key in memo) { memoHits++; return memo[key]; }
  // compute result, store in memo before returning
  const t0 = packratTerm(s, pos);
  let result = null;
  if (t0 !== null) {
    let cur = t0;
    while (cur < s.length && s[cur] === '+') {
      const t1 = packratTerm(s, cur + 1);
      if (t1 === null) break;
      cur = t1;
    }
    result = cur;
  }
  memo[key] = result;
  return result;
}

function packratTerm(s, pos) {
  packratCalls++;
  const key = 'Term,' + pos;
  if (key in memo) { memoHits++; return memo[key]; }
  // compute result, store in memo before returning
  let result = null;
  if (pos < s.length && /[0-9]/.test(s[pos])) {
    let i = pos;
    while (i < s.length && /[0-9]/.test(s[i])) i++;
    result = i;
  }
  memo[key] = result;
  return result;
}

// UI state and event wiring
let mode = 'naive';
let lastGrid = null;

document.getElementById('btn-naive').addEventListener('click', () => {
  mode = 'naive';
  document.getElementById('btn-naive').classList.add('active');
  document.getElementById('btn-packrat').classList.remove('active');
});
document.getElementById('btn-packrat').addEventListener('click', () => {
  mode = 'packrat';
  document.getElementById('btn-packrat').classList.add('active');
  document.getElementById('btn-naive').classList.remove('active');
});

function parse() {
  const s = document.getElementById('expr').value.replace(/\s/g, '');
  const stats = document.getElementById('stats');
  const gridEl = document.getElementById('grid');
  const legendEl = document.getElementById('legend');
  if (!s) { stats.textContent = 'Please enter an expression.'; stats.className = 'stats warn'; return; }

  // run the selected parser on the trimmed input
  let result, calls, hits;
  if (mode === 'naive') {
    naiveCalls = 0;
    result = naiveExpr(s, 0);
    calls = naiveCalls;
    hits = 0;
  } else {
    memo = {};
    packratCalls = 0;
    memoHits = 0;
    result = packratExpr(s, 0);
    calls = packratCalls;
    hits = memoHits;
  }

  const ok = result === s.length;
  // show result stats
  if (mode === 'naive') {
    stats.textContent = ok
      ? i18nFmt('Parsed OK — %calls% rule calls (naïve, no memo).', { calls })
      : i18nFmt('Parse failed — %calls% rule calls (naïve, no memo).', { calls });
  } else {
    stats.textContent = ok
      ? i18nFmt('Parsed OK — %calls% rule calls, %hits% memo hits (packrat).', { calls, hits })
      : i18nFmt('Parse failed — %calls% rule calls, %hits% memo hits (packrat).', { calls, hits });
  }
  stats.className = 'stats ' + (ok ? 'ok' : 'warn');

  // draw the memo table grid (packrat) or blank grid (naive)
  // Populate the memo grid for packrat, or a call-coverage grid for naive
  const cols = s.length + 1;
  gridEl.style.gridTemplateColumns = '80px ' + RULES.map(() => 'repeat(' + cols + ', 34px)').join(' 6px ');

  gridEl.innerHTML = '';

  // column headers: one char per input position
  const empty = document.createElement('div');
  gridEl.appendChild(empty);
  RULES.forEach((rule, ri) => {
    for (let p = 0; p <= s.length; p++) {
      const h = document.createElement('div');
      h.className = 'col-header';
      h.textContent = p < s.length ? s[p] : '#';
      gridEl.appendChild(h);
    }
    if (ri < RULES.length - 1) {
      const sep = document.createElement('div');
      gridEl.appendChild(sep);
    }
  });

  RULES.forEach((rule, ri) => {
    // row label for this rule
    const label = document.createElement('div');
    label.className = 'row-label';
    label.textContent = rule;
    gridEl.style.gridTemplateRows = 'auto auto';
    // We use a flat grid — rebuild with one row per rule
    // (rebuilt below as a proper 2-row grid)
  });

  // rebuild grid DOM with proper 2-row layout
  // Build a proper 2-row grid: header row + one row per rule
  gridEl.innerHTML = '';
  const totalCols = 1 + RULES.length * cols + (RULES.length - 1);
  gridEl.style.gridTemplateColumns =
    '80px ' + Array(cols).fill('34px').join(' ') + ' 6px ' + Array(cols).fill('34px').join(' ');

  // emit column header cells
  const hSpacer = document.createElement('div');
  gridEl.appendChild(hSpacer);
  RULES.forEach((rule, ri) => {
    for (let p = 0; p <= s.length; p++) {
      const h = document.createElement('div');
      h.className = 'col-header';
      h.textContent = p < s.length ? s[p] : '#';
      gridEl.appendChild(h);
    }
    if (ri < RULES.length - 1) gridEl.appendChild(document.createElement('div'));
  });

  // emit one data row per grammar rule
  RULES.forEach((rule, ri) => {
    const lbl = document.createElement('div');
    lbl.className = 'row-label';
    lbl.textContent = rule;
    gridEl.appendChild(lbl);

    for (let p = 0; p <= s.length; p++) {
      const cell = document.createElement('div');
      cell.className = 'cell';
      if (mode === 'packrat') {
        const key = rule + ',' + p;
        if (key in memo) {
          const end = memo[key];
          if (end === null) { cell.classList.add('fail'); cell.textContent = '✗'; }
          else { cell.classList.add('computed'); cell.textContent = end; }
        }
      } else {
        // naive mode: no memo table to show
        cell.textContent = '';
      }
      gridEl.appendChild(cell);
    }
    if (ri < RULES.length - 1) gridEl.appendChild(document.createElement('div'));
  });

  // draw color legend below the grid
  legendEl.innerHTML = '';
  if (mode === 'packrat') {
    legendEl.innerHTML =
      '<span><span class="swatch computed"></span>computed & stored</span>' +
      '<span><span class="swatch fail"></span>failed (null)</span>' +
      '<span><span class="swatch empty"></span>not reached</span>';
  } else {
    legendEl.innerHTML = '<span>Naïve mode has no memo table — switch to Packrat to see it.</span>';
  }
}

document.getElementById('btn-parse').addEventListener('click', parse);
document.getElementById('expr').addEventListener('keydown', e => { if (e.key === 'Enter') parse(); });
parse();
Result
Console

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.

The Real Complexity

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(2n)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)O(n) time and O(n)O(n) space. Bryan Ford proved this in 2002. The key observation is that a grammar GG with ∣G∣|G| rules applied to an input of length nn has at most ∣G∣×n|G| \times n distinct (rule, position) pairs. Memoization ensures each pair is computed at most once, so total work is bounded by ∣G∣×n|G| \times n — linear in nn for a fixed grammar.
  • The tradeoff is memory. The memo table requires O(∣G∣×n)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(n3)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.

Where It Matters

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.

Conclusion

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)O(n) time, making the exponential backtracking of naïve recursive descent a problem you never have to think about again.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/packrat-parsing/Content licensed under CC BY-NC 4.0.