Lesson 2.7 — Syntax error recovery in top-down parsers¶
Techniques: panic mode with FOLLOW-based synchronizing sets, phrase-level recovery, insertion/deletion repair (local single-token and global minimum-distance) · Pebble implements: panic mode (lab exercise E6) · Lab:
labs/ch02-ll1-toolkit(SPEC, contractparseWithRecovery;ll1 parse --recover) · Prerequisites: Lesson 2.5 · Time: 3–4 hours
A compiler that stops at the first syntax error makes you recompile once per typo. The predictive parser of Lesson 2.5 detects an error at the first token that cannot continue a sentence (Theorem 2.5.9); this lesson is about what it does next: get back into a state from which parsing can continue, report each real error once, and avoid a cascade of spurious ones. The three families trade simplicity (skip tokens until something familiar appears) against precision (guess the edit the programmer forgot).
1. Problem and motivation¶
Input: an LL(1) parser that has just found an error (top of stack \(X\), lookahead \(a\), \(M[X, a]\) empty or \(X \ne a\)). Output: a changed configuration (stack and/or input) from which parsing resumes, plus a diagnostic. Requirements: always terminate, report at least one error per real mistake, and avoid reporting errors the programmer did not make. pebblec uses panic mode in its hand-written parser, like Clang and Go.
Panic mode with FOLLOW-based synchronizing sets¶
Skip input tokens until one appears that the parser can synchronize on, then pop the stack to a state that expects it. Wirth's recursive-descent compilers passed "stop symbol" sets down the calls [Wir76]; for table-driven LL parsers the Dragon book fills the empty cells \(M[A, a]\) with "synch" when \(a \in \mathrm{FOLLOW}(A)\) [ALSU07 §4.4.5]. It is simple, never loops (Theorem 2.7.9), and loses some text after each error.
Phrase-level recovery¶
Fill each empty table entry with a small routine that makes a local correction: insert the missing ), delete the stray ), insert a missing operand. Graham and Rhodes systematized local phrase-level corrections [GR75]; hand-written parsers do the same with messages such as "expected ';'" and a fix-it hint.
Insertion/deletion repair¶
Search for the smallest edit to the token stream that makes the program parse. Irons proposed error-correcting parsing [Iro63]; Aho and Peterson gave a minimum-distance error-correcting parser for any CFG in \(O(n^{3})\) [AP72]; Fischer, Milton and Quiring showed that LL(1) parsers can repair with insertions only for a large class of grammars [FMQ80]; Burke and Fisher combined local and global repair for LL and LR [BF87]. ANTLR 4's default strategy uses the cheapest local version: delete one token or insert one token when that lets parsing continue, otherwise fall back to panic mode [ANTLR4-ErrorStrategy].
2. Definitions and algorithms¶
Configurations and moves are those of Definition 2.5.1; \(M\) is conflict-free.
Definition 2.7.1 (Error configuration, synchronizing set, cascade)
An error configuration is a configuration \((X \gamma, i)\) with lookahead \(a = t_{i+1}\) in which no move of Definition 2.5.1 applies: \(X \in T\) and \(X \ne a\); or \(X \in N\) and \(M[X, a] = \emptyset\); or \(X = \$\) and \(a \ne \$\). A synchronizing set \(\mathrm{SYNC}(A) \subseteq T \cup \{\$\}\) is the set of lookaheads on which recovery pops \(A\); here \(\mathrm{SYNC}(A) = \mathrm{FOLLOW}(A) \cup \{\$\}\). A reported error is a cascade if it is caused by an earlier recovery rather than by a mistake in the input.
Definition 2.7.2 (Edits and repair distance)
An edit inserts one token or deletes one token (a substitution counts as two edits). The repair distance \(d(w)\) of \(w \in T^{*}\) is the minimum number of edits that turn \(w\) into a sentence of \(L(G)\) (finite whenever \(L(G) \neq \emptyset\): delete everything, insert a shortest sentence). For \(X \in N \cup T\) and a span, \(\mathrm{cost}(X, i, j)\) is the minimum number of edits that turn \(t_{i+1} \cdots t_j\) into a string of \(L(X)\).
Distance on the running example
For the expression grammar of §3, \(d(\mathtt{id}\ {+}\ {*}\ \mathtt{id}\ {)}) = 2\): deleting * and ) gives id + id, and no single edit yields a sentence (the input has one surplus ) and a + directly followed by *, two independent defects). \(d(\mathtt{id}\ {)}) = 1\).
Panic mode with FOLLOW-based synchronizing sets¶
Algorithm 2.7.3 (RecoverPanic)
- Input: an error configuration \((X \gamma, i)\) of the driver of Algorithm 2.5.4.
- Output: a new configuration and one recorded error.
- Precondition: \(M\) conflict-free; FOLLOW sets final.
- Postcondition: the new configuration has either a shorter stack or a larger \(i\); nothing was pushed (Lemma 2.7.8).
- Invariant: the driver, with this routine in place of
return error, always reaches \((\$, n)\) (Theorem 2.7.9).
Reference solution: solutions/labs/ch02-ll1-toolkit/src/PredictiveParser.cpp; contract ll1::parseWithRecovery. The driver of Lesson 2.5 calls it instead of returning an error and continues its loop.
function RecoverPanic(stack, i): # called with top X, lookahead a = t(i)
record an error at position i
if X = $: skip every remaining token; return # extra input
if X is a terminal: pop X; return # pretend X was there
if a ∈ FOLLOW(X) or a = $: pop X; return # X derived "nothing"
i ← i + 1 # skip a, keep X
Clang and Go synchronize after an error
Reproduce (run with clang 23.1.2 and gofmt from go 1.24.7; the Go source pointer [GO-Parser] is pinned at go1.23.0, which has the same advance(stmtStart) recovery; any OS):
cat > panic.c <<'EOF'
int f(int a, int b) {
int x = a + ) b * 2;
int y = x * b;
return y + ;
}
EOF
clang -fsyntax-only panic.c
cat > panic.go <<'EOF'
package p
func f(a, b int) int {
x := a + ) b * 2
y := x * b
return y +
}
EOF
gofmt -e panic.go
Output (complete; both commands exit with status 1 or 2):
panic.c:2:15: error: expected expression
2 | int x = a + ) b * 2;
| ^
panic.c:4:14: error: expected expression
4 | return y + ;
| ^
2 errors generated.
panic.go:4:11: expected operand, found ')'
panic.go:6:2: expected ';', found 'return'
panic.go:7:1: expected operand, found '}'
panic.go:7:3: expected ';', found 'EOF'
panic.go:7:3: expected ';', found 'EOF'
panic.go:7:3: expected '}', found 'EOF'
What to notice: two real mistakes. Clang reports exactly two errors: after expected expression it skips ) b * 2 with Parser::SkipUntil(tok::semi, …) [CLANG-Parser], resynchronizes on ; (in FOLLOW of the declaration's initializer) and parses line 3 normally. Go's parseOperand calls (*parser).advance(stmtStart) [GO-Parser], whose synchronizing set is statement keywords (§6), so it skips the correct line 5 entirely and then reports a cascade, expected ';', found 'return'; the three errors at end of file are cascades of the second mistake. Both are Algorithm 2.7.3 with different SYNC sets (Definition 2.7.1).
Phrase-level recovery¶
Algorithm 2.7.4 (RecoverPhrase)
- Input: an error configuration, a table
routine[X, a]of hand-designed corrections (wildcards allowed). - Output: a new configuration (stack and/or input edited) and one recorded error with the routine's message.
- Precondition: each routine inserts a token, deletes the lookahead, or pops; unmatched entries fall back to panic mode.
- Postcondition: at most one insertion per input position before a token is consumed (the guard); termination (Proposition 2.7.10).
- Invariant: if no routine pops, the tokens matched so far, with the inserted ones, form a prefix of a sentence.
Oracle: phrase_level_parse.
function RecoverPhrase(stack, input, i, routine):
record an error at position i with the routine's message
(message, action) ← routine[X, a], or panic mode if there is none
if action = insert t:
if something was already inserted at position i: action ← delete # termination guard
else: insert t into the input before position i; return
if action = delete and a ≠ $: remove t(i) from the input; return
pop X # action = pop, or delete at $
Clang and rustc insert the missing ;
Reproduce (run with clang 23.1.2 and rustc 1.94.1; the rustc source pointer [RUSTC-Parser] is pinned at 1.90.0; any OS):
cat > semi.c <<'EOF'
int g(int a) {
int x = a + 1
return x;
}
EOF
clang -fsyntax-only -fdiagnostics-parseable-fixits semi.c
cat > semi.rs <<'EOF'
pub fn g(a: i32) -> i32 {
let x = a + 1
x
}
EOF
rustc --edition 2021 --crate-type lib --emit=metadata -o /dev/null semi.rs
Output (complete):
semi.c:2:16: error: expected ';' at end of declaration
2 | int x = a + 1
| ^
| ;
fix-it:"semi.c":{2:16-2:16}:";"
1 error generated.
error: expected `;`, found `x`
--> semi.rs:2:18
|
2 | let x = a + 1
| ^ help: add `;` here
3 | x
| - unexpected token
error: aborting due to 1 previous error
What to notice: both front ends run a phrase-level routine for the cell (end of a declaration or let, lookahead return / x): insert ; and continue as if it had been there, so the next line parses without a cascade. The fix-it: line is the machine-readable record of that insertion (an edit of Definition 2.7.2 at line 2, column 16), which IDEs apply with one click; in Clang it comes from Parser::ExpectAndConsume / ExpectAndConsumeSemi [CLANG-Parser], in rustc from expected_one_of_not_found [RUSTC-Parser].
Insertion/deletion repair¶
Algorithm 2.7.5 (RecoverLocal: single-token repair)
- Input: an error configuration with top \(X\), lookahead \(a = t_i\) and next token \(b = t_{i+1}\).
- Output: a new configuration: \(a\) deleted, \(X\) popped as "missing", or a panic-mode step.
- Precondition: \(M\) conflict-free.
- Postcondition: every action consumes an input token or pops a stack symbol (Proposition 2.7.12).
- Invariant: as for panic mode: nothing is pushed.
Oracle: local_repair_parse.
function RecoverLocal(stack, i): # top X, lookahead a = t(i), next b = t(i+1)
record an error
if X is a terminal:
if b = X: delete a; return # single-token deletion
if CanContinue(stack without X, a): pop X; report "missing X"; return # single-token insertion
pop X; return # panic
if X is a nonterminal and M[X, b] has one production: delete a; return
RecoverPanic(stack, i)
function CanContinue(stack, a): # could the parser move on a?
Y ← top(stack)
return (Y = $ and a = $) or (Y is a terminal and Y = a) or (Y ∈ N and |M[Y, a]| = 1)
Algorithm 2.7.6 (MinEditCost: global minimum-distance repair [AP72])
- Input: \(G\) and \(w = t_1 \cdots t_n\).
- Output: \(d(w)\).
- Precondition: \(L(G) \neq \emptyset\).
- Postcondition: returns \(\mathrm{cost}(S, 0, n) = d(w)\) (Theorem 2.7.11).
- Invariant: every table entry is an upper bound on the true cost of its span (an edit sequence of that cost exists), and the entries only decrease.
Oracles: min_edit_cost and the brute-force min_repair.
function MinEditCost(G, t1 … tn):
cost(t, i, j) ← (j − i − 1) if t occurs in t(i+1) … t(j) else (j − i + 1) # keep one, delete the rest
cost(A, i, j) ← ∞ for all A, i ≤ j
repeat # least fixed point: equal spans recurse
for each span length ℓ = 0 … n, each i, j = i + ℓ, each A → Y1 … Yk:
c ← min over split points i = m0 ≤ m1 ≤ … ≤ mk = j of Σr cost(Yr, m(r−1), mr)
(for k = 0, c ← j − i: delete everything)
cost(A, i, j) ← min(cost(A, i, j), c)
until nothing changed
return cost(S, 0, n)
ANTLR 4's single-token deletion and insertion
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
for input in 'a + * b )' '( a + b' 'a b + c'; do
echo "== $input"; echo "$input" > err.txt
java -cp antlr-4.13.2-complete.jar org.antlr.v4.gui.Interpreter ExprLL1.g4 s -tree err.txt
done
Output (complete):
== a + * b )
line 1:4 extraneous input '*' expecting {'(', ID}
line 1:8 extraneous input ')' expecting <EOF>
(s:1 (e:1 (t:1 (f:2 a) t1:2) (e1:1 + (t:1 (f:2 * b) t1:2) e1:2)) ) <EOF>)
== ( a + b
line 2:0 missing ')' at '<EOF>'
(s:1 (e:1 (t:1 (f:1 ( (e:1 (t:1 (f:2 a) t1:2) (e1:1 + (t:1 (f:2 b) t1:2) e1:2)) <missing ')'>) t1:2) e1:2) <EOF>)
== a b + c
line 1:2 mismatched input 'b' expecting {<EOF>, '+', '*'}
(s:1 (e:1 (t:1 (f:2 a) t1:2) e1:2) b + c)
What to notice: the first input is §3's running example (with ID for id): "extraneous input" is a single-token deletion (DefaultErrorStrategy.singleTokenDeletion [ANTLR4-ErrorStrategy]), applied twice, giving the repair "delete *, delete )" of §3, whose length 2 equals \(d(w)\). The second input gets a single-token insertion ("missing ')'", singleTokenInsertion), recorded in the tree as <missing ')'>. The third input needs neither (after a the parser is at the end of e, and neither deleting b nor inserting one token lets it continue), so ANTLR falls back to panic mode: recover consumes tokens until one in the error-recovery set (getErrorRecoverySet, the FOLLOW of the rule invocation stack), here <EOF>.
3. Worked example¶
Running example: the Dragon expression grammar (tests/ch02/Inputs/expr-ll1.grammar) and the input id + * id ): one missing operand and one stray parenthesis. \(\mathrm{FOLLOW}(E) = \mathrm{FOLLOW}(E') = \{), \$\}\), \(\mathrm{FOLLOW}(T) = \mathrm{FOLLOW}(T') = \{+, ), \$\}\), \(\mathrm{FOLLOW}(F) = \{+, *, ), \$\}\).
flowchart LR
err{{"error: top X, lookahead a"}} -->|panic| skip["skip a / pop X"]
err -->|phrase level| fix["routine(X, a): insert, delete or pop"]
err -->|repair| edit["cheapest edit that lets the parser continue"]
skip --> resume([resume the driver])
fix --> resume
edit --> resumePanic mode on the running example¶
Every step (oracle ll1_parse(..., recover=True); the C++ ll1 parse --recover prints the same derivation and errors):
| step | stack | input | action |
|---|---|---|---|
| 1 | $ E | id + * id ) $ | output (1) E → T E' |
| 2 | $ E' T | id + * id ) $ | output (4) T → F T' |
| 3 | $ E' T' F | id + * id ) $ | output (8) F → id |
| 4 | $ E' T' id | id + * id ) $ | match id |
| 5 | $ E' T' | + * id ) $ | output (6) T' → ε |
| 6 | $ E' | + * id ) $ | output (2) E' → + T E' |
| 7 | $ E' T + | + * id ) $ | match + |
| 8 | $ E' T | * id ) $ | **error: M[T, *] is empty; * ∉ FOLLOW(T): skip *** |
| 9 | $ E' T | id ) $ | output (4) T → F T' |
| 10 | $ E' T' F | id ) $ | output (8) F → id |
| 11 | $ E' T' id | id ) $ | match id |
| 12 | $ E' T' | ) $ | output (6) T' → ε |
| 13 | $ E' | ) $ | output (3) E' → ε |
| 14 | $ | ) $ | error: extra input ); skip to $ |
| 15 | $ | $ | stop: $ meets $ after 2 error(s); reject |
Two errors, both real; tokens 3 and 5 skipped. On id * + id the other rule fires: at \(T' \to * F T'\) the parser has \(F\) on top and + as lookahead; \(+ \in \mathrm{FOLLOW}(F)\), so \(F\) is popped ("missing operand") and parsing continues with + id.
Phrase-level recovery on the running example¶
Routines designed for this grammar: on \(E\), \(T\) or \(F\) with an operator, ) or $ ahead: "missing operand", insert id; on \(E'\) or \(T'\) with id or ( ahead: "missing operator", insert +; ) expected at $: "missing )", insert ); $ on top with ) ahead: "unbalanced )", delete it (oracle phrase_level_parse):
| step | stack | input | action |
|---|---|---|---|
| 1 | $ E | id + * id ) $ | output (1) E → T E' |
| 2 | $ E' T | id + * id ) $ | output (4) T → F T' |
| 3 | $ E' T' F | id + * id ) $ | output (8) F → id |
| 4 | $ E' T' id | id + * id ) $ | match id |
| 5 | $ E' T' | + * id ) $ | output (6) T' → ε |
| 6 | $ E' | + * id ) $ | output (2) E' → + T E' |
| 7 | $ E' T + | + * id ) $ | match + |
| 8 | $ E' T | * id ) $ | error (missing operand): insert id |
| 9 | $ E' T | id * id ) $ | output (4) T → F T' |
| 10 | $ E' T' F | id * id ) $ | output (8) F → id |
| 11 | $ E' T' id | id * id ) $ | match id |
| 12 | $ E' T' | * id ) $ | output (5) T' → * F T' |
| 13 | $ E' T' F * | * id ) $ | match * |
| 14 | $ E' T' F | id ) $ | output (8) F → id |
| 15 | $ E' T' id | id ) $ | match id |
| 16 | $ E' T' | ) $ | output (6) T' → ε |
| 17 | $ E' | ) $ | output (3) E' → ε |
| 18 | $ | ) $ | error (unbalanced )): delete ) |
| 19 | $ | $ | stop after 2 error(s) |
The parser effectively parsed id + id * id: the messages say what is wrong ("missing operand" at token 3, "unbalanced )" at token 5), and the corrected program is a sentence. With every error cell covered by an insert/delete routine, the effective input is always a sentence (Proposition 2.7.10; checked on 500 random inputs by test_recovery_strategies_terminate).
Insertion/deletion repair on the running example¶
Local single-token repair (oracle local_repair_parse):
| step | stack | input | action |
|---|---|---|---|
| 1 | $ E | id + * id ) $ | output (1) E → T E' |
| 2 | $ E' T | id + * id ) $ | output (4) T → F T' |
| 3 | $ E' T' F | id + * id ) $ | output (8) F → id |
| 4 | $ E' T' id | id + * id ) $ | match id |
| 5 | $ E' T' | + * id ) $ | output (6) T' → ε |
| 6 | $ E' | + * id ) $ | output (2) E' → + T E' |
| 7 | $ E' T + | + * id ) $ | match + |
| 8 | $ E' T | * id ) $ | **error: M[T, *] empty, M[T, id] is not: delete *** (single-token deletion) |
| 9 | $ E' T | id ) $ | output (4) T → F T' |
| 10 | $ E' T' F | id ) $ | output (8) F → id |
| 11 | $ E' T' id | id ) $ | match id |
| 12 | $ E' T' | ) $ | output (6) T' → ε |
| 13 | $ E' | ) $ | output (3) E' → ε |
| 14 | $ | ) $ | error: extra input; delete ) |
| 15 | $ | $ | stop after 2 error(s) |
The repair is "delete *, delete )", giving id + id, the same two deletions ANTLR makes (real-world box in §2). The global minimum-distance computation confirms that two edits are necessary: MinEditCost returns 2, and a breadth-first search over all inputs 0, 1 and 2 edits away finds its first sentence at distance 2.
MinEditCost in full on a smaller input, id ) (positions 0–2). One row per span; the entries are \(\mathrm{cost}(A, \text{span})\) after the fixed point, reached in 4 relaxation passes (the last one changes nothing):
| span | tokens | E | E′ | T | T′ | F |
|---|---|---|---|---|---|---|
| 0..0, 1..1, 2..2 | ε | 1 | 0 | 1 | 0 | 1 |
| 0..1 | id | 0 | 1 | 0 | 1 | 0 |
| 1..2 | ) | 2 | 1 | 2 | 1 | 2 |
| 0..2 | id ) | 1 | 2 | 1 | 2 | 1 |
\(E\) over the empty span costs 1 (insert id); \(E\) over id ) costs 1: keep id for \(T\) and let \(E' \to \varepsilon\) delete ). So \(d(\mathtt{id}\ {)}) = 1\).
Try it
./course drill predict-trace --seed 9 --difficulty hard gives an erroneous input: trace panic mode (skipped tokens, popped symbols) and compute the repair distance.
4. Invariants and correctness¶
Panic mode with FOLLOW-based synchronizing sets¶
Lemma 2.7.7 (Immediate error detection of LL(1) tables)
Let \(M\) be the conflict-free table of an LL(1) grammar. If a symbol \(Y\) is pushed by an expansion while the lookahead is \(a\), then \(Y\) is never the top of an error configuration while the lookahead is still \(a\).
Proof
Let the expansion be \(X \to Y_1 \cdots Y_k\) at lookahead \(a\), so \(a \in \mathrm{PREDICT}(X \to Y_1 \cdots Y_k)\), and suppose \(Y_j\) becomes the top while the lookahead is still \(a\). By induction on the number of pushes, \(Y_1, \dots, Y_{j-1}\) were removed without an error and without consuming input, so each derived \(\varepsilon\) by expansions at lookahead \(a\); in particular each is nullable. Moreover no \(Y_l\) (\(l < j\)) has \(a \in \mathrm{FIRST}(Y_l)\): if it had, the unique production of \(M[Y_l, a]\) would have \(a\) in its FIRST set (a nullable alternative is only there via FOLLOW, and two alternatives cannot share the cell), and by the same argument down the tree \(a\) would eventually be matched, i.e. consumed. Hence \(a \in \mathrm{PREDICT}(X \to Y_1 \cdots Y_k)\) gives either \(a \in \mathrm{FIRST}(Y_j \cdots Y_k)\), or \(Y_j \cdots Y_k\) nullable and \(a \in \mathrm{FOLLOW}(X) \subseteq \mathrm{FOLLOW}(Y_j)\). In the first case, \(a \in \mathrm{FIRST}(Y_j)\) (so \(M[Y_j, a] \ne \emptyset\), or \(Y_j = a\) if it is a terminal), or \(Y_j\) is nullable and \(a \in \mathrm{FIRST}(Y_{j+1} \cdots) \subseteq \mathrm{FOLLOW}(Y_j)\), so \(Y_j\)'s nullable alternative is in \(M[Y_j, a]\). In the second case, likewise. In every case \(Y_j\) is not in an error configuration.
Lemma 2.7.8 (Recovery never pushes)
Every action of Algorithm 2.7.3 either consumes an input token or pops a stack symbol, and none pushes.
Proof
By inspection of the four branches: skipping the rest of the input and skipping \(a\) consume tokens; the other two branches pop \(X\).
Theorem 2.7.9 (Panic mode terminates and reports the true first error)
For an LL(1) grammar, the driver of Algorithm 2.5.4 with Algorithm 2.7.3 terminates on every input in \(O(n)\) moves (for a fixed grammar), and its first reported error is the error of the plain parser, which satisfies the correct-prefix property.
Proof
First error: until the first error the two parsers perform the same moves, so the first error is the plain parser's, and Theorem 2.5.9 gives the correct-prefix property. Termination and \(O(n)\): reuse the burst counting of Proposition 2.5.15. By Lemma 2.7.7 an error never happens on a symbol pushed at the current lookahead, so every error is on an old symbol that is on top before any expansion of it (a burst that ends in an error made no expansion), and recovery pushes nothing (Lemma 2.7.8). Each recovery action either skips input (at most \(n + 1\) times) or removes an old symbol; as in Proposition 2.5.15, old symbols are the start symbol and those left by the at most \(n\) bursts that end in a match, so there are at most \(1 + n\, r\, c_G\) removals of old symbols in total, by bursts or by recovery. A burst starts at a new lookahead or after such a removal, so there are at most \(2 + 2n + n\, r\, c_G\) bursts, each with at most \(c_G\) expansions. Adding the \(n\) matches and the recovery actions gives \(O(n)\) moves for a fixed grammar.
Why FOLLOW: popping \(A\) when \(a \in \mathrm{FOLLOW}(A)\) models "the programmer left out the text that \(A\) derives", after which \(a\) can legally appear. When it breaks: later errors can be cascades (popping the wrong \(A\)), and a synchronizing token inside a nested construct (a ) that belongs to an outer expression) can make the parser skip a lot; Go's keyword-based SYNC skips a correct statement in the real-world box of §2. Real parsers suppress reports until a few tokens have been matched after a recovery (§6).
Phrase-level recovery¶
Proposition 2.7.10 (Phrase-level recovery terminates; with insert/delete routines it repairs)
With the insertion guard, the driver with Algorithm 2.7.4 terminates on every input. If every routine inserts or deletes (never pops), the tokens matched by the parser form a sentence of \(L(G)\) and the number of errors is an upper bound on \(d(w)\).
Proof
Termination: deletions consume input; pops shrink the stack and push nothing; an insertion at position \(i\) is followed either by progress (the inserted token is matched) or, at the same position, by a forced deletion (the guard), which consumes \(t_{i+1}\). So at each position there is at most one insertion, and between edits the argument of Theorem 2.7.9 bounds the moves. Repair: if there are no pops, every move after an edit is a move of the plain parser on the edited input, and the parse ends in \((\$, n)\) with accept: by Theorem 2.5.9 the edited input, which is exactly the matched tokens, is a sentence. Each error performed one edit, so \(d(w) \le\) the number of errors.
When it breaks: routines that insert a token which cannot be matched next loop forever without the guard; routines are grammar-specific and must be revised whenever the grammar changes.
Insertion/deletion repair¶
Theorem 2.7.11 (MinEditCost computes the repair distance)
Algorithm 2.7.6 terminates and \(\mathrm{cost}(S, 0, n) = d(w)\).
Proof sketch (full proof: [AP72])
Characterization: an edited string derived from \(A\) comes from a production \(A \to Y_1 \cdots Y_k\) and a split of the original span among \(Y_1, \dots, Y_k\) (every original token that survives lies in exactly one part; deleted tokens can be charged to the part they fall in; inserted tokens are charged to the symbol that derives them), and the parts are edited independently. So \(\mathrm{cost}(A, i, j)\) is the minimum over productions and splits of the sum of the parts' costs, and for a terminal \(t\) it is "keep one occurrence of \(t\) and delete the rest" or "delete all and insert \(t\)". These min-plus equations have equal-span dependencies (a nullable symbol takes an empty part), so their solution is the greatest fixed point below \(\infty\) reached by relaxation from \(\infty\), which is the least in the reversed order. Termination: costs are non-negative integers bounded by \(n + \min_w \lvert w \rvert\) once finite, and every pass except the last lowers some entry. The implementation agrees with the brute-force search on 120 random inputs (test_edit_distance_dp_matches_search).
Proposition 2.7.12 (Local repair terminates)
The driver with Algorithm 2.7.5 terminates on every input.
Proof
Every branch consumes a token (a deletion, or panic's skip), pops the terminal \(X\) (single-token insertion and the terminal fallback), or runs panic mode; none pushes. The argument of Theorem 2.7.9 applies unchanged.
When it breaks: the minimum edit is not always the intended edit (the programmer may have meant id + id * id, which is also two edits away).
5. Complexity¶
Variables: \(n\) tokens, \(\lvert G \rvert\) grammar size, \(\lvert P \rvert\) productions, \(r\) longest right side, \(e\) number of errors.
| Technique | Time (worst) | Time (typical) | Space | Variables |
|---|---|---|---|---|
| Panic mode | \(O(n)\) extra over the parse | negligible | none | — |
| Phrase-level | \(O(1)\) per error plus the routine | negligible | a routine table \(O(\lvert N \rvert \cdot \lvert T \rvert)\) | — |
| Insertion/deletion repair | local: \(O(1)\) table probes per error; global DP: \(O(\lvert P \rvert \cdot r \cdot n^{3})\) per pass, \(O(n)\) passes | local: negligible; global: fine for statements, not whole files | global: \(O(\lvert N \rvert \cdot n^{2})\) | as above |
Proposition 2.7.13 (Cost of recovery)
(a) Panic mode adds at most \(n\) skips and at most (number of pushes) pops to a parse. (b) One relaxation pass of Algorithm 2.7.6 costs \(O(\lvert P \rvert \cdot r \cdot n^{3})\) with the split minimum computed symbol by symbol, and \(O(n)\) passes suffice.
Proof
(a) Each skip consumes one of the \(n\) tokens; each pop removes a symbol that some expansion pushed. (b) As in Proposition 2.1.15, the minimum over split points is computed incrementally over the right side (a prefix table per production suffix and span), costing \(O(n)\) per (production position, span) pair: \(O(\lvert G \rvert \cdot n^{2} \cdot n)\). Within a pass, spans are processed shortest first, so only equal-span dependencies (through nullable symbols) need repeated passes; each such chain has length at most \(\lvert N \rvert\) per span, and costs decrease by integers bounded by \(O(n)\).
Pathological input: for panic mode, a missing ( early in a long expression: every later ) is "extra input" at the outermost level, so panic mode skips to the end and reports errors the programmer did not make. For global repair, the cost grows as \(n^{3}\): minimum-distance repair of a whole file is impractical, which is why Burke and Fisher repair within a bounded window around the error [BF87].
At scale: Go's parser bounds the damage of cascades explicitly: (*parser).advance in src/go/parser/parser.go (Go 1.23) [GO-Parser] returns at a synchronization token only if the parser made progress since the last sync, or at most 10 times without progress, "to avoid an endless parser loop".
6. Variants and refinements¶
Panic mode with FOLLOW-based synchronizing sets¶
- FIRST-based and keyword sync sets (Go's
stmtStart, statement keywords): synchronize on tokens that start a construct rather than follow it — trade-off: resynchronizes at the next statement, loses the rest of the current one, and can skip a correct statement (real-world box in §2). - Error-count suppression (report a new error only after \(k\) tokens were matched): removes most cascades — trade-off: a genuine second error close to the first is not reported.
Phrase-level recovery¶
- Error productions [ALSU07 §4.1.4]: add rules such as
Stmt → Expr error ;that match common mistakes — trade-off: precise messages for known mistakes, but they enlarge the grammar and can introduce conflicts. - Fix-it hints (Clang, rustc; real-world box in §2): the routine records the edit so an IDE can apply it — trade-off: must be right, or it misleads.
Insertion/deletion repair¶
- Insertion-only LL(1) repair [FMQ80]: precompute the cheapest insertion string for every (stack symbol, lookahead) pair — trade-off: linear-time and always succeeds on "insert-correctable" grammars, but cannot delete stray tokens.
- Bounded-window global repair [BF87]: try all edits in a window of a few tokens around the error, pick the one that lets the parser go furthest — trade-off: much better repairs than single-token ones, at a bounded cost.
7. In real compilers¶
Panic mode with FOLLOW-based synchronizing sets¶
- Clang (LLVM 23.1.2)
clang/lib/Parse/Parser.cpp—Parser::SkipUntil, with flagsStopAtSemiandStopBeforeMatchdeclared inclang/include/clang/Parse/Parser.h: skip tokens until a synchronizing token, balancing(),[]and{}while skipping;BalancedDelimiterTrackerinclang/include/clang/Parse/RAIIObjectsForParser.hkeeps the delimiter counts [CLANG-Parser] (real-world box in §2). - GCC
gcc/c/c-parser.cc—c_parser_skip_until_found;gcc/cp/parser.cc—cp_parser_skip_to_end_of_statement(GCC 15) [GCC-CParser, GCC-CPParser]. - rustc
compiler/rustc_parse/src/parser/diagnostics.rs—Parser::recover_stmtandrecover_stmt_(Rust 1.90.0) skip to the end of the statement or block [RUSTC-Parser]. Gosrc/go/parser/parser.go—(*parser).advance(stmtStart)[GO-Parser].
Find where LLVM does it. Open clang/include/clang/Parse/Parser.h (LLVM 23.1.2) and read enum SkipUntilFlags. Question: which flag makes SkipUntil also stop at a ;? (quiz clang-skipuntil)
Phrase-level recovery¶
- Clang
clang/lib/Parse/Parser.cpp—Parser::ExpectAndConsumeandParser::ExpectAndConsumeSemi: when the expected token is missing, report "expected ';'" with a fix-it that inserts it, and continue as if it had been there (a phrase-level insertion; real-world box in §2) [CLANG-Parser]. - swift-syntax
Sources/SwiftParser/Recovery.swift—canRecoverToandRecoveryConsumptionHandle(601.0.1): recovery decides how many unexpected tokens to consume, based on token precedence, and stores them in the tree as "unexpected" nodes [SWIFTSYNTAX-Recovery]. - rustc
diagnostics.rs—expected_one_of_not_foundbuilds "expected one of … found …" messages with suggestions [RUSTC-Parser].
Insertion/deletion repair¶
- ANTLR 4
runtime/Java/src/org/antlr/v4/runtime/DefaultErrorStrategy.java(4.13.2):recoverInlinetriessingleTokenDeletionthensingleTokenInsertion;syncandrecoverfall back toconsumeUntil(getErrorRecoverySet())(panic mode with a context-based FOLLOW set) [ANTLR4-ErrorStrategy] (real-world box in §2). - Global minimum-distance repair is not used in production compilers (cubic cost); bounded-window variants [BF87] appear in research LR tools and in Menhir-style generated error messages (Ch 3).
8. Comparison¶
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Panic mode (FOLLOW sync) | Always terminates; may skip large parts of the input | O(n) extra · negligible | Correct first error; later ones may be cascades | Low: a FOLLOW test and a skip loop | Clang SkipUntil, GCC, rustc, Go, pebblec |
| Phrase-level recovery | Local, grammar-specific corrections; complete if every error cell has a routine | O(1) per error | Precise messages and fix-its when routines are well designed | High: one routine per error entry, maintained with the grammar | Hand-written parsers' "expected ';'" (Clang ExpectAndConsumeSemi), swift-syntax |
| Insertion/deletion repair | Local: one-token edits; global: the true minimum distance | Local O(1) per error · global O(|P|·r·n³) per pass | Best messages ("insert ')'"), but the minimum edit may not be the intended one | Medium (local) to high (global) | ANTLR 4 DefaultErrorStrategy; research tools; bounded windows |
Choose panic mode when you need a robust default that cannot loop (Theorem 2.7.9): every production parser has it underneath. Choose phrase-level routines when you know the common mistakes of your users (missing ;, missing )) and want fix-its. Choose single-token repair when you want good messages for the most frequent one-token typos at no cost; choose global or windowed repair only for tools that must produce a best-effort tree (IDEs, formatters) and can afford the search.
9. Assessment¶
| Technique | Quiz ids (solutions/quizzes/ch02.yaml) |
Drill | Flashcard tag | Exercises |
|---|---|---|---|---|
| Panic mode | panic-mode-trace, clang-skipuntil |
./course drill predict-trace --difficulty hard |
panic-mode |
E6 |
| Phrase-level recovery | phrase-level-effective, repair-distance |
— see note | phrase-level |
— (oracle phrase_level_parse) |
| Insertion/deletion repair | repair-distance, phrase-level-effective |
./course drill predict-trace --difficulty hard (asks the repair distance) |
repair |
— (oracle local_repair_parse, min_edit_cost) |
Phrase-level recovery has no drill: its routines are designed by hand for one grammar, so there is no single right answer to generate and grade; the quiz asks about its termination guard and guarantees (Proposition 2.7.10) instead.
Recovery must never push
Popping a nonterminal on a FOLLOW token is not always progress: if the parser pops \(A\), the same token is an error again for the next stack symbol, and a careless implementation that pushes anything during recovery (for example "expand \(A\) with its first production") can loop forever. Recovery actions must only pop or consume (Lemma 2.7.8).
References¶
See the chapter references.