Parser Error Recovery

Parser error recovery has two jobs: explain the syntax problem the user can act on, and regain enough structure to continue without inventing a trail of misleading diagnostics. Recovery is a controlled guess about where parsing can resume.

Choose synchronization points that fit the grammar, retain useful source locations, and guarantee progress or termination. Test malformed input as a supported workload. A parser that accepts correct programs but loops, floods diagnostics, or silently treats damaged input as valid is unfinished.

TL;DR

Quick Example

This original Python parser accepts only assignments with a name, equals sign, unsigned integer, and semicolon. After a syntax error it discards tokens through the next semicolon. It returns valid nodes and diagnostics separately; it does not execute assignments or repair a complete language.

For a missing right-hand value, it reports one error at the semicolon and retains the later valid assignment.

The counterexample matters: with a missing semicolon between otherwise recognizable assignments, this strategy can discard the next assignment too. That behavior is recorded rather than called successful universal recovery. No Bison-generated parser, nested grammar, lexer modes, full compiler, or editor integration was tested.

Core Concepts

Reporting and recovery are separate decisions

A diagnostic identifies the unexpected input, a useful location, and a constrained expectation. Recovery decides what parser context to discard or retain and where to resume. A precise error message does not guarantee a good recovery point, and reaching the end of the file does not make every subsequent diagnostic meaningful.

The Bison manual describes grammar rules using the reserved error token, with strategies that can discard stack context and input. It explicitly notes that recovery strategies can guess incorrectly and cause additional errors. Its statement- and delimiter-oriented examples illustrate why recovery belongs in the grammar design. Bison error-recovery manual source.

For a small language, document the intended recovery boundary in ordinary terms: abandon this statement, retain the enclosing block, and resume after its terminator. For a larger grammar, specify which delimiters belong to the current nesting level. The next semicolon anywhere in the token stream may not be the end of the damaged construct.

The first actionable error deserves priority

An omitted delimiter can make a later token appear invalid. Prefer a diagnostic that explains the expected boundary and points to relevant context, rather than reporting every downstream symptom as an independent mistake. Avoid claiming certainty about a repair when several interpretations remain possible.

Store source spans in a representation the frontend can display correctly. Byte offsets, character indices, token spans, and screen columns are not automatically interchangeable. The example returns Python string offsets only. Its number is not a complete Unicode, tab, multiline, or editor-location solution.

Continuing must not hide invalidity

Keep the fact that recovery occurred in the parse result. A diagnostic list, explicit error node, or invalidity marker can prevent later phases from treating a guessed structure as an ordinary successful parse. Decide which later analyses can proceed and which outputs must be withheld.

The example omits the damaged assignment and returns an error alongside surviving nodes. A consumer that ignores the errors can still misuse that result. Its API contract must state whether recovered structure is for diagnostics, navigation, or another limited purpose. Recovery should not accidentally authorize execution or code generation for an invalid program.

Cleanup follows the abandoned context

Bison's manual also discusses discarded semantic values and lexer state affected by recovery. A production implementation may need to release resources and restore interpretation when it abandons part of a construct. The exact mechanism depends on the parser, semantic-value ownership, and lexer design. Bison manual source.

Think through a mode entered by a prefix and normally exited by a closing delimiter. If recovery abandons that construct without restoring the mode, later input can be tokenized incorrectly. Test the state after recovery, not merely the diagnostic count at the original error.

Best Practices

Build a small malformed-input corpus

Include missing, extra, and wrong tokens at the beginning, middle, and end of constructs. Add nested delimiters, adjacent independent errors, truncated input, and long malformed runs. For each case, record the intended first diagnostic, acceptable retained structure, and a bound on work or output.

Do not optimize only for fewer messages. Suppressing all errors after the first avoids cascades but can hide useful independent findings. Evaluate whether a user can fix the reported problem and then see sensible results on the next run.

Preserve the accepted language

Test valid input before and after recovery changes. An aggressive insertion or skipping rule can alter which programs appear accepted. Keep diagnostic recovery distinct from any explicit source-repair feature, and show a proposed repair as a proposal rather than silently rewriting the user's program.

Add state and resource checks where needed

Verify that aborted constructs release owned resources, later scopes have the intended environment, and repeated parses do not retain stale state. Run malformed-input tests with the implementation's supported memory and error-checking tools where applicable. The small Python illustration cannot establish those properties for a generated C or C++ parser.

Common Mistakes

Synchronizing on any delimiter

Treating a completed parse as success

Emitting diagnostics without progress

Testing only one missing token

FAQ

Is skipping to a semicolon always appropriate?

No. It can be useful for a grammar with suitable statement boundaries, but missing delimiters and nesting can make it discard useful input. The example exposes that limitation directly.

Should a recovered AST be executed?

Only according to an explicit language and application contract. Diagnostic or editor use can tolerate incomplete structure that execution or code generation should reject. Keep errors and validity visible to the consumer.

Does this example validate Bison recovery rules?

No. It is an independent toy parser. Bison's manual supplies conceptual recovery and ownership guidance; generated-parser behavior needs its own grammar, build, and malformed-input tests.

Related Topics

References