Error Recovery and Parser Generators

Every parser we have built so far shares an unspoken assumption: that the input is correct. Real programs are not. A working day at the keyboard is a stream of missing semicolons, unbalanced brackets, and typos, and the first tool to meet them is the parser. What it does next decides whether a programmer sees one clear message pointing at one real mistake, or a wall of forty confused complaints that bury the truth. Good error recovery is not a footnote to parsing — for the humans who use your compiler, it may be the single most visible thing it does.

A parser reports a syntax error the instant the input token cannot legally continue the current derivation — in a recursive-descent parser at an expect that fails, in an LR parser at a blank ACTION cell. Detecting the error is easy. The hard, interesting question is what to do after: how to dust yourself off and keep parsing so the next genuine error can also be found in the same run.

Four families of recovery strategy

There is a spectrum, from cheap-and-crude to expensive-and-optimal:

StrategyWhat it doesCost / trade-off
Panic-mode on error, skip input tokens until a chosen synchronizing token (e.g. ;, }, end), then resume trivial to implement, never loops; may skip a large chunk and miss errors inside it
Phrase-level locally patch the input — insert a missing token, delete an extra one, or swap two — to limp past the error gives targeted "did you forget a ;?" messages; risks bad guesses and, if it inserts without consuming, infinite loops
Error productions bake common mistakes into the grammar as extra rules that match the bad construct and emit a tailored diagnostic excellent messages for anticipated errors; only catches mistakes you foresaw
Global / minimum-distance correction find the smallest set of insertions/deletions/changes that turns the whole input into a legal program theoretically optimal, great for research; too slow and too surprising for production use

Real compilers blend these. A C or Java front end typically runs panic-mode at statement and block boundaries for robustness, sprinkles phrase-level repairs for the very common slips (a missing semicolon or closing paren), and adds a few error productions for notorious traps ("= used where == was meant"). Minimum-distance correction is mostly a beautiful idea that stays in the textbook.

How yacc's error token works

LR parser generators expose recovery through a special terminal named error. You write it into your grammar at the granularity where you want to re-synchronise, for example:

stmt : expr ';' | error ';' /* on any error, skip to the next ';' and recover here */ ;

When the parser hits an error, it does something very LR-flavoured: it pops states off the stack until it finds one whose ACTION table can legally shift the error token, it shifts error there, and then it discards input tokens until it finds one it can shift in the new configuration (here, a ;). In effect it is panic-mode, but with the synchronising points chosen declaratively by where you placed error in the grammar. To stop a flood of repeats, yacc stays quiet about further errors until it has successfully shifted three real tokens — a simple, effective throttle on cascades.

Panic-mode recovery, in code

Here is a small hand-written parser for a list of assignment statements (\textit{stmt} \to \texttt{id}\ \texttt{=}\ \textit{expr}\ \texttt{;}). On a syntax error it records a message and then synchronises by skipping to just past the next ; — the classic panic-mode move. Watch it survive two separate errors and still parse the good statements around them.

type Tok = { kind: string; text: string; at: number }; function lex(src: string): Tok[] { const toks: Tok[] = []; src.trim().split(/\s+/).forEach((w, i) => { let kind = w; if (/^[0-9]+$/.test(w)) kind = "num"; else if (/^[a-z]+$/.test(w)) kind = "id"; // '=', '+', ';' keep their own text as kind toks.push({ kind, text: w, at: i }); }); toks.push({ kind: "eof", text: "<eof>", at: toks.length }); return toks; } class ParseError extends Error {} class Parser { private toks: Tok[]; private pos = 0; errors: string[] = []; ok = 0; // successfully parsed statements constructor(toks: Tok[]) { this.toks = toks; } private peek(): Tok { return this.toks[this.pos]; } private atEnd(): boolean { return this.peek().kind === "eof"; } private expect(kind: string): Tok { if (this.peek().kind !== kind) throw new ParseError(`token ${this.peek().at}: expected '${kind}' but found '${this.peek().text}'`); return this.toks[this.pos++]; } // Panic-mode: discard tokens up to and including the next ';'. private synchronize(): void { while (!this.atEnd() && this.peek().kind !== ";") this.pos++; if (this.peek().kind === ";") this.pos++; } parse(): void { while (!this.atEnd()) { try { this.stmt(); this.ok++; } catch (e) { if (e instanceof ParseError) { this.errors.push(e.message); this.synchronize(); } else throw e; } } } // stmt -> id '=' expr ';' private stmt(): void { this.expect("id"); this.expect("="); this.expr(); this.expect(";"); } // expr -> term ('+' term)* private expr(): void { this.term(); while (this.peek().kind === "+") { this.pos++; this.term(); } } // term -> num | id private term(): void { const k = this.peek().kind; if (k === "num" || k === "id") { this.pos++; return; } throw new ParseError(`token ${this.peek().at}: expected a number or identifier but found '${this.peek().text}'`); } } const src = "a = 1 + 2 ; b = ; c = 3 3 ; d = 4 ;"; const p = new Parser(lex(src)); p.parse(); console.log(`input: ${src}`); console.log(`parsed OK: ${p.ok} statements`); console.log(`errors found: ${p.errors.length}`); for (const e of p.errors) console.log(" - " + e);

Two independent mistakes — an empty right-hand side in b = ; and a stray extra number in c = 3 3 ; — are both reported in a single run, while a and d parse cleanly. Without recovery the parser would have died at the first error and never seen the second. That is the entire point: keep going, to find more real errors.

Parser generators: pick your class

You rarely write LR tables by hand. A parser generator takes a grammar and emits the parser — and each tool commits to a particular grammar class, which is really a statement about how much of the ambiguity and lookahead problem it is willing to solve for you.

ToolMethod / classCharacter
yacc / bisonbottom-up, LALR(1) (bison also does GLR / IELR)the classic; compact tables, the error token for recovery
ANTLRtop-down, LL(*) / adaptive-LL (ALL(*))readable generated code, arbitrary lookahead, great tooling and error messages
tree-sitterGLR (generalised LR)handles ambiguity and, crucially, incremental & error-tolerant parsing for editors
PEG tools (e.g. pegjs, pest)parsing expression grammars, packratordered choice, no ambiguity by construction, linear time with memoisation

The pattern to notice: bottom-up LR tools (yacc, bison, tree-sitter) accept a wider class of grammars and shine on established languages; top-down LL tools (ANTLR, PEG) generate code that reads like the hand-written recursive-descent parsers of page one, which many teams prefer for readability and error messages. GLR tools sit above the whole hierarchy: by forking the parse on conflicts and pruning dead branches, they accept any context-free grammar, at some runtime cost — which is exactly why an editor like a modern IDE, needing to parse half-typed, broken code on every keystroke, reaches for tree-sitter.

Because the theory was never the bottleneck — effort was. The parsing algorithms behind Elm and Rust are the same LR/recursive-descent ideas everyone uses; what changed is that their teams treated the error message as a designed product feature, not an afterthought. Elm's compiler, whose author literally launched a "compiler errors for humans" initiative, prints the offending source line with a caret under the exact span, names what it expected in plain English, and often suggests the fix ("Maybe you want :: instead of :?"). Rust's rustc does the same at scale: coloured multi-line spans, notes, help text, and machine-applicable suggestions that cargo fix can apply automatically. None of this needs a fancier parsing algorithm — it needs the parser to preserve source spans, recover gracefully so it can report several errors at once, and carry enough context to phrase a human sentence. The lesson for a compiler writer: the distance between "syntax error" and a message a beginner actually understands is engineering care, not a theorem.

The great hazard of error recovery is the cascade: one real mistake throws the parser out of sync, and every subsequent token looks wrong, so it spews a dozen fake errors that all trace back to a single missing brace. Beginners see the flood, panic, and start "fixing" errors that do not exist. The recovery machinery exists precisely to prevent this — but it can also cause it if tuned badly (synchronise too eagerly and you skip real errors; too timidly and you cascade).

Two guards keep cascades in check. First, suppress secondary messages until the parser has re-established solid footing — yacc's "shift three good tokens before complaining again" is the canonical version. Second, choose synchronising tokens that are strong statement or block delimiters (;, }, end) so that recovery lands cleanly at a fresh construct rather than mid-expression. Keep this north star in view: the aim of recovery is not to fix the program and it is not to keep the error count high — it is to keep parsing far enough, and quietly enough, to surface the other genuine errors in one pass, without drowning them in noise.