Packrat Parsing and the Linear-Time Guarantee

A parser combinator library with backtracking has an obvious failure: a grammar that nests alternatives can re-parse the same input many times, and the worst case is exponential. Packrat parsing removes that failure by remembering the result of every rule application at every input position. If a rule has already been tried at position i, the second attempt is a table lookup.

The result is a parser with guaranteed linear time in input length. The price is memory proportional to grammar size times input size, and a change in what a grammar means.

Parsing expression grammars

A PEG is not a context-free grammar with a different notation. Its operators are ordered choice, sequence, and the two predicates & and !. Ordered choice a / b means: try a; if it succeeds, commit to it, and only try b if a fails. There is no way for the choice to reconsider, so a PEG has no ambiguity by construction.

That property is the reason PEGs are attractive for language syntax. Ambiguity in a CFG is a property of the grammar that must be analysed and resolved; in a PEG, the first alternative that matches is the meaning, and a grammar’s behaviour is a deterministic function of its text. Two grammars that describe the same language can produce different trees, and the tree is part of the specification.

The ! predicate is what makes the notation practical. !keyword identifier matches an identifier only if it does not begin with a keyword, which expresses reserved words without a separate keyword table. Negative lookahead is also how a repetition is bounded: item (!"," any)* stops at a comma.

Where exponential behaviour comes from

Consider a rule for a list of items separated by commas, where each item is itself a list. A naive recursive matcher tries the nested alternative at a position, fails partway, backtracks, tries the flat alternative, and re-parses the same prefix. If the failure can happen at every level, the work doubles per level and the total is exponential.

The classic pathological case in a CFG setting is a grammar that can derive the same prefix through many different paths, and the equivalent PEG is a nested choice where each branch re-tries a shared prefix. Without memoisation, the same rule at the same position is evaluated once per path that reaches it.

Memoisation turns the tree into a table

Packrat parsing adds a cache keyed by (rule, position). Before applying a rule at a position, the parser checks the cache. On a miss it computes the result, stores it, and returns it. Every (rule, position) pair is computed at most once, so the total work is bounded by the number of pairs, which is the grammar’s rule count times the input length.

class Packrat:
    def __init__(self, text):
        self.text = text
        self.memo = {}          # (rule_name, pos) -> (ok, new_pos, node)

    def apply(self, rule, pos):
        key = (rule.name, pos)
        hit = self.memo.get(key)
        if hit is not None:
            return hit
        # Seed the entry before recursing: a left-recursive rule that
        # re-enters here would otherwise recurse forever.
        self.memo[key] = (False, pos, None)
        result = rule.body(self, pos)
        self.memo[key] = result
        return result

The seeding line matters more than it looks. A PEG rule that calls itself at the same position, which is what left recursion means, would recurse without bound. Seeding the entry with failure makes the recursive call fail immediately, so the rule terminates, but it also means the rule cannot parse the left-recursive construct at all. Left recursion in a PEG has to be rewritten into iteration or handled by a specialised algorithm; the memo table does not solve it.

The memory cost, stated plainly

The table has one entry per (rule, position) pair. For a grammar with a few hundred rules and a source file of 100,000 bytes, that is tens of millions of entries. Each entry needs at least a success flag, a resulting position, and a reference to the node, so a compact entry of a dozen or two bytes still puts the table in the hundreds of megabytes.

This is the reason packrat parsing is described as linear time and linear space in input length for a fixed grammar, with a large constant: the size is the grammar’s rule count times the input length times the per-entry record size, and the first factor is what makes the product unwieldy rather than the second.

Three mitigations are used. The first is to memoise only the rules that actually backtrack, leaving cheap rules uncached; the parser then needs a static or dynamic analysis of which rules can be re-entered. The second is to use a bounded cache and evict entries, which loses the linear-time guarantee but recovers memory. The third is to pack entries tightly: store the resulting position as a 32-bit integer and the node as an index into an arena, which brings an entry to a dozen bytes or so and makes the table large but not absurd.

For an interactive editor, the table’s size is the binding constraint, and the usual answer is to parse only the changed region and keep the table for the rest, which is the incremental strategy described in Incremental Reparsing After an Edit.

The node allocation problem

Memoisation returns a node, and a node that is returned from two different positions must not be mutated later, because the same object would appear in two places in the tree. Packrat implementations therefore build immutable nodes and share them freely.

Sharing creates a subtle diagnostic problem. A node built at position i may appear in the final tree at a place the programmer would not expect, because the rule that produced it was reached through a different path than the one the final tree followed. Error messages attached to nodes can then point at a position that seems unrelated to the reported construct.

The common fix is to attach positions to nodes and let the diagnostic layer reconstruct the path from the final tree rather than from the parse order. That keeps the memo table’s sharing invisible to the user.

Where PEGs and CFGs disagree

The two formalisms are not equivalent. A syntactic predicate can test a subexpression of arbitrary length before any input is consumed, which lets a PEG recognise some languages that no context-free grammar derives, so a CFG-to-PEG translation is a construction that has to be checked rather than applied mechanically.

The deeper difference is that PEG ordered choice commits. A grammar written with the wrong alternative order silently accepts a different language: ("a" / "ab") never matches ab, because the first alternative matches a and the choice commits, leaving b to fail later at a higher level. Reordering to ("ab" / "a") fixes it, and the failure without the reorder is a parse failure on valid input, not an ambiguity report. The grammar’s alternative order is part of its meaning, which is exactly unlike a CFG.

PEGs also cannot express the left-recursive grammar for a left-associative operator directly, so a - b - c needs an explicit fold in the semantic action of an iterative rule. The result is a correct left-associative tree, but the grammar no longer reads like the language’s specification.

When the guarantee is worth the memory

The linear-time guarantee matters when input is adversarial or when parse time must be predictable. A PEG parser’s time is bounded regardless of how the input is shaped, which is the property that makes it suitable for network-facing or user-supplied input.

The memory cost matters when inputs are large and the grammar is big. For a configuration language with a hundred rules and files of a few kilobytes, the table is trivial. For a general-purpose programming language with a thousand rules and files of a megabyte, it is not.

The middle ground is a PEG parser with selective memoisation and a hand-written lexer: the lexer removes the token-level work from the parse, the PEG handles the syntax, and only the rules that can backtrack carry a memo entry.

The contrast with deterministic table-driven parsing is worth stating: an LR parser also runs in linear time, with no memo table and a fixed table size, but it refuses grammars that are not deterministic. A packrat parser accepts any PEG and pays in memory. Neither dominates; they fail on different axes.

For the class of grammars that are deterministic but awkward to rewrite, the table-driven answer is in LALR Table Construction and What the Conflicts Mean. For grammars that are genuinely ambiguous and must yield all parses, the generalized approach is in GLR Parsing and the Graph-Structured Stack.