Skip to content

Error-Tolerant Parsing

Fault-tolerant parsing method — instantiates Grammar-Guided Structure Recovery

Keeps parsing through malformed input by bounding the damaged region, resynchronizing at a safe point, and returning a partial structure plus an explicit list of what it could not recover.

Error-Tolerant Parsing is built for the case its siblings assume away: input that is malformed, incomplete, or hostile. Instead of aborting at the first syntax error, it localizes the damage, resynchronizes at a safe boundary, and returns a partial-but-usable structure together with an explicit record of what it could not parse. The idea that makes it this mechanism is that recovery is first-class, not an afterthought: it treats a broken token stream as the normal operating condition, so one bad token damages a bounded region rather than destroying the whole parse. Everything else in the archetype produces structure from well-formed input; this one produces the most structure it can despite ill-formed input, and is honest about the holes.

Example

An IDE parses source code as the developer types, arriving mid-edit at:

func total(items) {
  for it in items {
    sum += it.

The it. is an unfinished member access and the braces are unbalanced. A strict parser would give up, and the editor would lose all highlighting, folding, and completion. Error-tolerant parsing instead brackets it. as an error node, resynchronizes at the next statement boundary, and still returns a tree covering the function signature and the loop header — so the editor keeps highlighting and can even offer completions at the cursor, precisely where the code is broken. Only the it. span is flagged red. The unrecoverable fragment is recorded, and if some downstream step actually needs that expression, it is escalated rather than silently dropped.

How it works

What distinguishes error-tolerant parsing is what it does on failure — where other parsers simply stop:

  • Bound the damage. On a parse error it marks an error-recovery boundary — how far the malformed region extends — instead of unwinding to the top.
  • Resynchronize. It skips to a known-safe token (a statement terminator or closing delimiter — "panic-mode" recovery) or inserts/deletes a token to continue ("phrase-level" repair), then resumes normal parsing.
  • Emit and continue. It drops an error node in place and keeps building the surrounding tree, so good structure on either side of the fault survives.
  • Record and route. Spans it cannot recover confidently are logged and, when they block a needed result, escalated — never quietly guessed.

Tuning parameters

  • Recovery strategy — panic-mode (skip to a sync token) vs. phrase-level repair (insert/delete to continue). Repair salvages more structure but is a guess that can be wrong.
  • Sync-token set — which tokens count as safe resynchronization points. More sync points recover faster but can swallow a larger region as collateral.
  • Error-region granularity — how tightly the damage is bounded, one token vs. a whole block. Tighter preserves more good structure but risks cascading secondary errors.
  • Escalation threshold — how much unrecovered input, or how central a span, triggers escalation versus a silent partial return.
  • Cascade suppression — how aggressively to mute secondary errors induced by the first, to avoid an error avalanche from a single fault.

When it helps, and when it misleads

Its strength is turning all-or-nothing parsing into graceful degradation. It is indispensable wherever input is routinely broken or half-finished — editors, linters, log and telemetry pipelines, anything fed adversarial data — because it keeps a partial structure useful and localizes blame to a bounded span.

It misleads because recovery is fundamentally a guess: a wrong resynchronization can mis-parse everything after the fault into a plausible-looking but incorrect tree, and aggressive repair can hide a real error behind a "successful" partial parse. The most dangerous misuse is the one the archetype warns of directly — letting tolerant parsing turn malformed or hostile input into confidently executed structure.[1] The discipline is to keep recovered and error regions explicitly marked, never treat a recovered parse as equal in trust to a clean one, and escalate low-confidence recoveries rather than act on them.

How it implements the components

Error-Tolerant Parsing fills the robustness-and-recovery slice of the archetype's machinery:

  • error_recovery_boundary — its core move: it bounds each damaged region and marks the safe point at which parsing resumes, so a fault stays local.
  • exception_handling — malformed tokens and structures are caught and turned into in-place error nodes and recoverable events, rather than fatal aborts.
  • ambiguity_escalation_path — spans it cannot recover with confidence are routed out — logged and flagged for a human or a fallback — instead of being silently guessed into the tree.

It does not recover structure from clean input — that is the base parsers (Recursive-Descent Parsing, Shift-Reduce Parsing); it does not own the durable register where escalated ambiguities are held and adjudicated (Ambiguity Register); and it does not validate the meaning of what it did recover (Semantic Schema Validation).

Notes

Error-Tolerant Parsing is usually a recovery mode layered onto a base parser rather than a standalone algorithm; its resynchronization has to be co-designed with that parser's control flow (top-down descent and bottom-up shift-reduce recover differently). Downstream consumers must keep recovered spans trust-tagged — a partial parse of hostile input is not equal-trust to a clean one, and the gap between "parsed something" and "parsed it correctly" is exactly where malformed input becomes executable meaning.

References

[1] Panic-mode recovery discards tokens after an error until it reaches a designated synchronizing token (such as ; or }), then resumes. It is the simplest, most robust recovery strategy and the reason a single syntax error need not abort an entire parse — but the discarded region is a bounded loss, not a repair, and should be reported as such. ↩