Introduction

1 . 0序言

童话胜于现实，不仅是因为童话告诉我们巨龙存在， 更是因为它们告诉我们巨龙可以被打败。

尼尔·盖曼，卡洛琳（《鬼妈妈》）

很高兴我们能一起携手开启这段旅程。这是一本关于如何实现程序语言解释器的书。这也是一本关于如何设计一门程序语言的书。这是本我初入程序设计语言领域就想要拥有的书，这是本我 10 年前就在我脑海中构思的书。

在这本书中，我们将一步一脚印地为一门五脏俱全程序设计语言实现两枚解释器（Interpreter）。我会预设这是你初次涉足程序设计语言开发领域，所以你不需要有任何的心理负担。我将详细阐述构建完整、可用、高效的语言解释器所需要的每一个基本概念及其代码实现。

为了将两枚解释器的完整实现塞到一本书中而又不使得该书变得臃肿不堪，我选择不在编译理论部分着墨过多。当我们逐步搭建起编译系统的各个部分之时，我再向你介绍关于这部分的历史与其背后的概念。我会努力让你理解那些在鸡尾酒晚会上的程序设计语言研究者们所说的“行话”，相信你很快就能理解适应这些“术语”了。

在大部分情况下，我们都将绞尽脑汁先让我们的程序运行起来。这并不意味着理论不重要，能够正确且形式化地推导语法和语义是开发程序设计语言一项至关重要的技能。但是，我个人还是喜欢边做边学。通读大段大段充斥抽象概念的段落并充分理解其含义对我来说实在是太过困难，但如果让我写下几行代码，跑一跑，跟踪 debug 一下，我很快就可以掌握它。

这也是我对你的期望。我希望你通过动手实操，对一门真正程序设计语言的诞生过程留下一个坚实的印象，如此一来，以后当你在阅读其他更具理论性的书籍著作时，这些概念将深深镌刻进你的大脑，使得你可以更加充分地理解它们。

1 . 1为什么要学习它？

似乎每一本有关编译原理的书都会在开头部分来上这么一段，告诉读者为什么要学习编译原理。我不知道造成这种“存在性怀疑”的程序设计语言是什么。

我敢肯定地说，你们中的大多数人创造出一门被广为使用的通用程序设计语言的可能性微乎其微，毕竟，即使把这个世界上被广为应用程序语言的设计者们都拉出来，还塞不满一辆大众巴士呢，如果学习编译原理的唯一理由就是要加入这群精英，创造出世界流行的程序设计语言，这无疑令人费解。幸运的是，事实并非如此。

1 . 1 . 1小众语言无处不在

对于任何一支成功的通用程序设计语言，都会有上千种其他语言与其相辅相成。我们通常将它们称为“小众语言”。但这一称呼其实并不准确，更为确切的称呼应该是：领域特定语言（Domain-specific Languages、DSL）。领域特定语言被设计用以完成某些特定任务，如：应用程序脚本、模版引擎、标记格式、配置文件等。

几乎每个大型软件项目都需要用到其中的一个或多个。如果可以的话，最好是复用一支已经存在的领域特定语言，而不是自己再创造一个，因为一旦使用自己编写的小众语言替换，在文档撰写、程序调试、编辑器支持、语法高亮等方面，你都将面临许多不必要的麻烦。

但如果当现有的领域特定语言代码库无法满足你的需求时，你还是需要勉为其难地手写一枚解析器或者类似的工具以满足需求。即使你想要重用一些现有的代码，你也将不可避免地对其进行调试和维护，深入研究其原理。

1 . 1 . 2着实锻炼编程技艺

长跑运动员时常会在脚踝绑上重物，或是去到在氧气稀薄的高海拔地区训练自身。当他们卸下重负，来到富氧地区比赛时，他们的四肢变得轻盈，脚步变得稳健，跑得更快更远。

实现一门程序设计语言是对编程技艺一次极好地磨练。代码实现复杂艰深，对代码性能也有着至关重要的要求。你必须很好地掌握递归、动态数组、树、图、哈希表等关键技术。你也许经常在日常编程中使用哈希表数据结构，但你是否真正理解它了呢？当我们从头开始完成语言解释器之后，我保证你对这些基础算法数据结构的认知会更上一层楼。

尽管我想努力向你传达，实现一枚程序语言解释器并不如你想象的那般困难，但实际上这仍是一个巨大的挑战。克服它，你会变得更加强大，在日常工作中，你也将更加聪明地运用算法与数据结构。

1 . 1 . 3另一个原因

最后一个原因我其实有点难以启齿，因为这是我内心深处最为真切的想法。在我还是一个孩童时，就觉得程序设计语言非常神奇，我一个字符一个字符敲下了一支 BASIC 程序，程序正常运行了起来，但我却不知道 BASIC 语言背后是如何工作的。

后来我上了大学，上编译原理课的同学对我说，程序语言黑客简直是另一种人类，就像会施展奥术的巫师一样，说这话时脸上还充满了敬畏之情。

那可真是幅迷人的画面。但我并不觉得我自己像个巫师，也许我天生就缺少一些加入巫师集团的特质。从那时起，我被程序设计语言深深吸引，我在学校笔记本上涂满了拼凑而成关于程序语言的关键字。在往后数十年时间里，我都在学习它们，探索着程序设计语言“魔盒“背后的奥秘。

说不定，你也与我有同样的感受呢。

当我真正开始动手制作一枚小编译器的时候，我意识到，这其中并没有什么“神奇魔法“，仅是一堆代码罢了， 而创造程序语言的也仅是普通人而已。

当然，实现一门程序设计语言多少会涉及一些你在外头很少见到的技术，其中某些部分确实有点难度，但也不会比你一路走来所克服的困难难上多少。如果你曾对程序设计语言和编译原理心生畏惧，希望这本书可以帮你克服恐惧，为你带来些许勇气。

说不定，下个知名程序设计语言的创造者就是你呢！

1 . 2本书是如何组织的

本书主要分为三个部分，你目前正在阅读的正是第一部分。第一部分通过几个章节带你快速进入程序设计语言的世界，为你讲解程序设计语言开发者们时常挂在嘴边的那些“术语”。第一部分还将带你认识 Lox ，我们将要实现的程序设计语言。

之后的两大部分，每一部分都将带你构建一支完整的 Lox 解释器。这两部分的章节组织也大同小异，每章取一个语言特性，讲解其背后的核心概念，带你完整实现一遍代码。

为了将两枚解释器的庞杂内容切分成各个内容适中的篇章，让各个篇章之间尽可能相对独立不相互影响，可着实费了我一番功夫。从第一个篇章开始，你就可以写出一支可以运行的解释器程序，随着章节推进，这支小解释器程序逐步成长，羽翼渐丰，直到你完整实现出全部功能。

除了内容丰富、语句清晰的主体内容外，每个章节还会包含以下数个讨喜的部分：

1 . 2 . 1代码

既然我们要开发一枚货真价实的程序语言解释器，代码部分自然是不可或缺的。任何一行重要的实现代码都将被包含其中，详细阐释。贴出的代码片段还会用心地告诉你应在何处插入这段代码。

许多讲授程序设计语言开发的书籍都会借助一些类似Lex、Yacc这样的编译器编译程序（Compiler-compilers），让编译器编译程序帮忙自动生成一些源代码文件，这么做有人说好，有人说不好，争论双方各执己见，各有各的道理。

在这本书中，我们不会使用这些辅助工具。我想确保在实现程序设计语言的道路上不会有任何黑暗的角落和神奇的魔法，我们将完完整整地写下全部代码，你也将充分理解写下的每一行代码是如何在解释器里工作的。

写在书中的代码与“真实世界”的代码总会有一些不同，某些代码风格也不是编写可维护软件代码的最佳方式。如果被你发现，比如说：漏写了个private，声明了一个全局变量，还请不要见怪。我力求代码简洁易懂，而且在这里书页的宽度也比不上集成开发环境（IDE）。

另外，书中的代码不会带有太多的注释，这是因为每行代码的含义都会在周围的几个段落被详细地解释清楚。如果以后你也提笔撰写一本自己的技术书，我也推荐这样的技术文风：少注释，多解释。

虽然书中包含了每一行需要实现的代码和对这些代码的解释，但我没有加入如何让解释器程序编译运行起来的步骤描述。这是因为我相信你有能力快速撰写一份 Makefile 或是使用 IDE 建立一个工程项目，从而让代码运行起来，相信我，这不是什么难事。而且，描述如何让程序编译执行的文字很快就会过时，新的代码工具层出不穷。我希望这本书能像白兰地酒那样，越老越醇香。

1 . 2 . 2代码片段

除了包含实现解释器所需的代码之外，本书还会包含一些描述精准的代码片段。这是因为我需要让解释器程序在缺失某些主体功能的情况下也能正常运行，所以我会用代码片段告诉你如何添加上临时性代码，以及后续如何替换掉它们。

一份典型的代码片段长这样：

      default:

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

        break;

可以看到，在代码片段的中心位置，有需要添加的代码，这部分代码被着重显示。新增代码上下环绕几行颜色偏淡已经存在的上下文代码。侧边会有个简短提示，告诉你应在哪个文件的哪个位置插入代码。如果提示文字中有诸如“替换_行”的描述，这就表示你需要先移除此处的旧代码，再替换上代码片段中的新代码。

1 . 2 . 3旁注

旁注通常包含一些简单草图、章节的历史背景、相关主题的参考内容以及对其他领域的建议，忽略这部分内容完全不会影响你阅读接下来的章节内容。所以，你可以放心大胆地忽略它们。忽略这部分的内容我也不会怪你，只是，我可能会有点难过啦。

1 . 2 . 4挑战

在每个章节的结尾部分，会带有几道挑战性质的练习题。与教科书后的习题集不同，本书的练习题旨在帮助你复习你已经学到的内容，引导你去思考章节内容之外的东西。习题迫使你走出既定的引导路线去探索更多，这对你研究其他语言的功能实现大有裨益。不是有句话这么说嘛：你要勇于跳出舒适区。

努力克服这些挑战，你定会有新的感悟与收获。亦或是，你也可以简单地跳过它们，继续前进。

1 . 2 . 5设计笔记

大多数描述开发“程序设计语言”的书都将视线聚焦于如何按照定义严格实现一门语言，却很少谈及一个语言特性背后的设计思路，为什么这门语言要如此设计。实现程序语言的过程非常有趣，因为一门程序语言的语法规范是经过严格定义的。程序员们似乎总是很喜欢被严格定义清楚的事物，非黑即白，非零即一，泾渭分明，毫无歧义。

就我个人而言，我觉得这个世界只需要实现 FORTRAN 77 这一门语言就足够了。如果有一天，你自己开始着手设计一门全新的程序语言，这时候，一些考虑“人”的因素就会浮现出来，比如：哪些语言特性简单易学，如何平衡语言的创新性与相似性，语法上是否更应该注重可读性，这门语言的目标人群是哪些等等。

上述的这些都是你的新语言能否成功的重要因素。我也希望你的语言能大获成功，所以在部分章节的结尾，我会留下“设计笔记”，一篇从程序语言使用者视角出发，探讨程序语言设计的小短文。当然，我个人并不是这方面的专家，写得不好也请别见怪，糊上一把盐吞下去吧，味道能好不少。如果我写的这些内容能够发人深思，那我的目的也就达到了。

1 . 3第一支解释器

我们马上就要开始编写我们的第一支解释器：jlox，顾名思义，使用 Java 语言编写。在这一版的实现中，我们着重关注程序设计语言开发的一些基本概念。我们将编写最直观、最清晰的代码来正确实现 Lox 语言的语法语义。这使得我们可以快速熟悉程序设计语言开发的一些基本技术，也让我们对程序设计语言的工作原理有一个浅显的认识。

使用 Java 语言来实现解释器是一个非常合适的选择。一方面，Java 语言足够“高阶“，使得我们不必太过关注一些底层实现的细节。另一方面，Java 语言简单清晰，不像很多脚本语言那样充斥着不太能理解的花哨技法，Java 是一门静态类型的语言，我们能够清楚地看到我们正在使用的数据结构是什么。

我选用 Java 还有一个特殊的原因：Java 是一门面向对象的程序设计语言。“面向对象“这一程序开发范式兴起于上世纪 90 年代，现如今早已被广大程序员所熟知。通过“类（Class）”与“方法（Method）”组织代码，这对熟悉“面向对象”程序开发范式的程序员朋友们而言，无疑是非常友好的。

虽然很多学院派程序语言研究人员有些看不上面向对象程序设计语言，但事实上，面向对象程序设计语言在各个领域都有着广泛的应用，甚至是在计算机程序设计语言开发领域，它们也有着出色的高光表现：GCC 与 LLVM 使用 C++ 编写，大部分 JavaScript 虚拟机同样使用 C++ 实现。面向对象语言的身影随处可见。通常来说，某一门语言的编译器和周边工具都使用该语言本身编写。

最后，Java 非常流行，这意味着你或多或少有机会接触到它，也会写一点 Java 代码。这样一来你就不需要为阅读本书而重新学习一门程序设计语言了。如果你不太熟悉 Java 语言也不必担心，我会尽可能地使用 Java 语言最基本的特性。为了使代码看上去更加简洁干练，我使用了 Java 7 引入的钻石运算符<>，这就是我所使用的最“高级”的 Java 语言特性了。如果你熟悉其他面向对象的程序设计语言，如：C#，C++，相信你很快就能上手。

当你走完第二部分的全部内容时，我们即实现了一枚代码简单，可读性较高的 Lox 语言解释器。虽然这枚小解释器运行速度不快，但其对 Lox 各项语言功能的实现都是准确无误的。我们的解释器实现依赖了许多 Java 虚拟机（JVM）自身的运行时特性，那么自然我们也想对虚拟机工作原理一探究竟，由此就有了第二支我们要实现的解释器。

1 . 4第二支解释器

在本书的第三部分，我们将从头开始重新实现 Lox 解释器，这一次我们使用 C 语言编写。C 真是一门非常棒的语言，对我们认识底层大有帮助。我们将深入对象在内存中的字节表示，语句在 CPU 中的执行序列等，充分理解程序语言解释器底层实现的具体细节。

使用 C 语言的一个重要原因就是：我会向你展示 C 语言真正擅长做的事，操作底层。这意味着你必须熟练掌握 C 语言与计算机基础知识。你不需要是丹尼斯·里奇（C语言之父）转世，但你也不能一看到指针（Pointer）就发怵。

当然，如果你还没有熟练掌握 C 语言，你可以先找本书来学习学习 C 语言，再回过头来阅读这部分内容。当你最终完成这部分的所有内容之后，你一定会成为一名更加强大的 C 程序员。值得一提的是，许多知名程序设计语言都是用 C 实现的：Lua、CPython、Ruby MRI  . . . 

在我们实现 C 版本解释器clox的过程中，将着重关注那些 Java 虚拟机已经为我们完成的事。我们将写下动态数组与哈希表数据结构，制定对象在内存中的表示形式，还会构建一个垃圾收集器，在合适的时机回收内存。

我们使用 Java 实现的解释器重点关注实现的正确性，现在我们也开始关注起解释器的性能表现。我们的 C 解释器将包含一枚编译器（Compiler），将 Lox 编译到运行高效的字节码（Bytecode）表示形式（如果你不知道字节码是什么，不要担心，我们马上就会讲到）再执行。字节码翻译技术同样被诸多知名程序设计语言所采用：Lua、Python、Ruby、PHP  . . . 

我们还将尝试程序语言解释器的基准测试与性能优化，最终，我们将得到一枚健壮、精确、高效的 Lox 语言解释器，完全不逊于其他专业级别的语言编译器实现。仅通过一本书的内容和数千行代码就能做到这个地步，真不错。