前言

这是一个神奇的时刻，当程序员按下运行按钮后，软件开始执行。不知何故，一个用高级语言编写的程序，可以在一台只能进行位变换操作的计算机上运行。在这里，我们将揭示使这一时刻成为可能的魔法背后的秘密。从20世纪50年代Backus及其同事的开创性工作开始，计算机科学家开发出了一种技术，用于构建称为编译器的程序，该程序可以将高级语言程序自动转换成机器代码。

我们将带你踏上这样的一段旅程：为一种规模小但功能强大的语言构建自己的编译器。在这个过程中，我们将解释编译器背后的基本概念、算法和数据结构。我们帮助你理解程序如何映射到计算机硬件上，这有助于你推断硬件和软件结合层面的属性，例如软件的执行时间、软件错误和安全漏洞等。对于那些有志于以构造编译器为职业的人，我们的目标是为你奠定一个进入更高级主题的基础，例如即时编译、程序分析和程序优化；对于那些对设计和实现编程语言感兴趣的人，我们会把语言设计中的可能选择与这些选择对编译器和生成的代码的影响联系起来。

编译器通常被组织为一系列阶段，这些阶段逐步将程序转换为可在硬件上运行的代码。我们将这一方法发挥到极致，将编译器划分为大量的微编译遍，每个微编译遍执行一个单一的任务。这样，我们就可以独立地测试编译过程的每一遍，并可集中注意力于相应的遍，从而使编译器的工作过程更易理解。

描述编译器最常见的方法是每章专门介绍一个编译遍。对于如何根据语言特性挑选编译器的设计方案，这种方法的回答是模糊的。因此，我们采用增量方法，在每章中都将构建一个完整的编译器，从只包含算术和变量的小型输入语言开始，在后续章节中不断添加新的语言特性，并根据需求对编译器进行相应的扩展。

我们对语言特性的选择旨在引出编译器中使用的基本概念和算法。

❑ 在第1章和第2章中，我们从整数算术和局部变量开始，介绍了编译器构造的基本工具：抽象语法树和递归函数。

❑ 在第3章中，我们应用图着色算法将程序变量分配到机器寄存器。

❑ 第4章增加了条件表达式，这激发出了一个优雅的递归算法，用于将它们转换为条件goto语句。

❑ 第5章增加了循环和可变变量，这就需要在寄存器分配器中进行数据流分析。

❑ 第6章增加了基于堆分配的元组，引出了内存垃圾回收。

❑ 第7章将函数添加为没有词法作用域的第一类值，类似于C编程语言中的函数（Kernighan and Ritchie 1988）。读者将了解过程调用栈和调用约定，以及它们如何与寄存器分配和内存垃圾回收交互。本章还描述了如何生成高效的尾调用。

❑ 第8章增加了具有词法作用域的匿名函数，即lambda表达式。读者将了解闭包转换，其中lambda式被转换为函数和元组的组合。

❑ 第9章增加了动态类型。在此之前，输入语言是静态类型的。读者可使用Any类型扩展静态类型语言，该类型用作编译动态类型语言的目标类型。

❑ 第10章使用第9章介绍的Any类型来实现一种渐变类型语言，其中程序的不同区域可以是静态类型或动态类型。读者可实现对代理的运行时支持，这些代理允许值在不同类型区域之间安全地移动。

❑ 第11章增加了自动装箱泛型，它利用了第9章和第10章中开发的Any类型和类型强制转换。

许多语言特性还没有包括在本书的讨论中。我们的选择平衡了语言特性附带的复杂性和它所展示的基本概念。例如，我们包含了元组而没有包含记录，因为尽管它们都需要研究堆分配和垃圾回收，但记录会带来更多额外复杂性。

自2009年以来，本书的草稿一直作为科罗拉多大学和印第安纳大学的高年级本科生和一年级研究生的16周编译课程的教科书。选修这门课的学生已经学完了编程、数据结构和算法以及离散数学的基础知识。学生在课程开始时就分成两到四人的小组。从第2章开始，会依据学生的兴趣并兼顾图0.1所示的各章依赖关系选取后续章节，各小组每两周完成大约一章的学习。第7章（函数）只在高效的尾调用的实现中依赖于第6章（元组）的实现。课程的最后两周包括一个期末项目，学生在其中设计并实现自己所选内容的编译器的扩展。最后几章可以用来支持这些项目。许多章节中都包含了我们留给研究生的富有挑战性的作业。

对于采用季度制（大约10周）的大学编译原理课程，我们建议完成第6章或第7章的课程内容，并为学生提供一些框架代码以完成编译器的每遍扩展。这门课可以通过跳过第5章（循环）并包括第8章（lambda式）来强调函数式语言；而通过引入第9章的内容，本课程适用于动态类型语言的编译课程学习。

图0.1 各章依赖关系

本书已被加州州立理工大学、波特兰州立大学、罗斯-霍曼理工学院、弗莱堡大学、马萨诸塞大学洛厄尔分校和佛蒙特大学的编译器课程采用。

我们使用Racket语言来实现编译器，并将其作为输入语言，因此读者应该精通Racket或Scheme。有许多学习Scheme和Racket的优秀资源（Dybvig 1987a；Abelson and Sussman 1996；Friedman and Felleisen 1996；Felleisen et al. 2001；Felleisen et al. 2013；Flatt, Findler and PLT 2014）。本书的支持代码位于以下GitHub存储库中：

https://github.com/IUCompilerCourse/

编译器的目标语言是x86汇编语言（Intel 2015），因此读者修读过计算机系统课程（Bryant and O'Hallaron 2010）将会非常有帮助（但不是必需的）。本书中介绍了编译器中需要使用的x86-64汇编语言的部分内容。我们遵循了UNIX系统V调用约定（Bryant and O'Hallaron 2005；Matz et al. 2013），因此在英特尔硬件上运行的Linux或MacOS操作系统，如果使用GNU C编译器（gcc）进行编译，所生成的汇编代码都可以与运行时系统（用C编写）一起工作。在Windows操作系统上，gcc使用了Microsoft x64调用约定（Microsoft 2018，2020）。因此，我们生成的汇编代码不能与Windows上的运行时系统一起工作。一种解决方法是使用以Linux作为客户机操作系统的虚拟机。

致谢

印第安纳大学编译器构造的传统可以追溯到Daniel Friedman在20世纪七八十年代对编程语言的研究和课程中。他的一个学生Kent Dybvig实现了Chez Scheme（Dybvig 2006），这是一个高效的、产品质量级的Scheme编译器。从20世纪90年代到21世纪初，Dybvig讲授编译器课程，并继续开发Chez Scheme。编译器课程逐渐融入了新颖的教学理念，同时也包含了现实世界中编译器的元素。Friedman的想法之一是将编译器分成许多小的“遍”。另一个被称为“对战”（the game）的想法是使用解释器测试每遍生成的代码。

Dybvig在他的学生Dipanwita Sarkar和Andrew Keep的帮助下，开发了支持这种方法的基础平台，并改进了课程以使用更小的微编译遍（Sarkar, Waddell，and Dybvig 2004；Keep 2012）的方法。本书中的许多编译器设计决策都受到了Dybvig和Keep（2010）课程作业的启发。在2000年代中期，Dybvig的一位名叫Abdulaziz Ghuloum的学生观察到，课程中的前端-后端组织方式使得学生很难理解编译器设计的基本原理。Ghuloum于是提出了增量方法（Ghuloum 2006），本书就基于这一方法。

感谢在印第安纳大学担任编译器课程助教的许多学生，包括Carl Factora、Ryan Scott、Cameron Swords和Chris Wailes。感谢Andre Kuhlenschmidt在垃圾回收器和x86解释器方面的工作，感谢Michael Vollmer在高效尾调用方面的工作，以及Michael Vitousek在印第安纳大学首次提供增量编译器课程方面的帮助。

感谢各位教授：Bor-Yuh Chang、John Clements、Jay McCarthy、Joseph Near、Ryan Newton、Nate Nystrom、Peter Thiemann和Andrew Tolmach和Michael Wollowski。他们基于本书草稿开设编译课程并及时进行了反馈。感谢美国国家科学基金会对这项工作的资助，资助号为1518844、1763922和1814460。

感谢Ronald Garcia在21世纪初帮助我熬过了Dybvig的编译器课程，尤其是帮助我找到了那个让垃圾回收器白费精力的软件缺陷！

Jeremy G. Siek
于印第安纳州布卢明顿市