概览

童话如此真实: 不是因为告诉我们龙是存在的， 而是因为告诉我们龙是可以被打败的.

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

我真的非常兴奋我们将要一起开始这趟旅程， 这是一本关于如何实现编程语言解释器的书， 也是一本如何设计一门实用编程语言的书， 一本我第一次学编程语言时就希望能读到的书，一本我已经在脑子里写了将近十年的书。

在本书中，我们将通过一步一步来实现2个解释器获得一个功能齐全的编程语言。 我假设这是你第一次涉足编程语言实现，所以我将详细介绍构建一个完整的，可用的，快速的语言实现所需要的每一个概念和每一行代码。

为了能将2个解释器的完整实现塞进一本书而又要避免它厚的变成门档，本书在理论上会比其它的书介绍的更浅显易懂一些。 在我们构建系统的每个部分时，我将介绍其背后的历史和概念。 我会带领你熟悉这些术语，以便即使你发现自己在一个满是PL(编程语言)研究员的鸡尾酒会，你依然可以谈笑风生。

但是我们依然要绞尽脑汁来让编程语言跑起来，这不是说理论不重要，在我们学习编程语言时，能够对语法和语义进行精确而形式化解释是一项很重要的能力。 但是，对我个人来说，通过动手来学会学的更好。 对我来说，只是阅读满是抽象概念的文字，将很难真正理解它们，但是一旦我写点代码，跑一跑，调试一下，然后我就理解了。

这是我对你制定的目标，我希望你学完后拥有坚实的直觉，来理解编程语言的生老病死和一颦一笑。 我希望当你以后阅读更理论一些的书时，那些概念能牢牢的留在你的脑海里，附着在这个有形的基底上。

1 . 1为什么要学习这些东西?

每一本编译器相关书籍的前言似乎都有这一节，我不知道是什么导致编程语言会有这种存在性怀疑。 我不认为鸟类学书籍会担心其存在的合理性，他们假设读者喜欢鸟，然后开始教学。

但是编译语言有一点不同，我认为，我们中的任何一个人，成功创造一个被广泛应用的通用性编程语言的几率是很小的。 世界级流行编程语言的设计者们，一辆大众大巴就可以装得下，甚至都不需要把顶棚打开。 如果加入那种精英组织才是学习编程语言的唯一原因的话，确实很难给出合理的理由，幸运的是，只要你感兴趣，就可以学习。

1 . 1 . 1小众语言到处都是

对于每一种成功的通用语言，都有一千种成功的细分语言。 我们习惯称它们为“小众语言“，但是专业术语的滥用导致称之为“领域特定语言“。 它们是为特殊任务量身定做的混合语言，例如程序脚本语言，模板引擎，标记格式化和配置文件。

几乎每个大型软件项目都需要其中的一小部分，如果可以，重用已有的总是好的。一旦你把文档，调试器，编辑器支持，语法高亮，等等考虑进来，自己实现功能就变成了棘手的事情。

当没有合适的类库满足你的需求时，将会有很大可能，你会发现你需要自己改造分析器或者其它工具。 即使当你重用一些已有的实现时，你也不可避免地需要调试和维护它们，并在其内部探索。

1 . 1 . 2语言是很好的锻炼

长跑运动员有时候会在他们脚踝上绑上重物或者在氧气稀薄的高海拔地区来进行训练。 当他们后来卸下自己的负担时，相对轻巧的四肢，富含氧气的空气能让他们跑的更远和更快。

实现一门语言是对编程技能的真正考验，代码很复杂，而性能很关键。你必须掌握递归、动态数组、树、图和哈希表。 你可能已经在日常编程工作中使用过哈希表了，但是你真正理解他们了吗？等我们从零制作我们自己的哈希表之后，我保证你会真正理解。

虽然我想向你展示一个解释器并不像你认为的那样令人生畏，但实现一个好的解释器依然是一个挑战。战胜它，你将会成为更强的程序员，可以更聪明的使用你日常工作中遇到的数据结构和算法。

1 . 1 . 3还有一个原因

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

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

这是一张迷人的图片，但是它也有黑暗的一面。 我感觉自己不像个巫师，所以我认为自己缺乏加入秘社所需的先天品质。 虽然自从我在学校笔记本上随手涂鸦关键字以来，我一直对编程语言着迷，但是我花了很长时间才鼓起勇气试着真正去学习。 那种“神奇”的品质，那种排他性的感觉，将我挡在门外。

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

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

而且，谁知道呢，也许你会创造出下一个伟大的编程语言呢，一定有人会的。

1 . 2这本书的组织方式

这本书分为三个部分，你现在正在读的是第一部分，这部分由几个章节组成，通过教你一些编译原理的术语，介绍我们后续要实现的Lox编程语言，来让你逐步适应。

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

我花了不少时间去试错，但我还是成功地把两个解释器按照章节分开了，当前章节只需要之前的内容而不需要后续章节的内容。 从第一章开始，你就会有一个可以运行和使用的程序。 随着章节的推移，程序的功能越来越丰富，直到你最终拥有一门完整的编程语言。

除了丰富，精彩纷呈的主要内容外，这些章节还有一些其它锦上添花的内容。

1 . 2 . 1代码

我们是冲着自己动手写解释器来的，所以这本书肯定要包含代码，每一行代码都不会漏掉，而且每个代码片段都会告诉你插入到之前代码的什么位置。

许多其他的编程语言书籍和编程语言实现都使用Lex和Yacc这样的工具， 也就是生成编译器的编译器，可以从更高层次的描述自动生成一些源文件。 像这样的工具有利有弊，喜欢和不喜欢的人都各有观点，-- 有些人可能说这是信仰。

我们这里不会使用它们，我想要确保魔法和困惑没有黑暗的角落可以躲藏，所以我们会手写所有代码。 就像你将要看到的，并没有听起来那么糟糕，因为这意味着你可以真正明白每一行代码，以及两个解释器是如何工作的。

书与“真实世界”有不同的限制，因此这里的代码风格可能并不是编写可维护产品级软件的最佳实践。如果我看起来有点漫不经心，比如说，省略private关键字或者声明为全局变量，请理解我这样做是为了让你更容易看懂代码。书页不像IDE窗口那么宽，要惜墨如金。

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

虽然书中包含了每一行代码，并解释了每一行代码的含义，但它没有描述如何编译和运行解释器。我假设你可以使用Makefile或者在你IDE的项目里按序编译，以便让代码运行起来。这类机制很快就会过时，我希望这本书能像XO白兰地一样愈久弥香，而不是像后院的烈酒（一样）。

1 . 2 . 2代码片段

Since the book contains literally every line of code needed for the implementations, the snippets are quite precise. 既然本书包含了实现所需的每一行代码，所以代码片段比较清晰明确。 Also, because I try to keep the program in a runnable state even when major features are missing, 另外，因为我想要程序在缺少主要功能的情况下依然可以编译运行，所以有时候我们会添加一些，在后面代码片段里会被取代的临时代码。

一个花里胡哨的代码片段长这样：

      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不熟悉，不要惊慌。我会尽力使用它很小的子集，我将使用Java 7的泛型让代码更简洁一些，这就是所谓的“高级”功能了。 如果你懂其它的面向对象语言，比如C#或C++，你就不会有障碍。

在第二部分结束时，我们将得到一个简单易读的解释器实现。它虽然性能不好，但是至少正确。然而，我们依赖Java虚拟机运行时来完成，我们想知道Java自身是如何实现这些功能的。

1 . 4第二个解释器

所以在接下来的部分，我们从头开始，这一次我们使用C。C语言是理解实现是如何真正工作的完美语言，所有细节，包括内存中的字节和CPU中执行的指令。

A big reason that we’re using C is so I can show you things C is particularly good at, 我们将使用C语言的一个重要原因是，我可以向你展示它特别擅长的地方，但是这确实意味着你需要对使用C语言充满自信。 你不必成为丹尼斯·里奇（C语言之父），但是你也不应该被指针吓尿。

如果你对C语言一窍不通，拿本介绍C语言的书，吃了它（囫囵吞枣式的读一下），吃饱喝足后再回来。 作为回报，当你读完本书，你将成为一个更强大的C程序员。 给你看看有多少语言是使用C写的：Lua，CPython， Ruby’s MRI等等。

在我们的C解释器clox中，我们必须自己实现所有Java免费给我们的数据结构。 我们将写自己的动态数组，哈希表，我们将设计对象如何占据内存，并且开发一个垃圾收集器来回收它们。

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

我们甚至会尝试进行基准测试和优化。到最后，我们有一个强大，准确，快速的Lox解释器，并能够不落后于其他专业水平的实现。对于只有几千行代码和一本书来说，还不赖吧。