What does a packrat parser store in its memo table, and why does that make parse time linear in input length?
answer
- cache what, keyed by what
- rule plus input position
- each pair computed at most once
- count the keys to get the bound
- linear time, input-times-rules memory
basics
~20 sIt stores the outcome of each rule at each input position: failure, or success with the end position and result. Because every rule-position pair is computed once and then reused, total work is proportional to input length times grammar size.
solid answer
~50 sThe memo table is keyed by the pair `(rule, input position)` and holds what happened when that rule was last applied there — either a failure, or a success together with the position it ended at. Ordered-choice parsing backtracks, so the same rule is naturally attempted at the same position many times through different alternatives; the table turns every attempt after the first into a lookup. For an input of `n` characters and a fixed grammar of `r` rules there are only `r * (n + 1)` such pairs, and each is evaluated at most once, so parse time is `O(n * r)` — linear in `n` for a fixed grammar, with a constant factor set by grammar size. The bill is memory: the table holds an entry per pair, so space is `O(n * r)` too, which is why whole-input memoization suits editors and tools more than unbounded streams.
code
pseudocode · 11 linesfunction apply(rule, pos):
key = (rule, pos)
if memo contains key:
return memo[key] # already decided at this position
result = evaluate(rule.body, pos) # may call apply(...) again
memo[key] = result # written only after the body returns
return result
# result is FAIL, or (SUCCESS, endPos)
# a rule that re-enters itself at the same pos finds no entry yetgo deeper
Recall that the parser remembers the outcome of each rule at each position so it never re-parses the same thing twice after backtracking.
Explain the key and the counting argument: outcomes are fixed per rule per position, there are rules-times-positions of them, each is computed once, so the total is linear in input length.
Discuss the memory bill you actually pay on large inputs and how you bound it — memoizing selected rules, discarding entries behind a window, storing outcomes rather than whole results.
Judge whether guaranteed linear time is worth a table that grows with input size for your workload, versus a parser with a smaller footprint and a worse but acceptable tail.
## What is cached, and why caching is even sound here A packrat parser adds one table to an ordinary backtracking recursive parser. The key is a pair — **which rule** and **which input position** it was applied at. The value is the outcome of that application: `FAIL`, or `SUCCESS` with the position the rule ended at and whatever result it built. The cache is sound because of a property the formalism guarantees: applying a rule at a position has **exactly one outcome**, independent of how the parser arrived there. Ordered choice, left-to-right sequencing and possessive repetition leave no room for context to change the answer, so a result computed once is valid forever. A formalism where a rule's outcome depended on what the caller wanted next could not be memoized this way. ## Why the same work happens twice without it Backtracking is the reason there is anything to cache. Consider: ``` Entry <- Name "=" Value / Name "(" Args ")" / Name ``` Each alternative starts by applying `Name` at the same position. Without a table, a failure in the first alternative discards the `Name` result and the second alternative recomputes it, and so does the third. Nest that a few levels deep and the repeated work multiplies; in the worst case an unmemoized backtracking parser can take time exponential in input length. ## The bound, stated carefully Let `n` be the number of input characters and `r` the number of rules in a fixed grammar. 1. There are `r * (n + 1)` distinct keys — every rule at every position, including the end. 2. Each key's value is computed **at most once**; every later request for it is a table lookup. 3. Computing one value runs the body of one rule, whose sub-expressions are themselves either constant-time character tests or memoized rule applications. So total work is proportional to the number of keys: `O(n * r)`. With the grammar fixed, that is **linear in the input length**, and the hidden constant is not small — it scales with the size of the grammar, so a large grammar has a large constant even though the curve is a straight line. | Property | Plain backtracking | Packrat | |---|---|---| | Worst-case time | exponential in `n` | `O(n * r)` | | Memory for parser state | recursion depth only | `O(n * r)` table | | Predictability on adversarial input | poor | uniform | | Suits unbounded streaming | yes | not without bounding the table | ## The memory bill, and how it is paid A table entry per rule per position is a real cost: it grows with the input, not with the tree. Common ways to bound it, none of which change the grammar's meaning: - **Memoize selectively.** Most rules are never retried at the same position; profiling shows the handful that are, and only those need entries. - **Bound the window.** Entries for positions far behind the current one can be discarded when the grammar cannot backtrack that far. - **Store less per entry.** Keeping only the outcome and end position, and rebuilding the tree afterwards, shrinks the table substantially. ## What memoization does not do - **It does not remove backtracking.** Alternatives are still tried in order and still fail; the table only stops the *repeated* work. - **It does not change which input is accepted.** Every outcome is the outcome the unmemoized parser would have produced, just computed once. - **It does not rescue a directly left-recursive rule.** The entry for `(rule, position)` is written only *after* the body returns. A rule that re-enters itself at the same position therefore finds no entry, recurses again, and never terminates — which is why such rules are rejected up front rather than tolerated. - **It does not make the constant factor free.** Linear time with a table lookup per rule application can lose to a smaller non-memoizing parser on short inputs, and the crossover is worth measuring rather than assuming. The summary an interviewer wants: caching is sound because outcomes are position-determined; the bound follows from counting keys rather than from any clever algorithm; and the trade is time for memory, taken in full unless you deliberately memoize less.
- Why does memoization not rescue a directly left-recursive rule?Because the entry for a rule at a position is written only after its body returns. A left-recursive rule calls itself at the same position before any entry exists, so the lookup misses and the body runs again, unchanged, forever. The table can only help once a result exists to reuse.
- When would you deliberately not memoize every rule?When memory matters more than the worst case: on long inputs the table dominates, and most rules are never retried at the same position anyway. Memoizing only the rules that measurements show are re-applied keeps almost all the speed for a fraction of the space.
- Does memoization change which inputs the grammar accepts?No. Every cached outcome is the one the unmemoized parser would have computed, because a rule's outcome at a position is fixed by the grammar alone. Memoization is purely a performance transformation; a difference in accepted input would mean the cache key is wrong.
saying these in an interview costs you the question
- Says memoization is what makes the grammar unambiguous
- Claims packrat parsing removes backtracking rather than repeated work
- Assumes the memo table is small or a fixed size
- Thinks memoizing makes a left-recursive rule terminate
- Treats linear time as implying a small constant factor