AST 设计与错误恢复

语法树是前端与后续分析之间的契约。它需要表达正确程序的结构，也要决定怎样保存编辑到一半的源码、定位错误，以及追踪去糖后的节点来自哪里。适合优化器的树和适合格式化器的树，往往保留不同层次的信息。

AST、CST 与无损语法树

AST 抽去不必直接参与后续处理的文法细节。例如 1 + (2 * 3) 的括号可以通过树形嵌套表达，未必单独保留括号节点。

具体语法树（CST）保留更多文法结构，但“CST”这个名称本身不保证保留所有空白和注释。⁠无损语法树才明确要求能恢复完整原文，包括 trivia、错误 token 等。被 lexer 丢弃的信息不会因为树叫 CST 就自动回来。

rust-analyzer 的语法层采用无损树，并提供类型化访问层；这说明统一底层节点与专用 AST 接口可以组合，不是非此即彼。rust-analyzer 语法设计

Rustc 的 AST、HIR 与 GHC 的 Core 属于不同编译阶段的表示，不能把它们统一描述为“先 CST 再真正 AST”。AST 本身也可以保留宏调用、括号等高层信息，抽象程度是设计选择。

专用类型与统一节点

专用节点通过 enum 或类层次表达结构约束。例如下面的 Rust 定义明确让二元表达式有两个操作数，并为缺失输入留出口：

#[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,
}

真实 Span 还应绑定文件与版本，或通过所属语法树取得快照身份。使用 Box 是最直观的递归拥有关系；arena 加 ExprId 可以集中分配并便于建立旁表，但要防止 ID 跨 arena、跨版本混用。共享不可变树则适合结构重用，却需要另行表示父节点或上下文。

统一节点常用 kind、children 和 token 列表表达结构，遍历简单，扩展方便。代价是“第几个孩子是什么”需要运行时检查或类型化包装来约束。即便使用 enum，也不能自动保证名称已绑定、类型正确等语义不变量。

分析结果可放旁表，例如 ExprId 到类型、符号、常量值的映射。这样不同阶段不必不断修改同一个通用节点，也便于按依赖失效缓存。

Span 与来源映射

半开字节区间适合切片，但只对对应源码快照有效。宏展开可能包含多个来源：调用点、宏定义位置、参数片段；去糖或内联还会生成没有独立源码文本的节点。此时应保留 source map 或来源链，不能简单取所有子节点最小起点和最大终点。

“整个节点范围”与“主要诊断高亮范围”也可不同。二元表达式可有覆盖整式的 span，同时单独保存运算符位置，以便把“这个操作不支持该类型”的错误精确指向加号。

缺失 token 可以用零宽区间标记建议插入处；非法 token 则保留实际占据的范围。只有确保边界落在正确编码位置时，字节切片才有效。行列换算见 词法器设计。

Lowering：让后续阶段面对更简单的语义

例如把 for 循环降为迭代器初始化、重复取下一项、条件分支和循环体，可以减少后续阶段要处理的语法种类。但要保持初始化只执行一次、求值顺序正确、break 和 continue 指向正确目标，并遵循作用域与资源释放规则。

lowering 可以引入临时变量和新节点身份。它们应能映射回用户源码，以免诊断暴露内部临时名，或把多个去糖节点的错误重复报到同一位置。名字解析与 lowering 的顺序依语言而定，不能要求所有实现都在同一个阶段完成绑定。

错误恢复：保留已知结构，不伪装成合法程序

考虑 let x = 1 + ; let y = 2;。parser 已确定加法左侧为 1，但右侧缺失。它可以在分号前插入 MissingExpr，返回带缺失节点的 Binary，让语句层消费分号后继续下一条声明。

这样的树满足“数据结构能够被后续遍历”的约定，不代表原程序语法或类型正确。批量编译器可以在报告错误后停止代码生成；IDE 则继续对有效局部做宽松分析。不能要求每个工具都必须恢复到文件末尾，也不能让错误占位偷偷变成可执行的正常值。

把缺失表达式交回语句层，下一条声明仍能解析

下面只处理预先分词的 let name = number [+ number ...] ;。不包含块、括号或任意表达式；位置以 token 下标表示，不冒充源码字节 span。缺失操作数用零宽区间，非法操作数占据一个真实 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)  # 不吞语句边界
        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  # 外层每轮必须消费输入
        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 在第 5 个 token 的分号前返回 Missing，语句层随后消费该分号，外层继续解析 y。atom 自己可以不前进，因为它把边界交给了能够前进的调用方；要求“每个函数每次都消费 token”反而会吞掉外层需要的分隔符。

本例采用简单同步策略，缺少分号时可能跳过后续声明，且诊断未做全面去重。要提高恢复质量，应加入下一声明开头等上下文边界，并在支持块后把 } 交回块解析器。这里展示的是局部缺失恢复和进展契约，不是通用 IDE parser。

少一个操作数，为什么不该吞掉分号？

比较缺失与非法这两类错误，能看清恢复节点为什么需要不同范围。分号前的 Missing 没有原文，@ 对应的 Invalid 却占一个真实 token。恢复只是在树里记下缺陷并让语句层继续，既不能把 Missing 自动补成 0，也不能因为 y 还能解析就声称整份程序有效。下图把保留原文与构建语义树分开显示。

三种常见恢复手段可以组合

局部修复是在证据充分时插入缺失 token，或删除一个明显多余 token。例如已经看见调用实参和外层分号，可能建议补右括号。需要限制修复次数和代价，避免一连串猜测掩盖真实结构。

同步恢复跳到分号、闭括号、下一条声明开头等边界。边界由当前语法上下文决定：遇到 } 时常应返回给外层块解析器，而不是无条件消费，否则会吞掉正确的块结束。扫描时也需要考虑括号嵌套，不能停在内层任意一个分号。

显式错误规则让某些异常路径有定义的语义结果。Bison 的 error 是特殊恢复符号，涉及弹栈和丢弃输入，并非匹配任意 token 的普通词法通配符。详细过程见 LR 分析。

这几种手段都可以产出错误节点，也可以把跳过的 token 保存在无损树中。“panic mode 必定丢掉全部原文”并不是机制本身的要求。

两条实现不变量

第一，⁠恢复必须保证进展⁠：消费输入、退出当前层交由能处理边界的调用方，或在 EOF 结束。零宽缺失节点不能让同一个循环在同一位置不断产生错误。

第二，⁠错误值必须有传播规则⁠：例如类型检查遇到 MissingExpr 可返回专门的错误类型，抑制仅由它派生的运算符不匹配诊断，同时继续检查无关兄弟节点。错误类型不是普通的任意类型，也不意味着可以跳过整份文件。

诊断最好独立于节点存储，记录错误种类、主位置、相关位置和修复建议。节点保留 ErrorId 或轻量状态即可，避免树中大量重复错误字符串，也便于在重新解析后替换诊断。

无损保存与语义占位分别承担什么责任

恢复树中的 MissingExpr 是合成结构，没有对应原文。若格式化器遍历它时自动打印 0，就把错误程序改成了另一份合法程序；若忽略 Invalid 节点的原 token，又会丢失用户输入。无损层应该保留原始片段，修复建议则作为独立编辑操作。

下面仅演示 token/trivia 层的往返保留，包括注释、空白和非法字符 @；它不是完整无损树。原文仍可重建，但解析器可以同时报告 @ 不合法。

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

后续类型检查可以对 Missing 返回带 ErrorId 的错误结果，避免再产生“不能把 Int 与缺失类型相加”等派生诊断；但同一声明之外的独立错误仍应继续报告。代码生成应检查是否存在阻断性错误，不能因树遍历成功就把占位节点当成任意合法值。

如何衡量恢复质量

除了有效程序能否得到正确树，还应检查：删除一个括号后能否保住下一函数；缺失表达式后是否只报少量相关错误；EOF 和深度嵌套是否终止；无损树能否重建包括错误区间在内的原文。

增量系统还要核对重用子树的词法上下文和版本。一次编辑改变字符串是否闭合，可能影响很远处的 token；文本区域没改，并不总说明旧解析结果仍可直接复用。

后续语义分析可以从 符号表与作用域 继续，理解树上的名字怎样获得稳定的声明身份。

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