THE PACKRAT PARSER memoize (rule, position), pay linear
A Parsing Expression Grammar uses ordered choice: A <- e1 / e2 tries e1 first and only falls back to e2 — unambiguous by construction. The price is unlimited backtracking, which naive re-parsing pays exponentially. A packrat parser removes it by memoizing every (rule, position): each is computed at most once, so parsing is linear time (at linear space).
THE TECHNIQUE the memo table collapses the re-parse
Grammar (PEG): Add <- Mul ('+' Add)?, Mul <- Prim ('*' Mul)?, Prim <- '(' Add ')' / Digit. A memo cell memo[rule][pos] caches each result; when a rule is asked again at a position it already solved, it is a hit — a lookup, not a re-parse. Watch the cells fill and the hits land parsing 2*(3+4). live demo
HISTORY & CREDIT PEG and packrat are two things
“PEG = packrat” — no. PEG is the grammar (ordered choice, 2004); packrat is the linear-time memoized execution (2002). Separate papers. cited
1968 / 1970 · Donald Michie coins memoization (Nature); Alexander Birman (Princeton, advisor Ullman) gives TS/gTS — the backtracking top-down scheme, renamed TDPL/GTDPL by Aho & Ullman (1972). Sep / Oct 2002 · Bryan Ford coins packrat (MIT thesis; ICFP pearl): memoize every (rule, position) — TDPL-style backtracking in linear time. In Haskell the memo is a lazy self-referential structure, not an explicit array. 2004 · Ford names PEG (POPL) — the grammar formalism itself, unambiguous by fiat via ordered choice. 2008 / 2020 · LPeg (a parsing machine, no memo table) and CPython’s PEG parser (PEP 617, selective memo) prove full packrat is optional — O(n) space and constant factors often make plain backtracking faster.
Ordered choice does not resolve ambiguity — it forbids it, always committing to the first match (the classic longest-match surprise). Ford, 2002 / 2004
RECOMMEND FOR I-13 the PEG runs; the memo is a threaded array
The ordered-choice PEG parses and consumes all input on the real compiler, threading [value, pos, calls]:
$ i13 run packrat.i13 # PEG: Add/Mul/Prim, ordered choice
2*(3+4) -> value 14, endpos 7 (all consumed), 4 Prim parses (bind-once = memoized form)
Recommend: the PEG parse is LIT — input as an f64 code array, each nonterminal a recursive function returning [value, pos, …], ordered choice as sequential if branches (verified 14, all 7 chars consumed). Binding each sub-result once is the memo optimisation in miniature. Note: a full memo table is memo[rule][pos] — a 2-D array (PS-004); I-13 expresses it by threading a memo array through the recursion (the sieve pattern — value semantics as a mutable store). The demo animates the real 11-cell / 5-hit table; the corpus has the mechanism (a threaded array), the frontier is making it first-class.