AST Design and Error Recovery

The output of a parser is not a string but a tree—the design of the AST (heterogeneous vs. homogeneous, span encoding) determines the ease of use for all subsequent passes; and error recovery determines whether an IDE can provide useful completions while code is being written.

Overview

The output of a parser is an Abstract Syntax Tree (AST). It differs from a CST (Concrete Syntax Tree, or parse tree): a CST precisely reflects every step of the grammar's derivation—every parenthesis, semicolon, and keyword is present in the tree. An AST retains only semantically meaningful nodes: parentheses are discarded (replaced by nesting), semicolons are discarded (replaced by statement lists), and keywords are discarded (replaced by node types). This article discusses three design approaches for ASTs, the correct encoding of position information, and how an AST can "remain robust and provide useful information" when the input contains syntax errors.

Three AST Design Approaches

Heterogeneous AST: One Type per Node

Define dedicated nodes for each syntactic construct using Algebraic Data Types (ADTs, i.e., enum in Rust):

enum Expr {
    Number(i64, Span),
    Binary(BinOp, Box<Expr>, Box<Expr>, Span),
    Call(Box<Expr>, Vec<Expr>, Span),
    // ...
}

enum Stmt {
    Let(String, Option<Expr>, Box<Expr>, Span),
    If(Box<Expr>, Box<Stmt>, Option<Box<Stmt>>, Span),     ← else is optional
    While(Box<Expr>, Box<Stmt>, Span),
    Return(Option<Box<Expr>>, Span),
    // ...
}

This is the mainstream choice for industrial compilers (Clang, Rustc, Swiftc all follow this path). Advantages: Type safety (subsequent passes perform pattern matching on each node type, and the compiler ensures coverage), and Clarity (one glance at the enum variant reveals what syntactic construct it represents). Disadvantages: Many node types lead to a large amount of AST definition code; furthermore, every new analysis pass requires writing a match arm for each node type.

Homogeneous AST: One Generic Node Type

All nodes share a single type, distinguished by a tag:

struct Node {
    kind: NodeKind,          ← Number, Binary, Call, ...
    children: Vec<Node>,     ← List of child nodes
    span: Span,
}

This approach is common in Lisp-style compilers, JSON/XML parsers, and protobuf compilers. Advantages: Uniform traversal patterns (all nodes have the same API, and recursive traversal uses the same function), and Good extensibility (adding a new pass does not require writing match arms for N node types). Disadvantages: Lack of compile-time type safety (accessing child[0] expects an Expr, but the compiler doesn't guarantee it; errors are only caught at runtime), and weak semantic information (it is unclear whether the third child of an If node is an else branch or if it is absent).

CST First, Then Lower to AST

Some compilers (Rustc, GHC) introduce an intermediate representation layer after parsing: Rustc's AST → HIR (desugaring + type-related processing), GHC's Core, etc. A CST contains all syntactic details (parentheses, semicolons, comments) and is produced directly by the parser; then, a "lowering" pass converts the CST into an AST (discarding pure syntax nodes and resolving name references). The motivations for this approach are:

• IDEs/Formatting tools need a CST (completions, navigation, and formatting all rely on the complete position information provided by the CST).
• Comment ownership — comments are discarded outside the AST, but documentation generators need to attach comments to corresponding AST nodes — the CST retains comments, and the lowering pass handles the attribution.

Rustc's ast.rs is actually a rich-information AST close to a CST (retaining details like macro invocations), while hir.rs (High-Level IR) is the desugared, truly abstract representation.

Position Information: Encoding Spans

Each AST node carries a Span, indicating its position in the source code. A Span needs at least:

Span {
    start: BytePos,       ← Starting byte offset in the file
    end: BytePos,         ← Ending byte offset (exclusive)
}

From a Span, you can derive: the source text (source[span.start..span.end]), line/column numbers (inferred via a line table), and the "entire range covered by this tree" (from the start of the leftmost child to the end of the rightmost child).

Should Spans be stored inside AST nodes or maintained separately? Both approaches exist. Rustc stores Spans in nodes (one Span per node); LLVM and some IRs store position information in a global source-level debug info table, with AST nodes storing only an ID. The advantage of the former: simplicity, no need to look up tables during traversal. The advantage of the latter: no extra memory overhead for "nodes without source positions" (e.g., compiler-synthesized code).

Error Recovery: AST Must Not Collapse on Errors

When a parser encounters x = 1 + ; (an incomplete expression), it cannot return None or crash—subsequent semantic analysis, IDE completions, and documentation generation all depend on having an AST. The goal of error recovery is: produce a valid AST, where error nodes are marked as "errors".

Panic Mode: Jump to Synchronization Tokens

The most classic recovery method, also mentioned in LR Parsing:

When the parser encounters an unexpected token:
  1. Report the error
  2. Skip subsequent tokens until a synchronization token is encountered (e.g., ';' or '}')
  3. Resume parsing after the synchronization token

The cost is that all syntactic constructs within the "skipped token range" are lost—there is no AST subtree for them. For IDEs, this is the worst case: the area the user is editing might require completions or navigation, but all that information is lost.

Error Productions: Explicitly Write Error Rules

Explicitly add error productions to the grammar, giving the parser an exit path ("reduce even if it's incorrect"):

Stmt → error ';'
Expr → '(' error ')'

When an error occurs, the parser reduces to the error symbol (matching any token it sees until a synchronization token is encountered), producing an AST node marked with an error. This is better than panic mode—at least it preserves the structure "there is some statement/expression here," allowing subsequent passes to perform loose analysis on it.

Error Nodes: "Bad Nodes" in the AST

The ultimate solution for hand-written parsers (common in the LL approach): The parser still constructs AST nodes when encountering errors, just marking them as "internally erroneous":

enum Expr {
    Number(i64, Span),
    Binary(BinOp, Box<Expr>, Box<Expr>, Span),
    Error(String, Span),    ← "Bad expression", storing error info and the span of tokens it covers
}

In x = 1 + ;, the parser finds a missing operand after + → it constructs Expr::Error("expected expression after +", span_of_plus_to_semicolon), returning this AST subtree as an "error expression." The upper layer (Stmt::Let) receives an expression normally (even though the content is wrong), and parsing continues.

The benefit is that the entire AST remains intact—IDEs/LSP can perform token-aware completions on the erroneous AST, rather than facing blank space. Both Rustc and Clang are moving in this direction. In practical implementations, this is often combined with an is_error() method or a dedicated ErrorKind enum to distinguish error types, facilitating semantic analysis passes to skip or handle them appropriately.

Criteria for Error Recovery Quality

Good error recovery should satisfy:

• Do not discard error-free parts of the AST — errors only affect the local subtree they reside in.
• Report a single error only once — do not repeatedly report the same syntax error during recovery.
• Resume parsing to the end of the file after recovery — find all syntax errors, rather than exiting after the first one.

References

• Nystrom: "Crafting Interpreters", Chapters 5–6 (Practical design of CST/AST, Pratt parser and AST construction)
• Clang: include/clang/AST/Expr.h — The industrial benchmark for heterogeneous ASTs, with one node class per expression type
• Rustc: compiler/rustc_ast/src/ast.rs (CST/AST), compiler/rustc_hir/src/hir.rs (Post-desugaring)

Keywords: AST, abstract syntax tree, CST, concrete syntax tree, heterogeneous AST, homogeneous AST, sum type, enum, span, position, BytePos, lowering, error recovery, panic mode, synchronizing token, error production, error node, parse error, incremental parsing, IDE