用Go语言自制编译器
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

前言

可能不太礼貌，姑且让我以一个谎言来开启本书吧：本书的前传《用Go语言自制解释器》的成功是我从来没有设想过的。我当然是在撒谎。我肯定想象过它的成功：它出现在畅销书单的榜首，我因它获得无数的褒奖和称赞，并受邀参加各种高端活动，陌生人在街上认出了我，希望得到我的签名——在写了一本关于编程语言的书并将该语言命名为“Monkey”之后，谁不会设想这些场景呢？可是现在，我得严肃地说一个真实的想法：我的的确确没有料想到它会如此成功。

我当然感觉得到，有些人会喜欢那本书，主要因为我也很想读到那些内容，但在市场上找不到相关的书。在苦苦搜寻又徒劳而返的过程中，我发现其他人几乎跟我在搜索完全一样的内容：一本有关解释器的书，简单易懂，不是走马观花的简介，而是把经过测试的、可运行的代码放在首位。我当时想，如果我可以写这样一本书，那么其他人也许会喜欢。

想象归想象，事实上读者的确很喜欢我写的内容。他们不仅买了书，读了，还写邮件来感谢我，或者发博客文章表示他们有多喜欢那本书。有人在社交网络上推荐那本书，发起了线上投票；还有人把书中的代码拿出来改写、扩展，并分享在GitHub上；更有人修正了书里的错误代码。你能想象吗？他们给我发来了修改意见，然后还说他们很抱歉发现了这些错误。他们显然无法想象我有多感激他们的建议和这些修改意见。

后来，我看到一位读者发来的邮件，他表示希望读到更多的内容。我深受触动。这封邮件让原本仅存在于我脑海里的一个想法变成了一件必需要去做的事情：我必须得写第二本书。请注意，这不是随随便便的第二本，而是只此唯一的第二本。之所以这么说，是因为第一本书的诞生本身就带有遗憾。

在开始写《用Go语言自制解释器》这本书的时候，我想的只是写一本书，而不是一个系列的作品。后来当我意识到想写的内容太多，这本书到最后会变得非常厚的时候，我就改变了这个想法。我不想写一本大部头让读者望而生畏。即使我想写，其过程也会旷日持久，我大概很早就会放弃。

因此我做出了妥协。与其写一本书介绍如何构建树遍历的解释器并将之转换成一个虚拟机，不如只写树遍历的部分。这就是第一本书《用Go语言自制解释器》。你现在所读的就是我想写的后续内容。

但是所谓的“后续”具体是什么意思呢？这是说，本书并不是写于“第一本书出版几十年后，在另外一个星球上，Monkey这个名字失去了原有的意义”。这不是一本颠覆之作，而是跟上一本无缝衔接的书。这两本书遵循相同的路径，使用同一种编程语言以及同样的工具和代码库（第一本书最后所构建的代码库）。

我的想法很简单：从停下来的地方继续出发，继续在Monkey上的工作。这不仅仅是上一本书的续集，也是Monkey的续集，是Monkey进化的下一阶段。在揭开本书的真面目之前，我们需要回顾一下Monkey。

在《用Go语言自制解释器》这本书中，我们为Monkey语言构建了一个解释器。创建Monkey的目的是：让读者能从零开始用Go语言自制一个解释器。尽管网上到处是读者使用各种语言编写的非官方实现，但是Monkey唯一的官方实现只存在于《用Go语言自制解释器》这本书中。

如果你忘记了Monkey的特征，下面这个代码片段会以尽可能少的代码帮你回忆起Monkey的特性。

let name = "Monkey";
let age = 1;
let inspirations = ["Scheme", "Lisp", "JavaScript", "Clojure"];
let book = {
"title": "Writing A Compiler In Go",
"author": "Thorsten Ball",
"prequel": "Writing An Interpreter In Go"
};
let printBookName = fn(book) {
let title = book["title"];
let author = book["author"];
puts(author + " - " + title);
};
printBookName(book);
// => 打印“Thorsten Ball - Writing A Compiler In Go”
let fibonacci = fn(x) {
if (x == 0) {
0
} else {
if (x == 1) {
return 1;
} else {
fibonacci(x - 1) + fibonacci(x - 2);
}
}
};
let map = fn(arr, f) {
let iter = fn(arr, accumulated) {
if (len(arr) == 0) {
accumulated
} else {
iter(rest(arr), push(accumulated, f(first(arr))));
}
};
iter(arr, []);
};
let numbers = [1, 1 + 1, 4 - 1, 2 * 2, 2 + 3, 12 / 2];
map(numbers, fibonacci);
// => 返回：[1, 1, 2, 3, 5, 8]

由以上代码可见，Monkey语言的特性包括：

  • 整型
  • 布尔型
  • 字符串
  • 数组
  • 哈希表
  • 前缀运算符、中缀运算符、索引运算符
  • 条件表达式
  • 全局变量绑定和局部变量绑定
  • 头等函数
  • return表达式
  • 闭包

列表看起来很长？实际上，我们自己在Monkey中实现了以上所有的特性，最重要的是，我们从零开始，没有依赖任何第三方工具或者类库完成了这项工作。

从构建词法分析器开始，将字符串输入REPL并最终转换为词法单元。词法分析器的结构在lexer包中定义，生成的词法单元结构定义于token包中。

接着，我们构建了一个自上向下的递归下降式语法分析器（通常称之为普拉特语法分析器），将词法单元转换成抽象语法树，简称为AST。AST节点定义于ast包中，语法分析器则定义在parser包中。

经过语法分析后，Monkey程序在内存中就可以表示为树并等待求值。为此，我们构建了一个求值器。它的另一个名字是Eval函数，该函数定义在evaluator包中。Eval递归访问AST并对其进行求值，利用在object包中定义的对象系统得到最终结果。举个例子，这个过程会将表示1+2的AST节点直接转换成object.Integer{Value: 3}。到这里，Monkey代码的执行周期就结束了，最终结果会被保存到REPL中。

整个变化过程——从字符串转换为词法单元，再从词法单元转换成AST，接着从AST转换为object.Object——从头到尾都展现在我们构建的Monkey REPL的主循环中：

// repl/repl.go
package repl
func Start(in io.Reader, out io.Writer) {
scanner := bufio.NewScanner(in)
env := object.NewEnvironment()
for {
fmt.Fprintf(out, PROMPT)
scanned := scanner.Scan()
if !scanned {
return
}
line := scanner.Text()
l := lexer.New(line)
p := parser.New(l)
program := p.ParseProgram()
if len(p.Errors()) != 0 {
printParserErrors(out, p.Errors())
continue
}
evaluated := evaluator.Eval(program, env)
if evaluated != nil {
io.WriteString(out, evaluated.Inspect())
io.WriteString(out, "\n")
}
}
}

以上代码就是在上一本书的4.6节我们告别Monkey的地方。

半年之后，“遗失的篇章：Monkey的宏系统”出版，主要介绍了Monkey如何使用宏进行编程。不过，我并不打算让“遗失的篇章”和宏系统出现在本书中。实际上，本书是接着《用Go语言自制解释器》的第4章继续的，就像“遗失的篇章”从未出现过。这很好，因为我们的解释器实现得非常棒。

Monkey的运行完全符合预期，而且它的实现易于理解和扩展。所以在本书的开始自然而然地冒出一个问题：为什么要改变它，让它保持原样不好吗？

原因是，我们需要学习，Monkey仍然有许多内容可以教给我们。《用Go语言自制解释器》的目标之一就是学习每天工作中使用的编程语言的实现。我们确实做到了。实际工作中使用的大部分编程语言的早期实现跟Monkey语言类似。学习构建Monkey的过程帮助我们理解了编程语言的实现和起源。

但是编程语言始终在发展，并会逐渐成熟。面对生产环境的负载以及日渐增长的性能和语言特性需求，编程语言的架构和实现往往需要随之改变。这些改变的一个副作用是它们逐渐丧失了与Monkey的相似性，因为Monkey从设计之初就没考虑生产环境和性能问题。

Monkey与成熟编程语言之间的差距是其实现过程中最大的缺点之一：Monkey的架构和实际使用的编程语言的架构脱节，正如肥皂车和一级方程式赛车截然不同。肥皂车有4个轮子和一个座椅，它可以帮助学习转向系统，但是缺少发动机这一事实是无法忽视的。

在本书中，我们将缩小Monkey语言和实际使用的编程语言之间的差距。我们将在Monkey这辆肥皂车的发动机盖下面放一些东西。

我们将把Monkey中基于遍历语法树与即时求值的解释器升级成字节码编译器以及一个用来执行字节码的虚拟机。

这项工作很有趣，而且它确实是最常见的解释器架构。Ruby、Lua、Python、Perl、Guile、各种JavaScript实现以及更多的编程语言都采用了这种架构。即便是强大的Java虚拟机，也需要解释字节码。字节码编译器和虚拟机几乎无处不在，也在情理之中。

除了提供新的抽象层——从编译器传递到虚拟机的字节码——使系统更加模块化，这种架构的主要吸引力是它的性能。与其他架构相比，字节码解释器更快。

需要数据支撑？本书末尾将展现，基于本书实现的Monkey性能是上一本书中Monkey的3倍：

$ ./monkey-fibonacci -engine=eval
engine=eval, result=9227465, duration=27.204277379s
$ ./monkey-fibonacci -engine=vm
engine=vm, result=9227465, duration=8.876222455s

没错，3倍——无须进行底层的调整和广泛的优化就能实现。听起来很酷？已经迫不及待要写代码了？太棒了！那就开始吧！

与第一本书一样，本书也只有少量的说明。你最好从头到尾，一边阅读，一边敲出书中呈现的代码并调试它。这就是你需要做的一切。

这两本都是关于代码编写以及实现产品构建的实战书。如果你沉迷于编程语言相关理论，那么最好选择一本规范的教科书。这并不是说你从本书中学不到任何知识。我会尽力指导你，解释所有内容是什么以及各部分是如何组合在一起的。只不过本书并不会像编译器教科书那么学术，但这正是我想做的。

与第一本书一样，本书附带随书代码：https://compilerbook.com/wacig_code_1.2.zip。

在code文件夹中，你可以找到每一章对应的子文件夹。每个子文件夹都包含相应章节末尾的代码库。这些会在你遇到困难时提供帮助。

其中的子文件夹00很特殊，这也是本书与第一本书的不同之处：本书并不是从零开始，而是以第一本书的代码库为基础。00子文件夹与本书的任何一章都无关，它包含了上本书的完整代码库。这也意味着它不包含“遗失的篇章”中的宏系统，但如果你是宏系统的粉丝，那么追随宏系统扩展的步伐也不会太难。

这些子文件夹中的代码是本书的焦点。我尽量呈现更多，但是有时我只会引用代码库中的少量内容，而不是完全展示。为什么呢？大多数情况下，这表示它是已展示过的内容，而且完全展示会浪费篇幅。

关于这个code文件夹的介绍到此为止。现在来谈谈工具，因为有一个好消息：你需要准备的并不多。一个文本编辑器和一个Go语言执行环境就足够了。选择哪个版本的Go呢？至少是Go 1.10，因为这是我在写代码时所使用的版本，而且我们极少使用在Go 1.8和Go 1.9才引入的功能。

如果你使用的Go语言版本早于1.13，那么我仍然推荐利用direnv来配合code文件夹。direnv可以借助.envrc文件改变环境变量。无论何时进入一个文件夹，direnv都会检查当前文件夹是否有.envrc文件，如果有，就执行它。code文件夹中的每个子文件夹都包含.envrc文件，并且已经为该子文件夹设置了GOPATH。这使我们只需要进入子文件夹即可轻松执行代码。

但是如果你使用Go 1.13或之后的版本，就无须再设置GOPATH，因为code文件夹包含“开箱即用”的go.mod文件。

最后，本书注重实践：边阅读边写代码。最重要的是，让自己乐在其中！

扫描下方二维码，即可获取电子书相关信息及读者群通道入口。

本周热推：
视觉之外：全链路UI设计思维的培养与提升垃圾回收的算法与实现JavaScript语言精髓与编程实践（第3版）计算机网络基础Java核心技术卷I基础知识（原书第9版）
上一章目录下一章