书 · 1986 · 阿尔弗雷德·V. 阿霍、拉维·塞西、杰弗里·D. 乌尔曼

《编译原理》

计算机与 AI书单第 29 名

一句话结论

编译器把程序逐步变成便于分析和执行的表示；读懂这些步骤，你才能理解机器怎样落实语言规则，以及优化为什么必须有依据。

值不值得读完整本？

值得完整读过全书的主线，尤其值得把前端、运行时和后端连起来读；各算法的推导可以分轮消化，不必第一次就逐页攻克。

先读第一、二章，建立从源程序到目标代码的整体认识，并跟着做出简单翻译器。
第三、四章重点掌握正则表达式、自动机、上下文无关文法，以及自顶向下和自底向上分析的区别；复杂分析表的构造细节可以第二遍再读。
第五至八章要连读：语法制导翻译、类型检查、运行时环境和中间代码生成，共同回答程序结构怎样变成可执行操作。
第九、十章不要跳过。至少掌握基本块、控制流图、寄存器分配、公共子表达式、循环优化和数据流分析的作用与适用条件。
第十一章用于规划自己的编译器项目，第十二章的历史系统案例可以选读；配合附录 A 或自选的小语言项目，并手算几个分析与优化实例，效果远好于只看定义。

核心观点

1. 分阶段与中间表示，让复杂翻译可以被拆解

编译器把源程序的分析与目标代码的生成分成若干职责明确的阶段，并借助中间表示连接它们。阶段是逻辑分工，不等于每个阶段都必须单独扫描一遍程序。

为什么：源语言规则和机器指令之间的距离很大，直接同时处理两端会让实现相互牵连。先把名字、表达式和控制结构转成明确的内部表示，后续步骤就能围绕同一种对象工作。前端主要处理语言差异，后端主要处理机器差异，因此可以复用部分实现。中间表示还为优化提供了操作对象，而具体需要多少遍处理，则取决于内存、效率和实现复杂度。

2. 用匹配问题结构的形式模型，自动识别程序

词法分析与语法分析处理不同层次的问题：前者识别单词式的基本单位，后者识别表达式和语句的组合结构。正则表达式、有限自动机与上下文无关文法，使这些任务有了可执行的规范。

为什么：标识符和数字等词法模式通常可以用有限状态描述，因此能从正则表达式系统地构造识别器。表达式和语句存在递归嵌套，通常需要文法及带栈的分析过程来恢复层次。将这两层分开后，语法分析器可以围绕词法单元工作，不必反复处理字符细节。分析器生成工具再把规范转成程序，但文法歧义和分析冲突仍需要设计者理解并处理。

3. 语法结构必须与属性、名字和类型规则结合

认出程序结构只是开始，编译器还要计算类型、查找声明并生成相应表示。语法制导翻译把这些工作组织为附着在语法结构上的属性和规则。

为什么：相同形状的表达式，可能因为声明和操作数类型不同而具有不同含义。符号表保存名字所关联的信息，属性则让类型、位置等信息在语法结构之间传递。属性的依赖关系决定计算顺序，不能只凭方便任意执行语义动作。类型检查据此发现某些不合法的操作，并在语言规则允许时安排类型转换，但它并不保证程序没有其他错误。

4. 运行时组织必须兑现作用域、调用和存储期规则

变量在哪里存放、调用时保存什么、怎样访问外层名字，都必须由语言语义决定。编译器生成的代码需要与运行时存储组织相配合。

为什么：一段过程代码可以被递归调用多次，因此一个源程序变量可能同时对应多个活动中的实例。活动记录为每次调用保存参数、局部数据和恢复执行所需的信息。名字的可见范围与数据的存活时间又是两个问题，不能仅凭调用先后决定变量含义。栈分配适合符合后进先出规律的活动，而需要跨越这种规律存活的数据，则需要其他存储安排。

5. 代码生成是在机器约束下安排计算与保存结果

生成正确指令还不够，编译器还要选择指令、安排求值顺序，并分配有限的寄存器。代码质量取决于这些决策怎样相互配合。

为什么：同一段中间代码可以翻译成多种指令序列，而指令集和寻址方式会影响各方案的代价。寄存器数量有限，中间结果留存过多，就可能需要写回内存并在以后重新读入。求值顺序会改变同时需要保存的结果数量，因此它与寄存器使用紧密相关。基本块内的依赖关系和下一次使用信息，可以帮助生成器避免多余搬运，同时保留后续仍然需要的值。

6. 优化先要确认变换合法，再争取降低代价

优化是在保持程序语义的前提下改善代码，不是把源码改得更短。数据流分析帮助编译器判断某些值、表达式和赋值在不同路径上是否仍然有效。

为什么：局部看似重复的计算，可能因为另一条路径修改了操作数而不能复用。控制流图把执行路径明确下来，数据流方程则概括信息如何在各基本块之间传播。有循环时，需要反复传播这些信息，直到得到稳定结果。指针和别名还可能让一次写入影响多个名字，因此编译器必须保守处理不确定性，避免为了减少计算而改变行为。

反对意见

语法分析的算法选择并没有被讲全（Simon Tatham）

Tatham 在《In which I have Opinions about parsing and grammars》中直接指出，1986 年和后来的版本都没有介绍 Pager 的方法。这容易让读者以为只能在规范 LR 的大分析表与 LALR 合并状态可能引入的冲突之间取舍。他主张关注更谨慎的状态合并方法及其后继算法；批评针对算法覆盖范围，并不否定书中已有算法的价值。

先铺理论，可能让初学者迟迟接触不到完整编译器（Jack W. Crenshaw）

Crenshaw 在《Let's Build a Compiler! — Part I: Introduction》中批评常见教材的教学顺序：读者可能花大量时间学习文法和分析技术，却没有走到代码生成。他选择递归下降、逐步实验和直接输出汇编，让读者尽早看到完整翻译过程。这是对教学路线的具体异议，文章没有点名批评《编译原理》，也承认复杂问题需要理论。

入门课可以缩小范围，换取对完整实现的深入理解（Niklaus Wirth）

Wirth 在《Compiler Construction》序言中选择小型源语言、简单目标机，并主动舍弃复杂优化，使一门课能够详细解释和实现整个编译器。他把语法分析视为完成翻译的手段，重点放在清楚、可实现的整体结构。这与《编译原理》广泛比较技术的路线形成对照；它不是点名反对本书，而是认为入门教学应采用不同的范围取舍。