Skip to content

Lesson 4.2 — Parsing expression grammars and packrat parsing

Techniques: parsing expression grammars with ordered choice and syntactic predicates (Ford 2004; TDPL, Birman & Ullman 1973), packrat memoization (Ford 2002), left recursion in PEGs by seed growing (Warth, Douglass & Millstein 2008) and bounded left recursion (Medeiros, Mascarenhas & Ierusalimschy 2014) · Pebble implements: the packrat parser of the comparison lab (SPEC L3) · Prerequisites: Lesson 2.5 (backtracking and memoized recursive descent), Lesson 4.1 · Time: 3 hours

A context-free grammar generates a language and leaves open how to recognize it; its alternatives are unordered and may overlap, which is where ambiguity and parsing conflicts come from. A parsing expression grammar is a recognizer written as a grammar: A <- e1 / e2 means "try e1; only if it fails, try e2". There is no ambiguity by construction, and a backtracking recursive-descent parser implements it directly. Memoizing that parser makes it linear. CPython has parsed Python with a PEG since 3.9 [PEP617].

1. Problem and motivation

The problem. Given a grammar and an input, recognize (and parse) the input deterministically, without lexer/parser separation if desired, without computing lookahead sets and without conflicts, in linear time.

Parsing expression grammars

Backtracking recursive descent (Lesson 2.5) is simple but, run on a CFG, it either explores every alternative (exponential) or silently commits to the first success, which accepts a different language than the CFG says. Birman and Ullman formalized the committing behavior as the TS/TDPL formalism in 1970–73 [BU73]; Bryan Ford gave it a readable syntax and semantics as parsing expression grammars (PEGs) [For04]: ordered choice /, greedy repetition * + ?, and the syntactic predicates &e (and-predicate: e must match here, consume nothing) and !e (not-predicate). A PEG describes exactly what the backtracking parser does, so the grammar and the parser cannot disagree.

Packrat memoization

A PEG parser may call the same rule at the same position many times: after A 'x' fails, the alternative A 'y' re-parses A. Ford's packrat parser [For02] memoizes the result of every (rule, position) pair — "failed" or "succeeded, ending at position \(j\) with this tree" — so each pair is computed at most once, and parsing takes \(O(\lvert G \rvert\, n)\) time (Theorem 4.2.10) at the cost of \(O(\lvert G \rvert\, n)\) memory. Pebble's lab implements it (L3).

Left recursion in PEGs

A left-recursive rule E <- E '-' N / N calls itself at the same position without consuming anything, so the recursive interpreter loops. Warth, Douglass and Millstein [WDM08] made packrat parsers support it by growing a seed: the recursive call first fails, the rule's other alternative produces a first match, and the rule body is re-run with the memo table holding the previous match until it stops growing. CPython's pegen implements exactly this (memoize_left_rec [CPY-pegen]) for rules like sum: sum '+' term | term. Medeiros, Mascarenhas and Ierusalimschy [MMI14] gave the idea a formal semantics (bounded left recursion) and extended it to indirect and mutual recursion.

2. Definitions and algorithms

Throughout, \(x = x_1 \cdots x_n\) is the input (characters or tokens) and positions are \(0, \dots, n\).

Definition 4.2.1 (Parsing expression grammar)

A PEG is \(G = (N, T, R, e_S)\): nonterminals \(N\), terminals \(T\), a function \(R\) mapping each \(A \in N\) to a parsing expression \(R(A)\) (written A <- e), and a start expression \(e_S\). Parsing expressions are: \(\varepsilon\); a terminal \(a\); any single terminal .; a nonterminal \(A\); a sequence \(e_1 e_2\); an ordered choice \(e_1 / e_2\); a greedy repetition \(e^{*}\) (and \(e^{+} \triangleq e\, e^{*}\), \(e? \triangleq e / \varepsilon\)); an and-predicate \(\&e\); a not-predicate \(!e\).

Definition 4.2.2 (Semantics: the match function)

\(\mathrm{match}(e, i)\) is a position \(j \ge i\) (success, \(x_{i+1} \cdots x_j\) consumed) or \(\mathsf{fail}\), defined by: \(\mathrm{match}(\varepsilon, i) = i\); \(\mathrm{match}(a, i) = i + 1\) if \(x_{i+1} = a\), else \(\mathsf{fail}\); \(\mathrm{match}(., i) = i + 1\) if \(i < n\); \(\mathrm{match}(A, i) = \mathrm{match}(R(A), i)\); \(\mathrm{match}(e_1 e_2, i) = \mathrm{match}(e_2, \mathrm{match}(e_1, i))\) (fail propagates); \(\mathrm{match}(e_1 / e_2, i) = \mathrm{match}(e_1, i)\) if that succeeds, else \(\mathrm{match}(e_2, i)\); \(\mathrm{match}(e^{*}, i) = \mathrm{match}(e^{*}, j)\) if \(j = \mathrm{match}(e, i)\) succeeds with \(j > i\), else \(i\); \(\mathrm{match}(\&e, i) = i\) if \(\mathrm{match}(e, i) \ne \mathsf{fail}\), else \(\mathsf{fail}\); \(\mathrm{match}(!e, i) = \mathsf{fail}\) if \(\mathrm{match}(e, i) \ne \mathsf{fail}\), else \(i\). The PEG accepts \(x\) if \(\mathrm{match}(e_S, 0) = n\) (the start expression consumes the whole input; many PEGs write this as S <- e !.). This is the least-fixed-point reading of Ford's inference rules [For04, §3], restricted to grammars where it is total (Theorem 4.2.4).

Ordered choice commits: prefix capture

With S <- 'a' / 'a' 'b', \(\mathrm{match}(S, 0)\) on ab is 1: the first alternative succeeds and the second is never tried, so S !. rejects ab although the CFG \(S \to a \mid a\,b\) generates it. Reordering (S <- 'a' 'b' / 'a') fixes it: the longer alternative must come first. This is prefix capture, the PEG pitfall.

Parsing expression grammars

Definition 4.2.3 (Well-formed PEG)

\(A\) is left-recursive if \(R(A)\) can reach a call of \(A\) at the same position, i.e. \(A \leadsto A\) in the relation "\(B\) calls \(C\) before consuming input" (through sequences whose earlier parts are nullable, choices, repetitions and predicates). A repetition \(e^{*}\) is nullable-iterated if \(e\) can succeed without consuming input. A PEG is well-formed if no nonterminal is left-recursive and no repetition is nullable-iterated [For04, §3].

Theorem 4.2.4 (Well-formed PEGs are complete)

If \(G\) is well-formed, then for every expression \(e\) reachable from \(e_S\) and every position \(i\), the recursive evaluation of \(\mathrm{match}(e, i)\) in Definition 4.2.2 terminates. Hence a well-formed PEG decides every input: it accepts or rejects.

Proof sketch (full proof: [For04, §3], the completeness theorem for well-formed grammars)

Order the pairs \((i, e)\) by: larger \(i\) first (fewer characters left), then by the "calls before consuming" order on expressions, which is well-founded because \(G\) has no left recursion and expressions are finite trees. Every recursive step of Definition 4.2.2 either moves to a strictly larger position (after a terminal or a successful non-empty repetition step) or to a strictly smaller expression at the same position (a subexpression, or \(R(A)\) reached through a nonterminal, which cannot return to \(A\) at the same position). The repetition case re-evaluates \(e^{*}\) at \(j > i\) only, since a non-consuming success stops the loop; with no nullable-iterated repetition this case always progresses. Hence the recursion descends in a well-founded order and terminates.

Theorem 4.2.5 (A PEG language that is not context-free)

The PEG

S <- &(A 'c') 'a'+ B !.
A <- 'a' A? 'b'
B <- 'b' B? 'c'

accepts exactly \(\{\, a^m b^m c^m \mid m \ge 1 \,\}\), which is not context-free.

Proof

Claim A. If the input from position \(i\) is \(a^p y\) with \(p \ge 1\) and \(y\) not starting with a, then \(\mathrm{match}(A, i) = i + 2p\) if \(y\) starts with \(b^p\), and \(\mathsf{fail}\) otherwise. By induction on \(p\). \(A\) reads a; then A? at \(i+1\): if \(p = 1\) the input there is \(y\), \(A\) fails (it needs a), A? succeeds empty, and 'b' needs \(y\) to start with b: the claim for \(p = 1\). If \(p > 1\), by the induction hypothesis \(A\) at \(i + 1\) consumes \(a^{p-1} b^{p-1}\) if \(y\) starts with \(b^{p-1}\), and then 'b' needs one more b: success iff \(y\) starts with \(b^{p}\), ending at \(i + 2p\). If \(A\) at \(i+1\) fails, A? is empty and 'b' is tried at \(i + 1\), where the input is a (\(p > 1\)): fail. Symmetrically, Claim B: on \(b^p z\) (\(z\) not starting with b), \(B\) consumes \(b^p c^p\) iff \(z\) starts with \(c^p\).

Now let \(x\) be accepted. The predicate needs A 'c' at 0, so \(x = a^m y\) with \(m \ge 1\) and, by Claim A, \(y = b^m c\, y'\). Then 'a'+ consumes exactly \(a^m\) (greedy, stops at b), \(B\) at position \(m\) on \(b^m c\, y'\) succeeds by Claim B only if \(c\, y'\) starts with \(c^m\), consuming \(b^m c^m\), and !. forces the end: \(x = a^m b^m c^m\). Conversely each \(a^m b^m c^m\) passes all four steps. The language is not context-free by the pumping lemma [HMU07 §7.2].

Proposition 4.2.6 (Ordered choice changes the language: \(2^k - 1\))

Read the CFG \(S \to a\, S\, a \mid a\) (all odd-length strings of a) as the PEG S <- 'a' S 'a' / 'a'. Then S !. accepts \(a^r\) exactly when \(r = 2^k - 1\) for some \(k \ge 1\).

Proof

Let \(h(r)\) be the number of characters \(S\) consumes when \(r \ge 1\) characters a remain (\(S\) fails when \(r = 0\)). The first alternative succeeds iff \(r \ge 2\) and \(1 + h(r-1) + 1 \le r\); then \(h(r) = h(r-1) + 2\); otherwise \(h(r) = 1\). We show by induction on \(r\) that \(h(r) = 2(r - 2^k) + 1\) for \(2^k \le r \le 2^{k+1} - 1\). Base: \(h(1) = 1\) (\(k = 0\)). If \(r = 2^k\) with \(k \ge 1\): \(h(r-1) = r - 1\) (top of the previous block), so \(1 + (r - 1) + 1 = r + 1 > r\), the first alternative fails, \(h(r) = 1\). If \(2^k < r \le 2^{k+1} - 1\): \(h(r-1) = 2(r - 1 - 2^k) + 1\) and \(2 + h(r - 1) = 2(r - 2^k) + 1 \le r \iff r \le 2^{k+1} - 1\), true, so \(h(r) = h(r-1) + 2 = 2(r - 2^k) + 1\). Finally \(h(r) = r \iff 2(r - 2^k) + 1 = r \iff r = 2^{k+1} - 1\).

pegen rejects a grammar whose alternative can never be reached

Reproduce (pegen 0.3.0 from PyPI, the standalone release of CPython's parser generator; Python 3.11.15):

python3.11 -m venv venv && . venv/bin/activate && pip install -q pegen==0.3.0
cat > pitfall.gram <<'EOF'
start: e=call NEWLINE? ENDMARKER { e }
call: n=NAME { ('name', n.string) }
    | n=NAME '(' ')' { ('call', n.string) }
EOF
python -m pegen -q pitfall.gram -o pitfall.py 2>&1 | tail -2

Output (the last two lines of the traceback):

pegen.validator.ValidationError: In call there is an alternative that will never be visited:
NAME '(' ')'

What to notice: this is the prefix capture of the example after Definition 4.2.2, caught statically: pegen's validator (pegen/validator.py) finds an alternative whose prefix is an earlier alternative, which ordered choice makes unreachable. With the alternatives swapped the same generator accepts the grammar and the parser returns ('call', 'f') for f() and ('name', 'f') for f.

Packrat memoization

Algorithm 4.2.7 (Packrat parsing)

  • Input: a well-formed PEG \(G\); input \(x_1 \cdots x_n\).
  • Output: \(\mathrm{match}(e_S, 0)\) (and trees, if the rules build them).
  • Precondition: \(G\) well-formed (Definition 4.2.3); every repetition and predicate whose operand is not a nonterminal or terminal has been given its own rule (this bounds the work per call).
  • Postcondition: returns \(\mathrm{match}(e_S, 0)\) of Definition 4.2.2; Memo[A, i] \(= \mathrm{match}(A, i)\) for every entry stored.
  • Invariant: every stored entry Memo[A, i] equals \(\mathrm{match}(A, i)\), and Memo[A, i] is computed at most once.
function Parse(x):   return Eval(e_S, 0)

function Call(A, i):                        # the only memoized case
    if (A, i) ∈ Memo: return Memo[A, i]      # a memo hit
    r ← Eval(R(A), i)
    Memo[A, i] ← r
    return r

function Eval(e, i):
    case e of
        ε:        return i
        a:        return i + 1 if i < n and x[i+1] = a else fail
        .:        return i + 1 if i < n else fail
        A:        return Call(A, i)
        e1 e2:    j ← Eval(e1, i);  return fail if j = fail else Eval(e2, j)
        e1 / e2:  j ← Eval(e1, i);  return j if j ≠ fail else Eval(e2, i)
        e*:       j ← i
                  loop:  k ← Eval(e, j);  if k = fail or k = j: return j;  j ← k
        &e:       return i if Eval(e, i) ≠ fail else fail
        !e:       return fail if Eval(e, i) ≠ fail else i

pegen memoizes every rule call it generates

Reproduce (pegen 0.3.0, Python 3.11.15, in the venv of the previous box):

cat > memo.gram <<'EOF'
start: e=expr NEWLINE? ENDMARKER { e }
expr: t=term '+' e=expr { ('+', t, e) }
    | t=term { t }
term: n=NAME { n.string }
EOF
python -m pegen -q memo.gram -o memo.py && grep -n "@memoize" memo.py
cat > run.py <<'EOF'
import io, sys, tokenize
from pegen.tokenizer import Tokenizer
toks = tokenize.generate_tokens(io.StringIO(sys.argv[2]).readline)
print(__import__(sys.argv[1]).GeneratedParser(Tokenizer(toks), verbose=True).start())
EOF
python run.py memo a

Output (complete):

14:    @memoize
29:    @memoize
49:    @memoize
start() ... (looking at 1.0: NAME:'a')
  expr() ... (looking at 1.0: NAME:'a')
    term() ... (looking at 1.0: NAME:'a')
      name() ... (looking at 1.0: NAME:'a')
      ... name() -> TokenInfo(type=1 (NAME), string='a', start=(1, 0), end=(1, 1), line='a')
    ... term() -> a
    expect('+') ... (looking at 1.1: NEWLINE:'')
    ... expect('+') -> None
    term() -> a
  ... expr() -> a
  expect('NEWLINE') ... (looking at 1.1: NEWLINE:'')
  ... expect('NEWLINE') -> TokenInfo(type=4 (NEWLINE), string='', start=(1, 1), end=(1, 2), line='')
  expect('ENDMARKER') ... (looking at 2.0: ENDMARKER:'')
  ... expect('ENDMARKER') -> TokenInfo(type=0 (ENDMARKER), string='', start=(2, 0), end=(2, 0), line='')
... start() -> a
a

What to notice: the first alternative of expr calls term at token 0, then fails on +; the second alternative calls term at token 0 again, and the line term() -> a without ... is a memo hit: pegen/parser.py's memoize decorator [PEGEN-Parser] returns the cached (tree, position) for the pair (rule, token position), Call of Algorithm 4.2.7. CPython's generated C parser memoizes only rules marked (memo) in python.gram and all left-recursive ones [PEP617], because a full memo table costs memory per token.

Left recursion in PEGs

Algorithm 4.2.8 (Seed growing for a directly left-recursive rule)

  • Input: a rule A <- A α / β whose only left recursion is the leading \(A\) of the first alternative (\(\alpha\), \(\beta\) well-formed and not calling \(A\) first); position \(i\).
  • Output: \(\mathrm{grow}(A, i)\): an end position or \(\mathsf{fail}\), and a left-nested tree.
  • Precondition: the rest of the grammar is well-formed; Memo holds no entry for \((A, i)\).
  • Postcondition: the result equals \(\mathrm{match}(\beta\, \alpha^{*}, i)\) with the tree nested to the left (Theorem 4.2.9).
  • Invariant: before round \(r \ge 1\), Memo[A, i] holds the end of the round-\((r-1)\) match (\(\mathsf{fail}\) for \(r = 1\)), and the ends of successive rounds strictly increase.
function CallLeftRec(A, i):
    if (A, i) ∈ Memo: return Memo[A, i]
    Memo[A, i] ← fail                    # the seed: a left-recursive call fails at first
    best ← fail
    loop:
        r ← Eval(R(A), i)                # re-run the whole body; the inner A reads Memo
        if r = fail or (best ≠ fail and r ≤ best): break
        best ← r;  Memo[A, i] ← best     # grow: the next round starts from this match
    Memo[A, i] ← best
    return best

Theorem 4.2.9 (Seed growing parses left recursion as left-nested iteration)

Under the preconditions of Algorithm 4.2.8, \(\mathrm{grow}(A, i) = \mathrm{match}(\beta\, \alpha^{*}, i)\), and the tree built is \((\cdots((\beta\ \alpha_1)\ \alpha_2) \cdots \alpha_m)\) for the \(m\) iterations of \(\alpha\).

Proof

Let \(b = \mathrm{match}(\beta, i)\). If \(b = \mathsf{fail}\): round 1 has Memo[A, i] = fail, so A α fails and β fails, \(r = \mathsf{fail}\), and the result is \(\mathsf{fail} = \mathrm{match}(\beta \alpha^{*}, i)\). Otherwise define \(e_1 = b\) and \(e_{j+1} = \mathrm{match}(\alpha, e_j)\) while it succeeds with \(e_{j+1} > e_j\); let \(e_m\) be the last defined value, so \(\mathrm{match}(\beta \alpha^{*}, i) = e_m\). Claim: round \(j\) returns \(e_j\) for \(j \le m\), and round \(m + 1\) returns a value \(\le e_m\) or \(\mathsf{fail}\). Round 1: the inner \(A\) fails (seed), A α fails, β gives \(e_1\). Round \(j + 1\) (\(j \ge 1\)): the inner \(A\) reads Memo[A, i] \(= e_j\) (invariant), so A α gives \(\mathrm{match}(\alpha, e_j)\), which is \(e_{j+1}\) for \(j < m\); ordered choice takes it. For \(j = m\), A α fails or does not grow; if it fails, β gives \(e_1 \le e_m\); if it succeeds with \(e_{m+1} \le e_m\) (a non-consuming \(\alpha\)), the result is \(\le e_m\). Either way the loop stops with \(\mathrm{best} = e_m\). Each round wraps the previous tree as the left child of a new \(A \to A\,\alpha\) node, which gives the left-nested tree. The ends strictly increase, so the loop runs at most \(n - i + 2\) rounds.

pegen grows the seed of diff: diff '-' NAME | NAME

Reproduce (pegen 0.3.0, Python 3.11.15, venv and run.py of the previous boxes):

cat > leftrec.gram <<'EOF'
start: e=diff NEWLINE? ENDMARKER { e }
diff: a=diff '-' b=NAME { ('-', a, b.string) }
    | n=NAME { n.string }
EOF
python -m pegen -q leftrec.gram -o leftrec.py && grep -n "memoize_left_rec" leftrec.py
python run.py leftrec 'a - b - c' | grep -E 'Recursive|Bailing|diff\(\) ->'

Output (complete):

10:from pegen.parser import memoize, memoize_left_rec, logger, Parser
29:    @memoize_left_rec
  Recursive diff at 0 depth 0
    diff() -> None [fresh]
  Recursive diff at 0 depth 1: a to 1
    diff() -> a [fresh]
  Recursive diff at 0 depth 2: ('-', 'a', 'b') to 3
    diff() -> ('-', 'a', 'b') [fresh]
  Recursive diff at 0 depth 3: ('-', ('-', 'a', 'b'), 'c') to 5
    diff() -> ('-', ('-', 'a', 'b'), 'c') [fresh]
  Recursive diff at 0 depth 4: a to 1
  Bailing with ('-', ('-', 'a', 'b'), 'c') to 5
  diff() -> ('-', ('-', 'a', 'b'), 'c') [cached]
('-', ('-', 'a', 'b'), 'c')

What to notice: Algorithm 4.2.8 line by line: the seed is None (fail); rounds 1–3 end at token positions 1, 3, 5; round 4 falls back to the second alternative (a to 1), which does not grow, so the parser "bails" with the round-3 result, and the final lookup is a memo hit. The tree is left-nested, as Theorem 4.2.9 says. CPython 3.11's own parser grows sum, term and shift_expr this way (the tree in Lesson 4.1's CPython box).

3. Worked example

The PEG is the right-recursive arithmetic grammar (left recursion avoided on purpose, so that plain packrat applies):

E <- T '+' E / T
T <- F '*' T / F
F <- '(' E ')' / 'n'

and the input is n+n*n (positions 0–5). Every call of a nonterminal, in order (generated by the oracle, ./course drill packrat-memo prints the same format):

step call (indented by depth) event result why
1 E@0 call start rule
2   T@0 call E's first alternative begins with T
3     F@0 call T's first alternative begins with F
4     F@0 done 1 '(' fails, 'n' matches
5     F@0 hit 1 '*' failed at 1; T's second alternative calls F@0 again
6   T@0 done 1
7   E@2 call '+' matched at 1; E's first alternative continues with E at 2
8     T@2 call
9       F@2 call
10       F@2 done 3 'n' at 2
11       T@4 call '*' matched at 3
12         F@4 call
13         F@4 done 5 'n' at 4
14         F@4 hit 5 '*' failed at 5 (end); T's second alternative
15       T@4 done 5
16     T@2 done 5 first alternative F '*' T
17     T@2 hit 5 '+' failed at 5; E@2's second alternative calls T@2 again
18   E@2 done 5
19 E@0 done 5 first alternative T '+' E

The final memo table (every entry computed once):

rule position 0 1 2 3 4 5
E 5 5
T 1 5 5
F 1 3 5
  • 8 rule evaluations and 3 memo hits. Without the memo table the same parse makes 15 rule calls: each hit becomes a call, and the one at step 17 re-evaluates the whole subtree T@2, F@2, T@4, F@4, F@4 (5 calls instead of 1 hit): \(8 + 1 + 1 + 5 = 15\).
  • Positions 1 and 3 hold operators, so no rule is ever called there: a packrat table is sparse in practice.
  • E consumed the whole input (5 = n): accepted. The tree is \((+\ n\ (*\ n\ n))\); note that this grammar makes + and * right-associative, which is why real PEGs use repetition (E <- T ('+' T)*, the lab's grammar) or left recursion (Algorithm 4.2.8) instead.

Try it

./course drill packrat-memo --seed 2 --difficulty medium --solution runs this kind of table on other PEGs and inputs; --difficulty hard adds predicates and the prefix-capture grammar.

4. Invariants and correctness

Theorem 4.2.10 (Packrat parsing is correct and linear)

Let \(G\) be well-formed with every repetition and predicate operand a terminal or nonterminal (Algorithm 4.2.7's precondition), and let \(\lvert G \rvert\) be the total size of its rule bodies. Then Algorithm 4.2.7 returns \(\mathrm{match}(e_S, 0)\), every entry Memo[A, i] equals \(\mathrm{match}(A, i)\), and it runs in \(O(\lvert G \rvert\,(n+1))\) time and space.

Proof

Correctness. Eval is Definition 4.2.2 written as code, except that Call may return a stored value instead of re-evaluating. By induction on the order in which entries are stored: an entry Memo[A, i] is stored with the value of Eval(R(A), i), which equals \(\mathrm{match}(A, i)\) provided every entry read during that evaluation was correct, which holds by the induction hypothesis (entries read were stored earlier). The evaluation terminates by Theorem 4.2.4, because memo hits only shorten it.

Time. There are \(\lvert N \rvert\,(n+1)\) pairs \((A, i)\) and each is evaluated at most once (the invariant). One evaluation of \(R(A)\), not counting the time inside nested Calls, does \(O(\lvert R(A) \rvert)\) work plus the iterations of its repetitions; each iteration of e* (with \(e\) a terminal or nonterminal) consumes at least one position and makes one Call or terminal test. Charge each iteration to the pair (operand, position) it starts at: over the whole run a repetition node at a fixed position of the input is started only within the one evaluation of its enclosing rule at that position, so the total is \(\sum_A \lvert R(A) \rvert (n+1) = O(\lvert G \rvert (n + 1))\). Space: the memo table has \(\lvert N \rvert (n+1)\) entries and the recursion depth is at most \(\lvert N \rvert (n+1)\) (no pair is active twice).

Proposition 4.2.11 (Without memoization: exponential)

For the PEG S <- A 'x' / A 'y' / A, A <- '(' S ')' / 'n' and input \((^{d}\, n\, )^{d}\), the plain recursive interpreter makes \(2 \cdot 3^{d+1} - 2\) rule calls, and packrat makes \(2d + 2\) rule evaluations.

Proof

Let \(C(d)\) be the calls made by one call of \(S\) at the start of \((^{d} n )^{d}\), counting itself. \(S\) tries three alternatives, each starting with one call of \(A\); the first two fail after \(A\) succeeds (no x or y follows), the third succeeds. One call of \(A\) at depth \(d \ge 1\) makes itself plus one call of \(S\) at depth \(d - 1\): \(1 + C(d-1)\) calls; at \(d = 0\) it matches n with 1 call. Hence \(C(d) = 1 + 3(1 + C(d-1))\) for \(d \ge 1\) and \(C(0) = 1 + 3 = 4\), so \(C(d) = 4 + 3\,C(d-1)\), whose solution is \(C(d) = 2 \cdot 3^{d+1} - 2\) (\(C(0) = 4\), \(C(1) = 16\), \(C(2) = 52\)). With the memo table only the pairs \((S, i)\) and \((A, i)\) for \(i = 0, \dots, d\) are evaluated: \(2(d + 1)\).

Where the argument breaks. Left recursion violates Theorem 4.2.4's measure (a call returns to \((A, i)\) at the same position), so Algorithm 4.2.7 recurses forever; Theorem 4.2.9 repairs direct left recursion only. A nullable-iterated e* would loop in Ford's rules, which leave it undefined; Definition 4.2.2 (the \(j > i\) condition) and Algorithm 4.2.7 (the k = j test) both stop a non-consuming iteration, a standard deviation from [For04] that makes every repetition terminate.

5. Complexity

Let \(n\) be the input length, \(\lvert N \rvert\) the number of rules and \(\lvert G \rvert\) the grammar size.

Technique Time (worst) Time (typical) Space Notes
PEG, plain recursive interpreter \(\Theta(3^{n/2})\) on Proposition 4.2.11's family near-linear on grammars that rarely backtrack \(O(n)\) stack exponential from repeated sub-parses
Packrat \(O(\lvert G \rvert\, n)\) (Theorem 4.2.10) 4.46 (calls + hits) per token on the lab's Pebble expressions \(O(\lvert N \rvert\, n)\) memo memory is the practical limit
Seed growing \(O(\lvert G \rvert\, n)\) per left-recursive pair plus the rounds; \(O(n^2)\) in contrived cases one extra round per rule as packrat each round re-runs the rule body

Pathological family. Proposition 4.2.11 gives \(2 \cdot 3^{d+1} - 2\) calls for \(n = 2d + 1\) characters without memoization, \(2d + 2\) with it. The oracle reproduces the counts: packrat(peg, '('*d + 'n' + ')'*d, memoize=False).calls is 4, 16, 52, 160, 484, … for \(d = 0, 1, 2, 3, 4\) (tested in tools/course/tests/test_ch04.py).

At scale. The memo table has \(\lvert N \rvert\) entries per input position. For a grammar with a few hundred rules over a large file that is far more memory than the input itself, which is why CPython memoizes only rules marked (memo) in python.gram plus the left-recursive ones [PEP617], and why cut operators [MMY10] were invented. The lab's packrat parser makes 4.46 rule calls plus memo hits per token on random Pebble expressions (11.5 ms at 28 500 tokens; ch04-parsebench), so it stores fewer than 4.5 entries per token of the 13 × (n + 1) possible.

6. Variants and refinements

Parsing expression grammars

  • Scannerless parsing [For04]: terminals are characters, so one PEG describes lexical and syntactic structure (! handles keywords vs identifiers) — trade-off: no separate lexer, but every rule sees whitespace and the memo table is per character.
  • Cut operators (Mizushima, Maeda and Yamaguchi 2010 [MMY10]): a ^ after a committed prefix tells the parser that alternatives to the right will not be tried, so memo entries before the cut can be freed — trade-off: bounded memory for well-cut grammars, at the cost of annotating the grammar.

Packrat memoization

  • Selective memoization (CPython [PEP617]): memoize only rules that are re-invoked at the same position — trade-off: most of the speed with a fraction of the memory; the choice is made by profiling.
  • Error reporting by the furthest failure [For02]: record the rightmost position where any terminal test failed and the set of terminals expected there — trade-off: cheap and usually accurate (Lesson 4.5 uses it for combinators).

Left recursion in PEGs

  • Bounded left recursion [MMI14]: a semantics that interprets a left-recursive nonterminal by bounding its recursion depth and increasing the bound while the match grows; it handles indirect and mutual left recursion and defines the result for every grammar — trade-off: a cleaner theory than seed growing, same cost profile.
  • Curtailment (Frost & Hafiz 2006 [FH06], Lesson 2.5): cut off a left-recursive call when its depth exceeds the remaining input — trade-off: works for full (non-committing) backtracking and ambiguous grammars, but polynomial rather than linear.

7. In real compilers

Parsing expression grammars

CPython 3.9+ parses Python with a PEG (Grammar/python.gram [CPY-Gram], generated by Tools/peg_generator/pegen [CPY-pegen]; PEP 617 [PEP617] explains the switch from LL(1)). LPeg (Lua) implements PEGs as a parsing machine [Ier09]. Rust's pest and JavaScript's PEG.js are PEG generators used for DSLs. The real-world box under the Definitions shows pegen's reachability check.

Packrat memoization

pegen's memoize decorator (pegen/parser.py [PEGEN-Parser]) and the C code CPython generates from python.gram (memoizing (memo) rules and left-recursive rules). The box after Algorithm 4.2.7 shows a memo hit.

Left recursion in PEGs

pegen's memoize_left_rec [PEGEN-Parser] implements Algorithm 4.2.8, and compute_left_recursives in parser_generator.py [CPY-pegen] finds the leaders of left-recursive cycles (including indirect ones) so that only they grow seeds. The box after Theorem 4.2.9 shows the rounds.

8. Comparison

Technique Power / precision Speed (asymptotic · practical) Output / error quality Implementation effort Typical use
Parsing expression grammars Unambiguous by construction; recognizes some non-CFLs (\(a^m b^m c^m\), Theorem 4.2.5); ordered choice can silently shrink a CFG's language (Proposition 4.2.6) Linear with packrat; exponential without on adversarial grammars Furthest-failure messages; no conflicts to report Low: the grammar is the parser CPython, DSLs (pest, PEG.js, LPeg), scannerless parsers
Packrat memoization Same language as the PEG \(O(\lvert G \rvert\, n)\) · 4.46 calls+hits/token and 11.5 ms at 28 500 tokens in the lab Same as PEG Low: one table CPython (selectively), the lab
Left recursion in PEGs (seed growing) Adds direct (and, with cycle leaders, indirect) left recursion with left-nested trees One extra round per left-recursive call Same as PEG Medium: the growing loop and the leader analysis CPython's sum/term, Ohm, pegen

Choose a PEG when you want a grammar that is also an executable, conflict-free parser, possibly without a lexer, and you can afford to think about the order of alternatives. Choose packrat memoization when the grammar backtracks over large sub-parses (it is what makes a PEG linear), and selective memoization when memory matters. Choose seed growing when the natural grammar is left-recursive (binary operators) and you do not want to rewrite it into repetitions.

9. Assessment

Technique Quiz ids Drill Flashcard tag Exercises
Parsing expression grammars peg-prefix-capture, peg-anbncn packrat-memo --difficulty hard, paradigm-accepts peg lab L3
Packrat memoization packrat-table, packrat-hits packrat-memo packrat lab L3, R7
Left recursion in PEGs seed-rounds, seed-tree packrat-memo (the seed is the first round) left-recursion-peg lab stretch goal

References

See the chapter references.