导言

童话故事是无比真实的：不是因为它告诉我们龙的存在，而是因为它告诉我们龙可以被击败。

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这样的工具，也就是所谓的 “compiler-compiler”(生成编译器的编译器) ，可以从一些更高层次的（语法）描述中自动生成一些实现的源文件。这些工具有利有弊，而且双方都有强烈的主张--有些人可能将其说成是信仰。

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

为了写书，书中代码和“真实世界”的代码是有区别的，因此这里的代码风格可能并不是可维护生产软件的最佳方式。可能我的某些写法是不太准确的，比如省略 private 或者声明全局变量，请理解我这样做是为了让您更容易看懂代码。书页不像IDE窗口那么宽，所以每一个字符都很珍贵。

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

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

1 . 2 . 2片段

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

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

      default:

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

        break;

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

1 . 2 . 3题外话

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

1 . 2 . 4挑战

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

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

1 . 2 . 5设计笔记

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

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

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

1 . 3第一个解释器

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

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

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

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

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

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

1 . 4第二个解释器

所以在接下来的部分，我们从头开始，但这次是用C语言。C语言是理解实现的最佳语言，可以一直追溯到内存中的字节和通过CPU执行的代码。

我们之所以使用C语言的一个重要原因是为了向您展示C语言特别擅长的东西，但这也意味着您需要对它相当熟悉。您不必成为丹尼斯 · 里奇（Dennis Ritchie）的转世，但也不应该对指针感到困惑。

如果你（对C的掌握）还没到那一步，找一本关于C的入门书，仔细阅读，读完后再回来。作为回报，从这本书中你将成为一个更优秀的C程序员。可以想想有多少语言实现是用C完成的: Lua、CPython和Ruby s MRI等，这里仅举几例。 在我们的C解释器clox中，我们不得不自己实现那些Java免费提供给我们的东西。 我们将编写自己的动态数组和哈希表。 我们将决定对象在内存中的表示方式，并构建一个垃圾回收器来回收它。

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

我们的Java实现主要侧重于正确性。既然我们已经解决了这个问题，现在我们将着手提高程序的速度。我们的C解释器将包含一个编译器，将Lox语言转换为高效的字节码表示（不用担心，我会很快介绍它的含义），然后执行该字节码。这是Lua、Python、Ruby、PHP和许多其他成功语言实现所使用的相同技术。

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