一、什么是抽象语法树
抽象语法树(Abstract Syntax Tree,AST)是一种用于表示程序语法结构的树形数据结构。
编译器通过词法分析和语法分析,将源代码转换为 Token 序列,再根据语言文法构建 AST。
AST 不直接保存源代码的全部字符,而是提取程序中具有结构意义的信息,例如:
- 变量声明
- 函数定义
- 函数调用
- 表达式
- 运算符
- 条件判断
- 循环结构
- 返回语句
例如:
int result = a + b * c;
从源代码来看,这是一条变量声明语句。
从 AST 的角度来看,它包含以下结构:
- 变量声明节点:
VariableDeclaration - 变量名称:
result - 类型信息:
int - 初始化表达式:
a + b * c - 加法表达式:
BinaryExpression - 乘法表达式:
BinaryExpression
其核心结构可以表示为:
flowchart TB
A["VariableDeclaration"]
B["Type: int"]
C["Identifier: result"]
D["BinaryExpression: +"]
E["Identifier: a"]
F["BinaryExpression: *"]
G["Identifier: b"]
H["Identifier: c"]
A --> B
A --> C
A --> D
D --> E
D --> F
F --> G
F --> H
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style E fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style F fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style G fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style H fill:#E8EDF2,stroke:#B8C3CE,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
从树结构可以看出,乘法表达式是加法表达式的右子节点。
这意味着 AST 不仅记录了有哪些 Token,还记录了它们之间的嵌套关系和运算优先级。
二、为什么需要 AST
源代码本质上是字符序列。
对于编译器而言,直接处理原始字符存在几个问题:
- 字符串结构不便于表达程序的层次关系。
- 无法直接体现运算符的优先级和结合性。
- 变量、函数、表达式等程序结构难以统一处理。
- 代码优化需要识别程序结构,而不是简单替换字符。
- 语义分析需要知道变量声明、函数调用和作用域之间的关系。
AST 通过树形结构解决这些问题。
例如:
int result = a + b * c;
如果只看 Token 序列:
INT IDENTIFIER ASSIGN
IDENTIFIER PLUS IDENTIFIER MULTIPLY IDENTIFIER
SEMICOLON
只能知道出现了哪些词法单元。
而 AST 能够明确表达:
VariableDeclaration
└── Initializer
└── Add
├── Identifier(a)
└── Multiply
├── Identifier(b)
└── Identifier(c)
AST 将线性的 Token 序列转换成了具有层次关系的程序结构。
AST 的核心价值不是保存源代码,而是将源代码转换成便于程序分析和处理的结构化表示。
三、AST 的基本组成
AST 通常由节点(Node)构成。
每个节点代表一种程序结构,节点之间通过父子关系组织起来。
3.1 节点类型
不同编程语言的 AST 节点类型有所不同,但通常包含以下类别:
| 节点类型 | 典型名称 | 说明 |
|---|---|---|
| 程序节点 | Program | 整个程序或模块 |
| 声明节点 | VariableDeclaration | 变量声明 |
| 函数节点 | FunctionDeclaration | 函数定义 |
| 参数节点 | Parameter | 函数参数 |
| 标识符节点 | Identifier | 变量、函数或类型名称 |
| 字面量节点 | Literal | 数字、字符串、布尔值等 |
| 二元表达式 | BinaryExpression | 加减乘除、比较等 |
| 一元表达式 | UnaryExpression | 取反、逻辑非等 |
| 函数调用 | CallExpression | 函数调用 |
| 赋值表达式 | AssignmentExpression | 赋值操作 |
| 条件语句 | IfStatement | 条件分支 |
| 循环语句 | WhileStatement | 循环结构 |
| 返回语句 | ReturnStatement | 函数返回 |
节点名称并不是跨语言统一的标准。
例如,JavaScript AST、Python AST、Clang AST 和 Rust AST 的节点定义都存在差异。
3.2 节点的基本属性
一个 AST 节点通常包含以下信息:
| 属性 | 作用 | 示例 |
|---|---|---|
| Node Type | 节点类型 | BinaryExpression |
| Children | 子节点 | 左操作数、右操作数 |
| Operator | 运算符 | + |
| Value | 节点值 | 123 |
| Location | 源代码位置 | 第 1 行,第 5 列 |
| Metadata | 附加信息 | 类型、符号引用等 |
例如:
a + b
可以表示为:
BinaryExpression
├── operator: +
├── left
│ └── Identifier(a)
└── right
└── Identifier(b)
其中:
BinaryExpression表示二元表达式。operator表示运算符。left表示左操作数。right表示右操作数。
需要注意,AST 节点的具体字段由语言规范、编译器实现和 AST 库设计决定,并不存在一套所有语言都必须遵循的固定结构。
3.3 父节点与子节点
AST 是一种树形结构,通常包含:
- 根节点(Root):整棵树的入口。
- 父节点(Parent):包含其他节点的节点。
- 子节点(Child):由父节点组织的节点。
- 叶子节点(Leaf):没有子节点的节点。
例如:
a + b * c
其中:
- 加法表达式是根节点。
a和乘法表达式是加法表达式的子节点。b和c是乘法表达式的子节点。- 标识符节点通常是叶子节点。
这种结构使得编译器能够通过树遍历,逐层处理程序中的不同语法结构。
四、AST 是如何生成的
AST 通常由编译器前端的语法分析阶段构建。
整体过程如下:
flowchart TB
A["源代码"]
B["词法分析"]
C["Token 序列"]
D["语法分析"]
E["识别语法结构"]
F["创建 AST 节点"]
G["组织父子关系"]
H["生成 AST"]
I["语义分析"]
A --> B
B --> C
C --> D
D --> E
E --> F
F --> G
G --> H
H --> I
style A fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style C fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style E fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style F fill:#FFF5DE,stroke:#E8D29A,color:#334155
style G fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style H fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style I fill:#FFF5DE,stroke:#E8D29A,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
实际编译器通常不会先完整构建一棵具体语法树,再单独转换为 AST。
很多解析器会在识别产生式的同时创建 AST 节点,并直接组织父子关系。
4.1 词法分析:生成 Token
首先,词法分析器读取源代码,将字符序列转换为 Token。
例如:
int result = a + b * c;
得到:
INT
IDENTIFIER(result)
ASSIGN
IDENTIFIER(a)
PLUS
IDENTIFIER(b)
MULTIPLY
IDENTIFIER(c)
SEMICOLON
此时仍然是线性序列,没有完整的表达式树结构。
4.2 语法分析:识别结构
语法分析器根据语言文法识别 Token 之间的关系。
例如:
Declaration
Type
Identifier
Initializer
初始化表达式进一步识别为:
AddExpression
Identifier(a)
MultiplyExpression
Identifier(b)
Identifier(c)
语法分析器由此确定节点类型以及它们之间的层次关系。
4.3 构建 AST 节点
解析器根据识别结果创建节点。
例如:
createIdentifier("a")
createIdentifier("b")
createIdentifier("c")
createBinaryExpression("*", b, c)
createBinaryExpression("+", a, multiply)
createVariableDeclaration("result", "int", add)
最终形成一棵完整的 AST。
这是一种概念化的构建过程,真实编译器通常通过解析函数、节点构造器和内存分配器完成相关操作。
五、AST 与 CST 的区别
AST 和 CST 都可以表示程序的语法结构,但两者关注的内容不同。
5.1 具体语法树(CST)
CST(Concrete Syntax Tree)也称为具体语法树。
它更完整地反映源代码与语法规则之间的对应关系,通常保留更多语法细节。
例如:
a + b * c;
CST 可能包含:
- 表达式产生式节点。
- 运算符节点。
- 标识符节点。
- 分号等终结符。
- 文法推导过程中产生的中间节点。
5.2 抽象语法树(AST)
AST 会省略部分对后续程序分析没有必要的语法细节。
例如:
ExpressionStatement
└── Add
├── Identifier(a)
└── Multiply
├── Identifier(b)
└── Identifier(c)
AST 更关注表达式的核心结构,而不是完整保留每个语法符号。
5.3 CST 与 AST 对比
| 对比维度 | CST | AST |
|---|---|---|
| 全称 | Concrete Syntax Tree | Abstract Syntax Tree |
| 关注重点 | 完整语法结构 | 抽象程序结构 |
| 文法节点 | 通常保留较多 | 通常省略部分中间节点 |
| 标点符号 | 通常保留 | 通常省略 |
| 括号 | 通常保留 | 通常不单独保留 |
| 结构复杂度 | 相对较高 | 相对精简 |
| 典型用途 | 语法还原、代码编辑 | 语义分析、优化、代码生成 |
需要注意,AST 并不是简单删除所有标点符号。
例如,括号虽然通常不需要作为独立 AST 节点保留,但它们决定的表达式分组关系必须体现在 AST 结构中。
a * (b + c)
即使 AST 不保留括号节点,也必须保留 b + c 作为乘法右操作数这一结构。
六、AST 如何表达运算符优先级
运算符优先级是 AST 最重要的应用之一。
考虑表达式:
a + b * c - d
假设乘法优先级高于加法和减法,并且加减法都是左结合的。
其计算结构为:
(a + (b * c)) - d
对应的 AST:
flowchart TB
A["Subtract"]
B["Add"]
C["Identifier: d"]
D["Identifier: a"]
E["Multiply"]
F["Identifier: b"]
G["Identifier: c"]
A --> B
A --> C
B --> D
B --> E
E --> F
E --> G
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style D fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style E fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style F fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style G fill:#E8EDF2,stroke:#B8C3CE,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
从 AST 中可以直接判断:
b * c先形成一个乘法子树。a + (b * c)形成加法子树。- 最后整个加法子树与
d构成减法表达式。
这说明运算符优先级不需要在 AST 中额外保存为一个简单的数字。
它已经通过树的嵌套关系表达出来。
6.1 结合性对 AST 的影响
考虑:
a - b - c
减法通常是左结合的。
因此,AST 表示为:
Subtract
├── Subtract
│ ├── a
│ └── b
└── c
而不是:
Subtract
├── a
└── Subtract
├── b
└── c
这两棵树代表不同的运算顺序。
因此,语法分析器必须正确处理运算符的结合性,否则会生成错误的 AST。
七、AST 的遍历方式
AST 建立后,编译器需要对其进行遍历,以执行语义分析、优化和代码生成等任务。
常见遍历方式包括:
- 前序遍历(Preorder)
- 中序遍历(Inorder)
- 后序遍历(Postorder)
- 深度优先遍历(DFS)
- 广度优先遍历(BFS)
7.1 前序遍历
前序遍历的访问顺序:
- 访问当前节点。
- 遍历左子树。
- 遍历右子树。
对于:
+
/ \
a *
/ \
b c
前序遍历结果:
+ a * b c
前序遍历常用于生成前缀表达式,以及在需要先处理父节点的场景中使用。
7.2 中序遍历
中序遍历的访问顺序:
- 遍历左子树。
- 访问当前节点。
- 遍历右子树。
示例结果:
a + b * c
中序遍历常用于表达式的输出。
但如果涉及复杂运算符优先级和括号,直接输出节点名称并不足够,还需要根据父子关系和优先级决定是否添加括号。
7.3 后序遍历
后序遍历的访问顺序:
- 遍历左子树。
- 遍历右子树。
- 访问当前节点。
示例结果:
a b c * +
后序遍历常用于:
- 表达式求值。
- 生成栈式中间代码。
- 在子节点处理完成后再处理父节点。
7.4 三种遍历方式对比
| 遍历方式 | 访问顺序 | 典型用途 |
|---|---|---|
| 前序遍历 | 根、左、右 | 结构分析、前缀表达式 |
| 中序遍历 | 左、根、右 | 表达式输出 |
| 后序遍历 | 左、右、根 | 表达式求值、代码生成 |
遍历顺序并不是固定的编译器执行顺序。不同编译任务会选择不同的遍历方式,也可能采用多次遍历或访问者模式完成复杂处理。
八、AST 在编译器中的作用
AST 是连接语法分析与后续编译阶段的重要数据结构。
8.1 语义分析
语法正确不代表程序一定合法。
例如:
int result = "hello" + 10;
这段代码在某些语言中可能具有合法的语法结构,但表达式是否允许进行这样的运算,需要由语义规则判断。
语义分析会遍历 AST,检查:
- 变量是否已经声明。
- 标识符是否能够正确解析。
- 函数调用是否匹配函数定义。
- 运算符两侧的类型是否兼容。
- 返回值是否符合函数声明。
- 作用域和访问规则是否满足要求。
语义分析可能为 AST 节点附加类型信息、符号引用、隐式类型转换等信息。
因此,经过语义分析的 AST 有时也被称为带注解的 AST(Annotated AST)。
8.2 符号表与 AST 的关系
符号表(Symbol Table)用于记录程序中的标识符信息。
例如:
int count = 10;
int add(int a, int b) {
return a + b;
}
符号表可能记录:
| 名称 | 类型 | 作用 |
|---|---|---|
| count | int | 全局变量 |
| add | function | 函数 |
| a | int | 函数参数 |
| b | int | 函数参数 |
AST 负责表示这些声明和使用关系所在的程序结构,符号表则负责记录名称对应的定义信息。
二者通常相互配合:
- AST 中的声明节点可以创建符号。
- AST 中的标识符使用节点可以引用符号。
- 作用域结构决定符号查找范围。
- 类型信息可以关联到 AST 节点。
符号表并不一定直接嵌入 AST 中。很多编译器会使用独立的数据结构管理符号及其作用域。
8.3 代码优化
编译器可以基于 AST 识别表达式结构,并执行一些优化。
例如:
int result = 2 * 3 + x;
编译器可以识别常量表达式:
2 * 3
并将其计算为:
int result = 6 + x;
这种优化称为常量折叠(Constant Folding)。
其他可能基于 AST 或其后续中间表示执行的优化包括:
- 常量传播。
- 死代码消除。
- 表达式简化。
- 不可达代码分析。
- 冗余计算识别。
需要注意,现代编译器的大部分复杂优化通常发生在中间表示(IR)阶段,而不是直接在 AST 上完成。
AST 更适合表达高层程序结构,IR 通常更适合进行控制流、数据流和底层指令层面的优化。
8.4 代码生成
完成语义分析和必要的转换后,编译器可以根据 AST 或后续 IR 生成目标代码。
例如: