元数据卡

• 前置知识：第6章（语法分析与 AST）
• 预计时间：50 分钟
• 核心难度：进阶
• 阅读模式：高度专注（建议 50 分钟+）
• 完成标志：能解释类型检查和符号表的作用，能描述三地址码和 SSA 的核心思想

AST 看起来就是代码，但编译器还不会"理解"它。比如 x = "hello" * 42——语法分析能通过，因为它满足文法规则。但你知道这行代码没有意义——你不能把字符串和整数相乘。你能感觉到这一点，因为你知道类型。编译器也需要有这样的"感觉"。

---

你的进度

你的编译器前端已经完成了词法分析和语法分析。你得到了一棵 AST，上面挂满了节点，但还没有"语义"信息——类型、作用域、变量可见性。这一章你在 AST 上做语义分析，最终把它转化为一种"可有效运算"的中间表示，供下一阶段用。

---

你的任务

你为编译器添加"理解"能力。你会遍历 AST，跟踪每个变量的类型（符号表）、检查表达式类型是否匹配（类型检查）、处理作用域嵌套。然后把这些语义信息抹平——将 AST 转化为一条条线性指令序列，这就是中间代码。你会学到三地址码和 SSA（静态单赋值）这两种最广泛使用的中间表示形式。

---

破局 · 溯源

你拿到了一段代码的 AST：

(function_decl
  name: "add"
  params: (a: int, b: int)
  body: (return (binop + a b))
)

它在语法上完美无缺。但你还需要回答这些问题：

• a 和 b 是什么类型？（去问参数声明）
• a + b 的类型合法吗？（两个 int 相加 = int，合法）
• 返回值类型和声明匹配吗？（声明隐含 int -> int，匹配）
• a 和 b 在这个作用域中可见吗？（可见，在同一函数内）

符号表

符号表（Symbol Table）是你用来记录"变量名 -> 类型 + 其他信息"的映射。编译器在遍历 AST 时维护一个符号表栈：

当进入一个新的作用域（如函数体或代码块 { }），你在栈顶压入一个新的符号表。当离开作用域时，弹出。

符号表栈在执行到函数体"add"内部时：

栈顶: { a: int, b: int }   ← 当前作用域
栈底: { printf: (char*, ...) -> int }  ← 全局作用域

名字查找从栈顶往下找——先查当前作用域，找不到查外层，直到全局。这正是变量遮蔽（shadowing）的模型。

类型检查

在遍历 AST 节点时，对每个表达式节点检查子节点的类型和操作符是否兼容：

操作符	左类型	右类型	结果类型
+	int	int	int
+	float	float	float
+	int	float	float（隐式转换）
+	int *	int	非法
==	任意 T	T	int

类型检查的函数看起来像递归下降，但它在 AST 上工作，不是在 token 流上：

Type check_expr(ASTNode *node, SymTable *st) {
    switch (node->type) {
        case NODE_NUM:
            return TYPE_INT;
        case NODE_ID:
            return lookup_type(st, node->data.name);
        case NODE_BINOP:
            Type left_t = check_expr(node->data.binop.left, st);
            Type right_t = check_expr(node->data.binop.right, st);
            if (!compatible(left_t, right_t))
                error("type mismatch at %s", node->location);
            return result_type(node->data.binop.op, left_t, right_t);
        // ...
    }
}

从 AST 到中间代码：三地址码

AST 是一棵树，但计算机执行的是线性指令序列。三地址码（Three-Address Code, TAC）就是介于树和机器码之间的折中——每条指令最多有三个地址（两个操作数，一个目标）。

AST 节点： (a + b) * c

对应的三地址码：
  t1 = a + b
  t2 = t1 * c

每条指令处理一个基本运算。"三地址"的意思是两个源加一个目标。编译器引入临时变量（t1, t2）来保存中间结果。这样每条指令都很"原子"——一次运算，一个结果。

TAC 指令类型通常包括：

t = x op y        // 二元运算
t = op x          // 一元运算
t = x             // 赋值
goto L            // 无条件跳转
if x relop y goto L  // 条件跳转
param x           // 传参
call f, n         // 函数调用（n 个参数）
ret x             // 返回
t = &x            // 取地址
t = *p            // 指针解引用
*p = t            // 指针赋值

你要做的就是递归遍历 AST，对每个 AST 节点生成对应的 TAC 指令序列。遍历顺序就是代码执行顺序。

SSA：静态单赋值

三地址码的一个升级版本是 SSA（Static Single Assignment）。核心思想很简单：每个变量只被赋值一次。

TAC 版本：
  t1 = a + b
  t2 = t1 * c
  t1 = t2 + d     // 重新赋给 t1——SSA 不允许这样

SSA 版本：
  t1 = a + b
  t2 = t1 * c
  t3 = t2 + d     // 必须用新名字

当控制流汇合时（比如 if-else 的两条分支结束后），SSA 使用一个特殊的 φ（Phi）函数来"选择"变量的取值：

if (cond)
  x1 = 1
else
  x2 = 2
x3 = φ(x1, x2)    // 运行时选择是 x1 还是 x2

SSA 的好处：让数据流分析变得极其简单——你永远知道一个变量的"唯一定义点"。优化器因此可以做常量传播、死代码消除等操作，而不需要复杂的数据流分析。

---

第一层：够用——写一个最小的类型检查器 + TAC 生成器

你可以把一个只含整数加减乘除、没有类型错误的"安全表达式"翻译为 TAC：

int tac_temp = 0;

char* new_temp() {
    char buf[16];
    snprintf(buf, 16, "t%d", tac_temp++);
    return strdup(buf);
}

void gen_tac(ASTNode *node) {
    if (node->type == NODE_NUM) {
        // 数字的"结果"就是它自己
        return;
    }
    if (node->type == NODE_BINOP) {
        gen_tac(node->data.binop.left);
        gen_tac(node->data.binop.right);
        char *t = new_temp();
        printf("%s = %s %c %s\n", t,
            node->data.binop.left->result,
            node->data.binop.op,
            node->data.binop.right->result);
        node->result = t;
    }
}

这个简单函数打印出来的就是 TAC。对 (a + b) * c 会输出：

t0 = a + b
t1 = t0 * c

第二层：深入——为什么编译器要引入多个中间表示

现代编译器通常不止一个 IR。Clang/LLVM 的流水线是：

C source → AST（Clang）→ LLVM IR（SSA）→ Machine IR → 汇编

每层 IR 丢了上层不需要的信息，添了下层需要的细节。AST 保留变量名和类型；变成 LLVM IR 时就变成了 SSA 形式的虚寄存器；到 Machine IR 时，虚寄存器被映射到真实硬件寄存器。逐层降级的思路让你在每个阶段只用刚好够用的数据。

---

常见陷阱

陷阱1：以为类型检查只在变量声明时做。 类型检查本质上是递归过程——对每个表达式节点做。f(1, "hello") 在调用时检查，不是在 f 声明时检查。

陷阱2：在中间代码生成阶段混淆"左值"和"右值"。 a = b 中，左边 a 是地址（左值），右边 b 是值（右值）。a = a + 1 中，右边的 a 是读值，左边的 a 是写地址。TAC 生成时必须区分：左边生成"地址表达式"，右边生成"值表达式"。

陷阱3：SSA 的 φ 函数不是"执行的指令"。 φ 实际上是概念上的"选择器"，表示运行时控制流汇合时变量的来源。它不对应真实的 CPU 指令——寄存器分配时会消除 φ 函数，转化为 move 指令。

---

通关挑战

• 热身（5分钟）： 把下面这段代码转换为 AST → TAC：int x = 10; int y = x * 2 + 5;

• 挑战（30分钟）： 扩展上面的 TAC 生成器，增加 if-else 分支结构。需要为分支生成两个代码块，并通过跳转指令连接。输入 if (a > b) c = a; else c = b; 应当生成包含条件跳转和标签的三地址码。

• 观察： 在 LLVM 中运行 clang -S -emit-llvm example.c，查看生成的 .ll 文件。注意它的 SSA 形式——每个变量名前的 % 标识，phi 指令，以及 load/store 指令的界面。

---

旅人笔记

语义分析在 AST 上赋予代码"意义"——类型检查、作用域解析；中间代码（三地址码/SSA）将树形结构铺平为线性指令序列，这是优化和代码生成的基础。

---

下一站预告

AST 变成了 TAC 或 SSA，你已经可以从源代码"理解"到线性代码了。但这条线性代码很粗糙——它用了比实际需要多得多的临时变量和指令。最后一章你来做代码生成与优化，让它真正能在目标机器上高效运行。