5.5 Parser Error Recovery

Real source files are edited, incomplete, and sometimes deeply broken. A parser that stops at the first unexpected token is easy to implement but poor at serving an editor, a batch compiler, or a learner. A parser that guesses freely may continue but invent a misleading program. Error recovery is the disciplined middle ground: detect the earliest reliable failure, report it with context, make bounded progress to a safe point, and preserve enough structure for later diagnostics without pretending the program is correct.

Recovery is not an afterthought. It shapes token APIs, AST types, parser control flow, testing, and the trust users place in compiler messages.

Detect Errors Where Expectations Are Sharpest

The best parsing error occurs close to the violated grammar obligation:

let total = 1 + ;
                ^ expected expression after '+'

This is better than a later generic message such as “unexpected }.” The parser knows what it was doing: it had consumed + and was about to parse an expression. Capture that context in expect and in expression parselets.

A high-quality diagnostic normally includes:

• A primary source range, preferably the unexpected token or the missing-token insertion point.

• What was expected, in language terms rather than internal nonterminal names.

• What was found, when it helps.

• A small local fix or note when confidence is high.

Record errors in a list rather than throwing away all state after the first one. But cap the number of diagnostics, and guard every recovery loop against zero token consumption. An error handler that repeatedly “recovers” at the same cursor is an infinite loop with a nice name.

Synchronize at Grammar Boundaries

Panic-mode recovery discards tokens until it reaches a synchronization token that plausibly ends the broken construct or begins a new one. It is simple and reliable when chosen with grammar awareness.

For a statement-oriented language, a synchronizer might consume at least one token, then scan for ;, }, EOF, or a token that starts a new statement such as let, if, while, or print:

synchronizeStatement() {
  advance(); // guarantee progress after the failing token
  while (!at(EOF)) {
    if (previous().kind == SEMICOLON) return;
    if (at(RBRACE) || startsStatement(peek().kind)) return;
    advance();
  }
}

The function is intentionally context-dependent. Synchronizing an expression at , or ) makes sense inside a call; throwing away tokens until ; may destroy the remaining arguments and produce a noisy cascade. FIRST and FOLLOW sets offer principled candidates: a token in FOLLOW of the failed nonterminal may be a place to return control, while a token in FIRST of an enclosing sibling may begin a fresh construct.

Panic mode should not be the only tool. Phrase-level recovery can make a local, explicit repair: insert a missing ; before } without consuming the brace, or delete a single stray , when the surrounding grammar makes the intent nearly certain. Keep these repairs narrow, track them in the diagnostic, and never turn them into invisible semantic changes.

Preserve a Useful Partial Tree

Later frontend stages need to know that an error already occurred. A parser may return an ErrorExpr, ErrorStmt, or missing-token node carrying a source range and recovery details. This lets the parser continue to construct an enclosing block or declaration while preventing the type checker from emitting nonsense based on a fabricated expression.

let x = 1 + ;
print x;

Block([
  LetStmt(x, Binary(Number(1), +, ErrorExpr(at:semicolon))),
  PrintStmt(Name(x))
])

The goal is not a perfect tree. The goal is a stable enough partial tree for tooling, while diagnostics remain anchored to the original syntax mistake. Downstream passes should recognize error nodes and avoid cascading “unknown type” or “undefined variable” messages that add no new action for the user.

Test recovery with hostile inputs: missing delimiters, repeated operators, nested mistakes, EOF in the middle of a construct, and a valid declaration after each error. Assert both the diagnostic locations and that the parser makes progress. Recovery quality is observable behavior; a compiler's test suite should treat it that way.

Recovery Must Preserve the Next Useful Boundary

For let x = 1 + ; print x;, report the missing expression after +, then synchronize at ; so print x; can still be parsed. In contrast, inside f(1, , 3), skipping to ; would destroy useful call context; , or ) is a better expression-level boundary. Recovery tokens are therefore chosen by the current grammar context, not by one global list.

An error node should carry the failure range and allow the enclosing tree to exist, but downstream passes must recognize it and suppress derivative noise. The goal is one actionable message per root mistake, not a perfectly repaired imaginary program.