简介

童话故事不仅仅是真实的故事：不是因为它们告诉我们龙存在，而是因为它们告诉我们龙是可以战胜的。

奈尔·盖曼引用的G.K. 切斯特顿作品，鬼妈妈

我们一起踏上这段旅程，我真的很兴奋。这是一本关于实现编程语言解释器的书。它也是一本关于如何设计值得实现的语言的书。这是我希望在我第一次开始接触语言时就拥有的书，也是我近十年来一直在脑海中构思的书。

在这些页面中，我们将一步步地完成两种针对完整功能语言的完整解释器的构建。我假设这是您第一次涉足语言，因此我将涵盖构建完整、可用、快速语言实现所需的所有概念和代码行。

为了将两种完整实现塞入一本不变成门垫的书中，本书的理论比其他书籍要轻一些。当我们构建系统中的每一个部分时，我会介绍它背后的历史和概念。我会努力让你熟悉行话，这样如果你发现自己身处一个充满 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 那样宽，每个字符都很重要。

此外，代码没有太多注释。这是因为每几行代码都围绕着几段真正意义上的散文来解释它。当你编写一本与你的程序配套的书籍时，你可以在里面省略注释。否则，你可能应该比我使用//更多一些。

虽然本书包含实现所需的所有代码行，并教你每一行代码的含义，但它并没有描述编译和运行解释器所需的机制。我假设你能够在选择的 IDE 中拼凑一个 Makefile 或一个项目，以便让代码运行起来。那些类型的说明很快就会过时，我希望这本书像 XO 白兰地一样醇香，而不是像自家酿造的劣质酒一样。

1 . 2 . 2代码片段

由于本书包含了实现所需的每一行代码，因此代码片段非常精确。此外，因为我试图让程序在主要功能缺失的情况下仍然处于可运行状态，所以我们有时会添加在以后的代码片段中会被替换的临时代码。

一个带有所有花哨功能的代码片段看起来像这样

      default:

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

        break;

在中心位置，您将看到要添加的新代码。它可能在上方或下方有一些淡化的行，以显示它在现有代码中的位置。还会有一个小提示告诉你将代码片段放在哪个文件中的哪个位置。如果提示说“替换 _ 行”，则淡化行之间的部分现有代码需要删除，并用新的代码片段替换。

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 的代码。

我们使用 C 的一个重要原因是我可以向您展示 C 特别擅长的事情，但这确实意味着您需要对 C 非常熟悉。你不必是丹尼斯·里奇的转世，但你不应该害怕指针。

如果您还没有达到那个水平，可以找一本 C 语言入门书籍，仔细阅读，然后阅读完后再来这里。作为回报，你会从这本书中成为一个更强大的 C 程序员。鉴于有多少语言实现是用 C 编写的，这很有用：Lua、CPython 和 Ruby 的 MRI，仅举几例。

在我们的 C 解释器 clox 中，我们被迫自己实现 Java 免费提供给我们的所有内容。我们将编写自己的动态数组和哈希表。我们将决定对象如何在内存中表示，并构建一个垃圾收集器来回收它们。

我们的 Java 实现专注于正确性。现在我们已经解决了这个问题，我们将转向也快速。我们的 C 解释器将包含一个编译器，它将 Lox 翻译成有效的字节码表示（别担心，我很快就会讲到这意味着什么），然后执行它。这与 Lua、Python、Ruby、PHP 和许多其他成功的语言的实现所使用的方法相同。

我们甚至会尝试一下基准测试和优化。最终，我们将为我们的语言构建一个健壮、准确、快速的解释器，能够与其他专业级别的实现相媲美。一本几千行代码的书，效果还不错。