Error Recovery

When a parser encounters a token it did not expect, it has found a syntax error. The simplest approach is to stop immediately and report the error — but this is bad for the developer.

Imagine compiling a file with 10 syntax errors. A compiler that stops at the first error forces you to fix one error, recompile, find the next error, fix it, recompile... 10 times.

A good compiler detects one error, recovers, and continues parsing to find as many subsequent errors as possible. This way, the developer sees all problems at once.

Error recovery is the difference between a frustrating compiler and a helpful one.

Before looking at recovery strategies, it helps to know what kinds of errors a compiler can encounter:

The parser handles syntax errors. It knows what token it expected (based on the grammar) and what it actually received — and uses that information to recover.

How the Parser Detects an Error

A parser reports an error when the current input token does not match any valid production for the current grammar rule.

Panic mode is the simplest and most widely used error recovery strategy. When an error is found, the parser:

1. Discards input tokens one at a time until it finds a synchronisation token — a token that is likely to start a new valid statement (like ;, }, or a keyword like if, while, return).
2. Resumes parsing from that synchronisation point.

Example — Panic Mode in Action

Grammar (simplified C-like statements):

Input with error:

What happens:

Choosing Synchronisation Tokens

The choice of synchronisation tokens is critical:

Good synchronisation tokens are ones that cannot appear inside most expressions — they clearly mark the boundary between statements.

Pros and Cons

Phrase-level recovery is more precise than panic mode. Instead of blindly skipping tokens, the parser makes a local correction — inserting or deleting a single token to make the input valid.

Common Corrections

Example — Inserting a Missing Token

Example — Deleting an Extra Token

Pros and Cons

Error productions augment the grammar with special rules that match common mistakes. The grammar explicitly handles known error patterns so the parser can report a useful message and continue.

How It Works

You add extra productions to the grammar of the form:

When the parser matches the error form, it reports a specific, targeted error message.

Example — Common Mistake: Exponent Operator

In some languages, beginners confuse ^ (bitwise XOR in C) with the power operator. We can add an error production:

When the parser sees term ^ factor, it reports:

Example — Missing Operator

Error message: Missing operator between expressions on line 7

Pros and Cons

Global correction is the theoretically ideal strategy. Given the erroneous input string, find the minimum number of insertions, deletions, and replacements needed to turn it into a valid string, and report those as the errors.

This is similar to computing the edit distance between two strings.

Why Global Correction is Rarely Used

Global correction is mainly a theoretical concept. Real compilers use panic mode or phrase-level recovery because they are fast and good enough in practice.

Summary of Recovery Strategies