Crafting Interpreters - [1-2] A Map of the Territory

你一定要有一副地图，否则在这个世界里你只能像无头苍蝇般。在《指环王》中，我从未让任何人在某一天走得超过他的极限。

​ - J.R.R.Tolkien

我们不想像无头苍蝇一般，所以在我们动身之前，一起来看看语言实现人员所描绘的领域。它将帮助我们了解我们要去哪里

首先，让我来速记一下。这本书的大部分内容是关于一种语言的实现，它以某种柏拉图式的理想形式不同于语言本身。像堆栈、字节码和递归下行这样的东西，是一个特定实现可能会用到的具体细节。从用户的角度来看，只要产生的新语言遵循语言的规范，其就是所有的实现细节。

我们将在这些细节上花费大量时间，因此，如果我每次提到它们时都要写“语言实现”，那对我来说太痛苦了，手都会敲疼。 取而代之的是，除非区别不明显，否则我将使用“语言”来指代一种语言或一种语言的实现，或同时使用这两种语言。

2.1 语言的组成部分

自从计算机的黑暗时代以来，工程师们就一直在构建编程语言。我发现很有趣的一点是，尽管今天的机器确实比现在快了一百万倍，存储空间也比现在大了一个数量级，但我们构建编程语言的方式几乎没有改变。

并非每种语言都采用完全相同的路径（有些采用一种或两种捷径），但是令人难以置信的是，它们与从后海军上将Grace Hopper的第一个COBOL编译器一直到某些新的流行的JavaScript转换语言都很相似（其“文档”在某个Git存储库中完全由一个未经编辑的README文件组）。

我将实现可以选择的路径网络可视化为爬山。你从程序作为原始源文本的底部开始（其实就是一串字符）。每个阶段都分析程序，并将其转换为更高层次的表示，这样作者想要计算机做的语义就变得更加明显。

最终我们到达了顶峰。我们对用户的程序有一个鸟瞰，可以看到他们（语言开发人员）代码的意思。接下来，我们下到山的另一边。我们从这个最高级别的表示转换到一个接一个的低级别的形式，以便越来越接近我们知道如何让CPU实际执行的东西。

让我们跟踪每一个轨迹和感兴趣的点。我们的旅程将会从下面一句简单的用户源码文本开始。

2.1.1 扫描

第一步是扫描，也称为lexing（语法分析），或者(如果你想给某人留下深刻印象)lexical analysis（同语法分析，但是换了种表达方式）。它们的意思都差不多。我喜欢用lexing，因为它听起来像一个邪恶的超级恶棍会做的事情，但我将使用扫描，因为它似乎更贴近平常一些。

扫描器(或lexer)接受线性的字符流，并将它们块成一系列更类似于单词的东西。在编程语言中，这些词中的每一个都称为标记。有些标记是单个字符，如 ( 和 ，) 。其他可能是几个字符长，比如数字 (123) 、字符串常量 (“hi!”) 和标识符 (min) 。

源文件中的一些字符实际上并没有释义。空格通常是无关紧要的，而注释则被语言所忽略。扫描器通常会丢弃这些标记，只留下一系列有意义的标记。

2.1.2 解析

下一步是解析。这就是我们的语法能够从较小的部分组成较大的表达式和语句的地方。你在英语课上解释过句子吗？如果是这样，那么你做的和解析器所做的工作一样，只不过英语有成千上万的关键字和大量的歧义。编程语言要简单得多。

解析器接受标记的平面序列，并构建反映语法嵌套性质的树结构。这些树有两个不同的名称，解析树或抽象语法树，取决于它们与源语言的纯语法结构有多接近。在实践中，语言研究者通常称它们为语法树、ast，或者通常只是树。

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

事实证明，对于那些解析器能够处理的严格语法来说，人类语言太过混乱，但它们非常适合编程语言的更简单的人工语法。我们这些有缺陷的人仍然不能正确地使用这些简单的语法，因此解析器的工作还包括通过报告语法错误来告诉我们。

2.1.3 静态分析

前两个阶段在所有实现中都非常相似。现在，每种语言的各自特点开始发挥作用。现在，我们知道了代码的句法结构，比如运算符优先级和表达式嵌套，但除此之外，我们所了解的就不多了。

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

大多数语言做的第一个分析称为绑定或解析。对于每个标识符，我们找出该名称的定义位置，并将两者连接在一起。这就是作用域发挥作用的地方——源代码的区域，在这里可以使用某个名称来引用某个声明。

如果语言是静态类型的，这就是我们进行类型检查的时候。一旦我们知道a和b在哪里声明，我们还可以找出它们的类型。然后，如果这些类型不支持相互添加，我们报告一个类型错误。

深呼吸一下。我们已经快到顶了，对用户程序有了全面的了解。所有这些通过分析可见的语义分析都需要存储在某个地方。有几个地方我们可以把它储存起来：

• 通常，它作为语法树本身的属性被存储回节点中的额外字段，这些字段在解析期间没有初始化，但稍后会填充。
• 其他时候，我们可能将数据存储在一个查找表的一边。通常，这个表的键是变量的标识符、名称和声明。在这种情况下，我们称之为符号表，它与每个键关联的值告诉我们标识符指的是什么。
• 更加厉害的方法是将树转换为一个全新的数据结构，更直接地表达代码的语义。这是下一部分。

到此为止的所有内容都被认为是实现的前端。你可能会猜这之后的一切都是后端，但不是。在以前，当前端和后端都被创造出来的时候，编译器要简单得多。后来，研究人员发明了新的阶段，在两半之间填充。William Wulf和他的同事并没有抛弃旧的术语，而是将它们集中到一个迷人但空间上自相矛盾的名称“中端”。

2.1.4 代码的中间表示

你可以将编译器看作是一个管道，其中每个阶段的工作是组织代码，使下一个阶段更容易实现。管道的前端与用户正在编程的源语言有关。后端与代码将运行的最终架构有关。

在前后端中间，代码可以存储在一些中间表示(或IR)中，这些表示与源代码或目标码(因此是中间表示形式)没有紧密联系。相反，IR充当这两种语言之间的接口。

这使你可以更轻松地支持多种源语言和目标平台。假设你想实现Pascal, C和Fortran编译器，使其针对x86, ARM，还有SPARC等运行。通常，完成这些你要注册编写9个完整的编译器:Pascal --> x86、C —> ARM和每一个其他的组合。

共享的中间表示专门用来解决这种问题。你为每一种源语言编写一个前端，使其转化为中间表示。然后每个目标架构都有一个后端，用来将中间表示再进行编译和运行。于是你只需要针对前端与后端分别编写代码转换器，前端代码转换为中间表示形式，然后中间表示再通过后端编译器转化为后端可以运行的代码。

2.1.5 优化

一旦我们理解了用户程序的所要做的事情，我们就可以用一个表达方式来替换它，这个表达方式有相同的语义，但是实现起来更高效，我们可以优化它。一个简单的例子是常数折叠:如果某个表达式总是计算出完全相同的值，我们可以在编译时执行计算，并用表达式的结果替换表达式的代码。如果用户输入

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

我们可以将其转换为另一种表达方式：

pennyArea = 0.4417860938;

上面两个语句虽然意思相同，但是明显第二种表达方式的效率更高，避免了重复的计算来消耗计算机资源。

优化是编程语言业务的重要组成部分。许多语言研究者在这里度过了整个职业生涯，他们尽其所能地从编译器中压缩性能，以使他们的基准测试速度提高几分之一。

在这本书里，我们多半要跳过这个部分。许多成功的语言很少有编译时优化。例如，Lua和CPython生成的代码相对没有优化，它们的性能工作主要集中在”运行时“上。

2.1.6 代码生成

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

最后，我们到了后端，从山的另一边往下走。从现在开始，我们对代码的表示变得越来越原始，就像反向进化一样，因为我们越来越接近头脑简单的机器能够理解的东西。

我们要做一个决定。我们是为真实的CPU生成指令还是为虚拟的CPU生成指令?如果我们生成真正的机器码，我们得到一个操作系统可以直接加载到芯片上的可执行文件。Native代码非常快，但是其生成过程需要大量的工作。今天的架构有成堆的指令，复杂的管道，和足够装满一架747的历史包袱。

使用用于芯片的语言也意味着你的编译器被绑定到一个特定的架构上。如果编译器的目标是x86机器码，它就不会在ARM设备上运行。回溯到60年代，在计算机架构的寒武纪大爆发期间，缺乏可移植性是一个真正的障碍。

为了解决这个问题，像马丁•理查兹(Martin Richards)和尼克劳斯•沃斯(Niklaus Wirth)这样的极客，分别以BCPL和Pascal而闻名，他们让自己的编译器生成虚拟机代码。他们不是为真正的芯片编写指令，而是为一台假想的、理想化的机器编写代码。Wirth称其为p-code，表示可移植，但今天，我们通常称其为字节码，因为每条指令通常是一个字节长。

2.1.7 虚拟机

如果编译器生成字节码，那么工作还没有结束。由于没有芯片直接运行这种字节码，将其翻译为机械码也是我们需要做的。这种情况下，有两条路。你可以为每个目标体系结构编写一个小型的微型编译器，将字节码转换为本机代码。

或者你可以自己写一个虚拟机，一个可以在运行时，模拟支持虚拟体系结构的程序。在VM中运行字节码比提前将其转换为本机代码要慢，因为每次执行指令时都必须在运行时进行模拟。当然，你的语言就获得了简单性和可移植性。比如说，用C实现你的VM，你就可以在任何有C编译器的平台上运行你的语言。这就是我们的第二个解释器所做的。

2.1.8 运行时

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

在这两种情况下，除了最基本的低级语言之外，我们通常需要在程序运行时需要一些语言支持的服务。例如，如果语言自动管理内存，我们需要一个垃圾收集器来回收未使用的内存。如果我们的语言支持测试实例，那么我们需要一些数据来跟踪每个对象在执行期间的类型。

所有这些都是在运行时进行的，所以它叫做运行时。在完全编译的语言中，实现运行时的代码将直接插入到结果可执行文件中。例如，在Go中，每个编译后的应用程序都有自己的Go运行时副本直接嵌入其中。这就是Java、Python和JavaScript等语言的大多数实现的工作方式。

2.2 捷径与替换的线路

这是一条涵盖你可能实现的每一个阶段的漫长道路。许多语言都有对应完整的实现，但也有一些捷径和替代路径。

2.2.1 单遍编译器

一些简单的编译器将解析、分析和代码生成交织在一起，因此它们直接在解析器中生成输出代码，而不分配任何语法树或其他IRs。这些单遍编译器限制了语言的设计。这些语言没有中间数据结构来存储关于程序的全局信息，而且也不会重新访问代码中以前解析过的任何部分。这意味着只要对于一个表达式，在编译的时候，必须要有足够的信息，而只用将其编译一次就通过。

Pascal和C就是遵循该规定的语言。当时，内存是如此珍贵，以至于编译器甚至不能在内存中保存整个源文件，更不用说整个程序了。这就是为什么Pascal类语法要求类型声明首先出现在块中。这同时也是为什么在C语言中，你不能在定义函数的代码之上调用函数，除非你有一个显式的前向声明，告诉编译器它需要知道什么来生成调用后一个函数的代码。

2.2.2 树遍历解释器

一些编程语言在将代码解释为AST后，便开始执行代码（可能也会附带一些静态分析）。这些语言遍历了语法树的每一个分支和叶子，评估每一个遍历走过的节点，以使程序运行起来。

这种解释器风格在学生项目和小众语言中很常见，但在通用语言中并不广泛使用，因为它往往比较慢。一个值得注意的例外是Ruby的原始实现，在版本1.9之前它是一个树漫步器。

有些人使用“解释器”来表示这些类型的实现，但其他人对这个词的定义更为普遍，因此我将使用无可争议的显式树遍历解释器来指代这些实现。我们的第一个解释器是采用的就是这种树遍历解释器。

2.2.3 Transpiler 转编器

为一种语言编写完整的后端可能需要大量的工作。如果你有一些现有的通用IR目标，你可以把你的前端绑在它上面。否则，接下来的进展就不好继续下去。但是，如果将其他源语言视为中间表示会怎样呢？

我们为我们的语言编写一个前端。然后，在后端，我们无需做将该中间表示转化为机械码的工作，而是转化为和我们语言同样高级的语言的代码。然后，我们使用该语言现有的编译工具，作为我们从山顶吓到山脚的路。

他们过去称其为源到源编译器或转编译器。在编译成JavaScript以便在浏览器中运行的语言兴起之后，便出现了新词“transpiler”。

第一个转编译器将一种汇编语言翻译成另一种汇编语言，而今天，几乎所有的转编译器都在高级语言上工作。在UNIX流行于各种各样的机器后，开始了产生C作为输出语言的编译器的长期传统。只要有UNIX，就可以使用C编译器并生成高效的代码，因此以C为目标是让语言在许多体系结构上运行的好方法。

Web浏览器可以说是当今人们用的最多的软件，若将其比喻成操作系统，那它的机器代码就是JavaScript，所以现在几乎所有的语言都有一个针对JS的编译器，显而易见是为了是让代码在浏览器中运行。

转编器的前端扫描器和解析器看起来像其他语言的编译器。如果我们的语言只是目标语言上的一个简单的语法外壳，那么它可以完全跳过分析，直接输出目标语言中的类似语法。

如果这两种语言在语义上不是很相同，那么我们将看到完整编译器更多典型的阶段，包括分析甚至优化。然后在代码生成方面，我们的语言不是输出一些二进制语言(如机器代码)，而是生成目标语言的代码。

无论采用哪种方式，我们都可以通过输出语言的现有编译器运行结果代码，这样就算打到我们的目的了。

2.2.4 即时编译

最后一条不是我们所想像的捷径，相反，其很具有挑战性。执行代码的最快方法是将其编译为机器码，但是我们可能不知道最终用户的机器支持什么体系结构。那么我们该怎么做呢？

我们可以学习一下HotSpot JVM、Microsoft s CLR和大多数JavaScript解释器的做法。在最终用户的机器上，当程序以JS的形式从源代码加载时，或者以JVM和CLR的独立于平台的字节码加载时，其可以将其编译为本机架构支持的代码形式，以满足不同系统都可以运行的需求（Java曾经的宣传口号就是“write once，run anywhere”，即一次性开发完后，在不同系统上都可以直接运行）。这就是即时编译。大家基本都用JIT来简称Just-in-time。

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

2.3 Compilers and Interpreters 编译器与解释器

到目前为止，我们已经解除了大量编程语言术语，且面临了一个自古以来一直困扰程序员的问题：编译器和解释器之间有什么区别?

这就像问水果和蔬菜的区别一样。这似乎是一个非此即彼的选择，但实际上水果也是一个植物，而蔬菜也能生吃。一个并不意味着否定另一个。有非蔬菜的水果(苹果)和非水果的蔬菜(胡萝卜)，但也有可食用的植物，既是水果又是蔬菜，就像我们常吃的西红柿。

我们回到语言上：

• 编译是一种实现技术，涉及到将源语言转换为其他一些通常较低级别的形式。当我们的语言生成字节码或机器码时，就是在进行编译。当转换到另一种高级语言时，还是在编译。

• 当我们说语言实现是一个编译器时，我们的意思是它将源代码翻译成其他形式，但不执行它。用户必须获得结果输出并自己运行它。

• 相反，当我们说实现是解释器时，我们的意思是它接受源代码并立即执行它。它从源代码开始，直接运行程序。

就像苹果和橘子一样，有些实现显然是编译器而不是解释器。GCC和Clang将C代码编译成机器码。最终直接运行该可执行文件，用户可能不会甚至不用不知道使用了哪个工具来编译它。C语言的编译器就是这样的。

在较老版本的Matz规范Ruby实现中，用户从源代码运行Ruby。该实现不仅解析源代码，害通过遍历语法树直接运行它。源代码在语言内部或者以任何用户可见的形式，没有被编译、解释。所以这绝对是Ruby的一个解释器。

但是CPython呢？当使用它运行Python程序时，代码将被解析并转换为内部字节码格式，然后在VM中执行。从用户的角度来看，这显然是一个从源代码运行程序的解释器。但是你会发现CPython也有编译的过程。那CPython到底算什么呢？

答案是它两者都有，两者都算。CPython是一个解释器，但它也有一个编译器。在实践中大多数脚本语言都是这样工作的，下图可见：

我们的第二个解释器就术语中心的重叠区域的范围，因为它在内部编译成字节码。因此，虽然这本书名义上是关于解释器的，但我们也将涉及一些汇编。

2.4 我们的愉（shou）快（ku）之旅

一次要消化的东西太多了。但不用担心，这一章不期望你理解所有这些部分和内容。我只是想让你们知道它们是存在的以及了解一下它们是如何结合在一起的。

当我们想探索超越这本书中范围内的道路和领域时，这份地图也对我们很有帮助。我想让你渴望着自己去闯一闯，漫游这座技术大山中的每个地方。

但是，现在是时候开始我们自己的旅程了。系紧你的鞋带，收起你的背包，一起走吧。从现在开始，你所需要关注的就是你面前的路。

原文链接：Introduction

阅读并翻译者：Javen Liu