第1章：树形结构在编译器中的应用：语法分析树（AST）与符号表的作用域树

说到树形结构，很多初学者第一反应就是「二叉树遍历」、「红黑树旋转」这些纯数据结构的概念。但说实话，树形结构最精彩的应用场景之一，恰恰藏在编译器里。我做了这么多年C语言工具链相关的工作，每次打开AST可视化工具，都会感叹：树这东西，天生就是为编译器设计的。

1.1 语法分析树（AST）—— 编译器眼中的代码骨架

你写下一行 int a = 3 + 5;，编译器看到的可不是一串字符。它看到的是一个树形结构：根节点是「声明语句」，下面挂着「类型节点」、「变量节点」和「表达式节点」。表达式节点下面又分出「加法运算符」和两个「字面量节点」。

这就是抽象语法树（Abstract Syntax Tree，AST）。它去掉了源代码中不必要的细节——比如分号、括号、空格——只保留程序的逻辑结构。

核心要点：AST 是编译前端（词法分析 + 语法分析）的输出，也是编译后端（语义分析、代码生成）的输入。它是整个编译器的「中间桥梁」。

我个人习惯把 AST 比作「代码的骨架」。你想想看，人没了骨架就是一滩肉，代码没了 AST 就是一堆无意义的字符串。编译器后续的类型检查、作用域解析、代码优化，全都在这个骨架上操作。

一个简单的 AST 示例

假设我们有这么一段 C 代码：

int main() {
    int x = 10;
    int y = x + 5;
    return y;
}

对应的 AST 大概长这样（简化版）：

TranslationUnit
 └── FunctionDef: "main"
      ├── ReturnType: int
      ├── Body: CompoundStmt
      │    ├── DeclStmt: int x = 10
      │    │    ├── VarDecl: x
      │    │    └── Literal: 10
      │    ├── DeclStmt: int y = x + 5
      │    │    ├── VarDecl: y
      │    │    └── BinaryOp: '+'
      │    │         ├── VarRef: x
      │    │         └── Literal: 5
      │    └── ReturnStmt
      │         └── VarRef: y
      └── (implicit return 0)

嗯，这里要注意：AST 的节点类型是有限的，通常由文法规则决定。比如 BinaryOp、VarDecl、Literal 这些都是预定义的节点类型。我在项目中遇到过有人试图动态创建新节点类型，结果导致后续的遍历算法全部崩溃——教训就是：AST 的类型系统一定要在设计阶段定死。

避坑指南：我曾经在做一个自定义 DSL 的编译器时，把 AST 节点设计得过于灵活，允许任意嵌套。结果语义分析阶段需要写几十种特殊情况处理。后来我学乖了：AST 节点类型宁多勿泛，每个节点只做一件事。

1.2 符号表与作用域树 —— 名字的「户口本」

AST 告诉我们代码长什么样，但没告诉我们每个名字（变量、函数、类型）到底指的是谁。比如你写了个 x，它到底是全局变量还是局部变量？是当前函数的参数还是外层作用域的变量？

这就是符号表（Symbol Table）要做的事。而作用域树（Scope Tree），则是符号表的「组织架构图」。

作用域树长什么样？

每个作用域（Scope）对应树中的一个节点。子作用域嵌套在父作用域内部。比如：

Global Scope
 ├── int global_var
 ├── Function: foo
 │    ├── Param: a
 │    └── Block Scope
 │         ├── int local_x
 │         └── if Scope
 │              └── int temp
 └── Function: main
      └── Block Scope
           └── int local_y

你看，foo 函数内部又嵌套了一个 if 作用域。在 if 作用域里访问 a，会先查当前作用域，找不到就往上找父作用域——直到全局作用域。这就是所谓的「词法作用域」或「静态作用域」。

注意：C 语言的作用域规则比这复杂一点。比如 for 循环的初始化语句在 C99 之后有自己的作用域，而 goto 标签的作用域是整个函数。这些细节在实现符号表时都要考虑进去。

1.3 AST 与作用域树如何协同工作？

这两棵树不是各自独立的。实际上，编译器在语义分析阶段会同时遍历 AST 和作用域树，做一件叫「名字解析」的事情。

流程大致是这样的：

  1. 遍历 AST 的每个节点
  2. 遇到变量声明时，在当前作用域插入一条符号记录
  3. 遇到变量引用时，在当前作用域及其父作用域中查找
  4. 如果找不到，报错「未定义标识符」
  5. 如果找到，把 AST 中的引用节点和符号表中的记录关联起来

说白了，AST 是「静态结构」，作用域树是「动态查找路径」。两者结合，编译器才能理解你写的每一行代码到底在说什么。

1.4 一张图看懂整体结构

下面我用 SVG 画了一张图，把 AST、符号表、作用域树的关系展示出来。这张图我每次讲课时都会用，因为它把抽象的东西变得很直观。

编译器中的树形结构：AST + 作用域树 抽象语法树 (AST) TranslationUnit FunctionDef: main FunctionDef: foo DeclStmt ReturnStmt BinaryOp 每个节点对应一种语法结构 叶子节点通常是标识符或字面量 作用域树 (Scope Tree) Global Scope foo Scope main Scope if Scope for Scope 每个作用域包含一组符号记录 子作用域可访问父作用域的符号 ⇄ 语义分析 名字绑定 核心关系 AST 描述「代码长什么样」 作用域树描述「名字从哪里来」

1.5 实际项目中的一点体会

我记得有一次在优化一个嵌入式 C 编译器的内存占用时，发现 AST 节点占用了大量堆空间。原因很简单：每个节点都保存了源代码的行号、列号、文件名等调试信息。对于嵌入式场景，这些信息其实可以按需加载，不必每个节点都带一份。

后来我改成了「节点只保存一个文件偏移量，调试信息单独存表」，内存占用直接降了 40%。这个经验告诉我：AST 的设计要权衡「易用性」和「资源消耗」。你如果做的是教学编译器，怎么方便怎么来；但如果是产品级编译器，每个字节都要精打细算。

1.6 小结

这一章我们聊了两棵树：

  • AST：代码的骨架，描述程序的结构
  • 作用域树：名字的户口本，描述标识符的可见范围

两者通过语义分析阶段的名字绑定过程连接起来。理解了这两棵树，你就掌握了编译器前端最核心的两个数据结构。后面几章我们会深入每个节点的实现细节，包括怎么遍历、怎么优化、怎么处理各种边界情况。

个人建议：如果你正在学习编译原理，不妨自己动手写一个简单的表达式解析器，输出 AST 并打印出来。亲眼看到树形结构，比看任何文字描述都管用。我当年就是这么入门的。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →