1.1　编译器

如果让你给一个编译器命名，那么你可能会给出一个类似GCC、Clang或者Go编译器的名称。无论如何，它肯定是针对某种编程语言的编译器，并且能够生成可执行文件。我也会为它起一个类似上述名称的名字，因为我们就是这样理解“编译器”一词的。

但是编译器种类繁多，而且可以编译的内容不止编程语言，还有正则表达式、数据库查询甚至HTML模板。我敢打赌，你每天在毫无意识的情况下至少会使用一两种编译器。这是因为“编译器”的定义本来就非常宽泛，远超人们的预期。以下是维基百科对它的定义：

编译器是一种计算机程序，它会将某种编程语言写成的源代码（原始语言）转换成另一种编程语言（目标语言）。编译器是一种支持数字设备（主要是计算机）的翻译器。编译主要是将源代码从高级编程语言转换为低级语言（例如汇编语言、目标代码或机器代码），以创建可执行程序。

编译器是翻译器。这么解释可能有点含糊不清。难道将高级编程语言转换成可执行文件的只是一种特殊的编译器吗？听起来有点违反直觉，不是吗？你可能认为生成可执行文件就是编译器要做的事情：是GCC要做的事情，是Clang要做的事情，也是Go编译器要做的事情。难道“编译器”的定义不应该这样开头吗？这怎么可能不是关键点？

可以用另一种思考方式来解释这个疑惑：如果不是源代码，那什么是计算机可理解的可执行程序呢？因此，“编译为本地代码”与“编译为机器代码”是一个意思。生成可执行文件只是“翻译源代码”的一种变体。

如你所见，编译器本质上就是翻译器，因为翻译是它实现编程语言的方式。

我们来解释一下这句话的意思。编程意味着对计算机发号施令。这些指令是程序员用计算机可以理解的编程语言编写的，用其他语言没有意义。实现一种编程语言意味着让计算机理解它，有两种方法可以达到目的：为计算机即时解释编程语言，或者将编程语言翻译成计算机可以理解的另一种语言。

这就像我们人类一样，可以帮助朋友翻译他们不会的语言。我们听到信息后，可以先在自己脑海中翻译好，然后复述给朋友，也可以将翻译内容写下来，以便朋友自己阅读和理解。我们充当的就是解释器或者编译器的角色。

这听起来似乎解释器和编译器是对立的。尽管二者的途径不同，但是它们在构造上有很多相似点。它们都有前端，用于读取源语言编写的源代码并将其解析为数据结构。在编译器和解释器中，这个前端通常由词法分析器和语法分析器构成，二者合作将源代码转换成语法树。因此，在前端，编译器和解释器有很多相似之处。之后，它们都会遍历AST，从此二者分道扬镳。

由于已经构建了解释器，因此我们知道在遍历AST时，它所做的工作：求值。换言之，它直接执行树中编码的指令。如果树中某个节点表示源语言中的语句puts("Hello World!")，那么解释器在对这个节点求值后会直接输出“Hello World!”。

编译器则相反：它不会输出任何内容，而会以另一种语言（目标语言）生成源代码。源代码中包含源语言puts("Hello World!")的等效目标语言。随后，生成的代码由计算机执行并将"Hello World!"打印在屏幕上。

这是事情变得有趣的地方。编译器以哪种目标语言生成源代码？计算机能理解哪种语言？编译器又如何生成这种语言的代码？作为文本格式还是二进制格式？在文件中还是内存中？更重要的是，它用目标语言生成什么？如果目标语言没有与puts语义等效的部分会怎样？编译器又会用什么来代替呢？

一般来说，对于这些问题，我们必须给出统一的答案。不过在软件开发中，统一的答案是“看情况”。

很抱歉让你感到失落，只是这些问题的答案取决于多种变量和需求：源语言、执行目标语言的计算机体系结构、编译输出的使用方式（直接输出，还是再次编译后输出，还是解释输出）、输出需要运行多快、编译器自身需要运行多快、生成的源代码有多大、编译过程中可使用内存的大小、编译输出程序可使用内存的大小，以及……

不同编译器之间的差异如此之大，以至于我们无法对它们的结构做出统一的描述。话虽如此，我们仍然可以暂时忽略细节，勾勒出如编译器原型之类的架构。

图　1-2

图1-2展示了源代码被翻译成机器代码的生命周期。说明如下。

首先，由词法分析器和语法分析器对源代码进行标记和语法分析。我们对解释器这部分内容很熟悉。这被称为前端。经过这个步骤，源代码从文本转换成AST。

接着，被称为“优化器”（有时也被称为编译器）的组件将AST翻译成另一种中间表示（IR）。这个额外的IR可能是另一棵语法树，或者是二进制格式，甚至是文本格式。额外翻译成另一个IR的原因是多种多样的，但是主要的原因是IR可能比AST更适于优化和翻译成目标语言。

然后，这个新的IR进入优化阶段：消除死代码，预先计算简单的算术，移出循环体内的多余代码……优化方式非常多。

最后，代码生成器（也被称为编译后端）以目标语言生成代码。这是编译真正起作用的步骤。可以说，这是代码触及文件系统的地方。之后，我们可以执行生成的代码，计算机会按照我们在原始代码中的指示进行工作。

以上就是最简单的编译器的工作方式。即使如此简单，都有千百种可能。例如，编译器可以在IR上进行多次“扫描”，这意味着它会多次遍历IR，每次都进行不同的优化。举个例子，一次遍历删除死代码，一次遍历进行内联优化。或者编译器根本不对IR进行任何优化，仅对目标语言的源代码进行优化。或者仅在AST上进行优化，或者AST和IR都进行优化。或者根本没有进行优化。或者除了AST之外，它并没有额外的IR。也许它不输出机器代码，而是输出汇编语言或者其他高级语言。或者它存在多个用于生成不同体系结构机器代码的后端。一切都取决于具体的场景和使用方式。

更有甚者，编译器也不一定是读取源代码并输出目标代码的命令行工具（例如gcc、go）。它也可以是接收AST并返回字符串的单个函数。这也是一种类型的编译器。编译器可以由几百行代码完成，也可以拥有数百万行代码。

但是在这些代码背后潜藏着的才是编译器的基本理念。编译器获取一种语言的源代码并转换成另一种语言的源代码。剩下的仍然是“看情况”，大部分情况取决于目标语言。目标语言具有什么功能，可以在哪台计算机上执行，决定了编译器的设计。

如果我们不选择任何一种目标语言，而是用我们自己发明的目标语言会怎样？又或者如果我们不使用现有的机器，而是创建执行这种语言的机器会怎样？

1.3　虚拟机与编译器的二元性

在构建虚拟机和一个与之匹配的编译器之前，我们需要先解决“鸡生蛋和蛋生鸡”的哲学问题：到底应该先构建哪一个？是编译器，为一个不存在的虚拟机输出字节码，还是虚拟机，但是此时又没有任何代码可以执行？

我在本书中给的答案是：虚拟机与编译器同时构建！

在一个组件之前构建另一个组件（不管这个组件是什么）是一件令人沮丧的事，因为很难预判后续事情的进展，也无法了解当下所做事情的真正目的。如果优先构建编译器并定义字节码，那么在不知道后续虚拟机如何执行它时，你很难理解当下的事情为什么如此。在编译器之前构建虚拟机也存在着天然的缺陷，因为字节码需要事先定义，虚拟机才能执行。如果不仔细查看字节码旨在表示的源语言结构，很难提前定义字节码，这意味着无论如何都要优先构建编译器。

当然，如果已经拥有构建其中一个组件的经验，并且很清楚地知道你所要的最终效果，那你可以选择任意一个组件来构建。但是，对本书而言，我们的目标是学习如何同时从零开始构建两个组件。

这就是我们从小处着手的原因。我们将构建一个只支持少量指令的微型虚拟机，以及一个与之匹配的微型编译器，仅用于输出这些指令。如此一来，我们会对自己所构建的内容及其相互之间如何适配有很深的理解。我们将拥有一个从零开始构建而成的可运行系统。该系统能提供快速的反馈周期，使我们能调整、试验并逐步完善虚拟机和编译器。整个旅程因此变得充满乐趣！

现在知道了全部的计划，而且足够了解编译器和虚拟机的基本原理，因此我们不会一直迷茫无助。让我们开始吧！