A Map of the Territory

你必须要有一张地图，无论它是多么粗糙。否则你就会到处乱逛。在《指环王》中，我从未让任何人在某一天走得距离超出他力所能及的范围。

托尔金

我们不想到处乱逛，所以在我们开始之前，让我们先浏览一下以前的编程语言实现者所绘制的编程语言的领土地图。它能帮助我们了解我们的目的地和其他人采用的备选路线。

首先，我先做个简单说明。本书的大部分内容都是关于编程语言的实现，它与编程语言本身这种柏拉图式的理想形式有所不同。诸如“栈”，“字节码”和“递归下降”之类的东西是某个特定实现中可能使用的基本组件。从用户的角度来说，只要最终产生的装置能够忠实地遵循编程语言的规范，它内部的都是实现细节。

我们将会花很多时间在这些细节上，所以如果我每次提及的时候都写“编程语言实现”，我的手指都会被磨掉。相反，除非有重要的区别，否则我将使用“编程语言”来指代一种编程语言或该编程语言的一种实现，或两者皆有。

2 . 1编程语言的组成部分

自计算机的黑暗时代以来，工程师们就一直在构建编程语言。而当我们和计算机对话的时候，我们发现构建编程语言太难了，于是我们需要寻求远古工程师们的帮助。我觉得很有趣的是，即使今天的机器确实快了一百万倍，存储空间也大了几个数量级，但我们构建编程语言的方式几乎没有改变。

尽管编程语言设计师所探索的领域非常辽阔，但他们所遍历过的路径却很少。并非每种编程语言都采用完全相同的路径——有些会采用一种或两种捷径——但实际上，编程语言所采用的路径都是很相似的。从海军少将Grace Hopper实现的第一个COBOL编译器，一直到一些热门的移植到JavaScript的编程语言——它们的“文档”完全是由Git仓库中一个编辑得很差的README文件组成的，它们的实现路径都很相似。

我把一个编程语言的实现可能选择的路径网络类比为爬山。你从山底开始往上爬，山底是程序的原始的源文本，实际上只是一串字符。每个阶段都会对程序进行分析，并将其转换为更高层次的表示形式，从而使程序的语义（作者希望计算机做什么）变得更加明显。

最终我们达到了峰顶。我们可以鸟瞰用户的程序，可以看到他们的代码含义是什么。我们开始从山的另一边下山。我们将这个最高层的表示形式转化为连续的较低层次的表示形式，从而越来越接近我们所知道的可以让CPU真正执行的表示形式。

让我们沿着每一条路线和每一个感兴趣的地方走一遍。我们的旅程从左边的用户源代码的纯文本开始

2 . 1 . 1扫描

第一步是扫描，也就是所谓的词法，或者说（如果你想给别人留下深刻印象）词法分析。它们的意思都差不多。我喜欢“lexing”，因为这听起来像是一个邪恶的超级大坏蛋会做的事情，但我还是用“scanning”，因为它似乎更常见一些。

扫描器（或词法分析器）接收线性的字符流，并将它们组合成一系列更类似于“单词”的东西。在编程语言中，这些单词的每一个都被称为标记。有些标记是单个字符，比如(和 ,。其他的可能是几个字符组成的，比如数字（123）、字符串字面量（"hi!"）和标识符（min）。

源文件中的一些字符实际上没有任何意义。空格通常是无关紧要的，而注释，从定义就能看出来，会被语言忽略。扫描器通常会丢弃这些字符，留下一个干净的有意义的标记序列。

2 . 1 . 2语法分析

下一步是语法分析。 这就是我们从句法中得到文法的地方——文法能够将较小的部分组成较大的表达式和语句。你在英语课上画过句子图吗？如果有，你就做了语法分析器所做的事情，区别在于，英语中有成千上万的“关键字”和大量的歧义，而编程语言要简单得多。

语法分析器接受的是标记流，并构建反映文法嵌套本质的树形结构。这些树有两个不同的名称：语法分析树或抽象语法树，这取决于它们与源语言的语法结构有多接近。在实践中，编程语言黑客通常称它们为“语法树”、“AST”，或者干脆直接说“树”。

语法分析器在计算机科学中有着悠久而丰富的历史，它与人工智能界有着密切的联系。今天用于对编程语言进行语法分析的许多技术最初是由人工智能研究人员设想的，他们试图对人类语言进行语法分析来让计算机与我们对话。

事实证明，相对那些语法分析器能够处理的严格文法来说，人类语言的文法太混乱了；但对于编程语言中更简单的人工文法来说，人类语言却是完美的。唉，可惜我们这些有缺陷的人类仍然会错误地使用这些简单的编程语言文法，因此语法分析器的工作还包括通过报告语法错误让我们知道出错了。

2 . 1 . 3静态分析

在所有实现中，前两个阶段都非常相似。 现在，每种语言的个性化特征开始发挥作用。 至此，我们知道了代码的语法结构（诸如哪些表达式嵌套在其他表达式中）之类的东西，但是我们知道的也就仅限于此了。

在a+b这样的表达式中，我们知道我们要把a和b相加，但我们不知道这些变量名字指的是什么。它们是局部变量吗？全局变量？它们在哪里被定义？

大多数语言所做的第一点分析叫做绑定或决议。对于每一个标识符，我们都要找出定义该标识符的地方，并将两者连接起来。这就是作用域的作用——在这个源代码区域中，某个名字可以用来引用某个声明。

如果编程语言是静态类型的，这时我们就进行类型检查。一旦我们知道了a和b的声明位置，我们也可以弄清楚它们的类型。然后如果这些类型不支持互相累加，我们就会报告一个类型错误。

深吸一口气。 我们已经到达了山顶，并对用户的程序有了全面的了解。所有这些从语义分析中得到的语义信息都需要存储在某个地方。我们可以把它藏在几个地方：

• 通常，它会被直接存储在语法树本身的属性中——属性是语法树节点中的额外字段，这些字段在语法分析时不会初始化，但在稍后会进行填充。
• 有时，我们可能会将数据存储在外部的查找表中。 通常，该表的关键字是标识符，即变量和声明的名称。在这种情况下，我们称其为符号表，并且其中与每个键关联的值告诉我们该标识符所指的是什么。
• 最强大的记录工具是将树转化为一个全新的数据结构，更直接地表达代码的语义。这是下一节的内容。

到目前为止，所有内容都被视为实现的前端。你可能会猜至此以后是后端，其实并不是。在过去的年代，当“前端”和“后端”被创造出来时，编译器要简单得多。后来，研究人员在前端和后端之间引入了新阶段。威廉·沃尔夫（William Wulf）和他的同伴没有放弃旧术语，而是新添加了一个迷人但有点自相矛盾的名称“中端”。

2 . 1 . 4中间表示

你可以把编译器看成是一条流水线，每个阶段的工作是把代表用户代码的数据组织起来，使下一阶段的实现更加简单。流水线的前端是针对程序所使用的源语言编写的。后端关注的是程序运行的最终架构。

在中间阶段，代码可能被存储在一些中间表示（intermediate representation， 也叫IR）中，这些中间表示与源文件所使用的编程语言或目的文件所使用的编程语言都没有紧密的联系（因此叫作“中间表示”）。相反，IR充当了这两种语言之间的接口。

这可以让你更轻松地支持多种源语言和多种目标平台。假设你想实现Pascal、C和Fortran编译器，并且你想针对x86、ARM，还有SPARC体系结构开发编译器。通常情况下，这意味着你需要写九个完整的编译器：Pascal→x86，C→ARM，以及其他各种组合。

一个共享的中间表示可以大大减少这种情况。你为每个产生IR的源语言写一个前端。然后为每个目标平台写一个后端。现在，你可以将这些混搭起来，得到每一种组合。

还有一个重要的原因是，我们可能希望将代码转化为某种形式，使语义更加明确 . . . 。

2 . 1 . 5优化

一旦我们理解了用户程序的含义，我们就可以自由地用另一个具有相同语义但实现效率更高的程序来替换用户程序——我们可以对它进行优化。

一个简单的例子是常量折叠：如果某个表达式求值得到的始终是完全相同的值，我们可以在编译时进行求值，并用其结果替换该表达式的代码。如果用户输入：

pennyArea = 3.14159 * (0.75 / 2) * (0.75 / 2);

我们可以在编译器中完成所有的算术运算，并将代码更改为：

pennyArea = 0.4417860938;

优化是编程语言业务的重要组成部分。许多编程语言黑客把他们的整个职业生涯都花在了这里，竭尽所能地从他们的编译器中挤出每一点性能，以使他们的基准测试速度提高一个百分点。这可能会成为一种困扰。

我们在本书中会跳过优化这个棘手的问题。许多成功的语言令人惊讶地很少进行编译时优化。例如，Lua和CPython生成相对未优化的代码，并将其大部分性能工作集中在运行时上。

2 . 1 . 6代码生成

我们已经将所有可以想到的优化应用到了用户程序中。最后一步是将其转换为机器可以实际运行的形式。换句话说，生成代码（或代码生成），这里的“代码”通常是指CPU运行的类似于汇编的原始指令，而不是人类可能想要阅读的“源代码”。

最后，我们到了后端，从山的另一侧开始向下。从现在开始，随着我们越来越接近于思维简单的机器可以理解的东西，我们对代码的表示变得越来越原始，就像逆向进化。

我们需要做一个决定。我们是为真实CPU还是虚拟CPU生成指令？如果我们生成真实的机器代码，则会得到一个可执行文件，操作系统可以将其直接加载到芯片上。原生代码的执行速度快如闪电，但生成它需要大量工作。当今的体系结构包含大量指令，复杂的流水线和足够塞满一架波音747飞机行李舱的历史包袱。

使用芯片的语言也意味着你的编译器是与特定的架构相绑定的。如果你的编译器以x86机器代码为目标，那么它就无法在ARM设备上运行。一直到60年代，在计算机体系结构的寒武纪大爆发期间，这种缺乏可移植性的情况是一个真正的障碍。

为了解决这个问题，像BCPL的Martin Richards和Pascal的Niklaus Wirth这样的黑客，让他们的编译器生成虚拟机代码。他们不是为真正的芯片编写指令，而是为一个假设的、理想化的机器编写代码。Wirth称这种p-code为“可移植代码”，但今天，我们通常称它为字节码，因为每条指令通常都是一个字节长。

这些合成指令的设计是为了更紧密地映射到编程语言的语义上，而不必与任何一个计算机体系结构的特性和它积累的历史错误绑定在一起。你可以把它想象成编程语言底层操作的密集二进制编码。

2 . 1 . 7虚拟机

如果你的编译器产生了字节码，你的工作还没有结束。因为没有芯片可以执行这些字节码，因此你还需要进行翻译。同样，你有两个选择。你可以为每个目标体系结构编写一个小型编译器，将字节码转换为该机器的机器代码。你仍然需要针对你支持的每个芯片做一些工作，但最后这个阶段非常简单，你可以在你想要支持的所有机器上重复使用编译器流水线的其余部分。你基本上是把你的字节码作为一个中间表示。

或者，你可以编写虚拟机（VM），该程序可在运行时模拟支持虚拟体系结构的虚拟芯片。在虚拟机中运行字节码比提前将其翻译成机器代码要慢，因为每条指令每次执行时都必须在运行时模拟。作为回报，你得到的是简单性和可移植性。用比如说C语言实现你的虚拟机，你就可以在任何有C编译器的平台上运行你的语言。这就是我们在本书中构建的第二个解释器的工作原理。

2 . 1 . 8运行时

我们终于将用户程序锤炼成可以执行的形式。最后一步是运行它。如果我们将其编译为机器码，我们只需告诉操作系统加载可执行文件，然后就可以运行了。如果我们将它编译成字节码，我们需要启动VM并将程序加载到其中。

在这两种情况下，除了最基本的底层语言外，我们通常需要我们的语言在程序运行时提供一些服务。例如，如果编程语言是自动管理内存的，我们需要一个垃圾收集器去回收未使用的比特位。如果我们的语言支持“instance of”测试，这样你就可以看到你有什么类型的对象，那么我们就需要一些表示方法来跟踪执行过程中每个对象的类型。

所有这些东西都是在运行时进行的，所以它被恰当地称为，运行时。在一个完全编译的语言中，实现运行时的代码会直接插入到生成的可执行文件中。比如说，在Go中，每个编译后的应用程序都有自己的一份Go的运行时副本直接嵌入其中。如果语言是在解释器或虚拟机内运行，那么运行时将驻留于虚拟机中。这也就是Java、Python和JavaScript等大多数语言实现的工作方式。

2 . 2捷径和备选路线

这是一条漫长的道路，涵盖了你要实现的每个可能的阶段。许多编程语言的确走完了整条路线，但也有一些捷径和备选路径。

2 . 2 . 1单遍编译器

一些简单的编译器将语法分析、语义分析和代码生成交织在一起，这样它们就可以直接在语法分析器中生成输出代码，而无需分配任何语法树或其他IR。这些单遍编译器限制了编程语言的设计。你没有中间数据结构来存储程序的全局信息，也不会重新访问任何之前语法分析过的代码部分。这意味着，一旦你看到某个表达式，就需要足够的知识来正确地对其进行编译。

Pascal和C语言就是围绕这个限制而设计的。在当时，内存非常珍贵，一个编译器可能连整个源文件都无法存放在内存中，更不用说整个程序了。这也是为什么Pascal的语法要求类型声明要放在一个块的最前面。这也是为什么在C语言中，你不能调用后面才会定义的函数，除非在调用位置之前就明确地声明要调用的函数，告诉编译器它需要知道什么，以便生成调用后面才会定义的函数的代码。

2 . 2 . 2树遍历解释器

有些编程语言在将代码语法分析为AST后就开始执行代码（可能应用了一点静态分析）。为了运行程序，解释器每次都会遍历语法树的一个分支和叶子，并在运行过程中计算每个节点。

这种实现风格在学生项目和小型语言中很常见，但在通用编程语言中并不广泛使用，因为它往往很慢。有些人使用“解释器”仅指这类实现，但其他人对“解释器”一词的定义更宽泛，因此我将使用没有歧义的“树遍历解释器”来指代这些实现。我们的第一个解释器就是这样工作的。

2 . 2 . 3转译器

为一种语言编写一个完整的后端可能需要大量的工作。如果你有一些现有的通用IR作为目标，则可以将前端转换到该IR上。否则，你可能会陷入困境。但是，如果你将某些其他源语言视为中间表示，该怎么办？

你需要为你的编程语言编写一个前端。然后，在后端，你可以生成一份与你的编程语言层级差不多的其他语言的有效源代码字符串，而不是将所有代码降低到某个原始目标语言的语义。然后，你可以使用该语言现有的编译工具作为逃离大山的路径，得到某些可执行的内容。

人们过去称之为源到源编译器或转换编译器。随着那些为了在浏览器中运行而编译成JavaScript的各类语言的兴起，它们有了一个时髦的名字——转译器。

虽然第一个编译器是将一种汇编语言翻译成另一种汇编语言，但现今，大多数编译器都适用于高级语言。在UNIX病毒式地传播到各种各样的机器之后，开始了一个悠久的编译器传统，即编译器以C语言作为输出语言。只要UNIX存在，就可以使用C编译器，并生成有效的代码，因此，以C为目标是让语言在许多体系结构上运行的好方法。

Web浏览器是今天的“机器”，它们的“机器代码”是JavaScript，所以现在似乎几乎所有的语言都有一个以JS为目标的编译器，因为这是让你的代码在浏览器中运行的主要方式。

编译器的前端（扫描器和语法分析器）看起来跟其他编译器相似。然后，如果源语言只是在目标语言之上包装的简单语法外壳，则它可能会完全跳过分析，并直接输出目标语言中的类似语法。

如果两种语言的语义差异较大，那么你就会看到完整编译器的更多典型阶段，包括分析甚至优化。然后，在代码生成阶段，无需输出一些像机器代码一样的二进制语言，而是在目标语言中生成一串语法正确的源码（好吧，目标代码）。

不管是哪种方式，你再通过目标语言已有的编译流水线运行生成的代码，就可以了。

2 . 2 . 4即时编译

最后一个与其说是捷径，不如说是危险的高山争霸赛，最好留给专家。执行代码最快的方法是将代码编译成机器代码，但你可能不知道你的最终用户的机器支持什么架构。该怎么做呢？

你可以做和HotSpot JVM、Microsoft的CLR和大多数JavaScript解释器相同的事情。在终端用户的机器上，当程序加载时（无论是从JS中还是从源代码加载，或者是JVM和CLR的平台无关的字节码），都可以将其编译为对应的本机的机器代码，以适应本机支持的体系结构。自然地，这被称为即时编译。大多数黑客只是说“JIT”，其发音与“fit”押韵。

最复杂的JIT将性能分析钩子插入到生成的代码中，以查看哪些区域对性能最为关键，以及哪些类型的数据正在流经其中。然后，随着时间的推移，它们将通过更高级的优化功能自动重新编译那些热点部分。

2 . 3编译器和解释器

现在我已经向你的脑袋里塞满了一大堆编程语言术语，我们终于可以解决一个自远古以来一直困扰着程序员的问题：编译器和解释器之间有什么区别？

事实证明，这就像问水果和蔬菜的区别一样。这看上去似乎是一个非此即彼的选择，但实际上“水果”是一个植物学术语，“蔬菜”是烹饪学术语。严格来说，一个并不意味着对另一个的否定。有不是蔬菜的水果（苹果），也有不是水果的蔬菜（胡萝卜），也有既是水果又是蔬菜的可食用植物，比如西红柿。

好，回到编程语言上：

• 编译是一种实现技术，其中涉及到将源语言翻译成其他语言——通常是较低级的形式。当你生成字节码或机器代码时，你就是在编译。当你移植到另一种高级语言时，你也在编译。
• 当我们说语言实现“是编译器”时，是指它会将源代码转换为其他形式，但不会执行。用户必须获取结果输出并自己运行。
• 相反，当我们说一个实现“是解释器”时，是指它接受源代码并立即执行它。 它“从源代码”运行程序。

像苹果和橘子一样，某些实现显然是编译器，而不是解释器。GCC和Clang接受你的C代码并将其编译为机器代码。最终用户直接运行该可执行文件，甚至可能永远都不知道使用了哪个工具来编译它。所以这些是C的编译器。

在Matz的旧版本的Ruby规范实现中，用户从源代码中运行Ruby。该实现通过遍历语法树对其进行语法分析并直接执行。期间都没有发生其他的转换，无论是在实现内部还是以任何用户可见的形式。所以这绝对是一个Ruby的解释器。

但是CPython呢？当你使用它运行你的Python程序时，代码会被语法分析并转换为内部字节码格式，然后在虚拟机内部执行。从用户的角度来看，这显然是一个解释器——他们是从源代码开始运行自己的程序。但如果你看一下CPython的内部，你会发现肯定有一些编译工作在进行。

答案是两者兼而有之。CPython是一个解释器，但它也有一个编译器。实际上，大多数脚本语言都以这种方式工作，如你所见：

中间那个重叠的区域也是我们第二个解释器所在的位置，因为它会在内部将编程语言编译成字节码。所以，虽然本书名义上是关于解释器的，但我们也会涉及一些编译的内容。

2 . 4我们的旅程

一下子有太多东西要消化掉。别担心。这一章并不是要求你理解所有这些零碎的内容。我只是想让你们知道它们是存在的，以及大致了解它们是如何组合在一起的。

当你探索本书所指导的路径之外的领域时，这张地图应该对你很有用。我希望你自己出击，在那座山里到处游走。

但是，现在，是我们自己的旅程开始的时候了。系好你的鞋带，背好你的包，走吧。从这里开始，你需要关注的是你面前的路。