返回专栏
· 14 分钟阅读

抽象语法树(Abstract Syntax Tree,AST)


一、什么是抽象语法树

抽象语法树(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

源代码本质上是字符序列。

对于编译器而言,直接处理原始字符存在几个问题:

  1. 字符串结构不便于表达程序的层次关系。
  2. 无法直接体现运算符的优先级和结合性。
  3. 变量、函数、表达式等程序结构难以统一处理。
  4. 代码优化需要识别程序结构,而不是简单替换字符。
  5. 语义分析需要知道变量声明、函数调用和作用域之间的关系。

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 前序遍历

前序遍历的访问顺序:

  1. 访问当前节点。
  2. 遍历左子树。
  3. 遍历右子树。

对于:

      +
     / \
    a   *
       / \
      b   c

前序遍历结果:

+ a * b c

前序遍历常用于生成前缀表达式,以及在需要先处理父节点的场景中使用。

7.2 中序遍历

中序遍历的访问顺序:

  1. 遍历左子树。
  2. 访问当前节点。
  3. 遍历右子树。

示例结果:

a + b * c

中序遍历常用于表达式的输出。

但如果涉及复杂运算符优先级和括号,直接输出节点名称并不足够,还需要根据父子关系和优先级决定是否添加括号。

7.3 后序遍历

后序遍历的访问顺序:

  1. 遍历左子树。
  2. 遍历右子树。
  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 生成目标代码。

例如: