Introduction to Compilers and Language Design（编译器与语言设计导论）

引用

Thain, D. (2020). Introduction to Compilers and Language Design (2nd ed.). Self-published. Free official edition: https://dthain.github.io/books/compiler/

章节概要

第1章：引言

开篇一章承担了前言的作用。它把编译器定义为从源语言到目标语言的翻译器，区分编译器与解释器（Java 字节码和即时编译是介于两者之间的情形），并说明学习这门学科的理由，从写出更好的代码到构建小型领域专用语言。Thain 主张学习编译器的方法就是亲手写一个：用 C 语言编写，面向广泛使用的处理器。他还说明，与大多数编译器教材相比，本书对优化理论着墨较少，而更多讨论工程实现和语言设计中的取舍。

第2章：快速浏览

这一短章先把编译器放到 Unix 工具链中（预处理器、编译器本体、汇编器、静态与动态链接器），再列出编译器内部的各个阶段：扫描器、语法分析器、语义例程、中间表示、优化器和代码生成器。一条语句 height = (width+56) * factor(foo); 被完整地跟踪到每个阶段：从记号到抽象语法树，再到拥有无限寄存器的线性 IR，最后得到 X86 汇编。练习要求读者手动运行工具链的每一步，并比较不同的优化级别。

第3章：扫描

本章从语言需要哪些种类的记号讲起，给出一个用 ungetc 回退字符的手写 C 扫描器，然后说明为什么需要更严格的方法。它定义正则表达式、确定型与非确定型有限自动机，以及三种转换算法（正则表达式转 NFA、用子集构造法把 NFA 转为 DFA、Hopcroft 式 DFA 最小化）。在解释有限自动机为何无法匹配任意深度的嵌套括号之后，本章转向 Flex 扫描器生成器并给出完整的规格文件，最后讨论关键字处理、源代码位置跟踪等实际问题。

第4章：语法分析

这是全书理论性最强的一章。它定义上下文无关文法、推导和二义性，然后展开 LL(1) 分析：消除左递归和公共前缀、计算 FIRST 和 FOLLOW 集合，并编写递归下降分析器和表驱动分析器。后半部分讲自底向上分析：移进-归约分析、LR(0) 自动机、SLR、规范 LR(1) 和 LALR，并配有完整的自动机和分析表示例。本章最后梳理各文法类之间的关系（LL(1) ⊂ SLR ⊂ LALR ⊂ LR(1) ⊂ CFG），并介绍乔姆斯基层级。

第5章：语法分析实践

本章借助 Bison 语法分析器生成器把理论付诸实践。基于同一个算术表达式的 LALR 文法，依次构建三个程序：只判断输入是否合法的验证器、在分析过程中直接计算结果的解释器，以及先构建表达式树、再对其求值或打印的版本。这为读者编写项目语言的完整语法分析器做好准备。

第6章：抽象语法树

本章为课程项目所用的类 C 语言 B-Minor 定义抽象语法树，由五种 C 结构组成：声明、语句、表达式、类型和参数。它仔细区分这些术语，展示每种程序片段如何映射为树节点，最后用 Bison 动作自动构建整棵树。

第7章：语义分析

语义分析被表述为先进行名字解析、再进行类型检查。本章先从三个维度考察类型系统（安全或不安全、静态或动态、显式或隐式），配有 C、C#、Go 和 Rust 的简短示例，并讨论结构体、联合、变体类型以及不同类型之间转换等设计选择。随后它规定严格的 B-Minor 类型系统，用作用域栈构建嵌套符号表，解析声明和表达式中的名字，实现 expr_typecheck 和 stmt_typecheck，并就如何写出有用的错误信息给出建议。

第8章：中间表示

本章比较几种 IR 及其取舍。它从 AST 本身出发，接着介绍有向无环图（DAG），在其中公共子表达式可以共享、常量折叠也很容易；然后是控制流图、静态单赋值形式、线性（三地址）IR 和栈式机器 IR。来自 GCC 的 GIMPLE、LLVM 和 Java 虚拟机的真实示例展示了生产系统如何运用这些思想。

第9章：内存组织

在生成代码之前，本书先解释运行中的程序如何使用内存：代码、数据、堆和栈这几个逻辑段，以及硬件分段如何被分页取代。它给出 malloc 和 free 的一个简单链表实现，比较基于栈和基于寄存器的调用约定，说明编译器如何定位全局变量、局部变量、参数和数组元素，并介绍程序加载。

第10章：汇编语言

Thain 认为编译器只需要指令集中的一小部分（大约 30 条指令），并以两组平行、各自独立的小节讲授两种体系结构。对于 X86-64 和 ARM，本章依次介绍寄存器与数据类型、寻址方式、算术运算、比较与跳转（或分支）、栈、调用约定（X86 采用 System V ABI），以及完整的叶函数和非叶函数，最后说明 64 位 ARM 的差异。

第11章：代码生成

本章用一种刻意简单的方法生成可运行的 X86-64 代码：把每个 AST 节点单独处理。它先建立管理临时寄存器和标签的辅助函数，再以后序遍历编写 expr_codegen，处理函数调用，生成语句、条件表达式和声明，并指出更好的代码留待下一章。练习要求完成整个代码生成器、与 gcc 的输出进行比较，并可选地为 ARM 或 LLVM 增加第二个后端。

第12章：优化

最后一章是概览而非完整论述。它区分局部、全局和过程间优化，并首先建议程序员在依赖编译器之前先改进算法、做性能剖析。接着介绍高层变换（常量折叠、强度削减、循环展开、代码外提、函数内联、死代码检测）、低层变换（窥孔优化和基于树覆盖的指令选择），以及利用活跃范围、冲突图和图着色进行寄存器分配。简短的小节提醒读者注意会改变程序含义的优化，以及优化之间的相互影响。

附录 A–C：课程项目示例、B-Minor 语言、编码规范

附录 A 把学期项目安排为一系列作业（扫描器、语法分析器、美化打印器、类型检查器、可选的 IR、代码生成器、可选的语言扩展）。附录 B 有意通过示例而不是形式文法来描述 B-Minor，让学生自己提炼出精确的规格。附录 C 列出作者对 C 项目的编码要求，例如使用版本控制、"从可运行到可运行"地推进，以及删除死代码。

核心概念

第1–2章：引言与快速浏览

• 编译器与解释器：编译器输出翻译后的程序，解释器直接执行源程序；即时编译则把两者结合起来。
• 编译器的阶段：扫描器、语法分析器、语义例程、IR、优化器和代码生成器，每个阶段处理前一阶段的输出。

第3章：扫描

• 正则表达式与有限自动机：描述记号模式的两种等价方式；正则表达式可转为 NFA，再转为 DFA，并可最小化。
• 扫描器生成器：如 Flex，把一组带有 C 动作的正则表达式转换成扫描器代码的工具。

第4章：语法分析

• 上下文无关文法：左侧只有一个非终结符的规则，能够描述正则表达式无法表达的嵌套结构。
• LL(1) 分析：根据当前非终结符和一个向前看记号选择规则的自顶向下分析，通常写成递归下降形式。
• LR 分析：由自动机驱动的自底向上移进-归约分析；LALR 是生成器采用的实用折中方案。

第5–6章：语法分析实践与抽象语法树

• Bison 动作：附加在文法规则上的 C 代码，用于在分析过程中验证、解释或构建树节点。
• 抽象语法树：由声明、语句、表达式、类型和参数组成的树，记录程序结构而不包含语法分析的细节。

第7章：语义分析

• 类型系统的维度：安全/不安全、静态/动态、显式/隐式，共同刻画一门语言如何检查值。
• 符号表：把名字映射到声明的作用域栈，用于在类型检查之前解析每个标识符。

第8章：中间表示

• DAG：一种简化的图状 IR，共享公共子表达式，使常量折叠变得直接。
• 静态单赋值（SSA）：每个变量只被赋值一次的形式，可简化许多分析。

第9–10章：内存组织与汇编语言

• 逻辑段：进程地址空间中代码、数据、堆和栈的常规布局。
• 调用约定：关于传递参数、返回值和保存寄存器的约定规则，例如 System V ABI。

第11–12章：代码生成与优化

• 后序代码生成：在处理完子节点之后再为节点生成指令，用临时寄存器保存中间值。
• 图着色寄存器分配：根据活跃范围构建冲突图并对其着色，使相互冲突的变量分到不同的寄存器。
• 强度削减：用代价更低的等价运算替换昂贵的运算，例如把乘法换成移位。

评析

优点

• 一个项目贯穿始终。 每一章都服务于同一个 B-Minor 编译器，练习大多是扩展这个编译器的代码。附录 A 把它整理成现成的作业序列，使本书很容易用于一学期的课程。
• 真实的工具和目标平台。 读者用 C 编写代码，使用 Flex 和 Bison，阅读 GIMPLE、LLVM 和 JVM 的示例，并生成真实的 X86-64 代码（另有平行的 ARM 内容）。"大约 30 条指令就够用"的说法让汇编学习保持在可控范围内。
• 语言设计是内容的一部分。 语义分析一章比较了 C、C#、Go 和 Rust 在类型系统上的不同选择；B-Minor 本身也有意设计了一些特别之处（Pascal 风格的类型语法、需要类型推断的 print 语句、需要运行时支持的运算符），以引发讨论。
• 篇幅短、易读。 全书约 230 页，每个算法都配有小型实例（子集构造、LR 自动机、x=(a+10)*(a+10) 的 DAG、寄存器冲突图），而不是依赖密集的形式化符号。

局限

• 优化与分析内容较少。 作者对此毫不讳言：第12章只是一次浏览，SSA 形式只在第8章简短出现，活跃性和可达性等分析只是勾勒而未深入展开。打算从事编译器研究的学生之后需要更高阶的教材。
• 默认读者熟悉 C 并具备一定体系结构知识。 全书代码都是 C，第9–10章对内存布局和调用约定讲得很快；没有学过系统或计算机组成课程的学生会觉得吃力。
• 练习分布不均。 第3章和第4章有纸笔练习，但第9章和第10章完全没有练习；项目语言又有意只用示例来规定，需要教师帮助或仔细阅读才能消除含糊之处。
• 语言覆盖面较窄。 书中的模型是静态类型、类 C 的过程式语言。垃圾回收、闭包和面向对象特性没有涉及，动态类型只在第7章的一般性讨论中出现。

在课程中的定位

在本课程书单中，Thain 的书与 Robert Nystrom 的 Crafting Interpreters 同为入门读物，是篇幅紧凑、以项目驱动的选择。两者互为补充：Nystrom 用手写语法分析器为一门动态类型语言构建解释器，而 Thain 为一门静态类型语言构建编译器，讲授文法理论（LL 与 LR 分析）以及扫描器和语法分析器生成器，并最终生成真实的汇编代码。想同时理解语法分析背后的理论和通向本机代码之路的学生，应从 Thain 开始。

Cooper 和 Torczon 的 Engineering a Compiler 以及 Aho、Lam、Sethi 和 Ullman 的 Compilers: Principles, Techniques, and Tools 是自然的下一步；Thain 本人推荐后者作为全面的研究生水平参考书，而这两本书通常被认为对优化和分析的论述远比第12章深入。Pierce 的 Types and Programming Languages 列在第7章的延伸阅读中，适合想了解 Thain 只作非形式化处理的类型系统形式理论的读者。

如何使用本书

本书面向已经能熟练使用 C 编程、并修过数据结构和计算机组成或体系结构入门课程的本科生。不要求事先具备编译器或形式语言背景；自动机和文法在第3、4章从零讲起。

无论是学期课程还是自学，都建议按书中顺序并配合附录 A 的作业进行。第1–2章可以一次读完。用 Flex 完成第3章，用 Bison 完成第4–5章，并做关于 FIRST/FOLLOW 集合和 LR 自动机的纸笔练习，因为这些是大多数课程考查的内容。第6章和第7章是项目的核心（AST 和类型检查器）。如果像作者在自己课程中那样直接从 AST 生成代码，第8章可以略读。在编写第11章的代码生成器之前先读第9章和第10章；第10章可先只读 X86 或 ARM 中的一半。第12章可作为最后几周的扩展选题清单。

每完成一个阶段，都用小程序进行测试后再继续，并按练习的建议把自己的输出与 gcc -S 的结果比较。作者网站链接了一个 GitHub 仓库，其中有示例扫描器和语法分析器、项目起始代码以及每个阶段的测试用例。

版本与来源

本导读依据第二版（2020），阅读的是作者官方页面 https://dthain.github.io/books/compiler/（也可通过 compilerbook.org 访问）提供的完整免费 PDF（compilerbook.pdf，修订日期为 2026 年 7 月 28 日）。内容取材于致谢页、完整目录和插图目录、全部十二章（第1–2章全文；第3–12章的开头、每个小节标题、核心示例以及章末练习和延伸阅读），以及附录 A–C。