前言

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

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

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

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

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

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

●第3章，将学习如何使用Lark语法分析器框架为整数算术和局部变量语言创建分析器。将了解Lark内部的分析算法，包括Earley和LALR（1）。

●第4章，应用图着色算法来将程序中的变量分配给机器的寄存器。

●第5章添加了条件表达式，它激发出了一个优雅的递归算法，将条件表达式转换为条件goto语句。

●第6章加入了循环语句，该语句的处理需要在寄存器分配器过程中进行数据流分析。

●第7章增加了堆分配的元组，引出了内存垃圾回收。

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

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

●第10章增加了动态类型。在此之前讨论的输入语言都是静态类型的。本章使用Any类型扩展静态类型语言，该类型用作编译动态类型语言的目标类型。

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

●第12章添加了带有自动装箱的泛型，它是借助第10章和第11章中开发的Any类型和类型强制转换来实现的。

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

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

图0.1 各章依赖关系图

对于季度制（大约十周）的大学编译原理课程，我们建议完成第7章或第8章前的课程内容，并为编译器相关的编译遍给学生提供一些框架代码。本课程可以通过跳过第6章（循环）和第9章（λ表达式）来强调函数式语言；而通过将第10章加入到课程中，本课程可以适应动态类型语言的编译原理课程的学习。

本书已经在下述大学的编译原理课程中使用：加州州立理工大学、波特兰州立大学、罗斯-霍尔曼理工学院、弗莱堡大学、马萨诸塞大学洛厄尔分校和佛蒙特大学。

本书使用Python来实现编译器和输入语言，所以读者应该精通Python语言。有许多学习Python的优秀资源（Lutz 2013；Barry 2016；Sweigart 2019；Matthes 2019）。本书的支持代码位于以下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世纪70年代和80年代对编程语言的研究和课程。他的学生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）课程作业的启发。在20世纪00年代中期，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
印第安纳州布卢明顿市