编译器

1957 年，约翰·巴克斯（John Backus）领导的 IBM 团队发布了第一个 FORTRAN 编译器，把人类用代数公式写的代码翻译成 IBM 704 的机器指令。当时许多程序员不相信这会有用——他们断言，编译器产生的代码不可能比手写的汇编快，而速度就是一切。

他们错了。FORTRAN 编译器产生的代码的效率让大多数手工汇编程序黯然失色，并且写 FORTRAN 代码只需要手写汇编代码时间的几分之一。编译器就此成为计算机历史上最具杠杆效应的工具之一。

破除误解：编译器不只是"翻译机器"#

把编译器理解为"把源代码翻译成机器码的工具"在技术上没错，但遮蔽了它最有趣的部分：编译器是理解程序意图的工具，能够在翻译过程中对程序进行大量变换和优化，使结果比原始代码更快、更安全。

现代编译器（如 GCC、Clang/LLVM）会做这些事： - 消除死代码（永远不会执行的代码） - 展开循环（把 for i in range(4) 展开成 4 次重复操作，避免循环开销） - 内联函数调用（把函数体直接替换到调用处，省去函数调用开销） - 推断变量的取值范围（利用类型信息生成更紧凑的代码） - 对向量化运算生成 SIMD 指令（用一条 CPU 指令同时处理 4/8 个数据）

这些优化通常对程序员透明，但对性能的影响是数倍甚至数十倍。

历史：从汇编到自动翻译#

1950 年代之前：裸机编程

早期程序员直接用二进制（0 和 1）或八进制数字写程序，后来出现了汇编语言（用助记符如 MOV、ADD 代表指令）和汇编器（把汇编指令翻译成机器码的简单工具）。但汇编仍然非常底层——程序员需要手动管理寄存器、跳转地址，不同机器的汇编完全不兼容。

1952 年：A-0，编译器的雏形

在 FORTRAN 之前五年，格蕾丝·霍珀（Grace Hopper）在 UNIVAC I 上做出了 A-0 系统：程序员写下子程序的编号序列，机器把磁带上的子程序找出来、填好参数、拼成可执行程序。按今天的标准它更像链接器而非编译器，但它第一次让机器替人做了"把符号变成指令"的工作。霍珀后来回忆，当时几乎没人相信计算机能自己"写程序"——多数人认为机器只能做算术。

1957 年：FORTRAN 的革命

巴克斯的 FORTRAN 项目花了三年（1954–1957）来说服 IBM 管理层这是值得做的事，并克服了计算机科学界普遍的怀疑主义。项目成功后，其他高级语言的编译器迅速出现：COBOL（1959）、LISP（1960）、ALGOL（1960）。

1960 年代–1970 年代：编译器理论的建立

这个时期，Noam Chomsky 对形式文法的研究（原本是语言学）被计算机科学家采纳，奠定了词法分析和语法分析的理论基础。Alfred Aho、Jeffrey Ullman 等人系统化了编译器的各个阶段：他们 1977 年的《Principles of Compiler Design》因封面有一条绿龙被称为"绿龙书"，而 1986 年由 Aho、Sethi、Ullman 合著、封面换成红龙的《Compilers: Principles, Techniques, and Tools》（即广为人知的"龙书"），至今仍是编译器课程的标准教材。

1987 年：GCC 与自由软件

此前编译器是昂贵的商业软件。理查德·斯托曼（Richard Stallman）为 GNU 计划写下 GNU C Compiler，1987 年发布第一个版本——这是第一个可自由复制、修改的成熟编译器，后来的整个 Linux 生态都建立在它提供的免费工具链之上。1997 年，不满官方开发进度的社区分叉出 EGCS 分支，两年后这个分叉被接纳回主线，成为 GCC 的新本体——这次"分叉吞并主干"也重塑了 GCC 的治理方式。

编译器的结构：五个阶段#

一个典型的编译器把源代码转换成机器码，要经历五个主要阶段。

这五个阶段在工程上常被归为三段：前端（词法、语法、语义分析——只懂语言，不懂机器）、中端（与机器无关的优化——只懂中间表示）、后端（代码生成——只懂机器，不懂语言）。这个划分不是学术洁癖，而是算术：M 种语言乘以 N 种机器，三段式把编译器的工作量从 M×N 降到 M+N。

1. 词法分析（Lexical Analysis）#

把源代码字符串分割成词法单元（Tokens）——有意义的最小单位。

x = 42 + y * 3
```
→ `[IDENTIFIER:x, ASSIGN:=, NUMBER:42, PLUS:+, IDENTIFIER:y, STAR:*, NUMBER:3]`

词法分析器（Lexer）通常用有限自动机（DFA）实现，由正则表达式描述词法规则。这是形式语言理论的直接应用：正则文法 ↔ 有限自动机 ↔ 词法规则。

2. 语法分析（Parsing）#

把词法单元序列组织成抽象语法树（AST, Abstract Syntax Tree），反映程序的结构。

    ASSIGN
    /    \
   x    PLUS
        /   \
      42   MULT
            /  \
           y    3
```

语法分析器（Parser）由上下文无关文法（CFG）描述语法规则，通常实现为递归下降分析器或 LR 分析器。如果源代码有语法错误（如括号不匹配），就在这个阶段被捕获。

3. 语义分析（Semantic Analysis）#

AST 语法正确，但不一定语义正确。语义分析检查： - 类型检查："hello" + 42 在静态类型语言中是类型错误 - 作用域检查：变量是否在使用前已声明 - 控制流分析：函数是否所有路径都有返回值

语义分析的输出是带有类型注解的 AST，或对 AST 的报错。

类型检查是语义分析里理论最深的部分，它本质上是把类型系统的规则机械地套在语法树上。有些语言的编译器走得更远：不只检查程序员标注的类型，还能推断类型——Haskell、OCaml 里一个标注都不写，编译器也能从用法反推出每个表达式的类型（Hindley–Milner 算法），推不出来才报错。类型系统越强，编译期能替程序员抓住的错误就越多；这句话的另一面是，类型系统越灵活，编译器能做的优化假设也越多。

4. 中间代码生成与优化#

直接从 AST 生成机器码很困难（机器太多样，优化在高层做更方便）。现代编译器先生成中间表示（IR，Intermediate Representation）——一种介于高级语言和机器码之间的抽象指令集。

LLVM IR 是一个著名的例子：

define i32 @add(i32 %a, i32 %b) {
  %result = add nsw i32 %a, %b
  ret i32 %result
}
```

在 IR 上做优化（而非直接在机器码上）的好处：一套优化算法可以被所有支持 LLVM 后端的语言（Rust、Swift、C/C++、Julia……）共享。

现代 IR 普遍采用 SSA（静态单赋值）形式：每个变量只允许被赋值一次，再次赋值就换一个新名字（x₁、x₂），分支汇合处用特殊的 φ 函数标明"这个值来自哪条路径"。SSA 由 IBM 研究院的 Cytron 等人在 1991 年系统化（发表于 ACM TOPLAS），它让"每个值从哪来"在 IR 里一目了然，常量传播、死代码消除这类分析因此从昂贵变得廉价。上面 LLVM IR 例子里的 %result 只被赋值一次——这不是巧合，是形式的要求。

常见优化：

优化趟次（pass）的执行顺序本身就是一门学问：内联会制造新的常量折叠机会，常量折叠又制造新的死代码，所以 GCC 和 LLVM 会把某些 pass 反复运行好几轮，直到收敛或预算耗尽。-O0 到 -O3 不是"优化力度"的连续刻度，而是几张不同的 pass 组合菜单——-O2 与 -O3 的差别，有时只是某几个激进 pass 开没开。

静态分析看不到的东西，可以让程序自己报告。Profile-Guided Optimization（PGO）分两步：先用插桩版本跑一遍代表性负载，记下哪些分支常走、哪些函数最热，再带着这份"体检报告"重新编译，让内联和代码布局全部服从实测数据。Google 的 AutoFDO（CGO 2016）把这套流程做到了生产环境：直接对线上机器采样硬件性能计数器，免去了插桩编译的部署成本，让仓库级应用也能常态化地吃上 FDO 的收益。

5. 代码生成#

把优化后的 IR 翻译成目标机器的汇编/机器码。这一步需要： - 寄存器分配：决定哪些变量放在寄存器（快），哪些放内存（慢）——这是一个 NP 完全问题，实际使用启发式算法 - 指令选择：为 IR 操作选择合适的机器指令 - 指令调度：重排指令顺序以利用 CPU 流水线，避免数据依赖导致的停顿

LLVM：现代编译器的基础设施#

2000 年，伊利诺伊大学的克里斯·拉特纳（Chris Lattner）开始开发 LLVM（Low Level Virtual Machine）。它不是一个编译器，而是一套编译器基础设施：一个模块化的 IR + 一组优化趟次（pass）+ 多种后端（x86、ARM、RISC-V、WebAssembly……）。

任何新语言只需要写一个"前端"（词法→语法→语义→生成 LLVM IR），就能免费获得 LLVM 的所有优化和所有后端支持。

这极大地降低了新编程语言的实现成本。使用 LLVM 的语言包括： - Rust（系统编程安全语言） - Swift（Apple 应用开发语言） - Julia（科学计算语言） - Kotlin/Native（Kotlin 的本地编译） - Crystal（Ruby 风格的静态类型语言）

拉特纳还领导了 Clang（C/C++/Objective-C 的 LLVM 前端），现在是 macOS 和 iOS 开发的默认编译器。

即时编译（JIT）：运行时的编译器#

传统编译（Ahead-of-Time，AOT）在运行前完成翻译；即时编译（JIT）在程序运行期间动态编译最热点的代码：

1. 程序开始以解释器运行（慢但启动快）
2. 分析器（Profiler）识别频繁执行的"热点"函数
3. JIT 编译器把热点函数编译为机器码（快）
4. 后续调用直接执行机器码

JIT 的独特优势：能利用运行时信息（如实际调用的类型、实际的分支频率）进行"投机优化"——如果猜测被推翻，退回到解释执行。

JVM（Java 虚拟机的 HotSpot JIT）、V8（JavaScript 引擎）、PyPy（Python JIT）都是典型的 JIT 系统。在某些基准测试中，JIT 编译的 Java 性能可以媲美甚至超过 C++——因为 JIT 能利用 AOT 编译器无法得到的运行时信息。

形式验证与正确性#

编译器本身有 bug 吗？当然有。编译器的 bug 是最危险的 bug 之一——因为编译器 bug 会静默地把正确的源代码编译成错误的机器码，而程序员通常不会怀疑编译器。

CompCert（2006）是第一个经过形式验证的 C 编译器：用 Coq 定理证明器证明了编译器的语义保持性——即编译后的代码行为与源代码在形式语义下完全一致。代价是性能（约为 GCC -O1 的速度），但在安全关键领域（航空、核电控制系统）这个代价是值得的。

但验证有边界。CompCert 证明的是"如果编译器本体和工具链可信，那么输出保持语义"；肯·汤普森（Ken Thompson）在 1984 年的图灵奖演说《Reflections on Trusting Trust》里指出了更深一层的漏洞。他演示了一个被动过手脚的 C 编译器：编译 login 程序时自动植入后门，编译编译器自身时又把这段恶意逻辑重新注入——源码再干净也没用，因为你审查的源码并不是你运行的二进制。这场演说留下的问题至今悬着：信任链的第一环该放在哪里。可复现构建（reproducible builds）是当前的务实回答——让独立第三方能从源码逐字节重建出同一个二进制，至少把"编译器被动了手脚"变成可检测的事件。

代价与争议#

优化的不透明性：激进的编译器优化有时会消除程序员认为必要的操作。经典案例：安全代码写了 memset(password_buf, 0, size) 来清除内存中的密码，但编译器发现这块内存此后不再被读取，就"优化掉"了这个 memset——密码留在内存里，被后续恶意代码读取。这需要程序员使用 memset_s（C11 标准保证不被优化掉）或 volatile 关键字。

严格别名规则的停战协议：C 标准允许编译器假设"不同类型的指针不指向同一块内存"，并据此做激进优化。Linux 内核大量代码故意打破这个假设（类型双关是系统编程的惯用手法），于是内核选择用 -fno-strict-aliasing 编译——相当于与编译器签下停战协议：这部分优化你别做。Torvalds 多年来反复批评的正是这类心态：编译器开发者把"标准允许"当成了"应该如此"。

未定义行为的危险：C/C++ 的"未定义行为"（undefined behavior，UB）——如整数溢出、空指针解引用、无效内存访问——理论上可以被编译器以任何方式处理，包括删除包含 UB 的整个代码路径。现实中，编译器的 UB 利用导致了许多难以追踪的安全漏洞。Rust 语言的诞生，很大程度上就是对 C/C++ UB 泛滥问题的回应。

编译器成了安全防线的一部分：2018 年 Spectre 系列漏洞曝光后，一部分修补工作落到了编译器头上——LLVM 和 GCC 学会了生成 retpoline（用返回指令改写间接跳转，让分支预测器猜不到真正目标）、在关键路径插入投机屏障。代价是真实存在的：开启全套缓解措施后，某些负载的性能损失可达两位数百分比。这是编译器史上罕见的时刻——优化器被用来故意让代码慢下来，换取不被偷看。

跨域连接#

• 形式化方法与程序验证：编译器的缺陷会静默地把正确源码译成错误机器码，而程序员几乎不会怀疑它——这种"出错无声"的性质，使它成为少数值得付出完整证明代价的组件。但被证明的是编译成功时的语义保持，不是生成代码没有缺陷。推论是：值得验证的不是代码量最大的部分，而是错误最难被察觉的部分。
• 句法学：形式文法的层级把表达能力与识别机器一一对应：正则对应有限自动机，上下文无关对应下推自动机。可检验推论：一旦语言把某个特性做成上下文相关，分析器就必须把语义信息回喂给语法阶段，分层随之破裂。
• 蒯因：翻译不确定性逼人先说清什么算"意义保持"。编译器给出了一个精确答案：只保证可观察行为等价，寄存器分配与指令顺序不在其列。那次用于清除密码的内存写被优化掉，正因为它落在这个可观察集合之外。对策不是指望编译器手下留情，而是改用标准承诺不会被优化掉的写法。
• 图论：寄存器分配是图染色，颜色数就是可用寄存器数，因而是 NP 完全问题，实践中只能用启发式。染不上色的变量必须溢出到内存——所谓"寄存器不够用"，形式上就是图的色数超过了硬件给的颜色。
• 平台经济学：中间表示把前端乘后端的工作量降成前端加后端，这是通用中间品的典型收益。代价同样典型：所有依附其上的语言共享同一套优化偏好与同一批缺陷，生态越大，换掉它的成本越高。推论是：新语言的实现门槛被大幅拉低，它的性能上限也被这套中间层框住了。

参考文献#

• Aho, A., Lam, M., Sethi, R. & Ullman, J. Compilers: Principles, Techniques, and Tools (龙书，第 2 版). Addison-Wesley, 2006.
• Cytron, R. et al. Efficiently Computing Static Single Assignment Form and the Control Dependence Graph. ACM TOPLAS 13(4), 1991.（SSA 形式的奠基论文）
• Thompson, K. Reflections on Trusting Trust. Communications of the ACM 27(8), 1984.（图灵奖演说，编译器信任问题）
• Lattner, C. & Adve, V. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. CGO 2004.（LLVM 的原始论文）
• Leroy, X. Formal Certification of a Compiler Back-End. POPL 2006.（CompCert 的论文）
• Chen, D., Li, D. X. & Moseley, T. AutoFDO: Automatic Feedback-Directed Optimization for Warehouse-Scale Applications. CGO 2016.
• Appel, A. W. Modern Compiler Implementation in ML. Cambridge University Press, 1998.（面向函数式语言视角的经典教材）