欢迎来到编译器设计的深水区。在构建编译器的过程中，如何高效地表示源代码的结构是至关重要的一步。你可能已经听说过“语法树”，但你真的了解它在编译器后端优化中扮演的角色吗？
在这篇文章中，我们将超越基础，不仅探讨标准的语法树，还会深入挖掘它的强大变体——有向无环图（DAG）。我们将一起探索这些数据结构是如何通过复用公共子表达式来优化代码生成的。准备好提升你的编译器设计内功了吗？让我们开始吧。
语法树的基础架构
首先，让我们快速回顾一下核心概念。语法树是编译器中一种抽象的语法结构表现形式。为什么我们需要它？因为简单的源代码文本对于机器来说太难以分析了，而语法树将代码转化为了机器易于理解和操作的数据结构。
在语法树中：
- 叶子节点：通常代表操作数，比如变量名或常量。
- 内部节点：代表操作符，比如加法 INLINECODEe6ad2955、赋值 INLINECODEf6396f1d 或 函数调用。
#### 节点的数据结构设计
在实际开发中，我们通常将树中的每个节点设计为一个对象或结构体。这种设计需要高度的灵活性，以便处理不同的节点类型。我们可以通过以下三个核心函数来构建语法树的底层逻辑。想象一下，我们正在用 C 或 C++ 编写编译器的前端，这些函数将是你的得力助手。
1. 构建二元操作符节点
这是处理大多数算术逻辑的核心。
// 函数功能：创建一个带有操作符的内部节点
// 参数：op (操作符标签), left (左子树指针), right (右子树指针)
Node* mknode(char op, Node* left, Node* right) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->label = op; // 设置节点的标签，如 ‘+‘ 或 ‘-‘
newNode->type = OPERATOR; // 标记类型为操作符
newNode->leftChild = left; // 连接左子节点
newNode->rightChild = right; // 连接右子节点
return newNode; // 返回新创建节点的指针
}
2. 构建标识符叶子节点
当我们的词法分析器遇到一个变量名时，我们需要创建一个指向符号表的节点。
// 函数功能：创建一个代表变量或标识符的叶子节点
// 参数：id (标识符名称), entry (符号表中的条目指针)
Node* mkleaf_id(char* id, SymbolTableEntry* entry) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->label = id; // 可以存储变量名用于调试
newNode->type = ID; // 标记类型为标识符
newNode->symbolTableEntry = entry; // 关键：指向符号表的引用
return newNode;
}
3. 构建常量叶子节点
处理数字字面量时使用。
// 函数功能：创建一个代表常量的叶子节点
// 参数：val (常量的整数值)
Node* mkleaf_num(int val) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->val = val; // 存储数值
newNode->type = NUMBER; // 标记类型为数字
return newNode;
}
实战演练：构建真实的语法树
光说不练假把式。让我们通过一个具体的例子来看看这些函数是如何协同工作的。
假设我们有一个表达式：a - b * c + d。
根据运算优先级，乘法 INLINECODEcbb062fd 优先级最高，其次是减法 INLINECODE31dd2e06，最后是加法 INLINECODE737edb5c。为了构建这棵树，我们可以按照如下顺序调用上述函数（这里 INLINECODE3f78141c, p2 等假设为符号表中的指针）：
- 构建
b * c：
Node* n1 = mknode(‘*‘, mkleaf_id("b", p2), mkleaf_id("c", p3));
- 构建
a - (b*c)：
Node* n2 = mknode(‘-‘, mkleaf_id("a", p1), n1);
- 构建
(a-b*c) + d：
Node* root = mknode(‘+‘, n2, mkleaf_id("d", p4));
最终形成的树结构清晰地展示了运算顺序：根节点是 INLINECODEf124cfa7，左子树包含 INLINECODE27418b60，而 INLINECODE9ebda61d 的右子树是 INLINECODE2a858d82。这种结构是后续代码生成的基础。
一个更复杂的例子
让我们看看带有括号的表达式：a * (b + c) - d / 2。
括号改变了树的结构。在这里，(b + c) 必须先被计算，形成一个子树。我们可以这样构建：
- 处理括号内的
b + c：
Node* n1 = mknode(‘+‘, mkleaf_id("b", pb), mkleaf_id("c", pc));
- 处理左侧乘法
a * n1：
Node* n2 = mknode(‘*‘, mkleaf_id("a", pa), n1);
- 处理右侧除法
d / 2：
Node* n3 = mknode(‘/‘, mkleaf_id("d", pd), mkleaf_num(2));
- 最后组合
n2 - n3：
Node* root = mknode(‘-‘, n2, n3);
通过这两个例子，你可以看到语法树如何完美地封装了运算符的优先级和结合性。
进阶：语法树的变体——有向无环图 (DAG)
如果你只掌握了语法树，你的编译器虽然能工作，但生成的代码可能不够高效。这就是我们要引入 DAG（Directed Acyclic Graph） 的原因。
#### 为什么我们需要 DAG？
想象一下，你的代码中有一个复杂的表达式重复计算了两次，比如 (a + b) * (a + b)。
- 在语法树中：INLINECODEa98a2044 这个子表达式会作为两棵完全独立的子树存在。这意味着编译器会生成两遍计算 INLINECODEc72ea8b1 的指令，浪费了 CPU 周期。
- 在 DAG 中：我们允许节点有多个“父”节点。INLINECODE0b79402b 只会计算一次，生成一个节点，然后 INLINECODE6e4b41b8 节点的左右指针都指向这个同一个节点。
这不仅仅是节省内存的问题，更重要的是公共子表达式消除，这是编译器优化中最基础也最重要的一环。
#### DAG 的结构特性
让我们看看 DAG 相比普通语法树有哪些独特的特性：
- 叶子节点的复用：如果变量 INLINECODEb81aa454 在多处被使用，DAG 中通常只有一个代表 INLINECODE8a3a8c5a 的节点，所有引用它的操作符节点都指向这同一个叶子。
- 内部节点的唯一性：对于每一个计算的值（如 INLINECODEe3715f82），在 DAG 中只有一个对应的节点。如果后续代码再次计算 INLINECODEaf319661，算法会直接复用该节点，而不是创建新的。
- 别名检测：DAG 能够很好地处理指针和别名关系，这是现代编译器优化中的难点。
#### 从语法树到 DAG 的转换实例
让我们看一段具体的代码序列，看看它是如何转化为 DAG 的。
代码序列：
T0 = a + b // 表达式 1
T1 = T0 + c // 表达式 2
构建过程：
- 处理 T0 = a + b：
– 我们创建或找到代表 INLINECODE8780aa66 和 INLINECODE5842036e 的叶子节点。
– 创建一个操作符节点 INLINECODE54f930c2，左子指向 INLINECODEff03e142，右子指向 b。
– 将这个 INLINECODE9158a784 节点标记为变量 INLINECODEad1d379e 的定义点。
- 处理 T1 = T0 + c：
– 我们需要 INLINECODEe3c4aa83。在 DAG 中，INLINECODEc8d5266b 实际上是指向刚才那个 + 节点的指针。
– 我们找到 c 的叶子节点。
– 创建一个新的 INLINECODE48aaee90 节点，左子指向 INLINECODE6877c06a 节点（即之前的 INLINECODE689358a9），右子指向 INLINECODE182140e6。
– 将这个新节点标记为 T1。
此时，DAG 隐式地记录了依赖关系：INLINECODEb3aa2f11 依赖于 INLINECODEa58f5434，而 INLINECODE2cc41914 依赖于 INLINECODE37bf6e6c 和 b。
深入底层：值编号方法
你可能会问：“我们如何在实际的代码中高效地构建 DAG？如果一个节点已经存在，我们怎么知道不需要再创建一个新的？”
答案就是值编号。
这是一种哈希表与数组结合的经典技术。它的核心思想是：给每个唯一的“值”或“表达式”分配一个唯一的整数 ID。当我们试图创建一个新节点时，我们先检查这个组合（例如，节点1是 INLINECODE546e994e，节点2是 INLINECODE00b7469b，操作符是 +）是否已经存在。如果存在，直接返回已存在节点的 ID。
#### 值编号的数据结构实现
我们可以维护一个三维数组或哈希桶来记录节点信息。假设我们使用基于数组的节点池：
// 节点记录结构体
struct NodeRecord {
int op; // 操作码或标签 (如 ‘+‘，或 ID/NUM 类型标记)
int left; // 左子节点的索引/值编号
int right; // 右子节点的索引/值编号
int value; // 如果是常数节点，存储数值；否则可能是符号表索引
// 其他字段...
};
// 全局节点数组
struct NodeRecord nodes[MAX_NODES];
int nodeCount = 0;
#### 值编号算法的逻辑
让我们手动模拟一个表达式 i = i + 10 的 DAG 构建过程。这是编程中极其常见的自增操作。
- 查找或创建叶子
i：
– 检查是否存在一个 ID 节点，值为 i 的符号表指针。
– 假设这是第一次见到 INLINECODE98d98490，我们创建节点 0：INLINECODEe40772f7。
- 查找或创建叶子
10：
– 检查是否存在值为 10 的常数节点。
– 创建节点 1：{op: NUM, left: -1, right: -1, val: 10}。
- 构建
+操作：
– 我们要找是否有这样的节点：INLINECODEfb978279 为 INLINECODE427e323c，INLINECODE4f7d9ecc 为 0 (节点i)，INLINECODE9fb5993f 为 1 (节点10)。
– 不存在。
– 创建节点 2：{op: ‘+‘, left: 0, right: 1, val: -1}。
- 构建赋值
=操作：
– 我们需要一个节点表示 INLINECODE864ca364。注意，这里 INLINECODE7d6493ee (节点0) 作为左操作数，结果 (节点2) 作为右操作数（或者反过来，取决于具体实现约定）。
– 创建节点 3：{op: ‘=‘, left: 0, right: 2, val: -1}。
通过这种值编号的方法，编译器不仅构建了树，还自动完成了去重。如果在后面又出现了 i + 10，算法会发现节点 2 已经存在，直接返回节点 2，避免了重复计算。
优化视角：为什么选择 DAG 而非简单的树？
作为开发者，我们需要权衡性能和复杂度。
- 代码生成效率：DAG 能够清晰地告诉我们哪些变量在基本块内被使用了，哪些变量被定义了（活跃变量分析）。这对于寄存器分配至关重要。
- 死代码消除：如果在 DAG 构建完成后，某个定义节点没有被任何后续节点引用，也没有被导出（Export，即基本块结束时还活着的变量），那么这个计算就是“死代码”，可以直接删除。例如：
a = b + c;
a = 5;
在 DAG 中，INLINECODE6d6e4b3a 的节点会被生成，但随后 INLINECODEbba98f0c 的指针会移动到常数节点 INLINECODEb5aa7350。如果 INLINECODE70d93a8c 没有其他用途，它在生成汇编代码时就会被忽略掉。
常见误区与最佳实践
在实际的编译器项目中，有几个陷阱需要你特别注意：
- 数组和指针的副作用：DAG 假设节点是纯净的。但是，如果代码中有数组赋值 INLINECODE11c9c80a 或者指针操作 INLINECODE887a2881，我们可能无法确定
a + b的结果是否会被覆盖。在这种情况下，我们必须简化 DAG 构建，例如将数组引用视为叶子节点，而不是内部操作符节点，以确保安全性。
- 函数调用：函数调用可能会产生副作用（修改全局变量）。在遇到函数调用节点时，通常需要“杀死”所有依赖于内存的缓存节点。
- 性能平衡：构建 DAG 需要额外的哈希表查找和维护开销。对于非常短的表达式，简单的递归下降遍历生成语法树可能更快。通常在基本块 的范围内构建 DAG 是性价比最高的选择。
总结与展望
今天，我们深入探讨了编译器设计中用于表示程序结构的两种核心形式：语法树及其更高级的变体——有向无环图（DAG）。
我们了解到：
- 语法树通过 INLINECODE9ef1445a 和 INLINECODE8d847fab 等函数将代码结构化。
- DAG 通过共享公共子表达式，提供了比语法树更紧凑的表示，是实现局部优化的关键数据结构。
- 值编号算法是实现 DAG 构建的高效手段，利用哈希思想确保节点的唯一性。
掌握这些概念，不仅有助于你理解现有的编译器工作原理，如果你正在尝试编写自己的 DSL（领域特定语言）或解释器，这些技巧更是必不可少的。
接下来，建议你可以尝试查看开源项目（如 LLVM 或 LuaJIT）的源码，看看现代工业级的编译器是如何在内存中维护这些中间表示（IR）的。继续保持好奇心，编译器的设计世界充满了精妙的逻辑之美！