第 2 章：全景地图（A Map of the Territory）

原文：Robert Nystrom, Crafting Interpreters, Chapter 2。原书以 CC BY-NC-SA 4.0 协议发布；本译文用于学习与研究。

无论地图多么粗略，你都必须有一张。否则就会四处乱走。在《魔戒》中，我从不让任何角色在一天内走得比他所能走的更远。

J. R. R. Tolkien

我们不想四处乱走，因此出发前，先浏览先前的语言实现者已经绘出的疆域。这能帮助我们理解将去往哪里，以及其他人走过的替代路线。

先约定一种简写。本书大量内容讨论语言的实现，它不同于某种柏拉图式理想形态中的语言本身。栈、字节码、递归下降等事物，是某一特定实现可能使用的零件。从用户视角看，只要装置忠实遵循语言规范，这些都是实现细节。

我们会在这些细节上花很多时间；若每次都写“语言实现”，手指都要磨坏。因此，除非需要区分，后文的“语言”可以指语言本身、其实现，或两者兼指。

2.1 一门语言的组成部分（The Parts of a Language）

从计算机的黑暗时代开始，工程师就在构建编程语言。我们刚能与计算机交谈，就发现这样做太困难，于是请计算机帮忙。有趣的是，尽管今天的机器速度快了数百万倍，存储空间多了好几个数量级，构建编程语言的方式几乎没有改变。

语言设计者探索的区域很广，但开辟出的路径并不多。并非所有语言都走完全相同的路，有些会抄一两条近道；但除此之外，它们令人安心地相似。从 Grace Hopper 少将的第一台 COBOL 编译器，到某个刚出炉、编译到 JavaScript 的新语言，即使其“文档”只是 Git 仓库里一份编辑糟糕的 README，也是如此。

当然也有死路：没有引用的计算机科学论文构成的小小尽头，以及只在内存按单个字节计量时才有意义、如今已被遗忘的优化。

我把实现可以选择的路径网络想成攀登一座山。山脚是程序的原始源文本，也就是一个字符串。每个阶段都会分析程序，并把它转换为更高层的表示，使语义，也就是作者希望计算机做什么，变得更明显。

最终会到达山顶。此时可以鸟瞰用户程序，并看清其代码意味着什么。接着从山的另一侧下行，把最高层表示逐步转换为更低层形式，越来越接近能让 CPU 真正执行的东西。

下面逐一沿着这些路径和地标前进。旅程从用户源代码的裸文本开始，例如：

var average = (min + max) / 2;

2.1.1 扫描（Scanning）

第一步是扫描（scanning），也称词法分析（lexing 或 lexical analysis）。它们大致是同一个意思。我喜欢 lexing，因为听起来像邪恶超级反派会做的事；但下文使用更常见的“扫描”。

扫描器（scanner，也叫 lexer）接收线性的字符流，把它们组合成更接近“词”的一串单位。在编程语言中，每个这样的词称为一个记号（token）。有些记号只是一个字符，例如 ( 和 ,；有些则包含多个字符，例如数字 123、字符串字面量 "hi!" 和标识符 min。

这里把 token 类比为“词”，只是为了建立直觉：编程语言的 token 不一定是自然语言意义的单词，例如 >= 虽由两个字符组成，仍是一个 token。lexical 来自希腊语词根 lex，意为“词”。

源文件中的一些字符其实没有意义。空白往往不重要，注释按定义会被语言忽略。扫描器通常丢弃它们，留下干净的、有意义的记号序列：

[var] [average] [=] [(] [min] [+] [max] [)] [/] [2] [;]

2.1.2 解析（Parsing）

下一步是解析（parsing）。此时，语法获得了文法（grammar），即由较小片段组合出较大表达式和语句的能力。你在英语课上画过句子成分图吗？若画过，就做过解析器的工作，只是英语有成千上万个“关键字”，歧义多得不可胜数；编程语言简单得多。

解析器（parser）接收扁平的记号序列，构建出一棵反映文法嵌套性质的树。这些树有不同名称，取决于它们与源语言裸语法结构的接近程度：解析树（parse tree）或抽象语法树（abstract syntax tree）。实际中，语言黑客通常称其为语法树、AST，或者干脆叫“树”。

解析在计算机科学中历史悠久，也与人工智能领域紧密相关。今天用于解析编程语言的许多技术，最初由尝试让计算机与人类交流的 AI 研究者提出，用于解析人类语言。

人类语言对这些严格文法来说过于混乱，却与更简单的人造编程语言文法完美契合。遗憾的是，有缺陷的人类仍会错误使用这些简单文法，因此解析器还负责通过报告语法错误（syntax error）来告诉我们哪里错了。

2.1.3 静态分析（Static Analysis）

前两个阶段在各种实现中非常相似。从这里开始，每种语言的个性开始发挥作用。此时已知代码的语法结构，例如哪些表达式嵌套在哪些表达式内，但所知不多。

在 a + b 这样的表达式中，我们知道在相加 a 和 b，却不知道这些名字指向什么。它们是局部变量还是全局变量？在哪里定义？

多数语言首先进行的分析称为绑定（binding）或解析（resolution）。对于每个标识符（identifier），找出其定义位置，并把两者关联起来。作用域（scope）就在这里发挥作用：它是源代码中某个名称可用来指代某个声明的区域。

若语言是静态类型的，现在会进行类型检查。知道 a 与 b 的声明位置后，也能推断其类型；若这些类型不支持彼此相加，就报告类型错误（type error）。本书构建的语言是动态类型的，因此会在稍后的运行时进行类型检查。

本书构建的是动态类型语言，因而类型检查会在运行时完成。

深吸一口气。我们已到达山顶，对用户程序一览无余。分析所获得的所有语义信息需要存放在某处，常见选择有：

• 直接存为语法树上的属性（attributes）：解析时未初始化、后来填入的节点额外字段。
• 存在旁边的查找表中。该表通常以标识符，即变量和声明的名字为键；此时称为符号表（symbol table），与每个键关联的值说明该标识符指向什么。
• 最强大的记账工具是把树转换为一个全新数据结构，更直接地表达代码语义；下一节将介绍它。

截至此处的一切都算实现的前端（front end）。你可能猜想之后就是后端（back end），但并非如此。前端与后端这些词诞生时，编译器简单得多；后来研究者发明了大量夹在两者之间的新阶段。William Wulf 等人没有废弃旧称，而是把新阶段归入一个迷人却空间上自相矛盾的名字：中端（middle end）。

2.1.4 中间表示（Intermediate Representations）

可以把编译器看作一条管线，每个阶段的任务都是以让下一阶段更容易实现的方式，组织代表用户代码的数据。管线前端与程序使用的源语言相关，后端则关注程序最终运行的体系结构。

中间的代码可以存为某种中间表示（intermediate representation，IR），它与源形式和目标形式都不紧密绑定，因此称为“中间”。IR 充当这两种语言之间的接口。

IR 有一些成熟的风格，例如控制流图（control flow graph）、静态单赋值（static single-assignment）、续延传递风格（continuation-passing style）和三地址代码（three-address code）。

这些都是成熟 IR 风格；可搜索“control flow graph”“static single-assignment”“continuation-passing style”和“three-address code”进一步了解。

这样可以用较少工作支持多种源语言与目标平台。假设要实现 Pascal、C 和 Fortran 编译器，并支持 x86、ARM 和 SPARC。通常需要写出九个完整编译器：Pascal 到 x86、C 到 ARM，以及其他每种组合。

共享的中间表示会大幅减少工作：每种源语言只写一个生成 IR 的前端，每种目标体系结构只写一个后端；两者任意组合即可得到所有组合。GCC 之所以能支持如此多语言和体系结构，正是因为语言前端面向少数几种 IR，主要是 GIMPLE 和 RTL，目标后端再把它们产生成本机代码。

这正是 GCC 能支持大量语言与体系结构的原因：语言前端面向少数 IR，主要是 GIMPLE 与 RTL；例如 68k 目标后端再把这些 IR 产成本机代码。

把代码转换为更显露语义的形式，还有另一个重要理由。

2.1.5 优化（Optimization）

一旦理解用户程序的含义，就可以把它替换为语义相同却实现得更高效的程序，也就是优化它。

一个简单例子是常量折叠（constant folding）：若某表达式总会计算为同一精确值，就可以在编译时算出结果，并用结果替换表达式代码。用户写下：

pennyArea = 3.14159 * (0.75 / 2) * (0.75 / 2);

编译器可以完成全部算术，并把它改为：

pennyArea = 0.4417860938;

优化是编程语言行业的重要部分。许多语言黑客整个职业生涯都在这里，竭力从编译器中挤出每一滴性能，让基准测试快上百分之零点几；它很容易成为一种痴迷。

若忍不住想踏进这个洞，可从常量传播、公共子表达式消除、循环不变代码外提、全局值编号、强度削减、聚合标量替换、死代码消除和循环展开等关键词开始。

本书大多会跳过这个深坑。许多成功语言的编译时优化少得惊人。例如 Lua 和 CPython 会生成相对未经优化的代码，并把大部分性能投入放在运行时。想深入时，可从常量传播、公共子表达式消除、循环不变代码外提、全局值编号、强度削减、聚合标量替换、死代码消除和循环展开等关键词开始。

2.1.6 代码生成（Code Generation）

已经把能想到的优化都应用于用户程序后，最后一步是把它转换为机器真正能运行的形式，即代码生成（code generation，或 code gen）。这里的“代码”通常指 CPU 执行的原始类汇编指令，而非人类想阅读的“源代码”。

我们终于进入后端，开始从山的另一侧下行。从现在起，代码表示会越来越原始，仿佛进化倒放，逐渐接近简单机器能理解的东西。

需要做一个选择：为真实 CPU 还是虚拟 CPU 生成指令？生成真实机器码，可得到操作系统直接加载到芯片上的可执行文件。本机代码快如闪电，但生成它工作量很大。今天的体系结构有成堆指令、复杂流水线，以及足以装满一架 747 行李舱的历史包袱。

说芯片的语言也意味着编译器被绑在特定体系结构上。面向 x86 机器码的编译器不能运行在 ARM 设备上。早在 20 世纪 60 年代计算机体系结构爆发的时期，这种不可移植性就是重大障碍。

历史包袱的一个例子是 x86 的 AAD（ASCII Adjust AX Before Division）：它看似支持除法，却要求两个 BCD 数字被打包在同一个 16 位寄存器中。你上一次需要在 16 位机器上处理 BCD 是什么时候？

为此，BCPL 的 Martin Richards 与 Pascal 的 Niklaus Wirth 等人让编译器生成虚拟机器码。不再生成真实芯片的指令，而是为假想、理想化机器生成代码。Wirth 称其为强调可移植性的 p-code；如今通常叫作字节码（bytecode），因为每条指令往往只有一个字节长。

这些合成指令更贴近语言语义，也较少受单一计算机体系结构及其历史遗留物影响。可以把它看作语言低层操作的一种紧凑二进制编码。

2.1.7 虚拟机（Virtual Machine）

若编译器生成字节码，工作尚未结束。没有芯片能直接理解该字节码，因此还要翻译。再次有两个选择：为每种目标体系结构写一个小型编译器，把字节码转换为相应机器的本机代码。仍需为每种芯片做工作，但最后阶段相当简单，且能在所有支持的机器之间复用前面的编译管线；字节码本质上就是中间表示。

另一种选择是编写虚拟机（virtual machine，VM）：一个在运行时模拟支持虚拟体系结构的假想芯片的程序。在 VM 中运行字节码比预先翻译成本机代码慢，因为每条指令在每次执行时都必须被模拟；作为回报，得到简单性和可移植性。用 C 实现 VM 后，语言就能运行在任何拥有 C 编译器的平台上。本书构建的第二个解释器采用此法。

“虚拟机”还指另一种抽象：系统虚拟机以软件模拟整个硬件平台和操作系统，因此能在 Linux 机器上玩 Windows 游戏，也让云服务商能让客户像拥有自己的服务器一样操作，而不必为每位客户实际分配独立计算机。本书讨论的则是语言虚拟机，或为避免歧义称为进程虚拟机。

系统 VM 模拟整台机器的硬件边界；语言 VM 只实现语言所需的抽象指令和运行时服务。两者共享名称，但解决的问题不同。

把体系结构相关工作推得越靠近管线末端，越能在不同体系结构之间共享前面的阶段。但寄存器分配、指令选择等优化又需要了解特定芯片的能力；决定哪些部分共享、哪些部分目标专有，是一门艺术。

2.1.8 运行时（Runtime）

终于把用户程序敲打成可执行形式，最后一步就是运行它。若编译为机器码，只需让操作系统加载可执行文件；若编译为字节码，则启动 VM 并在其中加载程序。

无论哪种情况，除最底层语言外，通常都需要语言在程序运行期间提供一些服务。例如语言自动管理内存，就需要垃圾收集器回收不再使用的内存；若语言支持“instance of”测试以判断对象种类，就需要在执行时保留每个对象类型的表示。

这些都发生在运行时，因而统称为运行时。在完全编译的语言中，实现运行时的代码会直接插入最终可执行文件，例如每个编译出的 Go 应用都内嵌一份 Go 运行时。若语言运行在解释器或 VM 内，运行时就居住在那里；Java、Python 和 JavaScript 的大多数实现都是如此。

2.2 近道与替代路线（Shortcuts and Alternate Routes）

以上是涵盖所有可能阶段的长路线。许多语言确实走完整条路线，但也有一些近道与替代路径。

2.2.1 单遍编译器（Single-pass Compilers）

一些简单编译器将解析、分析和代码生成交织起来，直接在解析器中产出目标代码，从不分配任何语法树或其他 IR。这类单遍编译器限制了语言设计：没有中间数据结构存放程序全局信息，也不会回访先前解析的代码。因此一看到某表达式，就必须立即知道足够信息来正确编译它。

Pascal 和 C 都围绕这项限制设计。当时内存极其宝贵，编译器甚至未必能把整个源文件放入内存，更遑论整个程序。这就是 Pascal 文法要求类型声明放在块开头的原因，也解释了 C 中为何不能调用定义在后面的函数，除非先有明确的前向声明来告诉编译器生成该调用所需的信息。

语法制导翻译（syntax-directed translation）是典型单遍做法：为每条产生式关联一个通常用于生成目标代码的动作；解析器匹配该语法片段时立刻执行动作。它节省内存，却让之后才获得的信息难以影响已经生成的代码。

2.2.2 树遍历解释器（Tree-walk Interpreters）

有些编程语言刚被解析为 AST（可能再做少量静态分析）便开始执行。要运行程序，解释器一次沿一个分支、一片叶子地遍历语法树，并在经过每个节点时对其求值。

这种实现风格常见于学生项目和小语言，但一般不用于通用语言，因为往往较慢。有人把“解释器”只用于这类实现，另一些人对其定义更宽泛；因此这里使用无可争议的明确名称：树遍历解释器。我们的第一个解释器就是如此。

一个重要例外是早期 Ruby：1.9 时，标准实现由原 MRI（Matz's Ruby Interpreter）切换为 Koichi Sasada 的 YARV（Yet Another Ruby VM），后者是字节码虚拟机。这也说明“解释器”并不锁死一种架构。

2.2.3 转译器（Transpilers）

为一门语言写完整后端可能很费工。若已有通用 IR 可作为目标，可以把前端接到上面；否则似乎无路可走。但若把另一种源语言视为中间表示呢？

为自己的语言写前端。后端不再把语义完全降到原始目标语言，而是生成另一门大致同样高层语言的合法源代码字符串；随后借助那门语言既有的编译工具，作为下山并获得可执行程序的出口。

这种技术过去称为源到源编译器（source-to-source compiler）或 transcompiler。随着为浏览器而编译到 JavaScript 的语言兴起，人们采用了更时髦的称呼：转译器（transpiler）。今天大部分转译器处理高层语言。UNIX 广泛传播后，生成 C 的编译器形成传统，因为 C 编译器到处可用且生成高效代码；当今浏览器是“机器”，JavaScript 是其“机器码”，所以几乎每种语言都有面向 JS 的编译器。WebAssembly 又提供了第二种更低层的 Web 目标语言。

转译器的前端，扫描器和解析器，与其他编译器相同。若源语言只是目标语言简单的语法外衣，可能跳过分析，直接输出目标语言的对应语法；若两种语言的语义差异较大，则会有分析甚至优化等完整编译器阶段。代码生成时，输出的不是机器码等二进制语言，而是目标语言中语法正确的源代码。之后让该代码经过目标语言已有的编译管线即可。

首个转译器 XLT86 把 8080 汇编译为 8086 汇编。8080 是 8 位芯片，而 8086 是能把寄存器当作一对 8 位寄存器使用的 16 位芯片；XLT86 用数据流分析追踪源程序的寄存器使用，再高效映射到 8086 寄存器集。它由 Gary Kildall 编写，他还创造了 PL/M 与 CP/M，这门最早的微型计算机高级语言和操作系统。

今天的转译器多处理高层语言。UNIX 传播后，生成 C 的编译器长期盛行：C 编译器到处可用且代码高效。如今浏览器是“机器”、JavaScript 是其“机器码”，几乎每门语言都有面向 JS 的编译器；WebAssembly 又为 Web 提供了第二种更低层目标语言。

2.2.4 即时编译（Just-in-time Compilation）

最后一种与其说是近道，不如说是只适合专家的危险高山攀爬。执行代码最快的方法是编译成本机机器码，但你可能不知道最终用户机器支持哪种体系结构，怎么办？

可以采用 HotSpot Java 虚拟机（JVM）、Microsoft 公共语言运行时（CLR）以及多数 JavaScript 解释器的做法：在用户机器上加载程序时，JS 从源代码加载，JVM 与 CLR 从平台无关字节码加载，然后编译为该计算机体系结构支持的本机代码。这自然叫作即时编译（just-in-time compilation，JIT），通常读作与 fit 押韵的“jit”。

最先进的 JIT 会在生成代码中插入性能分析钩子，观察哪些区域最影响性能，以及有哪些数据流过。随后随着时间推移，自动使用更高级优化重新编译这些热点（hot spots）。HotSpot JVM 的名称正来自这里。

JIT 不只是延后编译：它还能利用运行时已知的真实类型、调用频率和分支行为。代价是实现复杂、启动与预热时间增加，并需要在优化假设失效时回退。

2.3 编译器与解释器（Compilers and Interpreters）

现在已经往脑中塞进一整本词典的编程语言术语，终于可以回答一个自远古以来困扰程序员的问题：编译器和解释器有什么区别？

这就像询问水果与蔬菜的区别。看似二元对立，实际上“水果”是植物学术语，“蔬菜”则是烹饪学术语；一者并不严格意味着另一者的否定。有不是蔬菜的水果，例如苹果；有不是水果的蔬菜，例如胡萝卜；也有既是水果又是蔬菜的可食植物，例如番茄。

这里原图其实画错了一点：花生（甚至不算坚果）和小麦等谷物在植物学上都是果实；松子则似乎既不是果实也不是蔬菜。作者承认自己是软件工程师而非植物学家，却舍不得擦掉可爱的花生小人。

回到语言：

• 编译（compiling）是一种实现技术，把源语言翻译成另一种，通常更低层的形式。生成字节码、机器码，或转译到另一门高层语言，都是编译。
• 说某语言实现“是一个编译器”时，是指它把源代码翻译成其他形式但不执行；用户必须自行运行生成的输出。
• 相反，说实现“是一个解释器”时，是指它接收源代码并立即执行，从源代码运行程序。

GCC 与 Clang 显然是 C 的编译器而不是解释器：它们将 C 代码编译成机器码，终端用户直接运行该可执行文件，甚至可能不知道编译时用了什么工具。旧版本 Ruby 的标准实现则明确是解释器：用户从源代码运行 Ruby，实现解析代码并直接遍历语法树执行，没有发生其他内部或用户可见的翻译。

Go 工具是更奇特的园艺案例：go build 只把 Go 源代码编译为机器码；go run 则先编译再立即运行。因此 go 既可作为编译器使用，也可从源代码立即执行程序，同时其内部又拥有编译器。

那么 CPython 呢？使用它运行 Python 程序时，代码会被解析并转换为内部字节码格式，再在 VM 内执行。对用户来说，它显然是解释器，因为程序从源代码运行；但查看 CPython 的内部，会发现其中确实发生了编译。

答案是：它两者都是。CPython 是解释器，也拥有编译器。实践中多数脚本语言都如此。本书第二个解释器也位于这种交集：它内部会编译为字节码。因此，尽管本书名义上讲解释器，也会涵盖一部分编译内容。

2.4 我们的旅程（Our Journey）

一次吸收这么多内容确实不少，不必担心。本章并不要求你理解所有零件，只希望你知道它们存在，并大致了解如何组合。

在探索本书引导路线以外的疆域时，这张地图会很有用。我希望它让你渴望独自出发，在那座山上四处漫游。

此刻不必记住每个术语；知道这些零件存在、并大致知道如何组合，就已足够。后续章节会逐一让它们具体起来。并且从这里开始，作者承诺会收敛这套登山比喻。

但现在，该开始我们自己的旅程了。系紧鞋带，收紧背包，一起出发。从现在起，你只需要专注于眼前的道路。

挑战（Challenges）

1. 选一个喜欢的开源语言实现，下载源代码并探索。尝试找出实现扫描器和解析器的代码：它们是手写的，还是由 Lex、Yacc 等工具生成？通常 .l 或 .y 文件意味着后者。
2. 即时编译通常是实现动态类型语言最快的方式，但并非所有动态类型语言都使用它。有哪些不采用 JIT 的理由？
3. 大多数编译到 C 的 Lisp 实现也包含解释器，用于即时执行 Lisp 代码。为什么？