Error Recovery in Recursive Descent Parsers

A parser that stops at the first syntax error is easy to write and unpleasant to use. A misplaced brace early in a file makes every later declaration appear wrong, and a single diagnostic that names the first offending token forces the programmer to recompile once per error. Recovery exists to convert one fatal error into several local ones, each reported near its cause.

The mechanism is not complicated. The difficulty is that every recovery decision trades the accuracy of a diagnostic against the risk of inventing errors that the source does not contain.

Detection is the easy half

Recursive descent detects an error at the point where the current token is not in the expected set. That set is already computed for the parser’s decisions: the FIRST sets of the alternatives, plus the FOLLOW set when an optional construct may be skipped. The parser knows exactly which tokens would have allowed it to continue, so the message can list them.

The hard question is what to do next. Three families of answers exist: delete tokens until something acceptable appears, insert a token that would have made the parse continue, or abandon the current construct and resume at a token that can start a new one.

Deletion and insertion are called local repair. Abandonment is called panic mode. Most hand-written parsers use panic mode for statements and declarations, and reserve a small amount of local repair for list separators and closing delimiters, where the repair is unambiguous.

Panic mode with synchronisation sets

The parser maintains, for each construct it can parse, a set of tokens that can begin the next construct. On error it discards tokens until the current token is in that set, then returns a placeholder node so the caller can continue as though the construct had been parsed.

SYNC_STMT = {"SEMI", "RBRACE", "IF", "WHILE", "RETURN", "LET", "EOF"}

def parse_block(p):
    p.expect("LBRACE")
    stmts = []
    while p.peek().kind not in ("RBRACE", "EOF"):
        before = p.pos
        try:
            stmts.append(parse_statement(p))
        except ParseError as e:
            p.report(e)
            # Discard until something can start or end a statement.
            while p.peek().kind not in SYNC_STMT:
                p.advance()
            if p.peek().kind == "SEMI":
                p.advance()          # consume the terminator, keep going
        if p.pos == before:         # no progress: force one token
            p.advance()
    p.expect("RBRACE")
    return Block(stmts)

Two details in that loop carry most of the weight. The first is the progress check: if recovery consumes nothing, the loop would spin forever on the same token, so the parser forces one token forward. Without it, a synchronisation set that does not contain the current token turns into an infinite loop rather than a diagnostic.

The second is that EOF is in the synchronisation set. A missing closing brace near the end of a file otherwise causes the parser to consume the entire remainder looking for a brace that is not there, and to report nothing useful about where the block actually ended.

Why the synchronisation set is not the FOLLOW set

The FOLLOW set from the grammar is the theoretically correct set of tokens that can follow a nonterminal, and using it is the textbook recipe. It is also often too large to be useful. The FOLLOW set of an expression includes every token that can follow an expression anywhere in the grammar, which may be most of the terminal alphabet, and discarding until one of those appears means the parser resynchronises immediately and reports the same error again.

Practical parsers use a smaller, hand-chosen set: statement starters, statement terminators, and closing delimiters. The set is smaller than FOLLOW, which means recovery may skip over tokens that the grammar would have accepted, and the cost is the occasional missed error. The benefit is that recovery lands somewhere a new construct can genuinely begin, which is what keeps the diagnostic count proportional to the number of real mistakes.

Choosing those sets is a design decision with no automatic answer. A set that is too small causes cascades; a set that is too large causes the parser to skip past several real errors and report one.

Cascading errors and how to bound them

Recovery creates a failure mode of its own: the placeholder node built after a recovery may itself be wrong, and the construct that follows may fail because of it. The standard defences are a cap on consecutive errors at the same position, and a rule that suppresses a diagnostic when the parser has not consumed a token since the last one.

The second rule is the important one. If the parser reports an error, discards nothing, and reports again at the same token, the second report adds no information. Track the token offset of the last reported error; suppress any diagnostic at the same offset. This single rule removes most duplicate reports.

A third defence is speculative parsing with backtracking for ambiguous prefixes. When the parser can try two interpretations, it saves the token position, attempts one, and on failure restores and attempts the other. The restored position must also restore any state the attempt mutated, which is why speculative parsing works cleanly only when the parser’s state is a token index and an immutable context.

Insertion and deletion, and the risk of false acceptance

Local repair inserts or removes a single token and retries. Inserting a missing semicolon is the classic case: the parser sees a token that can follow a statement, reports “expected ;”, and proceeds as though it were there. This produces a good message and keeps the parse going.

The risk is that a repair makes invalid input parse. If the parser will insert any token that makes the parse continue, then input that is not in the language is accepted with a diagnostic, and a tool that treats “parsed with errors” as success may compile it. The usual discipline is to report the repair as an error rather than a warning, and to refuse to emit code when any repair was applied.

Deletion has a subtler failure: removing a token that was a real part of the program changes the meaning of everything after it. Deleting a stray operator may turn an expression into a different valid expression, and the later type checker then reports errors about code the programmer did not write.

What the diagnostic should contain

A useful syntax diagnostic states the token that was found, its position, and the set of tokens that would have been acceptable. The set is the parser’s expected-token list at that point, and printing it is what turns “syntax error” into an actionable message.

error: expected one of ';', ')', or an operator, found '}'
  --> src/main.rs:14:9
   |
14 |     let x = (a + b}
   |                    ^ expected ';' here

The quality of that set depends on where the parser was when it failed. A recursive-descent parser that fails inside a deeply nested expression has a narrow expected set, which produces a precise message. A table-driven parser that fails in a state with a large action row produces a long list, which is why LR-based tools often report a token plus a short list of plausible continuations rather than the whole row.

The one thing that must not happen is reporting a token that is perfectly valid and blaming it. A parser that consumed a valid token while looking for something else, then reported the next token, has produced a diagnostic that points at the wrong place. This is why error detection should happen before the offending token is consumed, not after.

Recovery in generated parsers

Table-driven parsers recover by popping the state stack until a state is found that can shift an error token, then discarding input until a token is found that the recovered state can shift. The popping is cheap and the result is well-defined, but the choice of recovery point is determined by the table, not by the programmer’s intent, so the resulting diagnostics are often less specific than a hand-written parser’s.

The common middle ground is a generated parser with a hand-written error routine that is called from the generated code at chosen points. The generator exposes a hook at the error action, and the hook decides whether to report, insert, or pop. This keeps the table’s speed and gives the programmer control over the messages that matter.

Both approaches share the constraint that recovery must terminate. Any loop that discards tokens must advance, and any loop that pops states must pop at least one. A progress assertion in the recovery path costs two lines and converts a hang into a diagnostic.

The lookahead machinery that produces the expected-token sets is covered in Recursive Descent and the Cost of One Token of Lookahead. For grammars where the parser cannot decide without more context, the recovery problem gets harder in ways described in Context-Dependent Lexing.