第4章 抽象语法树（程序的树形表示） Abstract Syntax Trees

一、导读

1.1 本章学习目标

理解抽象语法树（AST）与语法分析树（Parse Tree）的区别，以及为什么编译器选择使用 AST

掌握 AST 节点的设计原则，包括如何为不同语言结构定义合适的节点类型

理解符号表（Symbol Table）的数据结构设计，包括作用域嵌套和名字查找策略

掌握语义分析的核心任务：类型检查、作用域分析、常量求值和一致性验证

学会属性文法（Attribute Grammar）的基本概念及其在语义分析中的应用

理解 AST 遍历（Visitor 模式）的实现方法及其在编译器各阶段的应用

了解 AST 的序列化与反序列化技术在现代工具链中的意义

1.2 为什么本章如此重要

抽象语法树是编译器内部最核心的数据结构之一。它是源代码的"结构化灵魂"——去除了语法糖、括号、分隔符等表面装饰，只保留程序的语义骨架。从 AST 出发，编译器可以进行类型检查、常量折叠、代码生成等几乎所有后续工作。可以说，AST 的质量直接决定了编译器后续阶段的实现难度。

符号表是另一个贯穿编译全过程的关键数据结构。它记录了程序中所有名字（变量、函数、类型、标签等）的定义和属性信息，是语义分析的基础。符号表的设计需要妥善处理作用域嵌套、名字遮蔽（Shadowing）、重载解析等复杂问题。一个设计良好的符号表不仅服务于语义分析，还为调试信息生成、IDE 代码补全等下游任务提供支持。

语义分析是编译前端最后的"守门人"。它确保程序不仅在语法上合法，而且在语义上一致——类型匹配、变量已声明、函数参数正确等。许多难以调试的运行时错误，如果能在编译期通过语义分析检测出来，将为开发者节省大量时间。本章将系统讲解如何构建这些关键的编译基础设施。

1.3 核心问题引导

AST 为什么要去除语法分析树中的某些节点（如括号节点、逗号节点）？保留它们的代价是什么？

如何设计 AST 节点类型，使其既能表达丰富的语言结构，又便于遍历和变换？

符号表如何处理嵌套作用域？当内层作用域声明了与外层同名的变量时，应该如何查找？

类型检查应该在 AST 构建时立即进行，还是作为独立的遍历阶段进行？各自的优缺点是什么？

属性文法中的综合属性（Synthesized Attribute）和继承属性（Inherited Attribute）有什么区别？各自适用于哪些场景？

如何处理 C 语言中"声明即使用"的复杂性（如 typedef 引入的新类型名需要在词法分析阶段就被识别）？

AST 的不可变性（Immutable AST）对优化和并行分析有什么优势？

二、核心概念详解

2.1 AST 的设计与构建（约 700 字）

抽象语法树（Abstract Syntax Tree, AST）是源代码语法结构的树形表示。与语法分析树（Parse Tree）不同，AST 去除了对语义无用的中间节点，只保留程序的核心结构。例如，表达式 (a + b) * c 的语法分析树包含括号节点和多个冗余的非终结符节点，而 AST 直接表示为一个乘法节点，其左子节点为加法节点（子节点为 a 和 b），右子节点为 c。

AST 节点的设计通常采用面向对象的多态结构。每种语言结构对应一种节点类型：表达式节点（Expression）包括二元运算节点（BinaryOp）、一元运算节点（UnaryOp）、标识符节点（Identifier）、字面量节点（Literal）、函数调用节点（Call）等；语句节点（Statement）包括赋值语句（Assignment）、条件语句（If）、循环语句（While/For）、返回语句（Return）等；声明节点（Declaration）包括变量声明（VarDecl）、函数声明（FuncDecl）、类型声明（TypeDecl）等。

在 C 语言实现中，AST 节点通常用带标签联合体（Tagged Union）表示：一个枚举字段标识节点类型，一个联合体存储不同类型节点的特有数据。例如：

typedef enum { AST_BINARY, AST_UNARY, AST_NUMBER, AST_IDENT } AstKind;
typedef struct AstNode {
  AstKind kind;
  int line;
  union {
    struct { int op; struct AstNode *left, *right; } binary;
    struct { int op; struct AstNode *operand; } unary;
    struct { double value; } number;
    struct { char *name; } ident;
  } data;
} AstNode;

AST 的构建通常在语法分析阶段完成。语法分析器在归约产生式时，根据产生式的结构创建对应的 AST 节点，并将子节点连接为父节点的子树。这种方式使得 AST 构建与语法分析紧密耦合，但逻辑清晰、实现直接。

AST 构建后，编译器通过遍历（Traversal）来访问和处理树中的每个节点。最常见的遍历方式是深度优先遍历，可以进一步分为前序、中序和后序。对于表达式树，后序遍历（先处理子节点再处理父节点）自然地对应于"先计算操作数再执行运算"的语义。

2.2 符号表的设计与管理（约 700 字）

符号表（Symbol Table）是编译器用来记录程序中所有标识符（名字）及其属性信息的数据结构。每个标识符条目通常包含：名字（Name）、种类（Kind：变量、函数、类型、常量等）、类型（Type）、作用域（Scope）、存储位置（Storage：寄存器、栈、全局等）、定义位置（行号、文件名）等信息。

符号表的核心操作是插入（enter）和查找（lookup）。插入在遇到标识符声明时执行，将名字及其属性信息加入符号表；查找在遇到标识符使用时执行，从符号表中检索该名字的定义信息。如果查找失败（标识符未声明），则报告语义错误。

处理作用域嵌套是符号表设计的关键挑战。大多数编程语言支持嵌套作用域（如函数内的代码块、类内的方法），内层作用域可以声明与外层同名的标识符（名字遮蔽）。符号表需要支持分层查找：先在当前作用域查找，找不到则逐层向外查找，直到全局作用域。

实现分层查找的常见方法有两种。第一种是线性链式符号表：每个作用域维护一个哈希表，并通过指针链接到外层作用域的符号表。查找时沿链逐层搜索，插入时只在当前作用域的表中操作。离开作用域时，丢弃当前层的表。这种方法实现简单，但查找效率随嵌套深度线性增长。

第二种是统一哈希表加作用域标记：所有标识符存储在同一个哈希表中，但每个条目带有作用域层级信息。查找时从最内层开始，逐层降低层级直到找到匹配。这种方法查找效率更高（哈希表 O(1)），但离开作用域时需要批量删除该层的条目。

现代编译器通常采用更精细的设计。例如，LLVM 的符号表不仅记录名字和类型，还维护名字的定义链（Definition Chain），支持名字遮蔽的精确追踪。Rust 编译器（rustc）的符号表还包含生命周期（Lifetime）信息，用于借用检查。

2.3 类型检查与语义分析（约 700 字）

类型检查（Type Checking）是语义分析的核心任务，它遍历 AST，验证程序中每个操作的类型一致性。类型检查的目标是确保程序在运行时不会因为类型不匹配而崩溃——将所有可能的类型错误前移到编译期发现。

类型检查的基本规则包括：赋值兼容性，右侧表达式的类型必须能赋值给左侧变量的类型；运算符类型约束，加法操作的两个操作数必须都是数值类型（或都是字符串，取决于语言）；函数调用一致性，实参的数量和类型必须与函数声明的形参匹配；数组索引类型，索引表达式必须是整数类型。

类型检查的实现通常采用属性传递的方式：AST 的每个节点被赋予一个类型属性，类型检查从叶节点（标识符、字面量）开始，自底向上传递类型信息。例如，二元加法节点的类型由其两个子节点的类型决定：如果两个子节点都是 int，则结果类型为 int；如果一个是 int 另一个是 float，则需要进行类型提升（Promotion），结果类型为 float。

类型系统可以分为强类型（Strong Typing）和弱类型（Weak Typing），静态类型（Static Typing）和动态类型（Dynamic Typing）。强类型语言（如 Java、Rust）严格禁止隐式类型转换，弱类型语言（如 JavaScript、C）允许较多的隐式转换。静态类型语言在编译期进行类型检查，动态类型语言在运行期进行类型检查。

除了基本的类型检查，语义分析还包括其他任务：常量折叠（在编译期计算常量表达式的值）、可达性分析（检测不可达代码）、初始化检查（确保变量在使用前已初始化）、返回值检查（确保非 void 函数的所有路径都有 return 语句）等。这些检查共同确保程序在语义层面的正确性。

2.4 属性文法与语法制导翻译（约 500 字）

属性文法（Attribute Grammar）是在上下文无关文法的基础上，为每个文法符号附加属性（Attribute），并为每条产生式附加语义规则（Semantic Rule）的形式化框架。它是语法制导翻译（Syntax-Directed Translation）的理论基础。

属性分为两类。综合属性（Synthesized Attribute）的值由子节点的属性计算得出，信息自底向上传递。例如，表达式节点的类型属性就是综合属性：BinaryOp.type = promote(left.type, right.type)。继承属性（Inherited Attribute）的值由父节点或兄弟节点的属性计算得出，信息自顶向下或横向传递。例如，声明语句中变量的类型通常作为继承属性传递给标识符：在 int x, y, z; 中，类型 int 从声明节点继承给每个变量标识符。

属性文法的求值依赖于属性之间的依赖关系。如果依赖图中存在环，则属性文法是不可求值的（Circular Attribute Grammar）。对于只有综合属性的属性文法（S-属性文法），可以在语法分析的归约步骤中自然地计算属性值。对于包含继承属性的文法（L-属性文法），需要在推导过程中传递属性信息。

在实践中，属性文法的思想被广泛应用于编译器的语义分析和中间代码生成。AST 遍历中的类型检查、类型推导、中间代码生成等任务，本质上都是属性文法求值的具体实现。

三、深入分析与讨论

3.1 Visitor 模式与 AST 遍历（约 500 字）

AST 遍历是编译器中最常见的操作之一。类型检查、常量折叠、中间代码生成、代码优化等任务都需要遍历 AST 的每个节点。如何设计遍历机制，使其既能支持多种不同的遍历目的，又能保持代码的清晰和可维护性，是一个重要的工程问题。

Visitor 模式是面向对象语言中处理 AST 遍历的经典设计模式。它定义一个 Visitor 接口，为每种 AST 节点类型声明一个 visit 方法。具体的遍历逻辑（如类型检查器、代码生成器）实现 Visitor 接口。AST 节点提供 accept 方法，接受 Visitor 对象并调用对应的 visit 方法。

Visitor 模式的优势在于关注点分离：每种遍历逻辑独立封装在一个 Visitor 类中，添加新的遍历（如新的优化 Pass）不需要修改 AST 节点的定义。缺点是当 AST 节点类型增加时，所有 Visitor 实现都需要更新。

在函数式语言中，模式匹配（Pattern Matching）提供了更简洁的 AST 遍历方式。例如，在 Haskell 或 Rust 中，可以使用 match 表达式直接根据节点类型和结构进行分支处理，代码更加紧凑直观。

3.2 C 语言的语义复杂性案例（约 500 字）

C 语言的语义分析有一个著名的复杂性：类型名（typedef 引入的名字）和标识符在词法层面无法区分。例如，在 T x; 中，T 可能是类型名（表示声明变量 x 类型为 T），也可能是变量名（表示将 T 乘以 x）。区分这两种情况需要查询符号表，而符号表在语义分析阶段才可用。

这意味着 C 语言的词法分析不能独立完成，它需要与语法分析协作。当语法分析器遇到一个标识符时，需要查询符号表判断它是否是 typedef 引入的类型名，然后将结果反馈给词法分析器，以便选择正确的 Token 类型（TYPE_NAME 或 IDENTIFIER）。

这种词法-语法耦合是 C 语言设计的历史遗留问题，它增加了编译器实现的复杂度。现代语言（如 Java、Rust）通过保留关键字（如 Java 的 class、Rust 的 struct）或在语法层面消除歧义，避免了这种耦合。

3.3 AST 的变换与优化（约 400 字）

AST 不仅是语义分析的载体，也是早期优化的操作对象。在 AST 层面可以进行的优化包括：常量折叠（将 2 + 3 替换为 5）、常量传播（将已知常量的变量替换为常量值）、代数化简（将 x * 1 替换为 x、x * 0 替换为 0）、短路求值优化等。

AST 变换的实现需要特别注意副作用（Side Effect）。例如，将 f() * 0 化简为 0 是错误的，因为 f() 可能有副作用。正确的做法是检查表达式是否纯（Pure，无副作用），只有纯表达式才能安全地消除。

AST 变换通常通过创建新节点（不可变方式）或原地修改节点（可变方式）实现。不可变方式更安全（不影响其他引用同一 AST 的 Pass），但内存开销较大；可变方式更高效，但需要谨慎处理遍历顺序和依赖关系。

四、实践案例

4.1 案例一：为简化 C 语言构建完整的符号表（约 400 字）

为一个简化 C 语言（支持 int/float 类型、函数定义、变量声明、嵌套代码块）实现符号表。符号表采用链式结构，每进入一个新的作用域（函数体或代码块），创建新的符号表层并链接到外层。

变量声明语句 int x = 3; 的处理流程：语法分析器识别到变量声明产生式，创建 AST 节点 VarDecl(name="x", type=int, init=3)，同时调用符号表的 enter 方法，将 (name="x", kind=VARIABLE, type=int, scope=currentScope) 插入当前层的符号表。如果同名标识符已在当前层存在，则报告重复声明错误。

标识符使用表达式 x + 1 的处理流程：语法分析器识别到标识符，创建 AST 节点 Identifier(name="x")，同时调用符号表的 lookup 方法。lookup 从当前层开始逐层搜索，找到 "x" 后返回其类型信息（int），类型检查器据此验证加法操作的类型兼容性。

4.2 案例二：实现表达式类型的递归推导（约 400 字）

类型检查的核心是递归地推导 AST 每个节点的类型。以表达式节点为例，实现一个 typeOf(node) 函数：

对于字面量节点 LiteralInt(value)，返回 int 类型；对于 LiteralFloat(value)，返回 float 类型。对于标识符节点 Identifier(name)，查询符号表获取该标识符的声明类型。对于二元运算节点 BinaryOp(op, left, right)，先递归推导 left 和 right 的类型，然后根据运算符和 operand 类型确定结果类型：如果 op 是加法且两个操作数都是 int，结果为 int；如果任一操作数为 float，结果为 float（类型提升）。对于函数调用节点 Call(name, args)，查询符号表获取函数的声明，验证实参数量和类型与形参匹配，返回函数的返回类型。

这种递归推导自然地对应于 AST 的后序遍历：先处理子节点获取子表达式类型，再根据当前节点的运算规则确定整体类型。

五、常见误区与注意事项

5.1 误区一：AST 应该保留源代码的所有信息

AST 的设计目标是保留语义信息，而非语法信息。括号、分号、逗号、关键字等语法元素在 AST 中通常不需要专门的节点，因为它们的作用已经在树结构中体现。例如，(a + b) * c 的括号信息已经通过树结构（乘法节点的左子节点是加法节点）隐含表达了。保留冗余节点会增加 AST 的复杂度，降低遍历效率。

5.2 误区二：符号表只需要存储变量名和类型

实际的符号表需要存储更多信息：标识符的种类（变量、函数、类型、枚举值等）、作用域层级、存储类别（auto、static、extern、register）、是否已初始化、定义位置（用于错误报告）等。对于函数，还需要记录参数列表、返回类型、是否是变参函数等信息。

5.3 误区三：类型检查可以在语法分析的同时完成

虽然某些简单的类型检查可以在语法分析过程中进行（语法制导翻译），但复杂的类型检查（如函数调用的参数验证、结构体成员访问）需要完整的符号表信息，而符号表需要在整个程序扫描过程中逐步构建。因此，完整的类型检查通常作为语法分析之后的独立阶段进行。

5.4 注意事项：AST 的内存管理

AST 可能占用大量内存，尤其是对于大型程序。设计 AST 时需要权衡内存效率：使用对象池（Object Pool）减少分配开销、使用紧凑的节点表示（如将小整数直接存储在节点中而非分配堆内存）、及时释放不再需要的 AST 节点。LLVM 使用 BumpPtrAllocator 进行 AST 内存的快速分配和批量释放。

六、本章小结

本章系统讲解了抽象语法树的设计与语义分析的核心技术。AST 去除了语法分析树中的冗余信息，以简洁的树形结构表示程序的语义骨架，是后续所有编译阶段的操作基础。符号表通过分层结构管理标识符的定义和属性信息，支持作用域嵌套和名字查找。类型检查遍历 AST，验证程序的类型一致性，将运行时错误前移到编译期发现。属性文法为语义分析提供了形式化的理论框架，综合属性和继承属性分别对应自底向上和自顶向下的信息传递。Visitor 模式为 AST 遍历提供了灵活的设计方案，使得不同的编译任务可以独立实现而不互相干扰。掌握这些技术，是构建高质量编译器前端的关键。

七、思考题与练习

为以下 C 语言代码片段画出 AST：int main() { int x = 3; if (x > 0) { return x * 2; } else { return -x; } }

设计一个支持嵌套作用域的符号表数据结构，实现 enter、lookup、beginScope、endScope 四个操作。

实现一个类型检查器，能够处理以下类型规则：int 和 float 可以混合运算（结果为 float），int 可以隐式转换为 float，但 float 不能隐式转换为 int。

用 Visitor 模式实现一个 AST 遍历，计算表达式树中所有常量子表达式的值（常量折叠）。

分析 C 语言中 typedef 对词法分析和语法分析的影响，说明为什么需要词法-语法反馈机制。

比较不可变 AST 和可变 AST 的优缺点，说明在什么场景下你会选择其中一种。

调研 LLVM 的 AST 设计（Clang AST），说明其节点类型体系和遍历机制。

实现一个属性文法，为算术表达式计算值和类型两种属性，说明哪些是综合属性，哪些是继承属性。