「语义分析与中间表示」

1. 语义分析的作用

一句话总结： 语义分析把语法结构绑定到符号与类型信息，拒绝编译违反语言规则的代码。

语法分析只保证结构合法，不保证意义正确。a + b 在语法上永远成立，但若 a 是字符串而 b 是数组，语义检查应当报错。语义分析遍历 AST，为每个名字建立绑定、为每个表达式推导类型、为每个语句验证控制流约束，并在合适时机输出带标注的语法树与中间表示。

AST（含语义标注）:
  Assign(id:a:var_int,
         Add(id:b:var_int,
             Lit(10:int)))

IR:
  t1 = b
  t2 = 10
  t3 = t1 + t2
  a  = t3

语义分析的输出既可以直接进入解释器，也可以进入中间表示生成。对于静态类型语言，语义分析集中在编译早期完成；对于脚本语言，类型信息往往推迟到运行时。中间表示则把机器无关的分析固化下来，成为优化与代码生成的公共底座。

2. 符号表设计

一句话总结： 符号表是名字到属性的映射，结构设计决定作用域查找与增量更新的效率与正确性。

符号表保存每个名字的类型、作用域、存储位置与常量性。最简单的实现是哈希表，但块级作用域要求进出块时保存与恢复状态。常见做法是用作用域栈：每进入一个块压入一层表，离开时弹出。查找时从栈顶向下逐层搜索，保证内层名字遮蔽外层同名名字。

class Scope:
    def __init__(self, parent=None):
        self.parent = parent
        self.symbols = {}

    def define(self, name, info):
        self.symbols[name] = info

    def lookup(self, name):
        if name in self.symbols:
            return self.symbols[name]
        if self.parent:
            return self.parent.lookup(name)
        return None

class SymbolTable:
    def __init__(self):
        self.stack = [Scope()]

    def enter(self):
        self.stack.append(Scope(self.stack[-1]))

    def leave(self):
        self.stack.pop()

    def lookup(self, name):
        return self.stack[-1].lookup(name)

带函数嵌套的语言如 Pascal 需要在符号表中记录活动记录链，支持闭包的语言则要区分定义时环境与调用时环境。多线程编译器还会在符号表上做并发访问控制，或用只读不可变表配合增量编译。符号表不仅是查名字，还要能回答方法重载、泛型实例化等高级查询。

3. 作用域与名字解析

一句话总结： 作用域规则决定名字绑定的可见窗口，词法作用域以静态文本结构为界，动态作用域以调用链为界。

大多数现代语言采用词法（静态）作用域：一个名字的绑定由它在源码中的嵌套位置决定，与调用路径无关。名字解析从最内层作用域向外层逐级查找，找到最近的一个绑定即停止。若解析发生在声明之前，语言需要规定前向引用的规则，例如函数声明可后置、变量声明不可后置。

def resolve_names(ast_root):
    env = Scope(global_scope)
    def walk(node, env):
        if node.kind == "Decl":
            env.define(node.name, node)
            for child in node.body:
                walk(child, env)
        elif node.kind == "Ref":
            sym = env.lookup(node.name)
            if sym is None:
                raise SemanticError(
                    f"undefined name {node.name} at {node.loc}")
            node.symbol = sym
        else:
            for child in node.children:
                walk(child, env)
    walk(ast_root, env)

名字遮蔽是常见语义缺陷来源：内层声明意外遮蔽外层变量导致读到的值不对。编译器的做法是给出 warning 或 require explicit qualification。还有一类问题是名字查找跨越了不该跨越的边界，例如误入全局命名空间，此时模块系统的作用域隔离设计就显得关键。语义分析结束后，每个引用节点都应指向唯一的符号定义。

4. 类型检查与类型推断

一句话总结： 类型系统用静态规则约束值的使用方式，类型检查在编译期验证这些约束。

类型检查遍历 AST，为每个表达式推导类型并验证运算合法性。整数与浮点相加是否需要隐式转换、数组下标是否必须是整数、函数返回值是否与声明一致，都是类型规则要回答的问题。类型推断允许省略部分类型标注，由编译器根据上下文推导，Hindley-Milner 类型推断是函数式语言的典型方案。

def infer(node, env):
    if node.kind == "Lit":
        node.type = literal_type(node.value)
    elif node.kind == "Ref":
        node.type = env.lookup(node.name).type
    elif node.kind == "BinOp":
        left = infer(node.left, env)
        right = infer(node.right, env)
        if not compatible(left, right):
            raise TypeError(
                f"type mismatch {left} vs {right} at {node.loc}")
        node.type = promote(left, right)
    elif node.kind == "Call":
        fn = infer(node.callee, env)
        node.type = fn.return_type
    return node.type

类型检查的难点在用户定义类型与泛型。泛型函数的类型参数在调用时被实例化，编译器要维护类型变量的替换环境。联合类型与代数数据类型要求模式匹配穷尽性检查。类型推断的实现核心是约束收集与合一（unification），把待定类型变量与已知类型做一致化替换。

4.1 合一与泛型实例化

合一算法把两个类型表达式通过替换变成相同形式：对待定类型变量尝试绑定为具体类型，冲突则失败。泛型函数 T -> T 的调用 f(3) 令 T 与 int 合一，返回类型也随之实例化为 int。实现上类型变量用不可变替换环境记录，嵌套推导需要沿替换链解析到最终类型。

def unify(t1, t2, subst):
    t1 = resolve(t1, subst)
    t2 = resolve(t2, subst)
    if isinstance(t1, TypeVar):
        subst[t1.name] = t2
        return True
    if isinstance(t2, TypeVar):
        subst[t2.name] = t1
        return True
    if isinstance(t1, Arrow) and isinstance(t2, Arrow):
        return unify(t1.arg, t2.arg, subst) and \
               unify(t1.ret, t2.ret, subst)
    return t1 == t2

# 实例化: id(3) 令 T = int
#   id: forall T. T -> T
#   应用 id 于 int: T 替换为 int → int -> int

5. 中间表示的选择

一句话总结： 中间表示位于源码与目标机之间，设计权衡决定优化能力与移植性。

中间表示（IR）架起前端与后端。高层 IR 贴近 AST，便于做类型与别名相关的分析；低层 IR 贴近目标机，便于做寄存器分配与指令选择。三地址码是经典线性 IR，每条指令形如 x = y op z，最多一个运算符。SSA 是带上唯一赋值性质的 IR，每个变量只被赋值一次，简化数据流分析。

三地址码:
  t1 = a
  t2 = t1 + 1
  a  = t2

SSA 形式:
  a_1 = a_0
  a_2 = a_1 + 1
  a_3 = phi(a_0, a_2)

LLVM 的 IR 采用静态单赋值与显式控制流图，兼顾分析与后端复用；GCC 历史上用 GIMPLE 类似机制。解释器常用字节码直接执行，JIT 编译器常把字节码转成低层 IR 再优化。中间表示的层次选择是架构决策：单层 IR 实现简单，多层 IR 优化空间大但工程成本成倍增加。

6. 三地址码生成

一句话总结： 三地址码把表达式拍平为带临时变量的指令序列，是后续控制流图与优化的基础。

三地址码生成自语义标注的 AST。每个二元运算分配一个临时变量保存结果，运算的嵌套被展开成直线指令序列。函数调用、数组访问、指针解引用等在内存或寄存器层面都有专门的三地址指令形式。标签用于标记跳转目标，条件跳转配合比较指令表达控制流。

def gen_expr(node, temps):
    if node.kind == "Lit":
        t = temps.new()
        emit(f"{t} = {node.value}")
        return t
    if node.kind == "BinOp":
        l = gen_expr(node.left, temps)
        r = gen_expr(node.right, temps)
        t = temps.new()
        emit(f"{t} = {l} {node.op} {r}")
        return t
    if node.kind == "Ref":
        return node.name

# 生成的指令示例
# t1 = 10
# t2 = b
# t3 = t1 + t2
# a  = t3

临时变量分配要注意生命周期：用完即可复用，避免无谓膨胀。三地址码生成过程中的临时变量数量会影响后续优化，但现代编译器通常让临时变量命名唯一，交由优化阶段再做命名消解与活跃分析。标签编号与基本块划分也在生成时同步记录。

6.1 语句的翻译

语句翻译负责把条件、循环与过程调用展开为带标签的控制流。if 翻译为比较与条件跳转加两个标签；while 翻译为条件测试、循环体与回跳标签；函数调用翻译为参数放置、调用指令与结果接收。翻译过程的标签表需要统一分配，避免不同语句的标签冲突。

if a > 0 then x = 1 else x = 2

  t1 = a
  if t1 > 0 goto L1
  x = 2
  goto L2
L1:
  x = 1
L2:

7. 控制流图与 SSA

一句话总结： 控制流图显式表达基本块之间的跳转关系，SSA 让每个变量只有一个定义点。

控制流图（CFG）把三地址码划分为基本块：块内指令顺序执行、块间以跳转相连。基本块划分的依据是跳转目标与跳转源。CFG 是数据流分析、循环识别与优化的骨架。SSA 形式要求每个变量恰有一个定义点，程序点上的变量用版本号区分，控制流汇合处用 φ 函数合并多个来源的值。

基本块 B1:  t1 = a
            if t1 > 0 goto B3
基本块 B2:  t2 = 0
            goto B4
基本块 B3:  t2 = 1
基本块 B4:  x = phi(t2_B2, t2_B3)

SSA 下每个 t2 都有唯一版本，phi 合并两路值。

把普通三地址码转成 SSA 需要做支配树计算与 φ 函数插入。反向转化（恢复非 SSA）发生在寄存器分配前，因为物理寄存器没有版本概念。SSA 上实现的常量传播、全局值编号与死代码消除都比非 SSA 形式简单且精确，这也是 LLVM 与 GCC 把 SSA 作为主要分析 IR 的原因。

8. 总结

语义分析与中间表示把源码从结构提升到意义，让机器可理解的数据结构取代人写文本。中间表示的质量直接决定后续优化的天花板。下一站将在这层 IR 上施展各种优化手段。

延伸阅读

• 词法分析器实现
• 语法分析与 AST 构建
• 中间代码优化
• 目标代码生成
• 解释器与 JIT 编译