编译流程

从字符流到机器码，编译器把翻译分成若干阶段，每个阶段只依赖前一阶段的输出。本章讲每个阶段的任务与经典算法，以及 LLVM 如何把前端与后端解耦（→ 指令集架构）。

流水线全景

\text{字符流} \xrightarrow{\text{词法}} \text{token 流} \xrightarrow{\text{语法}} \text{AST} \xrightarrow{\text{语义分析}} \text{带类型 AST/IR} \xrightarrow{\text{优化}} \text{优化后 IR} \xrightarrow{\text{代码生成}} \text{目标码}

阶段	任务	经典算法/技术
词法分析	字符 → token	有限自动机（DFA）、正则表达式
语法分析	token → AST	递归下降、LR/LALR
语义分析	类型检查、符号表、作用域	属性文法、符号表
中间表示	翻译到 IR	三地址码、SSA
优化	改写 IR（不改变语义）	数据流分析、循环优化
代码生成	IR → 目标码	指令选择、寄存器分配

词法与语法分析

词法分析把字符流切成 token（标识符、关键字、字面量）——词法分析器就是一个 DFA（→ 有限自动机与正则语言）：正则表达式描述 token，自动机执行匹配。

语法分析把 token 流组成 AST（→ 语法与语义）：

递归下降：文法直接映射为函数，手工书写直观，现代编译器主流（Clang、Go）；
LR/LALR：表驱动、自动生成（yacc/bison），处理更大的文法类，报错信息较差。

两者的分界是文法类与工程偏好：LL(1) 用递归下降，LR(1) 类用表驱动。

中间表示与 SSA

**中间表示（IR）**是前端与后端之间的通用语言。现代主流是 SSA（静态单赋值）：每个变量只赋值一次，合流点用 φ 函数选择。SSA 形式让很多优化变简单——"哪个定义到达这里"在 SSA 下是显式的，常量传播、死代码消除、公共子表达式都变成直接的图问题。

; x 的 SSA 形式：每次赋值都是新名字
define i64 @sum(i64 %n) {
entry:
  br label %loop
loop:
  %i = phi i64 [0, %entry], [%next, %body]
  %s = phi i64 [0, %entry], [%acc, %body]
  %next = add i64 %i, 1
  %acc = add i64 %s, %i
  %cond = icmp slt i64 %next, %n
  br i1 %cond, label %body, label %exit
body:
  br label %loop
exit:
  ret i64 %s
}

优化与代码生成

优化在不改变可观察行为的前提下改写 IR（下一章展开，→ 编译器优化）。

代码生成两步：

指令选择：IR 模式 → 机器指令（树模式匹配）；
寄存器分配：把无限个虚拟寄存器映射到有限的物理寄存器。寄存器分配是 NP 难的，用启发式——图着色（干涉图：同时活跃的变量不能共用寄存器，着色即分配）或线性扫描（JIT 常用，快但次优）。

LLVM 与解耦

前端—IR—后端的分离让 N 种语言 × M 种目标只需 N+M 个组件，而不是 $N \times M$ 个编译器。LLVM 提供中间的 IR 与后端（指令选择、寄存器分配、目标码），前端只负责把语言翻译到 LLVM IR：Clang（C/C++）、Rust（rustc）、Swift、Julia 共享同一个后端。JIT 语言（Julia、JVM 系）也用 LLVM 生成机器码。这个解耦模式——统一的中间表示 + 可替换的前后端——是编译器基础设施的通用设计，也解释了过去十年新语言爆发的工程原因（后端免费了）。

本章要点

阶段化是编译器的组织原则：词法（DFA）→ 语法（递归下降/LR）→ 语义 → IR → 优化 → 生成
SSA 形式让很多优化变简单：单赋值使数据流显式化
寄存器分配是 NP 难的，用启发式：图着色或线性扫描
前端—IR—后端分离：N 种语言 × M 种目标只需 N+M 个组件（LLVM 模式）