AST Design and Error Recovery

The syntax tree is a contract between the frontend and subsequent analysis phases. It must represent the structure of correct programs, decide how to preserve partially edited source code, locate errors, and track where desugared nodes originate. Trees suitable for optimizers and those suitable for formatters often retain different levels of information.

AST, CST, and Lossless Syntax Trees

An AST strips away grammatical details that do not need to participate directly in subsequent processing. For example, parentheses in 1 + (2 * 3) can be expressed through tree nesting and do not necessarily need to be retained as separate parenthesis nodes.

A Concrete Syntax Tree (CST) retains more grammatical structure, but the name "CST" itself does not guarantee that all whitespace and comments are preserved. A lossless syntax tree explicitly requires the ability to recover the complete original source, including trivia, error tokens, etc. Information discarded by the lexer will not automatically return just because the tree is called a CST.

The syntax layer of rust-analyzer adopts a lossless tree and provides a typed access layer; this demonstrates that unified underlying nodes and specialized AST interfaces can be composed, rather than being mutually exclusive. rust-analyzer Syntax Design

Rustc's AST and HIR, as well as GHC's Core, are representations at different compilation stages and cannot be uniformly described as "first CST, then real AST." An AST can also retain high-level information such as macro calls and parentheses; the degree of abstraction is a design choice.

Specialized Types and Unified Nodes

Specialized nodes express structural constraints through enums or class hierarchies. For example, the following Rust definition explicitly ensures that binary expressions have two operands and provides an exit for missing inputs:

#[derive(Clone, Copy)]
struct Span { start: usize, end: usize }

enum BinaryOp { Add, Multiply }
struct Expr { kind: ExprKind, span: Span }
enum ExprKind {
    Number(i64),
    Binary { op: BinaryOp, left: Box<Expr>, right: Box<Expr> },
    Missing,
    Invalid,
}

Real Spans should also bind to files and versions, or obtain snapshot identity through the owning syntax tree. Using Box is the most intuitive recursive ownership relationship; using an arena with ExprId allows centralized allocation and facilitates the creation of side tables, but care must be taken to prevent ID mixing across arenas or versions. Shared immutable trees are suitable for structural reuse but require separate representation for parent nodes or context.

Unified nodes commonly express structure using kind, children, and token lists. Traversal is simple, and extension is convenient. The cost is that "what is the nth child" requires runtime checks or typed wrappers to constrain. Even with enums, semantic invariants such as "name is bound" or "type is correct" are not automatically guaranteed.

Analysis results can be placed in side tables, such as mappings from ExprId to types, symbols, and constant values. This avoids constantly modifying the same generic node across different phases and facilitates caching based on dependency invalidation.

Spans and Source Mapping

Half-open byte intervals are suitable for slicing but are only valid for the corresponding source code snapshot. Macro expansion may involve multiple sources: the call site, the macro definition location, and parameter fragments; desugaring or inlining also generates nodes without independent source text. In such cases, a source map or source chain should be retained; simply taking the minimum start and maximum end of all child nodes is insufficient.

The "entire node range" and the "primary diagnostic highlight range" can also differ. A binary expression might have a span covering the entire expression, while separately storing the operator's position to precisely point the error "this operation does not support this type" to the plus sign.

Missing tokens can be marked with zero-width intervals to suggest insertion points; invalid tokens retain the range they actually occupy. Byte slicing is only valid when boundaries are ensured to fall at correct encoding positions. For row/column conversion, see Lexer Design.

Lowering: Presenting Simpler Semantics to Subsequent Phases

For example, lowering a for loop into iterator initialization, repeated fetching of the next item, conditional branching, and loop body can reduce the variety of syntax types subsequent phases need to handle. However, it must ensure that initialization executes only once, evaluation order is correct, break and continue point to the correct targets, and scope and resource release rules are followed.

Lowering can introduce temporary variables and new node identities. These should be mappable back to user source code to prevent diagnostics from exposing internal temporary names or reporting errors for multiple desugared nodes to the same location. The order of name resolution and lowering depends on the language; it is not required that all implementations complete binding in the same phase.

Error Recovery: Preserving Known Structure, Not Masquerading as Valid Programs

Consider let x = 1 + ; let y = 2;. The parser has determined that the left side of the addition is 1, but the right side is missing. It can insert a MissingExpr before the semicolon, return a Binary node containing the missing node, allow the statement layer to consume the semicolon, and then proceed to the next declaration.

Such a tree satisfies the convention that "the data structure can be traversed by subsequent phases," but it does not imply that the original program is syntactically or semantically correct. Batch compilers may stop code generation after reporting errors; IDEs continue with loose analysis of valid locals. It is not required that every tool must recover to the end of the file, nor should error placeholders secretly become executable normal values.

Returning Missing Expressions to the Statement Layer Allows the Next Declaration to Parse

The following only handles pre-tokenized let name = number [+ number ...] ;. It does not include blocks, parentheses, or arbitrary expressions; positions are represented by token indices, not masquerading as source code byte spans. Missing operands use zero-width intervals, while invalid operands occupy a real token.

class RecoveringParser:
    def __init__(self, tokens):
        self.tokens = list(tokens)
        self.pos = 0
        self.errors = []

    def peek(self):
        return self.tokens[self.pos] if self.pos < len(self.tokens) else None

    def atom(self):
        token, start = self.peek(), self.pos
        if token is None or token == ";":
            self.errors.append((start, "missing expression"))
            return ("Missing", start, start)  # Do not swallow statement boundaries
        self.pos += 1
        if token.isascii() and token.isdecimal():
            return ("Number", int(token), start, self.pos)
        self.errors.append((start, "invalid expression"))
        return ("Invalid", start, self.pos)

    def expr(self):
        left = self.atom()
        while self.peek() == "+":
            self.pos += 1
            left = ("Add", left, self.atom())
        return left

    def parse(self):
        nodes = []
        while self.peek() is not None:
            start = self.pos
            head = self.tokens[self.pos:self.pos + 3]
            if (len(head) == 3 and head[0] == "let" and head[2] == "="
                    and head[1].isascii() and head[1].isalpha() and head[1] != "let"):
                self.pos += 3
                node = ("Let", head[1], self.expr())
            else:
                self.errors.append((start, "invalid declaration"))
                node = ("InvalidDeclaration", start)
            if self.peek() != ";":
                self.errors.append((self.pos, "expected semicolon"))
                while self.peek() not in (None, ";"):
                    self.pos += 1
            if self.peek() == ";":
                self.pos += 1
            nodes.append(node)
            assert self.pos > start  # Outer loop must consume input each round
        return nodes


parser = RecoveringParser(["let", "x", "=", "1", "+", ";", "let", "y", "=", "2", ";"])
nodes = parser.parse()
assert nodes[0][2] == ("Add", ("Number", 1, 3, 4), ("Missing", 5, 5))
assert nodes[1] == ("Let", "y", ("Number", 2, 9, 10))
assert parser.errors == [(5, "missing expression")]
assert parser.pos == 11
for tokens in ([], [";"], ["@"], ["let", "x", "="], ["let", "x", "=", "1", "+"]):
    p = RecoveringParser(tokens)
    p.parse()
    assert p.pos == len(tokens)

expr returns Missing before the semicolon at the 5th token; the statement layer then consumes that semicolon, and the outer loop continues parsing y. atom itself does not need to advance because it hands the boundary over to the caller that can advance; requiring "each function consumes a token every time" would instead swallow delimiters needed by the outer layer.

This example uses a simple synchronization strategy, which may skip subsequent declarations when a semicolon is missing, and diagnostics are not fully deduplicated. To improve recovery quality, context boundaries such as the start of the next declaration should be added, and } should be returned to the block parser after supporting blocks. This demonstrates local missing recovery and the progress contract, not a universal IDE parser.

Why Shouldn't a Missing Operand Swallow the Semicolon?

Comparing missing and invalid error types clarifies why recovery nodes need different ranges. The Missing before the semicolon has no original text, while the Invalid corresponding to @ occupies a real token. Recovery merely records the defect in the tree and allows the statement layer to continue; it cannot automatically fill Missing with 0, nor can it claim the entire program is valid just because y can still be parsed. The figure below separates preserving original text from building the semantic tree.

Three Common Recovery Techniques Can Be Combined

Local repair involves inserting missing tokens when evidence is sufficient, or deleting an obviously redundant token. For example, if you have already seen the call arguments and the outer semicolon, you might suggest adding a closing parenthesis. The number of repairs and their cost must be limited to avoid a chain of guesses masking the true structure.

Synchronization recovery jumps to boundaries such as semicolons, closing parentheses, or the start of the next declaration. Boundaries are determined by the current syntactic context: encountering } often requires returning to the outer block parser rather than unconditionally consuming it, which would swallow the correct block end. Scanning also needs to consider parenthesis nesting; it should not stop at any semicolon inside an inner layer.

Explicit error rules give defined semantic results for certain exceptional paths. Bison's error is a special recovery symbol involving stack popping and input discarding, not a regular lexical wildcard matching any token. For detailed processes, see LR Parsing.

All these techniques can produce error nodes and can also save skipped tokens in the lossless tree. "Panic mode definitely loses all original text" is not a requirement of the mechanism itself.

Two Implementation Invariants

First, recovery must guarantee progress: consume input, exit the current layer to be handled by a caller that can process boundaries, or end at EOF. Zero-width missing nodes must not cause the same loop to continuously generate errors at the same position.

Second, error values must have propagation rules: for example, if type checking encounters a MissingExpr, it can return a specialized error type, suppressing operator mismatch diagnostics derived solely from it, while continuing to check unrelated sibling nodes. Error types are not ordinary arbitrary types, nor does it mean skipping the entire file.

Diagnostics are best stored independently of nodes, recording error kind, primary location, related locations, and fix suggestions. Nodes only need to retain ErrorId or lightweight state to avoid large amounts of repeated error strings in the tree and to facilitate replacing diagnostics after reparsing.

What Responsibilities Do Lossless Preservation and Semantic Placeholders Bear?

MissingExpr in the recovery tree is a synthetic structure with no corresponding original text. If the formatter automatically prints 0 when traversing it, it changes an erroneous program into another valid one; if it ignores the original token of Invalid nodes, it loses user input. The lossless layer should preserve original fragments, while fix suggestions should be treated as independent edit operations.

The following only demonstrates round-trip preservation at the token/trivia layer, including comments, whitespace, and invalid character @; it is not a complete lossless tree. The original text can still be reconstructed, but the parser can simultaneously report that @ is invalid.

import re
source = "let x = 1 + @; // keep this\n"
parts = re.findall(r"//[^\n]*|\s+|[A-Za-z_][A-Za-z_0-9]*|[0-9]+|.", source)
assert "".join(parts) == source
assert "@" in parts and "// keep this" in parts

Subsequent type checking can return error results with ErrorId for Missing, avoiding further derived diagnostics such as "cannot add Int and missing type"; but independent errors outside the same declaration should still be reported. Code generation should check for blocking errors and must not treat placeholder nodes as arbitrary valid values just because tree traversal succeeded.

How to Measure Recovery Quality

In addition to whether valid programs get the correct tree, one should also check: whether removing a parenthesis can save the next function; whether a missing expression results in only a few related errors; whether EOF and deep nesting terminate; and whether the lossless tree can reconstruct the original text including error intervals.

Incremental systems must also verify the lexical context and version of reused subtrees. Whether an edit changes whether a string is closed can affect tokens far away; text regions not changing does not always mean old parsing results can be directly reused.

Subsequent semantic analysis can continue from Symbol Tables and Scopes to understand how names on the tree obtain stable declaration identities.

Keywords: AST, CST, lossless syntax tree, trivia, arena, node identity, span, source map, lowering, missing node, error recovery, incremental parsing