Introduction

Fairy tales are more than true: not because they tell us that dragons exist, but because they tell us that dragons can be beaten.

G.K. Chesterton by way of Neil Gaiman, Coraline

我真的很兴奋我们能一起踏上这段旅程。这是一本关于为编程语言实现解释器的书。它也是一本关于如何设计一种值得实现的编程语言的书。我刚开始接触编程语言的时候就希望我能够看到这样的书，而这本书我在脑子里已经写了将近十年了。

在本书中，我将一步一步地介绍一种功能齐全的编程语言的两个完整的解释器实现。我假设这是你第一次涉足编程语言这个领域，因此我将介绍并构建一个完整、可用、快速的编程语言所需的每个概念和代码。

为了在一本书中塞进两个完整的实现，而且避免这变成一个门槛，本书（相比其它书籍）不会在理论上着墨太多。在构建系统的每个模块时，我将介绍它背后的历史和概念。我会尽力让你熟悉这些程序设计语言领域的行话，这样的话，即便你在充满PL（编程语言）研究人员的鸡尾酒会中，也能快速融入其中。

但我们主要还是要花费精力让这门编程语言运行起来。这并不是说理论不重要。在学习一门编程语言时，能够对语法和语义进行精确而形式化的推理是一项至关重要的技能。但是，就我个人而言，我通过实践来学习理论，效果最好。对我来说，要深入阅读那些充满抽象概念的书本并真正理解它们太难了。但是，如果我（根据理论）编写了代码，运行并调试成功，那么我就明白了。

这就是我对你的期望。我想让你们直观地理解一门真正的编程语言是如何生活和呼吸的。我的希望是，由于你已经自己实现过一门编程语言，在这个坚实的基础之上，当你以后阅读其他理论性更强的书籍时，这些概念会牢牢地留在你的脑海中。

1 . 1为什么要学习这些知识？

每一本编译器相关书籍的前言似乎都有这一节。我不知道为什么编程语言会引起这种存在性的怀疑。我认为鸟类学书籍作者完全不需要去顾虑一个问题，那就是，为什么需要存在鸟类学这一学科？他们假设读者喜欢鸟，然后就开始讲授内容。

但是编程语言有一点不同。我认为，对我们中的任何一个人来说，能够创建一种广泛成功的通用编程语言的可能性都很小，这是事实。设计世界级的通用编程语言的设计师们，一辆汽车就能装得下。如果加入这个精英群体是学习编程语言的唯一原因，那么就很难证明其合理性。幸运的是，事实并非如此。

1 . 1 . 1小型编程语言无处不在

对于每一种成功的通用编程语言，都有上千种成功的小众编程语言。我们过去称它们为“小语言”，但术语泛滥的今天它们有了新的名字：“领域特定语言（即DSL）”。这些是为特定任务量身定做的洋泾浜语言，如应用程序脚本语言、模板引擎、标记语言和配置文件。

几乎每个大型软件项目都需要一些这样的工具。如果可以的话，最好重用现有的工具，而不是自己动手实现。一旦考虑到文档、调试器、编辑器支持、语法高亮显示和所有其他可能的障碍，自己实现一门编程语言就成了一项艰巨的任务。

但是，当现有的库不能满足你的需要时，你仍然很有可能发现自己需要一个语法分析器或其他东西。即使当你重用一些现有的实现时，你也不可避免地需要调试和维护它们，并在其内部进行探索。

1 . 1 . 2实现编程语言是很好的锻炼

长跑运动员有时会在脚踝上绑上重物，或者在空气稀薄的高海拔地区进行训练。当他们卸下自己的负担以后，轻便的肢体和富氧的空气带来了新的相对舒适度，使它们可以跑得更快，更远。

实现一门语言是对编程技能的真正考验。代码很复杂，而性能很关键。你必须掌握递归、动态数组、树、图和哈希表。你在日常编程中至少使用过哈希表，但你对它们的理解程度有多高呢？嗯，等我们从头完成我们的作品之后，我相信你会理解的。

虽然我想说明解释器并不像你想的那样令人生畏，但实现一个好的解释器仍然是一个挑战。学会了它，你就会成为一个更强大的程序员，并且在日常工作中也能更加聪明地使用数据结构和算法。

1 . 1 . 3最后一个原因

最后一个原因我很难承认，因为它是很私密的理由。自从我小时候学会编程以来，我就觉得编程语言有种神奇的力量。当我第一次一个键一个键地输入BASIC程序时，我无法想象BASIC语言本身是如何制作出来的。

后来，当我的大学朋友们谈论他们的编译器课程时，脸上那种既敬畏又恐惧的表情足以让我相信，编程语言黑客是另一种人，某种获得了通向神秘艺术的特权的巫师。

这是一幅迷人的图像，但它也有黑暗的一面。我感觉自己不像个巫师，所以我认为自己缺乏加入秘社所需的先天品质。尽管自从我在学校笔记本上拼写关键词以来，我一直对编程语言着迷，但我花了数十年的时间鼓起勇气尝试真正地学习它们。那种“神奇”的品质，那种排他性的感觉，将我挡在门外。

当我最终开始拼凑我自己的小型编译器时，我很快意识到，根本就没有魔法。编译器只是代码，而那些掌握编程语言实现的人也只是人。

有一些技巧是你在编程语言之外不会经常遇到的，而且有些部分有点难。但不会比你克服的其他障碍更困难。我希望，如果你对编程语言感到害怕，而这本书能帮助你克服这种恐惧，也许我会让你比以前更勇敢一点。

而且，说不准，你也许会创造出下一个伟大的编程语言，毕竟总要有人做。

1 . 2本书的组织方式

这本书分为三个部分。你现在正在读的是第一部分。这部分用了几章来让你进入状态，教你一些编程语言黑客们使用的行话，并向你介绍我们将要实现的编程语言Lox。

其他两个部分则分别构建一个完整的Lox解释器。在这些部分中，每个章节的结构都是相同的。每一章节挑选编程语言的某个特性，并教你背后对应的概念，然后逐步介绍实现方法。

我花了不少时间去试错，但我还是成功地把这两个解释器按照章节分成了一些小块，每一小块的内容都会建立在前面几章的基础上，但不需要后续章节的知识。从第一章开始，你就会有一个可以运行和使用的工作程序。随着章节的推移，程序的功能越来越丰富，直到你最终拥有一门完整的编程语言。

除了大量妙趣横生的英文段落，章节中还会包含一些其它的惊喜：

1 . 2 . 1代码

本书是关于制作解释器的，所以其中会包含真正的代码。所需要的每一行代码都需要包含在内，而且每个代码片段都会告知你需要插入到实现代码中的什么位置。

许多其他的编程语言书籍和编程语言实现都使用Lex和Yacc这样的工具，也就是所谓的生成编译器的编译器，可以从一些更高层次的（语法）规范中自动生成一些实现的源文件。这些工具有利有弊，而且双方都有强烈的主张——有些人可能将其说成是信仰。

我们这里不会使用这些工具。我想确保魔法和困惑不会藏在黑暗的角落，所以我们会选择手写所有代码。正如你将看到的，这并没有听起来那么糟糕，因为这意味着你将真正理解每一行代码以及两种解释器的工作方式。

一本书和“真实世界”所面对的约束是有区别的，因此这里的代码风格可能并不是编写可维护地产品级软件的最佳实践。可能我对某些写法是无所谓的，比如可能我会省略private关键字或者声明一些全局变量，请理解我这样做是为了让你更容易看懂代码。书页不像IDE窗口那么宽，所以每一个字符都很珍贵。

另外，代码也不会有太多的注释。这是因为每一部分代码前后，都使用了一些真的很简洁的文字来对其进行解释。当你写一本书来配合你的程序时，欢迎你也省略注释。否则，你可能应该比我使用更多的//。

虽然这本书包含了每一行代码，并教授了每一行代码的含义，但它没有描述编译和运行解释器所需的机制。我假设你可以在IDE中选择一个Makefile或一个项目导入，以使代码运行。这类说明很快就会过时，我希望这本书能像XO白兰地一样醇久，而不是像家酿酒（一样易过期）。

1 . 2 . 2代码片段

因为这本书包含了实现所需的每一行代码，所以代码片段相当精确。此外，即使是在缺少编程语言的一些主要功能的时候，我也尝试将程序保持在可运行状态。因此我们有时会添加临时代码，这些代码将在以后的代码段中替换。

一个完整的代码片段可能如下所示：

      default:

        if (isDigit(c)) {
          number();
        } else {
          Lox.error(line, "Unexpected character.");
        }

        break;

中间是要添加的新代码。这部分代码的上面或下面可能有一些淡出的行，以显示它在周围代码中的位置。还会附有一小段介绍，告诉你在哪个文件中以及在哪里放置代码片段。如果简介说要“替换 x 行”，表明在浅色的行之间有一些现有的代码需要删除，并替换为新的代码片段。

1 . 2 . 3题外话

题外话中包含传记简介、历史背景、对相关主题的引用以及对其他要探索的领域的建议。你无需深入了解就可以理解本书的后续部分，因此可以根据需要跳过它们。我不会批评你，但我可能会有些难过。

1 . 2 . 4挑战

每章结尾都会有一些练习题。不像教科书中的习题集那样用于回顾已讲述的内容，这些习题是为了帮助你学习更多的知识，而不仅仅是本章中的内容。它们会迫使你走出文章指出的路线，自行探索。它们将要求你研究其他编程语言，弄清楚如何实现某些其它功能，换句话说，就是使你走出舒适区。

克服挑战，你将获得更广泛的理解，也可能遇到一些挫折。如果你想留在旅游巴士的舒适区内，也可以跳过它们。都随你便。

1 . 2 . 5设计笔记

大多数编程语言书籍都是严格意义上的编程语言实现书籍。他们很少讨论如何设计正在实现的语言。实现之所以有趣，是因为它的定义是很精确的。我们程序员似乎很喜欢黑白、1和0这样的事物。

就个人而言，我认为世界只需要目前这么多的FORTRAN 77实现。在某个时候，你会发现自己正在设计一种新的语言。一旦开始这样做，方程式中较柔和，人性化的一面就变得至关重要。诸如哪些编程语言特性易于学习，如何在创新和熟悉度之间取得平衡，哪种语法更易读以及对谁有帮助。

所有这些都会对你的新编程语言的成功产生深远的影响。我希望你的语言取得成功，因此在某些章节中，我以一篇“设计笔记”结尾，这些是关于编程语言的人文方面的一些文章。我并不是这方面的专家——我不确定是否有人真的精通这些，因此，请你在阅读这些文字的时候仔细评估。这样的话，这些文字就能成为你思考的食材，这也正是我的目标。

1 . 3第一个解释器

我们将用Java编写第一个解释器jlox。（这里的）主要关注点是概念。我们将编写最简单，最干净的代码，以正确实现该编程语言的语义。这样能够帮助我们熟悉基本技术，并磨练对编程语言表现形式的确切理解。

Java是一门很适合这种场景的语言。它的抽象层级足够高，我们不会被繁琐的实现细节淹没，但代码仍是非常明确的。与脚本语言不同的是，Java并没有隐藏太过复杂的底层机制，你可以使用静态类型来查看正在处理的数据结构。

我选择Java还有一个特别的原因，就是因为它是一种面向对象的语言。这种编程范式在90年代席卷了整个编程世界，如今已成为数百万程序员的主流思维方式。很有可能你已经习惯了将代码组织到类和方法中，因此我将让你在舒适的环境中学习。

虽然程序设计语言领域的专家有时瞧不起面向对象语言，但事实上，它们即使在编程语言的实现工作中也被广泛使用。GCC和LLVM是用C++编写的，大多数JavaScript虚拟机也是这样。面向对象的语言无处不在，并且针对该语言的工具和编译器通常是用同一种语言编写的。

最后，Java非常流行。这意味着你很有可能已经了解它了，所以你要学习的东西就更少了。如果你不太熟悉Java，也请不要担心。我尽量只使用Java的最小子集。我使用Java 7中的菱形运算符使代码看起来更简洁，但就“高级”功能而言，仅此而已。如果你了解其它面向对象的语言（例如C#或C++），就没有问题。

在第二部分结束时，我们将得到一个简单易读的解释器实现。但是我们得到的不会是一个高性能的解释器。它还是利用了Java虚拟机自身的运行时工具。我们想要学习Java本身是如何实现这些东西的。

1 . 4第二个解释器

所以在下一部分，我们将从头开始，但这一次是用C语言。对于理解解释器的实现来说，C语言是一门完美的编程语言，使用C语言实现解释器，可以帮助你一直理解到最底层，例如内存中的字节和流经CPU的代码。

我们使用C语言的一个重要原因是，我可以向你展示C语言特别擅长的东西，但这并不意味着你需要非常熟练地使用它。你不必是丹尼斯·里奇（Dennis Ritchie）转世，但也不应被指针吓倒。

如果你（对C的掌握）还没到那一步，找一本关于C的入门书，仔细阅读，读完后再回来。作为回报，读完本书你将成为一个更优秀的C程序员。可以想想有多少语言实现是用C完成的：Lua、CPython和Ruby’s MRI等，这里仅举几例。

在我们的C解释器clox中，我们不得不自己实现那些Java免费提供给我们的东西。我们将编写自己的动态数组和哈希表。我们将决定对象在内存中的表示方式，并构建一个垃圾回收器来回收它。

我们的Java版实现专注于正确性。既然我们已经完成了，那么我们就要变得越来越快。我们的C解释器将包含一个编译器，该编译器会将Lox转换为有效的字节码形式（不用担心，我很快就会讲解这是什么意思）之后它会执行对应的字节码。这与Lua，Python，Ruby，PHP和许多其它成功的编程语言的实现所使用的技术相同。

我们甚至会尝试进行基准测试和优化。到最后，我们将为Lox编程语言提供一个强大，准确，快速的解释器，并能够不落后于其他专业水平的实现。对于一本书和几千行代码来说已经不错了。