01 / 导读
导读
引用
Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Pearson.
章节概要
第二版约1,000页，共十二章和两个附录。每章以小结结束，多数章还有参考文献一节。Pearson称这一版经过全面修订，新增了三章（第10至12章），分别讨论指令级并行、面向并行与局部性的优化以及过程间分析。作者指出，很少有读者会真正去构造编译器，因此本书仍着眼于软件设计与开发中更广泛的问题。
第1章：Introduction
语言处理器、编译器的结构、程序设计语言的演化、构造编译器的科学，以及程序设计语言基础。它给出了后文依次展开的各个阶段。
第2章：A Simple Syntax-Directed Translator
一个小而完整的前端：语法定义、语法制导翻译、语法分析、简单表达式的翻译器、词法分析、符号表和中间代码生成。在后面各章深入讨论各阶段之前，先给出一个能运行的整体概览。
第3章：Lexical Analysis
词法分析器的作用、输入缓冲、记号的规约与识别、Lex生成器、有限自动机、从正则表达式到自动机、词法分析器生成器的设计，以及基于DFA的模式匹配器的优化。
第4章：Syntax Analysis
上下文无关文法、文法的编写、自顶向下分析、自底向上分析、简单LR分析、更强大的LR分析器、二义文法的使用以及分析器生成器。
第5章：Syntax-Directed Translation
语法制导定义、求值顺序、语法制导翻译的应用、翻译方案以及L属性定义的实现。
第6章：Intermediate-Code Generation
语法树的变体、三地址码、类型与声明、表达式的翻译、类型检查、控制流、回填、switch语句以及过程的中间代码。
第7章：Run-Time Environments
存储组织、栈上空间分配、对非局部数据的访问、堆管理，以及四个关于垃圾回收的小节：入门、基于跟踪的回收、短停顿回收和高级主题。
第8章：Code Generation
代码生成器的设计问题、目标语言、目标代码中的地址、基本块与流图、基本块的优化、简单代码生成器、窥孔优化、寄存器分配与指派、通过树重写进行指令选择，以及用动态规划为表达式生成最优代码。
第9章：Machine-Independent Optimizations
优化的主要来源、数据流分析入门及其基础、常量传播、部分冗余消除、流图中的循环、基于区域的分析和符号分析。
第10–12章：Instruction-Level Parallelism；Optimizing for Parallelism and Locality；Interprocedural Analysis
第二版的新增章节。第10章讨论处理器体系结构、代码调度约束、基本块调度与全局调度以及软件流水。第11章展开基本概念、作为深入示例的矩阵乘法、迭代空间、仿射数组下标、数据重用、数组数据依赖分析、无需同步的并行性以及局部性优化。第12章讲过程间分析，包括数据流的逻辑表示、指针分析（上下文不敏感与上下文敏感）以及用BDD实现的Datalog。
附录
附录A A Complete Front End列出源语言、主程序、词法分析器、符号表与类型、表达式的中间代码、布尔表达式的跳转代码、语句的中间代码、语法分析器以及前端的创建。附录B讨论如何求线性无关的解。
核心概念
第1–5章：前端
- 正则表达式与有限自动机：规约和识别记号的工具。
- 上下文无关文法与LR分析：形式体系和主要的自底向上分析算法。
- 语法制导定义：把计算附加到文法产生式上。
第6–8章：中间代码与后端
- 三地址码：第6章的中间表示。
- 垃圾回收：回收堆存储，共用四个小节讨论。
- 寄存器分配与指令选择：第8章的代码生成决策。
第9–12章：优化与分析
- 数据流分析：沿流图推理程序性质的框架。
- 软件流水与迭代空间：面向并行与局部性的调度和循环变换思想。
- 过程间分析与指针分析：跨过程边界的分析，以Datalog表达。
评析
优点
- 贯通始终的覆盖。 十二章从词法分析经语法分析、翻译、代码生成直到优化，沿着编译器的流程展开，附录中还有前端代码。
- 分析与优化部分分量足。 第9至12章共四章，专门讲数据流分析、并行性、局部性和过程间分析。
- 生成器与理论并重。 Lex和分析器生成器与其背后的自动机和文法理论并置。这种搭配适合那些在实验中既使用lex、yacc等工具、又要实现LL(1)和SLR(1)分析的课程。
- 结构一致。 每章以小结和参考文献结束，第二版又为现代体系结构新增三章。
局限
- 对第一个项目而言，前端与理论偏重。 在到达代码生成之前，书中先构建了大量自动机与语法分析理论，想尽快做出能运行的编译器的学生可能更适合项目式教材。
- 后端话题较高深。 第10至12章讨论指令级并行、仿射循环分析和基于Datalog的指针分析，比前面各章要吃力得多。
- 受版本所限。 第二版出版于2006年，距初版二十年，此后语言与处理器方面的发展未被涵盖。
在课程中的定位
Dragon Book是本课程中经典的、理论丰富的编译器教材。Nystrom的Crafting Interpreters是读者动手构建两个解释器的入门读物，是在读本书之前接触词法分析、语法分析和虚拟机的较温和途径。Thain的Introduction to Compilers and Language Design是围绕一个项目、适合一学期课程且可免费获得的精简教材。Cooper与Torczon的Engineering a Compiler对词法与语法分析着墨较少，而把更多篇幅给了中间表示、优化、指令选择、调度和寄存器分配，因此是本科课程中最接近的替代选择；下文介绍的UT Austin课程把二者并列为可选教材，未作高下排序。Pierce的Types and Programming Languages是类型系统的研究生教材，对类型系统的论述远比第6章中的类型检查一节详尽。
如何使用本书
本书适合数据结构扎实、了解基本自动机与文法、并接触过一些汇编级编程的高年级本科生和研究生一年级学生。作为一个具体参照，下文的UT Austin课程要求先修计算机组成与程序设计方面的课程（例如CS429和CS312，或对应的ECE课程），并期望学生具备机器组织、汇编概念、C++以及基本的面向对象编程知识。
实用的阅读方案：
- 第一门课的核心： 第1至8章，先把第2章当作一个小而完整的编译器来读。
- 优化： 第9章作为数据流分析入门，也是第10至12章的基础。
- 选读与进阶： 第10至12章，以及提供可运行前端代码的附录A。
- 垃圾回收： 7.5至7.8节可以暂时搁置，或作为独立单元阅读。
阅读时配合一个小型编译器项目；附录A中的前端展示了完整编译器的模样。
课程中的使用方式
下面两份课程文档中均未列出具体的章节或页码分配，因此宜把本书当作有选择查阅的参考书，而非从头读到尾的指定读物。
- 流程与实验型课程的参考书。 IIT Kharagpur计算机系网站上的一个编译理论与实验课程页面（页面上的通知与作业日期为2025年，页面未标明正式学期）在Books and References下列出本书，未标明为必读。同一列表还包括Holub的Compiler Design in C、Appel的Modern Compiler Implementation in C、Muchnick的Advanced Compiler Design and Implementation以及一本lex/yacc参考书。其实验作业涵盖Lex、LL(1)与SLR(1)分析、lex/yacc集成、L属性文法、赋值语句的中间代码以及回填。本书在第3至6章讨论这些主题，但课程页面并未把作业与教材章节对应起来。
- 面向优化的课程中的可选教材。 UT Austin的ECE479K Compilers（2025年秋季）没有必读教材。大纲将本书（第2版）与Cooper和Torczon的Engineering a Compiler（第3版，2022年）列为可选的替代教材，并指出学生不太可能两本都需要。课程主题从编译器结构、词法与文法分析开始，随后涵盖中间表示、运行时环境、控制流与数据流分析、优化、寄存器分配、指令选择和指令调度。其实验基于COOL和LLVM，从语法分析经中间代码生成、数据流优化，推进到后端代码生成与寄存器分配。在这类课程中，书中最贴近的内容是第6至9章，以及第10章中的调度部分；学习时宜把本书的概念与课程自己的COOL/LLVM工具材料对照着读。
版本说明
上述两门课程列出的都是第二版，即本页所列版本。ECE479K注明为Addison-Wesley，2006年9月。IIT Kharagpur课程页面注明为Addison-Wesley，2006年，并另列Pearson于2014年出版的印度版。该2014年印本仍是同一个第二版，并非新的版次。
