Lesson 2.5 — Predictive and backtracking recursive descent¶

Techniques: table-driven predictive parsing, hand-written predictive recursive descent, backtracking recursive descent, memoized backtracking · Pebble implements: table-driven (lab exercise E5) and hand-written recursive descent (pebblec's parser; lab L1–L2) · Lab: labs/ch02-ll1-toolkit (SPEC): parseLL1 vs rd::parseTree, backtrackRecognize naive vs memoized · Prerequisites: Lesson 2.3, Lesson 2.4 · Time: 4 hours

A predictive parser never guesses: the next token and the table decide every step, so it runs in linear time and stops at the first token that cannot continue a sentence. You can run it as a small loop over an explicit stack (table-driven), or write one function per nonterminal and let the call stack be the parse stack (recursive descent), which is what Clang, GCC, rustc, swiftc, Go and V8 do. When the grammar is not LL(1), a parser can instead try alternatives and back up on failure: simple and general, but exponential unless it remembers what it already parsed.

1. Problem and motivation¶

Input: an LL(1) table (or grammar) and a token sequence. Output: accept or the first syntax error, plus a leftmost derivation or a tree. In pebblec this is the front half of the parser that Ch 4 completes; in the lab it is two implementations that must agree token for token.

Table-driven predictive parsing¶

Lewis and Stearns's LL(k) parsers [LS68] and Knuth's analysis [Knu71] describe the parser as a pushdown automaton driven by the table: a stack of grammar symbols, one move per step. It is what parser generators emit when they want small, uniform code, e.g. CPython's LL(1) parser until 3.8, which walked per-rule DFAs with a table-driven stack [CPY38-pgen].

Hand-written predictive recursive descent¶

Recursive descent is older than the theory: Lucas described one recursive procedure per syntactic category in 1961 [Luc61], and Conway's COBOL compiler used transition diagrams as mutually recursive coroutines [Con63]. Each nonterminal becomes a function whose switch on the lookahead is that nonterminal's row of the LL(1) table. It won in production because each function is a place to put precise error messages, recovery, lookahead tricks and AST construction: GCC replaced its yacc-generated C++ parser with a hand-written recursive-descent one in GCC 3.4 (2004) and its Bison C parser in GCC 4.1 (2006) [GCC34, GCC41].

Backtracking recursive descent¶

When one token is not enough (C++ declarations vs expressions, or a grammar you do not want to transform), a recursive-descent parser can try an alternative and, if it fails, restore the input position and try the next. The "list of successes" formulation [Wad85] returns every way a nonterminal can match, so it never commits wrongly and recognizes every non-left-recursive context-free grammar, ambiguous ones included (Lemma 2.5.11). The price is exponential time (Proposition 2.5.14).

Memoized backtracking¶

Memoizing the result of each (nonterminal, position) pair removes the repeated work: Birman and Ullman's analysis of backtracking parsers gave the tabular algorithm [BU73], Ford's packrat parsers apply it to ordered choice [For02], and Frost and Hafiz apply it to full backtracking [FH06]. It is the bridge to PEG/packrat parsing in Ch 4.

2. Definitions and algorithms¶

Throughout, the input is $w = t_1 \cdots t_n$ and $t_{n+1} = \$$; $M$ is the LL(1) table of Definition 2.3.1.

Definition 2.5.1 (Predictive parser configurations and moves)

A configuration is a pair $(\gamma, i)$ of a stack $\gamma \in (N \cup T)^{*}\$$ written with its top on the left, and an input position $0 \le i \le n$; the lookahead is $a = t_{i+1}$. The initial configuration is $(S\,\$, 0)$. The moves are: match $(t \gamma, i) \vdash (\gamma, i+1)$ if $t = a \in T$; expand $(A \gamma, i) \vdash (\alpha \gamma, i)$ with output $A \to \alpha$ if $M[A, a] = \{A \to \alpha\}$; accept in $(\$, n)$; every other configuration is an error. (Trace tables print the stack bottom-first, top on the right.)

Definition 2.5.2 (Correct-prefix property)

A parser has the correct-prefix property if, whenever it reports an error at token $t_{i+1}$ (or at $\$$ when $i = n$), the prefix $t_1 \cdots t_i$ is a prefix of some sentence of $L(G)$ and $t_1 \cdots t_{i+1}$ is not.

Definition 2.5.3 (List-of-successes semantics, calls)

For $X \in N \cup T$ and a position $i$, $\mathrm{Parse}(X, i) \triangleq \{\, j \mid X \Rightarrow^{*} t_{i+1} \cdots t_j \,\}$, and for a string, $\mathrm{Seq}(Y_1 \cdots Y_k, i) \triangleq \{\, j \mid Y_1 \cdots Y_k \Rightarrow^{*} t_{i+1} \cdots t_j \,\}$. $w \in L(G)$ iff $n \in \mathrm{Parse}(S, 0)$. A call is one execution of a nonterminal's alternatives; a memo hit is not a call.

The semantics on ( id )

With $E \to T + E \mid T$, $T \to (\,E\,) \mid \mathtt{id}$ and $w = (\ \mathtt{id}\ )$: $\mathrm{Parse}(T, 1) = \{2\}$ (just id), $\mathrm{Parse}(E, 1) = \{2\}$, $\mathrm{Parse}(T, 0) = \{3\}$, and $\mathrm{Parse}(E, 0) = \{3\} \ni n$: accepted.

Table-driven predictive parsing¶

Algorithm 2.5.4 (PredictiveParse)

Input: $G$, a conflict-free table $M$, tokens $t_1 \cdots t_n$.
Output: the leftmost derivation (productions in order) and accept, or the first error with its expected set.
Precondition: $M$ has no conflicting cell (a conflicting cell is treated as an error), $G$ reduced.
Postcondition: accepts iff $w \in L(G)$; the output is the leftmost derivation of $w$; errors satisfy the correct-prefix property (Theorem 2.5.9).
Invariant: (matched input) $\cdot$ (stack minus $, read top to bottom) is a left-sentential form, and the output so far is its leftmost derivation (Lemma 2.5.8).

Reference solution: solutions/labs/ch02-ll1-toolkit/src/PredictiveParser.cpp; contract ll1::parseLL1.

function PredictiveParse(G, M, t1 … tn):
    stack ← [$, S];  i ← 1;  output ← []           # t(n+1) = $; top = last element
    loop:
        X ← top(stack);  a ← t(i)
        if X = $ and a = $: return accept(output)
        if X = $: return error(i, expected {$})
        if X is a terminal:
            if X = a: pop;  i ← i + 1                 # match
            else: return error(i, expected {X})
        else if M[X, a] = {X → Y1 … Yk}:
            pop;  push Yk, …, Y1                      # Y1 on top
            append (X → Y1 … Yk) to output
        else:
            return error(i, expected { t : M[X, t] ≠ {} })

ANTLR 4 interprets a grammar without generating code

Reproduce (ANTLR 4.13.2 complete jar, OpenJDK 21.0.10):

cat > ExprLL1.g4 <<'EOF'
grammar ExprLL1;
s  : e EOF ;
e  : t e1 ;
e1 : '+' t e1 | ;
t  : f t1 ;
t1 : '*' f t1 | ;
f  : '(' e ')' | ID ;
ID : [a-z]+ ;
WS : [ \t\r\n]+ -> skip ;
EOF
echo 'a + b * c' > in.txt
java -cp antlr-4.13.2-complete.jar org.antlr.v4.gui.Interpreter ExprLL1.g4 s -tree -trace in.txt

Output (complete):

enter   s, LT(1)=a
enter   e, LT(1)=a
enter   t, LT(1)=a
enter   f, LT(1)=a
consume [@0,0:0='a',<5>,1:0] rule f
exit    f, LT(1)=+
enter   t1, LT(1)=+
exit    t1, LT(1)=+
exit    t, LT(1)=+
enter   e1, LT(1)=+
consume [@1,2:2='+',<1>,1:2] rule e1
enter   t, LT(1)=b
enter   f, LT(1)=b
consume [@2,4:4='b',<5>,1:4] rule f
exit    f, LT(1)=*
enter   t1, LT(1)=*
consume [@3,6:6='*',<2>,1:6] rule t1
enter   f, LT(1)=c
consume [@4,8:8='c',<5>,1:8] rule f
exit    f, LT(1)=<EOF>
enter   t1, LT(1)=<EOF>
exit    t1, LT(1)=<EOF>
exit    t1, LT(1)=<EOF>
exit    t, LT(1)=<EOF>
enter   e1, LT(1)=<EOF>
exit    e1, LT(1)=<EOF>
exit    e1, LT(1)=<EOF>
exit    e, LT(1)=<EOF>
consume [@5,10:9='<EOF>',<-1>,2:0] rule s
exit    s, LT(1)=<EOF>
(s:1 (e:1 (t:1 (f:2 a) t1:2) (e1:1 + (t:1 (f:2 b) (t1:1 * (f:2 c) t1:2)) e1:2)) <EOF>)

What to notice: this is §3's grammar and sentence (with ID for id). org.antlr.v4.gui.Interpreter runs ParserInterpreter [ANTLR4-Interp], which walks the grammar's transition network with an explicit stack instead of generated code: the data-driven counterpart of Algorithm 2.5.4, used by grammar IDEs. Every enter X, LT(1)=a is an expand at lookahead $a$, every consume a match; in the tree t1:2 means "alternative 2 of t1", the $\varepsilon$-production chosen on a FOLLOW token (+ or <EOF>), exactly the cells $M[T', +]$ and $M[T', \$]$.

Hand-written predictive recursive descent¶

Algorithm 2.5.5 (Recursive descent for the lab's expression grammar)

Input: the tokens; one function per nonterminal of $E \to T E'$, $E' \to + T E' \mid - T E' \mid \varepsilon$, $T \to F T'$, $T' \to * F T' \mid / F T' \mid \varepsilon$, $F \to (\,E\,) \mid \mathtt{id} \mid \mathtt{num}$.
Output: the same tree and the same errors as Algorithm 2.5.4 (Parse), or a left-associative AST (ParseSum).
Precondition: each function's cases are exactly its row of $M$; $\varepsilon$-alternatives are taken on $\mathrm{FOLLOW}$, never as a default:.
Postcondition: Parse agrees with PredictiveParse on every input (Proposition 2.5.10).
Invariant: when ParseX is entered with lookahead $a$, the callers' pending right-side suffixes, innermost first, spell the table-driven stack below $X$.

Lab exercises L1–L2; contract ll1::rd::parseTree, ll1::rd::parseAst.

function Parse():            node ← ParseE();  Expect($);  return node

function ParseE():           # M[E, t] = (1) for t ∈ { (, id, num }
    if look ∉ { (, id, num }: error(expected { (, id, num })
    return Node(E, 1, [ParseT(), ParseEPrime()])

function ParseEPrime():
    switch look:
        case + or −: op ← Expect(look);  return Node(E′, 2 or 3, [op, ParseT(), ParseEPrime()])
        case ) or $: return Node(E′, 4, [])          # ε on FOLLOW(E′): error at the same token
        default:     error(expected { +, −, ), $ })  # as the table-driven parser

function ParseT():           # M[T, t] = (5) for t ∈ { (, id, num }
    if look ∉ { (, id, num }: error(expected { (, id, num })
    return Node(T, 5, [ParseF(), ParseTPrime()])

function ParseTPrime():
    switch look:
        case * or /: op ← Expect(look);  return Node(T′, 6 or 7, [op, ParseF(), ParseTPrime()])
        case +, −, ) or $: return Node(T′, 8, [])    # ε on FOLLOW(T′)
        default:     error(expected { +, −, *, /, ), $ })

function ParseF():
    switch look:
        case (:        l ← Expect(();  e ← ParseE();  r ← Expect());  return Node(F, 9, [l, e, r])
        case id, num:  return Node(F, 10 or 11, [Expect(look)])
        default:       error(expected { (, id, num })

function Expect(t):          if look = t: advance; return Leaf(t)  else error(expected {t})

function ParseSum():         # L2: EBNF loop E → T { (+|−) T }, left-associative AST
    acc ← ParseProduct()
    while look ∈ { +, − }: op ← look;  advance;  acc ← Binary(op, acc, ParseProduct())
    return acc

function ParseProduct():     # T → F { (*|/) F }
    acc ← ParseFactor()
    while look ∈ { *, / }: op ← look;  advance;  acc ← Binary(op, acc, ParseFactor())
    return acc

function ParseFactor():      # F → ( Sum ) | id | num
    if look = (: advance;  e ← ParseSum();  Expect());  return e
    if look ∈ { id, num }: leaf ← Leaf(look);  advance;  return leaf
    error(expected { (, id, num })

Clang's recursion depth follows the nesting depth

Reproduce (clang 23.1.2; any OS):

cat > deep.c <<'EOF'
int x = ((((((((((((((((((((1))))))))))))))))))));
EOF
clang -fsyntax-only -fbracket-depth=10 deep.c
clang -fsyntax-only -fbracket-depth=20 deep.c && echo "depth 20: accepted"

Output (complete):

deep.c:1:19: fatal error: bracket nesting level exceeded maximum of 10
    1 | int x = ((((((((((((((((((((1))))))))))))))))))));
      |                   ^
deep.c:1:19: note: use -fbracket-depth=N to increase maximum nesting level
1 error generated.
depth 20: accepted

What to notice: each ( is one nested call of Clang's hand-written expression parser (Parser::ParseParenExpression inside ParseCastExpression), so the call stack plays the role of Algorithm 2.5.4's explicit stack, as the invariant of Algorithm 2.5.5 says. A recursive-descent parser therefore needs a guard against unbounded recursion: BalancedDelimiterTracker::consumeOpen (clang/include/clang/Parse/RAIIObjectsForParser.h) counts open brackets and stops with a fatal error at the limit (the 11^th parenthesis, column 19) [CLANG-Parser]. A table-driven parser would grow a heap-allocated stack instead.

Backtracking recursive descent¶

Algorithm 2.5.6 (Backtracking recognizer, list of successes)

Input: any grammar $G$ and tokens $t_1 \cdots t_n$.
Output: accept or reject; or an error if $G$ is left-recursive.
Precondition: for a decision, $G$ has no left recursion; otherwise the depth guard fires (Lemma 2.5.12).
Postcondition: Parse(X, i, ·) $= \mathrm{Parse}(X, i)$ of Definition 2.5.3 (Lemma 2.5.11); accepts iff $w \in L(G)$.
Invariant: every recursive call is at depth $\le \lvert N \rvert (n + 1)$ on a grammar without left recursion.

Lab exercise L3; contract ll1::backtrackRecognize(G, Input, /*Memoize=*/false); oracle backtrack_recognize.

function Accepts(G, t1 … tn):   return n ∈ Parse(S, 0, 0)

function Parse(X, i, depth):
    if X is a terminal: return {i + 1} if i < n and t(i+1) = X else {}
    if depth > |N| · (n + 1): fail "left recursion"          # [FH06] bound
    calls ← calls + 1
    ends ← {}
    for each alternative X → Y1 … Yk:                        # try them all
        ends ← ends ∪ Sequence(Y1 … Yk, i, depth + 1)
    return ends

function Sequence(Y1 … Yk, i, depth):
    cur ← {i}
    for each Y in Y1 … Yk:
        cur ← ⋃ { Parse(Y, j, depth) : j ∈ cur }
        if cur = {}: return {}
    return cur

Clang's tentative parsing decides the most vexing parse

Reproduce (clang 23.1.2; any OS):

cat > vexing.cpp <<'EOF'
struct U { U(); };
struct T { T(U); };
void f() {
  T x(U());      // a declaration, if it can be one
  T y((U()));    // cannot be a declaration: an object
}
EOF
clang++ -fsyntax-only vexing.cpp
clang++ -fsyntax-only -Xclang -ast-dump -fno-color-diagnostics vexing.cpp 2>/dev/null \
  | sed -n '/FunctionDecl.* f /,$p' | sed -E 's/ 0x[0-9a-f]+//g'

Output (complete; the second sed also strips the address after parent):

vexing.cpp:4:6: warning: parentheses were disambiguated as a function declaration [-Wvexing-parse]
    4 |   T x(U());      // a declaration, if it can be one
      |      ^~~~~
vexing.cpp:4:7: note: add a pair of parentheses to declare a variable
    4 |   T x(U());      // a declaration, if it can be one
      |       ^  
      |       (  )
1 warning generated.
`-FunctionDecl <line:3:1, line:6:1> line:3:6 f 'void ()' external-linkage
  `-CompoundStmt <col:10, line:6:1>
    |-DeclStmt <line:4:3, col:11>
    | `-FunctionDecl parent <col:3, col:10> col:5 x 'T (U (*)())' external-linkage
    |   `-ParmVarDecl <col:7, col:9> col:9 'U (*)()'
    `-DeclStmt <line:5:3, col:13>
      `-VarDecl <col:3, col:12> col:5 y 'T' callinit
        `-CXXConstructExpr <col:5, col:12> 'T' 'void (U)'
          `-ParenExpr <col:7, col:11> 'U'
            `-CXXTemporaryObjectExpr <col:8, col:10> 'U' 'void ()'

What to notice: T x(U()); has two parses, a variable initialized by a temporary U and a function x taking a pointer to a function returning U; C++ picks the declaration whenever one exists. No fixed lookahead can tell, so Clang tries the declarator parse and reverts if it fails: TentativeParsingAction (Commit()/Revert()) in clang/include/clang/Parse/Parser.h and Parser::isCXXDeclarationStatement in ParseTentative.cpp [CLANG-ParseTentative]. That is Algorithm 2.5.6 restricted to a few decision points, with ordered choice (declaration first). The extra parentheses in line 5 make the declarator parse fail, so the expression wins.

Memoized backtracking¶

Algorithm 2.5.7 (Memoized backtracking)

Input, output, precondition: as Algorithm 2.5.6.
Postcondition: the same answer; at most one call per pair $(X, i)$ with $X \in N$, $0 \le i \le n$ (Lemma 2.5.13).
Invariant: $\mathrm{memo}[(X, i)]$, once set, equals $\mathrm{Parse}(X, i)$.

Lab exercise L4; contract ll1::backtrackRecognize(G, Input, /*Memoize=*/true).

function ParseMemo(X, i, depth):
    if X is a nonterminal and (X, i) ∈ memo: return memo[(X, i)]      # a hit is not a call
    ends ← Parse(X, i, depth)                                       # body as above, recursing into ParseMemo
    if X is a nonterminal: memo[(X, i)] ← ends
    return ends

CPython's pegen memoizes every rule of a generated parser

Reproduce (CPython source at tag v3.13.0, run with Python 3.11.15; needs network for the clone):

git -c advice.detachedHead=false clone -q --depth 1 --filter=blob:none --sparse -b v3.13.0 https://github.com/python/cpython
cd cpython && git sparse-checkout set Tools/peg_generator && cd Tools/peg_generator
cat > expr.gram <<'EOF'
start: expr NEWLINE? ENDMARKER
expr: expr '+' term | term
term: '(' expr ')' | NAME
EOF
python3 -m pegen -q python expr.gram -o expr_parser.py
grep -n -B1 '    def ' expr_parser.py | grep -E '@|def '
echo 'a + (b + c)' > in.txt
PYTHONPATH=. python3 expr_parser.py -v in.txt 2>&1 | sed -n '/^Caches sizes/,$p'

Output (complete):

14-    @memoize
15:    def start(self) -> Optional[Any]:
29-    @memoize_left_rec
30:    def expr(self) -> Optional[Any]:
49-    @memoize
50:    def term(self) -> Optional[Any]:
Caches sizes:
  token array :          9
        cache :         21

What to notice: every rule method of the generated parser is wrapped in memoize (Tools/peg_generator/pegen/parser.py [CPY-pegen]), whose cache key is (input position, rule name, arguments): the memo[(X, i)] of Algorithm 2.5.7, with 21 entries for 9 tokens. The left-recursive expr gets memoize_left_rec (seed growing [WDM08]) instead of failing like Algorithm 2.5.6. PEG uses ordered choice (§6), so this is packrat parsing [For02]; CPython's C parser memoizes only the 18 rules marked (memo) in Grammar/python.gram (_should_memoize in pegen/c_generator.py), trading time for memory.

3. Worked example¶

Running example: the Dragon LL(1) expression grammar (tests/ch02/Inputs/expr-ll1.grammar) on id + id * id, and, for backtracking, $E \to T + E \mid T$, $T \to (\,E\,) \mid \mathtt{id}$ (tests/ch02/Inputs/backtrack-exponential.grammar), which is the same expression language without the left factoring.

(1) E  → T E'     (3) E' → ε        (5) T' → * F T'    (7) F → ( E )
(2) E' → + T E'   (4) T  → F T'     (6) T' → ε         (8) F → id

Table-driven predictive parsing on the running example¶

Every step (C++ ll1 parse tests/ch02/Inputs/expr-ll1.grammar --trace id + id '*' id, identical to the oracle ll1_parse):

step	stack (top on the right)	input	action
1	$ E	id + id * id $	output (1) E → T E'
2	$ E' T	id + id * id $	output (4) T → F T'
3	$ E' T' F	id + id * id $	output (8) F → id
4	$ E' T' id	id + id * id $	match id
5	$ E' T'	+ id * id $	output (6) T' → ε
6	$ E'	+ id * id $	output (2) E' → + T E'
7	$ E' T +	+ id * id $	match +
8	$ E' T	id * id $	output (4) T → F T'
9	$ E' T' F	id * id $	output (8) F → id
10	$ E' T' id	id * id $	match id
11	$ E' T'	* id $	output (5) T' → * F T'
12	$ E' T' F *	* id $	match *
13	$ E' T' F	id $	output (8) F → id
14	$ E' T' id	id $	match id
15	$ E' T'	$	output (6) T' → ε
16	$ E'	$	output (3) E' → ε
17	$	$	accept

Output: 1 4 8 6 2 4 8 5 8 6 3, the leftmost derivation (11 expansions + 5 matches + accept = 17 steps). On id + * id the parser stops at step 8 with $T$ on top and lookahead *: $M[T, *]$ is empty, so the error is "expected one of ( id; found *" at token 3.

Hand-written predictive recursive descent on the running example¶

The same run as function calls (depth = call-stack depth). Each call's switch looks at the same lookahead as the table-driven step that expanded the same nonterminal:

call	depth	function	lookahead	case taken
1	0	parseE()	id	(1) E → T E'
2	1	parseT()	id	(4) T → F T'
3	2	parseF()	id	(8) F → id
4	2	parseTPrime()	+	(6) T' → ε
5	1	parseEPrime()	+	(2) E' → + T E'
6	2	parseT()	id	(4) T → F T'
7	3	parseF()	id	(8) F → id
8	3	parseTPrime()	*	(5) T' → * F T'
9	4	parseF()	id	(8) F → id
10	4	parseTPrime()	$	(6) T' → ε
11	2	parseEPrime()	$	(3) E' → ε

The call stack at call 9 is parseE → parseEPrime → parseT → parseTPrime → parseF; the pending "rest of each right side" ($T'$ in parseTPrime, $E'$ in parseEPrime, $ in the caller) is exactly the table-driven stack $ E' T' at step 13. The lab checks this agreement on 2 000 random inputs (ch02.RDCompare.AgreesOnRandomInputs), including identical errors. ll1 rd id - id - num prints the AST ((id-id)-num) from the loop form, although the tree is right-nested.

Backtracking recursive descent on the running example¶

( id ) with $E \to T + E \mid T$ (oracle backtrack_recognize trace; positions between tokens 0…3):

#	event	nonterminal at position (· = depth)	end positions
1	call	E at 0	—
2	call	· T at 0	—
3	call	· · E at 1	—
4	call	· · · T at 1	—
5	return	· · · T at 1	{2}
6	call	· · · T at 1	—
7	return	· · · T at 1	{2}
8	return	· · E at 1	{2}
9	return	· T at 0	{3}
10	call	· T at 0	—
11	call	· · E at 1	—
12	call	· · · T at 1	—
13	return	· · · T at 1	{2}
14	call	· · · T at 1	—
15	return	· · · T at 1	{2}
16	return	· · E at 1	{2}
17	return	· T at 0	{3}
18	return	E at 0	{3}

9 calls. Every $E$ tries $T$ twice (once per alternative), and each $T$ contains the next $E$, so the work doubles per nesting level. Measured by the lab (ll1 backtrack, identical to the oracle):

nesting depth d	tokens	naive calls	memoized calls
0	1	3	2
1	3	9	4
2	5	21	6
4	9	93	10
8	17	1 533	18
12	25	24 573	26

The naive count is $3 \cdot 2^{d+1} - 3$ (Proposition 2.5.14).

Memoized backtracking on the running example¶

The same input with the memo (a hit returns the stored result without running any alternative):

#	event	nonterminal at position (· = depth)	end positions
1	call	E at 0	—
2	call	· T at 0	—
3	call	· · E at 1	—
4	call	· · · T at 1	—
5	return	· · · T at 1	{2}
6	hit	· · · T at 1	{2}
7	return	· · E at 1	{2}
8	return	· T at 0	{3}
9	hit	· T at 0	{3}
10	return	E at 0	{3}

Calls: E at 0, T at 0, E at 1, T at 1 = 4 = $2d + 2$. The memo ends with one entry per (nonterminal, position) that was asked: (T,1) → {2}, (E,1) → {2}, (T,0) → {3}, (E,0) → {3}.

Try it

./course drill predict-trace --seed 4 --difficulty easy gives a random LL(1) grammar and sentence; write the productions the parser outputs, then check with --solution (the step table above).

4. Invariants and correctness¶

Table-driven predictive parsing¶

Lemma 2.5.8 (Driver invariant)

In every configuration $(\gamma\,\$, i)$ reached by Algorithm 2.5.4 (stack top on the left), $S \Rightarrow_{\mathrm{lm}}^{*} t_1 \cdots t_i\, \gamma$, and the output so far is the sequence of productions of that leftmost derivation.

Proof

By induction on the number of moves. Initially $(S\,\$, 0)$ and the empty derivation. A match moves $t_{i+1}$ from the front of $\gamma$ to the matched prefix: the string $t_1 \cdots t_i\, \gamma$ is unchanged. An expand replaces the top $A$ by $\alpha$; since everything left of $A$ in $t_1 \cdots t_i\, A \gamma'$ is terminal, this is one leftmost step $t_1 \cdots t_i A \gamma' \Rightarrow_{\mathrm{lm}} t_1 \cdots t_i \alpha \gamma'$, and $A \to \alpha$ is appended to the output.

Theorem 2.5.9 (Correctness of the predictive parser)

Let $G$ be reduced and LL(1). On every input, Algorithm 2.5.4 terminates after $O(n)$ moves; it accepts iff $w \in L(G)$, in which case its output is the (unique) leftmost derivation of $w$; and it has the correct-prefix property.

Proof

Soundness. Accept happens in $(\$, n)$; by Lemma 2.5.8, $S \Rightarrow_{\mathrm{lm}}^{*} w$.

Completeness. Let $w \in L(G)$ with leftmost derivation $\mathcal{D}$. By induction on the moves, the parser's configuration always corresponds to a form of $\mathcal{D}$: if the top is $A$ in $t_1 \cdots t_i A \gamma'$ and $\mathcal{D}$ expands this $A$ by $A \to \alpha$, then $\alpha \gamma'\,\$ \Rightarrow^{*} t_{i+1} \cdots t_n\,\$$, so $t_{i+1} \in \mathrm{PREDICT}(A \to \alpha)$ by Lemma 2.3.7(a), i.e. $A \to \alpha \in M[A, t_{i+1}]$, and it is the only production there (Theorem 2.3.8). If the top is a terminal it equals $t_{i+1}$ because $\mathcal{D}$ derives $w$. So the parser follows $\mathcal{D}$ and accepts.

Correct prefix. Suppose the parser reports an error in $(\gamma\,\$, i)$. By Lemma 2.5.8, $t_1 \cdots t_i$ is a prefix of $t_1 \cdots t_i\, \gamma$, which derives a sentence ($G$ is reduced), so $t_1 \cdots t_i$ is a prefix of a sentence. If some sentence $t_1 \cdots t_{i+1} z$ existed, the completeness argument applied to it would show that the parser, which behaves identically on the common prefix, has a move on $t_{i+1}$: contradiction.

Termination. A reduced LL(1) grammar has no left recursion, hidden or not [AU72, §5.1] (Corollary 2.3.10 proves the direct case), and it is cycle-free, because a reduced grammar with $A \Rightarrow^{+} A$ gives some sentence infinitely many trees, contradicting Corollary 2.3.9. Proposition 2.5.15 uses these two facts to bound the number of moves by a constant (depending on $G$) times $n + 2$.

Hand-written predictive recursive descent¶

Proposition 2.5.10 (Recursive descent simulates the table-driven parser)

If every ParseX of Algorithm 2.5.5 selects its alternative by the row $M[X, \cdot]$ ($\varepsilon$-alternatives on FOLLOW tokens, errors elsewhere with the row's expected set), then on every input it performs the same expansions in the same order as Algorithm 2.5.4, builds the same tree, and reports the same first error (position and expected set).

Proof

By induction on the number of expansions, maintaining the invariant of Algorithm 2.5.5: when ParseX is entered, the concatenation of the callers' unparsed right-side suffixes, innermost first, followed by $, equals the table-driven stack below $X$. Entering ParseX with lookahead $a$ corresponds to the table-driven parser having $X$ on top with the same $a$; both choose the unique production of $M[X, a]$ or report the same error. Choosing $X \to Y_1 \cdots Y_k$ and calling for $Y_1$ pushes the suffix $Y_2 \cdots Y_k$ as pending work, exactly the symbols the table-driven expansion pushes below $Y_1$. Expect on a terminal is a match. Returning from ParseX with an empty suffix pops the frame, as the table-driven parser pops the last pushed symbol.

When it breaks: taking the $\varepsilon$-alternative as a default: case (instead of on FOLLOW) is legal and common, but it moves error detection later (the error appears in the caller), so errors no longer agree with the table. Left recursion makes ParseE call itself without consuming a token.

Backtracking recursive descent¶

Lemma 2.5.11 (List-of-successes semantics)

On a grammar without left recursion, Algorithm 2.5.6 terminates and returns $\mathrm{Parse}(X, i)$ and $\mathrm{Seq}(Y_1 \cdots Y_k, i)$ of Definition 2.5.3. Hence it accepts iff $w \in L(G)$, for every such $G$, ambiguous or not.

Proof

Correctness, by induction on the pair (length $j - i$ of the derived substring, height of the derivation tree): $X \Rightarrow^{*} t_{i+1} \cdots t_j$ iff some alternative $X \to Y_1 \cdots Y_k$ has split points $i = m_0 \le m_1 \le \cdots \le m_k = j$ with $Y_r \Rightarrow^{*} t_{m_{r-1}+1} \cdots t_{m_r}$ by lower trees. Sequence computes exactly the set of reachable $m_r$ after each $Y_r$ (union over all predecessors $m_{r-1}$), using the hypothesis for each $Y_r$. A terminal matches exactly one position. Termination: Lemma 2.5.12.

Lemma 2.5.12 (Depth bound)

If $G$ has no left recursion, every call of Algorithm 2.5.6 has depth at most $\lvert N \rvert (n + 1)$, so the guard never fires; if $G$ is left-recursive and reduced, the recursion is unbounded without the guard.

Proof

A chain of nested calls $\mathrm{Parse}(X_0, i_0) \to \mathrm{Parse}(X_1, i_1) \to \cdots$ has non-decreasing positions. While the position stays equal, each $X_{r+1}$ is a symbol of an alternative of $X_r$ preceded only by symbols that matched the empty string, i.e. $X_r \Rightarrow^{+} X_{r+1} \cdots$; if a nonterminal repeated at the same position, $G$ would be left-recursive. So at most $\lvert N \rvert$ calls share a position, and there are $n + 1$ positions [FH06]. Conversely, for a reduced left-recursive $G$, $A \Rightarrow^{+} A \gamma$ lets the recognizer call $\mathrm{Parse}(A, i)$ inside $\mathrm{Parse}(A, i)$ without consuming input.

When it breaks: ordered choice (commit to the first alternative that succeeds, as in PEG) is not equivalent: with $S \to a \mid a\, b$, the input a b fails because $S$ commits to a [For04].

Memoized backtracking¶

Lemma 2.5.13 (Memoization is sound)

$\mathrm{memo}[(X, i)]$, once set, equals $\mathrm{Parse}(X, i)$, and each pair $(X, i)$ with $X \in N$ is called at most once.

Proof

$\mathrm{Parse}(X, i)$ depends only on $X$, $i$ and the fixed input: the function has no side effects besides the call counter and the memo. So the first computed value, correct by Lemma 2.5.11, can be returned for every later request. A call happens only on a miss, and after the first call the pair is in the memo.

When it breaks: if parsing has side effects (symbol-table updates, C's typedef names), the result for $(X, i)$ depends on context, and memoization is wrong unless the context is part of the key.

5. Complexity¶

Variables: $n$ = number of tokens, $\lvert N \rvert$ nonterminals, $\lvert G \rvert$ grammar size, $d$ = nesting depth of the example.

Technique	Time (worst)	Time (typical)	Space	Variables
Table-driven predictive	$\Theta(n)$ moves for a fixed grammar; the constant can be exponential in $\lvert N \rvert$ (Proposition 2.5.15)	17 steps for 5 tokens; one table lookup per step	$O(n)$ stack; table $O(\lvert N \rvert \cdot \lvert T \rvert)$	as above
Hand-written predictive RD	$\Theta(n)$ calls	fastest in practice: direct calls and `switch`, no table	$O(n)$ call stack	as above
Backtracking RD (full)	exponential: $3 \cdot 2^{d+1} - 3$ calls on $d$ nested parentheses	fine on inputs that rarely backtrack	$O(n)$ stack plus position sets $O(n)$	$d$
Memoized backtracking	$O(\lvert N \rvert (n+1))$ calls, each $O(\lvert G \rvert \cdot n^{2})$ set work: $O(\lvert N \rvert \cdot \lvert G \rvert \cdot n^{3})$	$2d + 2$ calls on the example	$O(\lvert N \rvert \cdot n^{2})$ (a position set per entry)	as above

Proposition 2.5.14 (Exponential and linear call counts)

On $E \to T + E \mid T$, $T \to (\,E\,) \mid \mathtt{id}$ and the input $(^{d}\ \mathtt{id}\ )^{d}$, the naive recognizer makes $C(d) = 3 \cdot 2^{d+1} - 3$ calls and the memoized one $2d + 2$.

Proof

Let $E(d)$ and $T(d)$ be the naive calls made by $\mathrm{Parse}(E, i)$ and $\mathrm{Parse}(T, i)$ at a position followed by $(^{d}\ \mathtt{id} \cdots$. $T$: its first alternative calls $E$ one position further if $d \ge 1$, its second is a terminal test, so $T(0) = 1$ and $T(d) = 1 + E(d-1)$. $E$: both alternatives start with $T$ at the same position (the + then fails, since the input has none), so $E(d) = 1 + 2\, T(d)$. Hence $E(0) = 3$ and $E(d) = 3 + 2 E(d-1)$, i.e. $E(d) + 3 = 2(E(d-1) + 3)$, so $E(d) + 3 = 6 \cdot 2^{d}$ and $E(d) = 3 \cdot 2^{d+1} - 3$. With memoization only the pairs $(E, i)$ and $(T, i)$ for the $d + 1$ positions $i = 0, \dots, d$ before id are ever called (Lemma 2.5.13), and each is: $2(d + 1)$ calls.

Proposition 2.5.15 (Linear time of predictive parsing)

Let $G$ be a reduced LL(1) grammar with $r \ge 1$, let $K \triangleq \sum_{h=0}^{\lvert N \rvert - 1} r^{h}$ and $c_G \triangleq (\lvert N \rvert + 1)\, r\, K$. On $n$ tokens, Algorithm 2.5.4 makes at most $(n + 2)(1 + c_G + r\, c_G^{2})$ moves. The constant can really be exponential in $\lvert N \rvert$: for $S \to a\, S \mid A_1$, $A_i \to A_{i+1} A_{i+1}$ ($1 \le i < m$), $A_m \to \varepsilon$, which is LL(1), the empty input takes $2^{m} + 1$ moves (for $m = 5$: 33, as the oracle ll1_parse confirms).

Proof

Two facts from Theorem 2.5.9's termination paragraph: $G$ has no left recursion and no cycle. Hence (i) a tree whose yield is $\varepsilon$ has no nonterminal twice on a root-to-leaf path (that would be a cycle $A \Rightarrow^{+} A$), so it has at most $K$ interior nodes; and (ii) no chain $Z_0, Z_1, \dots$ in which each $Z_{j+1}$ is a child of $Z_j$ whose left siblings all derive $\varepsilon$ repeats a nonterminal (that would be left recursion), so such a chain has at most $\lvert N \rvert$ nonterminals.

Call a stack symbol old if it was on the stack when the current lookahead became current. A burst is a maximal run of expansions at one lookahead that starts with an old symbol $Y$ on top and expands only $Y$ and symbols pushed during the run. It ends when a terminal is matched, when $Y$ and everything pushed in the run have been removed by $\varepsilon$-expansions (exposing the next old symbol), or at an error or accept.

A burst makes at most $c_G$ expansions. Its expansions build part of a tree rooted at $Y$, in preorder, without matching a token. If the run removes $Y$ completely, that tree derives $\varepsilon$: at most $K$ expansions by (i). Otherwise the unfinished nodes form a chain as in (ii), at most $\lvert N \rvert$ nodes, and each has at most $r$ finished children, each a tree deriving $\varepsilon$: at most $\lvert N \rvert + r \lvert N \rvert K \le c_G$ expansions (as $rK \ge \lvert N \rvert$).

There are at most $n + 2 + n\, r\, c_G$ bursts. A burst starts either when a new lookahead becomes current (at most $n + 1$ times) or when the previous burst removed its old root. Each old symbol is removed at most once. Old symbols are the start symbol and the symbols that a burst ending in a match leaves on the stack; at most $n$ bursts end in a match, each leaving at most $r\, c_G$ symbols.

Total. $n$ matches, one final move (accept or error), and at most $c_G$ expansions per burst: $n + 1 + c_G (n + 2 + n\, r\, c_G) \le (n + 2)(1 + c_G + r\, c_G^{2})$. For the example, the empty input expands $S \to A_1$ and then the complete binary tree of $A$'s with $2^{m} - 1$ nodes, plus the accept.

Pathological input: the nesting family $(^{d}\ \mathtt{id}\ )^{d}$ with $E \to T + E \mid T$ above: every level calls $T$ twice. Measured: 24 573 naive calls vs 26 memoized at $d = 12$; the naive time grows from 0.02 ms ($d = 4$) to 5 ms ($d = 12$) on the test machine (ll1 backtrack --max-depth 12).

At scale: GCC's C++ parser comment calls the performance of its tentative (backtracking) parsing a known cost ("The performance of the parser could probably be improved substantially…", gcc/cp/parser.cc, GCC 15 [GCC-CPParser]), which is why production parsers backtrack only in bounded, local places.

Table-driven predictive parsing¶

Parse-table compression and default rows (Lesson 2.3, [TY79]) — trade-off: smaller tables, later error detection.
Extended LL (ELL) with per-rule DFAs (CPython pgen [CPY38-pgen]): the grammar's right sides are regular expressions compiled to DFAs, and the stack holds (DFA, state) pairs — trade-off: EBNF grammars without left factoring or $E'$ helpers, but a more complex generator.

Hand-written predictive recursive descent¶

EBNF loops for left-associative operators (lab exercise L2; [Wir77]) — trade-off: correct left-nested ASTs with no $E'$ functions; the code no longer mirrors a BNF grammar.
Precedence climbing / Pratt parsing for expressions [Pra73] (Ch 4): one function for all binary levels — trade-off: much shorter and faster than one function per level; the precedence table replaces the grammar.

Backtracking recursive descent¶

Ordered choice (PEG) [For04]: commit to the first alternative that succeeds — trade-off: linear with memoization and never ambiguous, but it silently rejects inputs a CFG would accept ($S \to a \mid a\, b$).
Bounded, local backtracking (tentative parsing): try one construct, roll back the token position — trade-off: used only at a few decision points (C++ declaration vs expression; real-world box in §2), which keeps the cost acceptable.

Memoized backtracking¶

Packrat parsing [For02]: memoize ordered-choice results; linear time for PEGs — trade-off: memory $O(\lvert N \rvert \cdot n)$, often larger than the input by 100×; mitigated by memoizing only selected rules (CPython's C parser, (memo) rules; real-world box in §2).
Curtailment for left recursion [FH06] and seed growing [WDM08] — trade-off: left-recursive grammars work unchanged, at the cost of a more subtle algorithm.

7. In real compilers¶

Table-driven predictive parsing¶

CPython 3.8 Parser/parser.c — PyParser_AddToken (v3.8.0): the table-driven stack machine over pgen's DFAs; classify maps a token to a label, and the parser pushes or pops DFA states [CPY38-pgen]. Removed in 3.10 after the PEG parser replaced it [PEP617].
ANTLR 4 runtime/Java/src/org/antlr/v4/runtime/ParserInterpreter.java — ParserInterpreter.parse (4.13.2) runs a grammar without generated code by walking its ATN with an explicit stack (real-world box in §2) [ANTLR4-Interp]. Most modern LL generators (ANTLR, JavaCC) emit recursive-descent code instead.

Hand-written predictive recursive descent¶

Clang (LLVM 23.1.2) clang/lib/Parse/ParseStmt.cpp — Parser::ParseStatementOrDeclarationAfterAttributes is a switch (Kind) on the current token: case tok::kw_if: return ParseIfStatement(...), and so on — one row of an LL(1) table per function [CLANG-ParseStmt]; nesting depth is capped by BalancedDelimiterTracker (real-world box in §2).
GCC gcc/c/c-parser.cc — c_parser_statement and gcc/cp/parser.cc — cp_parser_statement (GCC 15); the C++ file's header comment describes the parser as "of the standard recursive-descent variety" [GCC-CParser, GCC-CPParser].
rustc compiler/rustc_parse/src/parser/stmt.rs — Parser::parse_stmt_without_recovery (Rust 1.90.0) [RUSTC-Parser]; swiftc lib/Parse/ParseStmt.cpp — Parser::parseStmt (Swift 6.1) [SWIFT-ParseStmt]; Go src/go/parser/parser.go — (*parser).parseStmt (Go 1.23) [GO-Parser]; V8 src/parsing/parser-base.h — ParserBase<Impl>::ParseStatement (V8 12.9) [V8-ParserBase].

Find where LLVM does it. Open clang/lib/Parse/ParseStmt.cpp (LLVM 23.1.2) and find the switch (Kind) in Parser::ParseStatementOrDeclarationAfterAttributes. Question: which case label dispatches to ParseWhileStatement? (quiz clang-stmt-dispatch)

Backtracking recursive descent¶

Clang clang/include/clang/Parse/Parser.h — class TentativeParsingAction (Commit() / Revert()), backed by Preprocessor::EnableBacktrackAtThisPos in clang/lib/Lex/PPCaching.cpp; clang/lib/Parse/ParseTentative.cpp — Parser::isCXXDeclarationStatement decides declaration vs expression (real-world box in §2) [CLANG-ParseTentative].
GCC gcc/cp/parser.cc — cp_parser_parse_tentatively, cp_parser_parse_definitely and cp_parser_simulate_error [GCC-CPParser].
rustc compiler/rustc_parse/src/parser/diagnostics.rs — create_snapshot_for_diagnostic / restore_snapshot: backtracking used to try recoveries [RUSTC-Parser]. swiftc uses Parser::BacktrackingScope in lib/Parse/ParseStmt.cpp [SWIFT-ParseStmt].

Memoized backtracking¶

CPython Tools/peg_generator/pegen/parser.py — the memoize and memoize_left_rec decorators (v3.13.0) cache (position, rule) results in generated Python parsers; the C generator memoizes only (memo) rules (real-world box in §2) [CPY-pegen].
Clang memoizes the expensive part of tentative parsing by annotating the token stream: clang/lib/Parse/Parser.cpp — Parser::TryAnnotateTypeOrScopeToken replaces a qualified name with a single annotation token, so a revert and re-parse does not look the name up again [CLANG-Parser, CLANG-Internals].

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Table-driven predictive parsing	Exactly the LL(1) grammars	Θ(n) · one table lookup per step (17 steps for 5 tokens)	Correct-prefix error detection; generic "expected one of" messages	Low driver (~50 lines), needs a generator	Generated LL parsers (CPython ≤ 3.8), teaching
Hand-written predictive recursive descent	LL(1) plus any hand-coded lookahead or predicates	Θ(n) · fastest in practice	Best: each function can give context-specific messages and recovery	High to write and maintain, full control	Clang, GCC, rustc, swiftc, Go, V8, `pebblec`
Backtracking recursive descent	Every non-left-recursive CFG, ambiguous included	Exponential: 24 573 calls at depth 12	Poor: the failure is wherever the last attempt died	Low	Prototypes; bounded tentative parsing in C++ front ends
Memoized backtracking	Same as backtracking	O(\|N\|·\|G\|·n³); 26 calls at depth 12	Same as backtracking	Low + a table	Packrat/PEG parsers (CPython pegen, Ch 4)

Choose the table-driven parser when a generator produces the table and you want small, uniform code. Choose hand-written recursive descent when you build a production compiler: the grammar is LL(1) nearly everywhere, and the few hard spots get hand-coded lookahead. Choose backtracking only locally (a few decision points, bounded depth); add memoization when backtracking is global or inputs nest deeply, and check that parsing has no side effects first.

Reproduce the lab numbers: build/<preset>/bin/ll1 backtrack --max-depth 12 and ll1 rd <tokens>; the tests are ch02.RDCompare.* and ch02.Backtracking.*.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch02.yaml`)	Drill	Flashcard tag	Exercises
Table-driven predictive	`predict-derivation`, `predictive-error-position`	`./course drill predict-trace`	`table-driven`	E5
Hand-written predictive RD	`predict-derivation`, `predictive-error-position`, `clang-stmt-dispatch`	`./course drill predict-trace --difficulty medium` (same decisions)	`recursive-descent`	L1, L2
Backtracking RD	`backtrack-calls`, `ordered-choice`	— see note	`backtracking`	L3
Memoized backtracking	`backtrack-calls`, `ordered-choice`	— see note	`memoization`	L4

Backtracking and memoization have no drill: their traces are long, mechanical and fully determined by the lab's call counter; the lab (L3, L4) plus the counting quiz questions exercise the one idea (repeated sub-parses vs one per (nonterminal, position)), and Proposition 2.5.14 gives the closed form to check against.

Left recursion overflows the stack, silently

A recursive-descent parser for a left-recursive rule does not fail with a syntax error; it overflows the stack (parseE calls parseE without consuming a token). Remove the left recursion first (Lesson 2.4), or write the rule as a loop.

References¶

See the chapter references.

Technique	Time (worst)	Time (typical)	Space	Variables
Table-driven predictive	\(\Theta(n)\) moves for a fixed grammar; the constant can be exponential in \(\lvert N \rvert\) (Proposition 2.5.15)	17 steps for 5 tokens; one table lookup per step	\(O(n)\) stack; table \(O(\lvert N \rvert \cdot \lvert T \rvert)\)	as above
Hand-written predictive RD	\(\Theta(n)\) calls	fastest in practice: direct calls and `switch`, no table	\(O(n)\) call stack	as above
Backtracking RD (full)	exponential: \(3 \cdot 2^{d+1} - 3\) calls on \(d\) nested parentheses	fine on inputs that rarely backtrack	\(O(n)\) stack plus position sets \(O(n)\)	\(d\)
Memoized backtracking	\(O(\lvert N \rvert (n+1))\) calls, each \(O(\lvert G \rvert \cdot n^{2})\) set work: \(O(\lvert N \rvert \cdot \lvert G \rvert \cdot n^{3})\)	\(2d + 2\) calls on the example	\(O(\lvert N \rvert \cdot n^{2})\) (a position set per entry)	as above

Lesson 2.5 — Predictive and backtracking recursive descent¶

1. Problem and motivation¶

Table-driven predictive parsing¶

Hand-written predictive recursive descent¶

Backtracking recursive descent¶

Memoized backtracking¶

2. Definitions and algorithms¶

Table-driven predictive parsing¶

Hand-written predictive recursive descent¶

Backtracking recursive descent¶

Memoized backtracking¶

3. Worked example¶

Table-driven predictive parsing on the running example¶

Hand-written predictive recursive descent on the running example¶

Backtracking recursive descent on the running example¶

Memoized backtracking on the running example¶

4. Invariants and correctness¶

Table-driven predictive parsing¶

Hand-written predictive recursive descent¶

Backtracking recursive descent¶

Memoized backtracking¶

5. Complexity¶

6. Variants and refinements¶

Table-driven predictive parsing¶

Hand-written predictive recursive descent¶

Backtracking recursive descent¶

Memoized backtracking¶

7. In real compilers¶

Table-driven predictive parsing¶

Hand-written predictive recursive descent¶

Backtracking recursive descent¶

Memoized backtracking¶

8. Comparison¶

9. Assessment¶

References¶