#compilers #语法分析
本页目录

AST 设计与错误恢复

Parser 的产出不是字符串而是树——AST 的设计(异构 vs 同构、span 编码)决定了后续所有 pass 的易用性;而错误恢复决定了在代码写到一半时 IDE 能不能给出有用的补全。

概述

Parser 的输出是一棵抽象语法树(AST)。它和 CST(Concrete Syntax Tree,解析树)不同:CST 精确反映文法的每一步推导——每个括号、分号、关键词都在树上。AST 只保留语义上有意义的节点:丢掉括号(用嵌套代替),丢掉分号(用语句列表代替),丢掉关键词(用节点类型代替)。这篇讲 AST 的三种设计路线、位置信息的正确编码方式、以及当输入有语法错误时 AST 怎么"不崩且给出有用信息"。

三种 AST 设计路线

异构 AST:每种节点一个类型

用代数数据类型(ADT,在 Rust 里就是 enum)为每种语法构造定义专属节点:

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 可选
    While(Box<Expr>, Box<Stmt>, Span),
    Return(Option<Box<Expr>>, Span),
    // ...
}

这是工业编译器的主流选择(Clang, Rustc, Swiftc 都走这条路)。优点:⁠类型安全⁠(后续 pass 对每种节点做模式匹配,编译器保证覆盖),⁠明确⁠(看一眼 enum variant 就知道这是什么语法构造)。缺点:节点种类多,AST 的定义代码量大;且后续 pass 每加一种新分析就要在每种节点上各写一个 match arm。

同构 AST:一个通用节点类型

所有节点共用一个类型,用 tag 区分:

struct Node {
    kind: NodeKind,          ← Number, Binary, Call, ...
    children: Vec<Node>,     ← 子节点列表
    span: Span,
}

Lisp 风格的编译器、JSON/XML 的解析器、protobuf 的编译器常用这种。优点:⁠遍历模式统一⁠(所有节点有相同的 API,递归遍历是同一个函数),⁠扩展性好⁠(加新 pass 不用在 N 种节点上各写 match arm)。缺点:缺乏编译期类型安全(取 child[0] 期望是 Expr 但编译器不保证,取错了到运行时才发现),语义信息弱(看不出 If 的第三个 child 是 else 分支还是不存在)。

CST 先行,再降级到 AST

有些编译器(Rustc, GHC)在解析后引入中间表示层:Rustc 的 AST → HIR(去糖+类型相关处理),GHC 的 Core 等。CST 包含所有语法细节(括号、分号、注释),parser 直接产出;然后一个"lowering" pass 把 CST 转为 AST(丢掉纯语法节点,解析名字的引用)。这条路线的动机:

  • IDE/格式化工具需要 CST(补全、跳转、格式化都依赖 CST 的完整位置信息)。
  • 注释归属问题⁠——注释被丢弃在 AST 外,但文档生成器需要把注释挂到对应的 AST 节点——CST 里保留注释,由 lowering pass 做归属。

Rustc 的 ast.rs 实际上是一种接近 CST 的富信息 AST(保留了 macro invocation 等细节),然后 hir.rs(High-Level IR)是去糖后的真正抽象表示。

位置信息:Span 的编码

每个 AST 节点都带一个 Span,标识它在源码中的位置。Span 至少需要:

Span {
    start: BytePos,       ← 文件中的起始字节偏移
    end: BytePos,         ← 结束字节偏移 (exclusive)
}

从 Span 可以推导:源码文本(source[span.start..span.end])、行号/列号(通过 line table 反推)、以及"这棵树涵盖的整个范围"(从树中最左 child 的 start 到最右 child 的 end)。

Span 要不要存进 AST 节点还是单独维护? 两种方案都存在。Rustc 把 Span 存在节点里(每个节点一个 Span);LLVM 和某些 IR 把位置信息存在一个全局的 source-level debug info 表里,AST 节点只存一个 ID。前者的优势:简单, traverse 时不需要查表。后者的优势:对"没有源码位置的节点"(如编译器合成代码)不占多余内存。

错误恢复:AST 不能碰见错误就空

Parser 碰见x = 1 + ;(表达式不完整),它不能返回一个 None 或崩掉——后续的语义分析、IDE 补全、文档生成全都依赖于有一棵 AST。错误恢复的目标是:⁠产出合法的 AST,其中错误节点标记为"错误"。

Panic mode:跳到同步标记

最经典的恢复,在 LR 分析 里也提过:

当 parser 遇到意外 token 时:
  1. 报告错误
  2. 跳过后续 token, 直到遇到同步标记 (如 ';' 或 '}')
  3. 从同步标记之后恢复解析

代价是"跳过的 token 范围"内的所有语法构造都丢失了——没有任何 AST 子树。对 IDE 来说,这是最差情况:用户正在编辑的区域可能有补全/跳转需求,全丢了。

Error productions:显式写错误规则

在文法里显式添加错误产生式,给 parser 一个"即使不对也能归约"的出口:

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

当出现错误时,parser 归约到 error 符号(匹配它看到的任何 token,直到遇到同步标记),产生一个带错误标记的 AST 节点。这比 panic mode 好——至少保留了"这里有某种语句/表达式"的结构,后续 pass 可以在其上做宽松分析。

错误节点:AST 里有"坏节点"

手写 parser(LL 路线常用)的终极方案:Parser 遇到错误时仍然构造 AST 节点,只是标记它"内部有错":

enum Expr {
    Number(i64, Span),
    Binary(BinOp, Box<Expr>, Box<Expr>, Span),
    Error(String, Span),    ← "坏的表达式", 存错误信息和它涵盖的 token span
}

Parser 在 x = 1 + ; 中,发现 + 后缺少项 → 构造 Expr::Error("expected expression after +", span_of_plus_to_semicolon),把该 AST 子树当作一个"错误表达式"返回。上层(Stmt::Let) 能正常收到一个表达式(虽然内容是错的),解析继续。

好处是整棵 AST 始终完整——IDE/LSP 可以在错误 AST 上做 token-aware 补全⁠,而不是面对空白。Rustc 和 Clang 的做法都在往这个方向走。实际实现中还会配合 is_error() 方法或专门的 ErrorKind enum 来区分错误类型,方便语义分析 pass 跳过或处理。

错误恢复的质量判据

好的错误恢复应满足:

  • 不丢弃无错部分的 AST——错误只影响它所在的局部子树。
  • 单一错误只报一次⁠——不要在恢复过程中对同一个语法错误重复报错。
  • 恢复后能继续解析到文件结束⁠——找出所有语法错误,而非第一个之后就退出。

参考

  • Nystrom: "Crafting Interpreters", Chapters 5–6 (CST/AST 的实践设计, Pratt parser 与 AST 构造)
  • Clang: include/clang/AST/Expr.h — 异构 AST 的工业标杆,每种表达式一个 node class
  • Rustc: compiler/rustc_ast/src/ast.rs (CST/AST), compiler/rustc_hir/src/hir.rs (去糖后)

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

相关页面

© 2026 liz's doc