编译器的诞生：从Grace Hopper的传奇讲起

第 1 章 编译器的诞生：从 Grace Hopper 的传奇讲起

1957 年 4 月，IBM 在加州圣何塞发布了一份薄薄的技术报告，编号 C-28。封面上的第一行作者署名是 "J. W. Backus and others"，后面跟着 10 位工程师的名字，其中几位是女性——在当时以男性为主导的计算机行业里，这本身就是一个不太寻常的信号。这份报告描述了世界上第一个真正承担"编译"二字的高级语言系统：Fortran I。它用了 18 人·月、运行在 IBM 704 大型机上、产出了第一段与手写汇编性能相当的自动生成代码。这一事件，是软件工程史的分水岭，也是本书的起点。

然而，要公正地讲清楚"编译器的诞生"，我们必须把时间再往回拨五年——回到 1952 年，一位名叫 Grace Hopper 的海军军官在 UNIVAC I 上写下了 A-0 系统。

1.1 从 A-0 到 Fortran I：两位先驱与两次跨越

Grace Hopper 的故事几乎已经成为计算机史的标准注脚，但她真正做到的事情常被误解。1952 年的 A-0 并不是"编译器"——至少不是我们在 2025 年使用这个词时所指的那个东西。A-0 的本质是一段子程序库：给定一段形如 `0 0 0 0 5 6 7` 的"伪代码"，它会把数字对 `(0, 0)`、(5, 6)、(7) 解释为子程序编号和参数，调用对应的机器码片段并拼接起来。换言之，A-0 是一个自动链接器 + 符号替换器。Hopper 的真正洞察并不是"写出编译器"，而是意识到"高级符号 → 机器码"这件事可以机械地完成——而这种机械性，才是后来所有编译技术的胚芽。

这个胚芽在 1954 年被另一位 IBM 工程师 John Backus 接住。他那时 29 岁，是 IBM 一名数学研究员，对硬件和软件都抱有强烈的不满：程序员用机器码或汇编写程序，效率低、不可移植、错误率高。他向 IBM 管理层提交了一份提案，核心论断是：自动生成代码的性能可以接近手写汇编。这个论断在当时几乎是异端。IBM 的老派工程师们嗤之以鼻：让机器自动写出和人类手写一样快的代码？怎么可能。

Backus 没有被吓退。他组了一个 10 人的团队，团队里有 Lois Mitchell、Irene Fithian、Sheldon Best、Harlan Herrick、Peter Sheridan、Robert Nelson、Richard Goldberg、David Sayre、Roy Nutt 和他自己。1957 年 4 月，Fortran I 在 IBM 704 上发布。报告里那个著名的"18 人·月"指的是从立项到首个可运行版本的累计工时，但更准确的数字是：从 1954 年提案到 1957 年发布，前后历时近三年，团队规模在 10–14 人之间波动。

为什么 Fortran I 的成就是分水岭？因为它第一次证明了 Hopper 胚芽的正确性：机器写出的代码，可以和人类写的一样好。Backus 团队在编译器里塞入了一个当时让人震惊的优化器——它能自动做寄存器分配、公共子表达式删除、循环不变代码外提。这些优化在今天看来稀松平常，但在 1957 年，它们意味着 Fortran 程序可以达到手写汇编 90% 以上的性能。机器第一次成为程序员的"合格协作者"，而不仅仅是"指令执行器"。

这个判断奠定了接下来 70 年编译器技术的根基：编译器的价值不在于把高级语言翻译成机器码，而在于把人类意图高效地映射到硬件。前者只是后者的一种实现方式。如果我们把"意图→硬件映射"看作目的，那么编译器、解释器、即时编译器、数据库查询优化器、深度学习算子编译器、硬件综合工具，就都站在了同一条血脉上——它们都是"变形器"，只是起点和终点不同。

1.2 现代编译器的三段式骨架：前端、优化器、后端

Backus 的 Fortran I 是一团庞大的整体——词法分析、语法分析、语义分析、优化、代码生成全部混在一起，没有清晰的边界。这种"单体"结构在 1960–1970 年代被逐步打破，最终沉淀为我们今天几乎所有现代编译器都采用的三段式架构：前端 (Frontend)、优化器 (Optimizer / Middle-end)、后端 (Backend)。

理解这三段的关键，是理解它们各自操作的"中间表示"（Intermediate Representation, IR）：

• **前端** 把源代码从人类可读的形式，转换成编译器可推理的形式。终点通常是一份富含语义信息的 IR（例如带有类型信息的 AST + 控制流图）。前端只关心"这个程序在说什么"，不关心"它要跑在什么机器上"。
• **优化器** 接手前端的 IR，做一系列**与目标机器无关**的等价变换。删除冗余计算、展开循环、内联函数、传播常量、向量化——这些变换在不同硬件上都有价值，所以被独立出来。优化器的存在让"一套优化，多个后端"成为可能。
• **后端** 把优化后的 IR 映射到具体的目标机器。指令选择、寄存器分配、调用约定、栈帧布局、机器码发射——这些决策完全依赖于硬件。x86-64、ARM64、RISC-V、WebAssembly、GPU 的 PTX/SPIR-V，每一个目标都需要一个独立的后端。

这种"三段式"并不是一开始就有的。它的形成是 30 年工程演化的结果。1970 年代 Niklaus Wirth 提出了基于自展 (bootstrapping) 和表格驱动代码生成的方法论。1987 年 GCC 发布，开始在中间层引入 RTL（Register Transfer Language）作为通用 IR。2003 年 LLVM 论文发表，把 SSA (Static Single Assignment) 形式作为中端 IR 的事实标准固化下来。今天的 Clang/LLVM 几乎可以被视为"三段式哲学"的教科书实现。

下面这张图描绘了 LLVM 风格的三段式架构，是后续章节展开讨论的宏观地图：

```mermaid flowchart LR Src[源代码] --> Lex[词法分析] Lex --> Tok[Token 序列] Tok --> Parse[语法分析] Parse --> AST[AST] AST --> Sema[语义分析] Sema --> Typed[类型化 AST] Typed --> IRGen[IR 生成] IRGen --> IR[LLVM IR] IR --> Opt[优化 Pass 链] Opt --> OptIR[优化后 IR] OptIR --> Sel[指令选择] Sel --> Reg[寄存器分配] Reg --> Emit[代码发射] Emit --> Bin[目标文件 / 汇编] ```

我们将在第 2 章到第 4 章深入前端的三道关卡——词法、语法、语义；在第 5 章和第 8 章展开中端 IR 与 SSA；在第 9 章到第 11 章剖析后端的三件大事——指令选择、寄存器分配、代码发射。这种"三段式"不仅是 LLVM 的内部组织，也是 GCC、HotSpot、V8、TurboFan、MLIR 等系统共同采用的事实标准骨架。

值得强调的是，三段式的真正威力在于"中间表示的抽象"。一旦 IR 足够稳定，针对某种新语言写一个前端和针对某种新硬件写一个后端的工作量都可以被大幅压缩。这是为什么今天新增一种语言（如 Mojo、Zig）或一个新硬件架构（如 RISC-V、Tenstorrent）的成本，比 1980 年代低一个数量级。本书会反复回到这个论点：IR 是编译器世界里的"通用语"。

1.3 编译还是解释：一条被反复跨越的边界

几乎每个学过计算机基础的人都被告知"编译型 vs 解释型"的二分法：Java 是编译的，Python 是解释的，JavaScript 是解释的，C++ 是编译的……但这种二分法在 2025 年已经几乎不成立了。

传统的定义是：编译器把整个程序一次性翻译成目标代码，然后执行；解释器逐行读取源程序，边解析边执行。但如果我们用这个定义去检验现代系统，会发现：

• **V8 (JavaScript)**：先做一次"字节码编译"生成 Bytecode，然后做"即时编译 (JIT)" 把它转成机器码——两道编译过程。
• **HotSpot (JVM)**：方法被调用 10000 次之后，会触发 C2 编译器把它从字节码编译到顶级优化的机器码；同时解释器还在跑别的代码。
• **CPython**：默认是解释执行，但通过 PyPy 或 mypyc 会被编译到 C 或 RPython。
• **WebAssembly**：设计上同时支持 AOT 编译和 JIT 编译两种场景。
• **PyTorch / XLA / TVM**：Python 写的前端，落到 GPU 上是经过多层编译器链路的产物。

更准确的理解方式是：编译与解释是一个连续谱的两个端点，中间存在大量混合模式。HotSpot 有一个"分层编译"的设计：第 0 层解释执行，第 1 层简单 C1 编译，第 2 层激进 C2 编译，第 3 层甚至有针对 profile 数据的 re-JIT。第 1 章里我们先建立这个连续谱的心智模型，第 13 章会专门深入 JIT 的内部机制。

为什么这一点对今天的专家程序员重要？因为性能问题往往出现在"边界处"。当一个 Python 程序的瓶颈是某个被频繁调用的数值计算循环时，"在解释器层面优化"是徒劳的——真正起作用的是"找到合适的 API 触发底层 C 加速"或"用 Numba/Cython 把这段循环编译掉"。这要求我们理解每个运行时背后到底有几条编译路径、每条路径的触发条件是什么。同样地，理解 V8 的 TurboFan 优化条件、HotSpot 的 escape analysis 触发条件，能够让"为什么这段代码快了 10 倍"从玄学变成可以推理的工程判断。

1.4 六十年的技术演化：从手工代码生成到 ML 引导的优化

把视野拉远，编译器技术从 1957 年到今天，可以大致划分为五个时代。每一个时代的标志不仅是技术方案，更是对"编译是什么"这个问题的回答方式的改变。

第一时代（1957–1970s）：手工代码生成时代。Fortran I 的优化器里几乎没有通用规则——循环展开是写死的、寄存器分配是手调的、指令序列是针对 IBM 704 量身定制的。每一段生成的代码背后都有工程师的笔迹。这个时代的工程师必须同时是机器专家和语言专家，人才极其稀缺。

第二时代（1970s–1980s）：表格驱动与形式化方法时代。Wirth 在 Pascal 编译器里引入"自展"和"代码生成模板表格"，把代码生成从"手写过程"变成"查表过程"。同期的 Knuth-Morris-Pratt 算法、LL/LR 语法分析理论，让前端从"试错"走向"形式化"。这个时代最深刻的影响是：编译过程可以被"自动构造"。yacc 这样的工具让一个研究生可以在一个学期里写出一个工业级语法分析器。

第三时代（1987–2000s）：IR 通用化与 SSA 时代。GCC 1987 年发布，引入了基于 RTL 的中间表示。1990 年代后期，IBM、Intel、HP、Compaq 的编译器团队陆续把 SSA 形式作为标准 IR 引入。SSA（静态单赋值形式）让数据流分析变成了近乎线性的过程——每个变量只被赋值一次，意味着"在哪里被赋值"和"在哪里被使用"之间有简洁的对应关系。LLVM 在 2003 年的论文里把 SSA 工程化、工具化，标志着这个时代的成熟。

第四时代（2003–2020s）：多层 IR 与领域专用时代。随着 ML、图形、数据库等领域的爆发，"通用 IR" 不再是最优解。MLIR（Multi-Level Intermediate Representation）项目提出"IR 可以分层、可组合、领域定制"。XLA 编译器把 Python 写成的机器学习模型直接编译到 TPU。TVM 和 Halide 把"图像处理流水线"作为独立 IR 来处理。Shader 编译器（DXC、glslang）把 GLSL/HLSL 转成 SPIR-V，再由 GPU 厂商翻译到自己的硬件指令集。这个时代的核心洞察是：编译器的"通用性"不在于一个 IR 走天下，而在于 IR 之间的转换和组合能力。

第五时代（2020s– ）：ML 引导的优化时代。我们正在进入一个由机器学习反哺编译器优化的阶段。传统的优化 pass 由启发式规则驱动，依赖编译器工程师的直觉。ML 编译器让"选择哪一组优化 pass、传入哪些参数"这件事本身成为一个机器学习问题——在 Ithemal、AutoTVM、Ansor、MetaScheduler 这些项目里，编译器优化的"超参搜索"被神经网络接管。LLM 也在改变前端：自然语言描述的需求可以直接生成代码并被优化器进一步处理。

这五个时代不是简单的"前一个被后一个取代"——它们更像地质上的地层叠加。今天的 LLVM 既有来自 1980 年代的表格驱动理论，也有来自 2020 年代的 ML 调度器。理解编译原理的专家，需要知道每一层地层在做什么，才能在调试、诊断和定制时找到正确的"挖掘点"。

1.5 ToyLang：一本可以"跑"起来的编译原理书

写到这里，本书已经给出了全景地图。但对一本技术书而言，光有地图不够——读者需要一条可以走通的具体路径。这就是为什么我们将在后续 14 章中，以一门名为 ToyLang 的小型教学语言为载体，把每一章的抽象理论落到可执行的代码上。

ToyLang 的设计目标有四个：

1. 极简但不残缺。它必须小到读者在 30 分钟内读完语法规则，但必须包含真实语言的核心要素：变量、函数、控制流、用户自定义类型、闭包。这些要素足以触发从词法分析到寄存器分配的几乎所有编译问题。 2. 强类型 + 显式标注。借鉴 Rust 和 TypeScript 的精神，所有类型必须显式标注，没有隐式转换。这让"类型推导"和"类型检查"这些通常被掩盖的过程在 ToyLang 里变得清晰可见。 3. 可分阶段演进。ToyLang 在每一章末尾会"长出"新特性。第 2 章只有表达式和字面量；第 3 章加入 if/while；第 4 章加入函数；第 7 章加入结构体；第 9 章加入泛型；第 12 章加入闭包。读者看到的不只是"功能增加"，更是编译技术如何决定语言的设计边界。 4. 可解释为目标真实机器码。ToyLang 最终会被编译到 x86-64 汇编（也会在第 13 章演示到 WebAssembly），读者可以自己反汇编、对比手写汇编和编译器输出。

在第 1 章的尾声，我们给出 ToyLang 的第一个版本 v0.1，程序是 `hello.toy`：

```toylang // hello.toy - ToyLang v0.1 fn main(): int { let x: int = 42; let y: int = x * 2; if y > 80 { print("big"); } else { print("small"); } return 0; } ```

这段程序已经触及了第 2–4 章将要讨论的几乎所有要素：词法上需要识别 `fn`、`let`、`if`、`else`、`return` 等关键字；语法上需要解析函数定义、变量声明、表达式、二元运算、if 语句；语义上需要处理 `int` 类型的运算、`return` 类型与函数签名的匹配。读者不需要立刻理解所有细节——它只是一张预告片。从第 2 章开始，我们会把这段程序拆开，逐一走过它穿越的三道关口：词法、语法、语义。

1.6 后续 14 章的旅程地图

在收束本章之前，让我们把后续 14 章的路线图摊开。这张地图不是"目录"——它是本书的论证骨架。每一章都回答一个具体的工程问题，并把 ToyLang 推进一步。

• **第 2 章：词法分析**——如何用正则表达式和有限状态自动机把字符流切成 token。ToyLang 学会识别第一个关键字。
• **第 3 章：语法分析**——从 LL 到 LR，从 BNF 到 Earley。ToyLang 学会解析 if 语句和函数定义。
• **第 4 章：语义分析**——符号表、作用域链、类型检查。ToyLang 开始拒绝错误的程序。
• **第 5 章：中间表示**——三地址码、控制流图、基本块。ToyLang 第一次"长出"自己的 IR。
• **第 6 章：控制流分析**——支配关系、循环识别、SSA 构造的前置工作。
• **第 7 章：数据流分析**——活跃变量、到达定值、可用表达式。优化器的"眼睛"。
• **第 8 章：优化基础**——常量折叠、死代码删除、窥孔优化。ToyLang 第一次跑得比手写快。
• **第 9 章：高级优化**——函数内联、循环变换、自动向量化。
• **第 10 章：指令选择**——树覆盖算法、BURS、模式匹配。IR 落到真实指令。
• **第 11 章：寄存器分配**——图着色、线性扫描、SSA 上的分配。
• **第 12 章：代码发射与链接**——调用约定、栈帧布局、可执行文件格式。
• **第 13 章：即时编译**——HotSpot 风格的 tiered compilation，WebAssembly 跨语言编译。
• **第 14 章：内存管理与 GC**——逃逸分析、标量替换、分代 GC、并发 GC。
• **第 15 章：编译器的未来**——ML 引导优化、形式化验证、量子/神经形态硬件的编译挑战。

贯穿这 14 章的主线是 ToyLang 的演化：每章末尾，ToyLang 都会增加一个能力，相应地，编译器也需要增加一个子系统。这意味着读者读到的不是"独立的 14 个话题"，而是一个完整编译器的纵向生长。从第 1 章的 8 行 `hello.toy`，到第 15 章 ToyLang 已经支持闭包、泛型、模式匹配和简单的 GC，编译器的复杂度也在同步增长。

1.7 专家为何仍要重读编译原理：AI 时代不可替代的"基底层"

最后，让我们直面一个绕不开的问题：在 GitHub Copilot、Cursor、Claude 等 AI 工具已经能写出 80% 工业代码的 2025 年，专家程序员为什么还要把编译原理再读一遍？

这个问题有三层回答，从浅到深。