Diagnosticsimplementation

Parser Synchronization

The judgement call inside error recovery: which token to resume at. Too eager and a whole function is skipped in silence; too timid and one missing brace produces forty messages that are all the same mistake.

The question

After a parse error, how does the parser decide where to start parsing again?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

The parser's state at the moment of failure: a position in the token stream, a call stack of half-finished constructs, and — in a parser that tracks them — a stack of delimiters it has opened and not yet closed. Synchronization is a decision made against that state, and the quality of the decision is bounded by how much of it the parser kept. A recursive-descent parser is *inside* a named production and knows what it was building; an LR parser has popped its stack to an error production and knows considerably less.

What this phase may assume or do

Recovery may skip tokens and synthesise nodes, but every skipped region must be covered by an error node and every synthesised node must be marked as such, so that later phases can distinguish a construct that parsed from one that was guessed. A parser may also assume that after synchronizing it is at a position where its grammar can make progress — if that assumption is wrong, the parser either loops without consuming input or discards the rest of the file. Both are recovery bugs rather than grammar bugs, and both are why synchronize must always consume at least the offending token.

Key points

Synchronization is the judgement step in recovery: which token the parser is willing to resume at.
Sync sets are built from terminators, closers and construct-introducing keywords; introducers are the safest members and closers the most dangerous.
EOF must be in the set and in the loop condition, or recovery hangs or runs off the end on a truncated file.
A panic flag suppresses messages until the parser has demonstrably recovered — cleared on successful synchronization and on consuming an expected token.
Our parser records suppressed diagnostics with cascading: true rather than dropping them, so a UI can choose and a test can assert on the cascade.
A global sync set skips past delimiters it owes; tracking the delimiter stack and threading per-construct sets are the two standard fixes.
Error productions produce the best messages because the mistake was recognised rather than guessed, at the cost of one rule per anticipated mistake.
Languages that removed syntactic redundancy have smaller sync sets and are correspondingly harder to recover in.

Panic mode, and the set that decides everything

The technique is simple enough to state in one line: throw tokens away until the ground looks solid. Everything interesting is in the definition of solid. A synchronization set is the set of tokens at which the parser is willing to resume, and choosing it is a design decision about the language as much as about the parser.

Three families of token qualify. Terminators — ; in C-family languages, NEWLINE and DEDENT in Python — mark the end of a construct, so the token after one is plausibly the start of the next. Closers — }, ), ], end — mark the end of an enclosing construct, which is useful and dangerous for the same reason: resuming there means abandoning everything the parser was in the middle of. Introducers — if, while, fn, let, class, return — mark the start of a new construct regardless of what preceded them, which makes them the safest members of the set.

AtlasLang's parser uses all three. Its sync set is LET, FN, IF, WHILE, RETURN, PRINT, RBRACE and EOF, and it additionally stops immediately after consuming a semicolon, on the reasoning that a statement has just ended whatever else went wrong. EOF is in the set for a mundane and essential reason: without it, a synchronize loop at the end of a broken file never terminates.

A language that is hard to synchronize is usually a language that removed redundancy. Optional semicolons, significant indentation without explicit block markers, and expression-oriented syntax with few keywords all shrink the sync set. That is one of the more concrete arguments for mandatory delimiters, and it is invisible until someone has to write the recovery.

The real synchronize in `src/compilers/sim/parser.ts`

1/** Tokens that plausibly begin a statement — the synchronization set. */
2const SYNC: TokenKind[] = ['LET', 'FN', 'IF', 'WHILE', 'RETURN', 'PRINT', 'RBRACE', 'EOF']
3 
4/** Panic-mode recovery: skip until something that could start a statement. */
5function synchronize() {
6  while (!at('EOF')) {
7    if (tokens[pos - 1]?.kind === 'SEMICOLON') break   // a statement just ended
8    if (SYNC.includes(peek().kind)) break              // a statement may start here
9    advance()
10  }
11  panicking = false                                    // recovered: report again
12}

EOF appears twice over — in the loop condition and in the sync set — and both are load-bearing. A synchronize that can walk off the end of the token array is the classic way to turn a syntax error into a crash, and a sync set without a terminating member is how a recovery loop hangs on a truncated file.

Cascades, and recording them rather than hiding them

The reason synchronization needs a suppression mechanism at all is that a parser after an error is not confused — it is confidently parsing in the wrong context. A missing } does not present as a missing }; it presents as the next function's fn keyword appearing where a statement was expected. Every construct after it is then misread, and each misreading produces a message that is specific, plausible and wrong.

The standard defence is a panic flag: after reporting, suppress further messages until the parser has demonstrably recovered. AtlasLang keeps a boolean panicking, set when a diagnostic is reported and cleared in exactly two places — inside synchronize, and inside expect when the expected token was actually found, because consuming what the grammar wanted is evidence that the parser is back in step.

What our parser does *not* do is drop the suppressed messages. It records every diagnostic and marks the suppressed ones cascading: true, so the data structure carries both the parser's best guess at the real error and the noise it produced afterwards. That choice matters for two reasons. A UI can then show the first error prominently and offer the rest behind a toggle, rather than deciding for the user. And a test can assert on the cascade itself — that the second message is marked cascading, that the first is not — which is the only way to tell an improvement in recovery from a change in the error count.

The alternative designs are worth naming because they are what most compilers do. Clang caps the total with -ferror-limit, defaulting to 20, and stops. GCC leaves -fmax-errors unlimited. rustc suppresses duplicates within a token-distance window and, for delimiters specifically, uses indentation to guess where the closing brace was meant to be and reports the *opening* one. Only the last of those makes the message better; the others make the output shorter.

Recovery over let x = ; let y = 2; — where the parser resumes

let x = ; let y = 2;

Read it asExactly one token is skipped and exactly one diagnostic is reported, which is what good recovery looks like on a small input. The interesting counterfactual is a missing } instead: nothing in the token stream marks it, the parser keeps consuming statements into a block that should have ended, and the first token that fails is somewhere entirely else — which is why delimiter errors get their own heuristics rather than being handled by the sync set.

Beyond panic mode: nesting, per-construct sets, and error productions

implementationThe sync set, the panic flag and the cascading marker are the AtlasLang parser in this build, and its set is statement-level and nesting-unaware on purpose — it is the version most hand-written parsers start with. rustc, Clang and Roslyn all thread per-construct expectations and track delimiters, and rustc additionally uses indentation to attribute unclosed braces. Every one of those heuristics is tuned per language and none of them transfers unchanged.

Panic mode as written has two known weaknesses, and both have standard answers.

It is nesting-unaware. A global statement-level sync set will happily skip a } that closes a block the parser is still inside, which desynchronises the delimiter structure for the rest of the file. The fix is to track the open delimiters and refuse to skip past one you owe: if the parser is inside a { it has not closed, } becomes a stopping point that pops a level rather than a token to skip over. This is bookkeeping rather than cleverness, and it is what separates a recovery that loses a statement from one that loses a file.

The sync set is global. An error inside an argument list resynchronizes at statement level, discarding the rest of the enclosing call and often the enclosing statement. The better structure threads a per-construct sync set down the recursive-descent call chain: while parsing an argument list, , and ) are added to the set contributed by the enclosing constructs, so recovery stays local. The set at any point is then the union of the FOLLOW sets of every construct currently on the stack, which is also the theoretical justification for the whole technique.

Error productions are the third technique and the one that produces the best messages, because the parser is no longer guessing — it recognised the mistake. A grammar rule that matches something *not* in the language, purely to diagnose it: = where == was meant in a condition, a missing fn keyword, Java-style else if chains in a language that spells it differently, >> closing two template argument lists. The cost is one rule per anticipated mistake, forever, and the trap is that an error production must never make the invalid construct work — it matches, diagnoses, and returns an error node.

Four synchronization strategies and what each one gets wrongtypical

Strategy	Resumes at	Characteristic failure
Global statement-level sync set	`;`, `}`, or a statement keyword, anywhere	Skips past a delimiter it owed, desynchronising the rest of the file
Per-construct sync set (FOLLOW-based)	A token that could follow any construct on the stack	Stays close to the failure and therefore reports more near-duplicates
Delimiter-stack aware	The matching closer for the innermost unclosed opener	Still has to guess which delimiter the user intended to close
Error production	Nowhere — the mistake was matched, not skipped	One rule per anticipated mistake, and a rule that accidentally accepts extends the language

How it works

The steps, in the order the compiler takes them.

The parser fails: the current token matches no applicable production for the construct it is building.
It reports a diagnostic anchored at the construct's span, and sets a panic flag so that immediately following errors are marked rather than trusted.
It consumes the offending token unconditionally, guaranteeing progress and preventing an infinite recovery loop.
It then advances until the next token is in the synchronization set, or until a terminator was just consumed, or until end of input.
It clears the panic flag, constructs an error node covering the skipped range, and returns it to the enclosing production.
The enclosing production continues as though the child had parsed, so the tree stays well-shaped and later constructs are still attempted.
A subsequent successful expect also clears the flag, since consuming exactly what the grammar wanted is evidence the parser is back in step.
Semantic phases skip subtrees containing error nodes, preventing a second wave of type errors derived from a guessed parse.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

One missing brace produces forty messages, and the true error is the first one, which has scrolled off the terminal.
An error inside an argument list resynchronizes at statement level, so the rest of the function is skipped and no diagnostic is reported for anything in it.
The parser reports a second error two tokens after the first, and a user fixes the wrong thing because the second message was more specific.
Recovery loops forever on a file that ends mid-construct, because the sync set had no terminating member and the loop did not check for end of input.
A parser skips past the } that closes the function it is inside, and every subsequent declaration is parsed as a nested statement.
Suppression is too aggressive and a genuinely independent second error is never reported, so the user recompiles three times for three mistakes.
An error production intended to diagnose = in a condition accidentally accepts it, and the invalid syntax becomes a de facto feature nobody can now remove.

When it helps

Any interactive tool, where the input is invalid most of the time and the parser must always return a tree.
Large or generated files, where finding all the independent errors in one pass is the difference between one fix cycle and dozens.
Evaluating a parser: feeding it files with a single deliberate deletion and checking whether the second reported error is independent of the first is a direct measurement of recovery quality.
Designing syntax, where the size of the achievable sync set is a real and rarely considered consequence of removing delimiters.

When it hurts

Where a wrong guess costs more than stopping. A configuration parser that recovers may apply a partially valid configuration, which is worse than refusing to start — input validation in Security is the counter-discipline.
When recovery is tuned by error count. Reporting more messages is not better recovery; the metric is whether the second message is about a different mistake.

What it costs

Every one of these is paid by something.

A large sync set buys quick resynchronization and pays coverage: every skipped token is a region in which no error can be reported, so a big skip hides real problems.
A small sync set buys coverage and pays noise, since staying close to the failure means reporting the same mistake several times.
Per-construct sync sets buy locality — an argument-list error stays inside the argument list — and pay a parser in which every production must accept and propagate an expectation set, which is a pervasive signature change.
Recording suppressed diagnostics instead of dropping them buys UI flexibility and testability, and pays memory plus the obligation on every consumer to check the flag; a consumer that ignores it prints the cascade.
Error productions buy the best messages obtainable and pay per-mistake effort forever, plus the standing risk that a production accepts what it was written to diagnose.

What else you could do

What a different compiler or language does instead, and when that is better.

Phrase-level repair: insert, delete or substitute a single token and continue. Cheap, effective for missing semicolons, and confidently misleading when the guess is wrong.
Burke–Fisher or least-cost repair: search for the minimum edit sequence that makes the input parse. Elegant, expensive, and the minimum edit is frequently not what the user meant.
GLR parsing with error nodes, as tree-sitter does: never commit to one interpretation, always return a tree containing ERROR and MISSING nodes, and decline to have an opinion about intent — excellent for editors.
Always-return-a-tree recursive descent with missing-token nodes, as Roslyn does: zero-width synthesised tokens and skipped-token trivia, so a tree exists for literally any input and the IDE never loses completion.
Recover in the lexer by synthesising tokens, which is what automatic semicolon insertion in JavaScript and Go amounts to — and which both communities regard very differently.

See it for yourself

The flag, dump or tool that shows you this directly.

Run the errors example in our pipeline explorer at /compilers/pipeline and look at the diagnostics list: the entries flagged cascading are the suppressed ones, shown rather than hidden.
Delete a } from the middle of a large C++ file and compile with clang -ferror-limit=0, then count the messages and find the first. That is the cascade, measured.
Compare the same broken Rust file under rustc: it reports the *opening* delimiter with an indentation note rather than the end of file, which is a heuristic rather than extra effort.
tree-sitter parse a file with a deliberate error and read the (ERROR ...) and (MISSING ...) nodes in an otherwise complete tree.
In your editor, type an incomplete expression inside an unclosed block and see whether completion still works — that tells you which recovery model the language server is built on.

Plausible wrong readings

Stated the way a confident engineer states them.

"Panic mode is crude, so good compilers do not use it." Every mainstream compiler uses it, augmented with per-construct sets, delimiter tracking and error productions. The augmentations are the difference, not the replacement.
"The parser is confused after an error." It is not confused; it is confidently parsing in the wrong context. That is why the following messages are specific and wrong rather than vague.
"Suppressing errors hides information." Recording them with a flag hides nothing; it moves the decision about what to show to the consumer, which is where it belongs.
"A bigger sync set is safer." A bigger set means faster resynchronization and larger skipped regions, and everything inside a skipped region is a diagnostic that will never be produced.

Misconceptions

The claim, and what is actually true.

Synchronization means finding where the error really was.

It means finding a token where parsing can resume. Locating the real cause is a separate, harder problem that delimiter heuristics attack directly.

Suppressed diagnostics should be discarded.

They should be marked. The parser cannot know which of them a user will find useful, and a flag lets the UI and the tests decide.

Recovery quality is about the parser algorithm.

It is mostly about how much context the parser still has when it fails. Recursive descent keeps the construct it was building; a deterministic LR parser has already popped that context off the stack.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

After a parse error the parser throws tokens away until it reaches one that plausibly starts something new — a semicolon, a closing brace, a keyword like if or let. That is synchronization. Skip too little and you get the same mistake reported over and over; skip too much and whole functions go unchecked in silence.

practical

Always consume the offending token before you start skipping, or recovery can loop. Put end-of-input in the sync set. Suppress messages until the parser has genuinely recovered, but mark the suppressed ones rather than dropping them, so the interface can decide what to show. And when your recovery loses whole functions, the cause is almost always a global sync set skipping past a delimiter the parser still owed — track the open delimiters before doing anything cleverer.

advanced

The theoretical framing is that the ideal synchronization set at any point is the union of the FOLLOW sets of every construct currently on the parse stack, which is exactly the set of tokens that could legally continue *some* enclosing construct. Recursive descent can approximate this by threading an expectation set down the call chain, and the reason it produces better recovery than a table-driven LR parser is that the information is still on the call stack when the failure happens. LR error recovery has to reconstruct it from error productions written into the grammar, which is why LR parser generators ship with recovery mechanisms that feel bolted on: they are recovering context the algorithm deliberately discarded in exchange for its determinism. That trade — analysable power against retained context at the moment of failure — is the same one [[ll-vs-lr]] describes from the other side, and it is the main reason production compilers moved back to hand-written recursive descent.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationAtlasLang's sync set and its cascading flag are this build's parser, and the set is deliberately statement-level and nesting-unaware — the version most hand-written parsers start with. Clang, rustc and Roslyn all thread per-construct expectation sets and track delimiter stacks, and their suppression heuristics are tuned per language and per version.

typicalClang defaults -ferror-limit to 20 and stops; GCC leaves -fmax-errors unlimited; rustc suppresses duplicates by token distance and uses indentation to attribute unclosed delimiters. All three are tunable and change across releases. What generalises is the shape of the defence rather than any number.

simplifiedOur parser reports at the offending token rather than at the start of the construct being parsed, which is one of the two most common sources of "the error is on the line after the mistake". A production parser threads the construct's start span down so the diagnostic can point at the fn or the ( that was left unfinished.

If you were asked this in an interview

Which tokens would you put in a synchronization set for a C-like language, and why those?
How do you stop one missing brace from producing forty messages, without hiding a genuinely independent second error?
Why does a recursive-descent parser tend to recover better than a table-driven LR parser?

Connections

DSAstack n-ary-tree

Securityinput-validation

API Designerror-taxonomy

Domains that do not exist yet

Testing & Reliability Engineering — Mutation and fault injection against known-good inputs
Recovery quality is measured by deleting or corrupting one token in a valid file and checking whether the second reported error is independent of the first. Generating those mutations systematically is a testing discipline owned there; the compiler-specific application is [[compiler-testing]].