抽象语法树 | Codeboy's Blog

形式陈述

抽象语法树（AST）是抽象语法的一种树形表示。每个节点标记一个语法构造，按顺序排列的子节点表示该构造的直接组成部分；标识符与字面量等原子构造通常成为叶节点。若抽象语法含

e ::= n \mid x \mid e+e \mid e\times e,

则可用 Num(n)、Var(x)、Add(e_1,e_2) 与 Mul(e_1,e_2) 节点表示对应项。

AST 通常是有根有序树，但“树”是实现约定而非抽象语法的本体要求。公共子表达式共享、名称解析边或类型注解可能把内存表示扩展成 DAG 或带附加边的图。只要抽象项及其操作语义保持一致，这些表示仍可服务同一语言层。

AST 与具体语法树不同：括号、分号、空白、注释和仅用于解析的非终结符可以不成为独立节点。需要无损格式化或逐字符重写时，应使用 concrete syntax tree、token stream 或保留 trivia 的语法树，而不是假定普通 AST 能恢复原文件。

直觉

抽象语法是数学对象，AST 是把该对象放进树节点和指针中的常见方式。二者的关系类似“有限序列”与“数组”：数组便于存储和遍历，却不是序列定义本身。

把这两层分开能避免三类错误：把某个解析器的节点布局当成语言语义；认为所有绑定都只是父子关系；以及在引入共享后误以为抽象语法已经改变。

例子与边界

表达式 1 + 2 * 3 在通常优先级下得到

\operatorname{Add}(\operatorname{Num}(1), \operatorname{Mul}(\operatorname{Num}(2),\operatorname{Num}(3))).

(1 + 2) * 3 的根则为 Mul。括号本身可以被丢弃，但它造成的分组差异保留在树形中。

同一个抽象项可用 de Bruijn 索引、唯一符号 ID 或表面变量名表示。若只存名字而不记录绑定关系，遮蔽会让后续替换与分析出错；若把重复子树 hash-cons 成共享节点，表示不再是严格的树，却可减少内存。

AST 的抽象层次也不唯一。源 AST 可保留 for 循环，核心 AST 可把它脱糖为 while 与赋值。跨层转换需要显式定义，并在编译器正确性中证明语义保持。

推论与应用

解析器从具体语法产生 AST；名称解析建立绑定关系，类型检查生成类型判断，解释器或编译器再遍历节点。操作语义应定义在抽象语法项上，AST 只是实现这些项的一种载体。

静态分析常从 AST 构造控制流图。该转换丢弃语法嵌套的一部分并加入可能后继边，因此 CFG 不是 AST 的同义表示，也一般无法唯一反推原语法。

参考资料

Robert Harper, Practical Foundations for Programming Languages, 2nd ed., Cambridge University Press, 2016, Chapters 1–2.
Benjamin C. Pierce, Types and Programming Languages, MIT Press, 2002, Chapters 3–5.
Andrew W. Appel, Modern Compiler Implementation in ML, Cambridge University Press, 1998, Chapters 3–4.