Crafting Interpreters（手写解释器）

引用

Nystrom, R. (2021). Crafting Interpreters. Genever Benning. Free official edition: https://craftinginterpreters.com/

章节概要

第1章：引言

引言阐明了本书的承诺：为同一门小语言 Lox 编写两个完整的解释器，展示并解释每一行代码，理论比其他书少。Nystrom 认为"小语言"无处不在，构建一门语言是很有挑战性的编程训练，而且这门学问并非只属于"巫师"。他介绍了本书的几种编排手段（注明插入位置的代码片段、旁注、章末挑战题和设计札记），说明为什么全部手写而不使用 Lex 和 Yacc，以及为什么第一个解释器用 Java、第二个用 C。

第2章：领地地图

本章概览语言实现的构造方式，跟随一个程序依次经过扫描、语法分析、静态分析、中间表示、优化、代码生成、虚拟机和运行时。接着介绍各种捷径，如单遍编译器、树遍历解释器、转译器和即时编译，并指出"编译器"与"解释器"之间的界线并不清晰，因此本书两者都讲。

第3章：Lox 语言

对将要实现的语言作一次非正式的介绍：一门动态类型、带垃圾回收、语法类似 C 的脚本语言，具有布尔值、数字、字符串和 nil，常见运算符、变量、控制流、带闭包的一等函数，以及支持单继承的类。其中一节解释 Lox 为什么采用类而不是原型。设计札记比较了以表达式为核心的语言与区分表达式和语句的语言。

第4章：扫描

第二部分开始编写 jlox，即用 Java 实现的树遍历解释器。本章搭建解释器框架（运行文件或 REPL、报告错误），并手写一个把源文本转为记号的扫描器，涵盖单字符和双字符运算符、字符串和数字字面量，以及按"最长匹配"原则区分关键字与标识符。有一小节把词法文法与正则语言联系起来，但没有深入讨论自动机。

第5–6章：表示代码；解析表达式

第5章介绍上下文无关文法并写出 Lox 表达式的文法，然后用一个小型元程序生成语法树类。它讨论"表达式问题"，引入访问者模式，并用它编写一个简单的树打印器。第6章用优先级和结合性规则消除二义性，为表达式构建递归下降语法分析器，并加入语法错误报告以及恐慌模式恢复与同步。

第7章：求值表达式

解释器开始对表达式树求值，用 Java 对象表示 Lox 的值。本章定义真值规则，实现一元和二元运算符，并加入带有清晰报告的运行时类型错误。设计札记权衡了静态类型与动态类型。

第8–9章：语句与状态；控制流

第8章加入语句、全局变量、赋值和块作用域，用一条环境链实现嵌套与遮蔽。第9章在简要介绍图灵机和图灵完备性之后，加入 if、短路求值的 and/or、while 和 for（后者通过脱糖转换为 while）。

第10章：函数

用户自定义函数登场：带参数个数检查的调用表达式、原生函数 clock()、函数声明与函数对象、return（通过抛出异常展开 Java 调用栈来实现），以及捕获其环境的局部函数。

第11章：解析与绑定

当闭包遇上可变环境时会出现一个隐蔽的错误，因此本章加入一个静态解析遍，在执行之前准确计算出每个变量引用指向哪个作用域。这是本书对语义分析的初步介绍，同一遍还会报告诸如在顶层代码中使用 return 之类的错误。

第12–13章：类；继承

第12章实现类声明、实例、字段（get 和 set 表达式）、方法、this 和初始化方法；设计札记比较了类与原型。第13章加入单继承和 super 调用，从而完成 jlox——该部分的引言称其不到两千行 Java 代码。

第14–15章：字节码块；虚拟机

第三部分用 C 从头开始构建 clox。第14章解释为什么选择字节码，而不是遍历 AST（内存局部性差）或生成本机代码（复杂且不可移植），并实现以动态数组存储的指令块、反汇编器、常量池和行号信息。第15章编写虚拟机的分派循环和值栈，使其成为一个计算器；设计札记讨论基于寄存器的字节码。

第16–17章：按需扫描；编译表达式

第16章编写只在需要时才产生记号的扫描器，并用类似字典树的状态机识别关键字。第17章编写一个直接输出字节码的单遍编译器，采用 Pratt 语法分析器：每种记号都有前缀和中缀解析函数以及一个优先级。

第18–19章：值的类型；字符串

第18章用 C 的带标签联合表示动态类型的值，加入布尔值和 nil 以及相应的类型检查和运行时错误。第19章引入共享同一头部的堆分配对象（"结构体继承"），实现字符串及其拼接，并维护所有对象的链表以便释放；设计札记讨论字符串编码。

第20章：哈希表

用整整一章从零构建哈希表：桶数组与负载因子、拉链法与开放寻址、FNV-1a 哈希函数、线性探测、扩容、用墓碑标记删除，以及字符串驻留——它使 clox 可以通过指针比较字符串。

第21–23章：全局变量；局部变量；来回跳转

这几章加入语句和全局变量（存放在哈希表中）、存放在栈槽中并在编译时解析的块作用域局部变量，以及用回填技术编译成条件跳转和无条件跳转的控制流。设计札记重新审视了关于 goto 的争论。

第24–25章：调用与函数；闭包

作者称第24章是一头"巨兽"，它加入函数对象、调用帧、用于嵌套函数的编译器栈、参数绑定、运行时栈跟踪和原生函数。第25章用上值（upvalue）实现闭包：上值起初是"打开的"（指向栈中），当变量离开作用域时被"关闭"（移到堆上）。

第26章：垃圾回收

虚拟机获得一个标记-清除垃圾回收器。本章定义可达性和根，使用三色抽象和灰色对象工作列表，把字符串表作为弱引用处理，讨论何时触发回收（延迟与吞吐量的权衡，以及自适应的堆阈值），并展示如何借助压力测试模式查找 GC 错误。

第27–29章：类与实例；方法与初始化方法；超类

对象模型用三章在 C 中重新构建：类对象和实例对象、字段、方法和绑定方法、this、初始化方法，以及一条使方法调用快上数倍的优化调用指令。第29章通过把方法向下复制到子类来实现继承，并实现 super 调用，从而完成整个虚拟机。

第30章：优化

最后一章测量并提升性能。它讨论基准测试与性能剖析，把哈希表探测中的取模运算替换为位掩码，并实现 NaN 装箱，把每个值压缩到 64 位中，后者报告的整体提升约为 10%。本章以进一步学习的建议作结，包括编译器优化教材和形式化的程序设计语言理论。

附录 I–II：Lox 文法；生成的语法树类

附录把完整的 Lox 文法集中在一处，并列出由第5章元程序生成的 Java 语法树类。

核心概念

第1–3章：欢迎

• 树遍历解释器与字节码虚拟机：本书先后构建的两种实现策略，以简单性换取速度。
• Lox：一门小型、动态类型、带垃圾回收的语言，具有闭包和类，专为被实现两次而设计。

第4–6章：jlox 的扫描与语法分析

• 记号与词素：词素是原始子串；记号在其基础上加入类型、字面量值和行号。
• 访问者模式：在不修改每个类的前提下，为一组固定的语法树类添加新操作的方法。
• 恐慌模式恢复：遇到语法错误后跳过记号，直到可能的语句边界，使分析得以继续并报告更多错误。

第7–11章：求值、状态与函数

• 环境：从名字到值的映射，链接到外层环境以模拟嵌套作用域。
• 脱糖：把方便的语法结构（如 for）翻译成更简单的结构（while）来实现。
• 闭包：保留其声明时所在环境的函数值。
• 解析器（Resolver）：在执行前把每次变量使用绑定到其声明的静态遍。

第12–13章：类与继承

• 绑定方法：与访问它的实例打包在一起的方法值，使 this 在之后仍然有效。
• 超类调用：super.method() 从包含该调用的类的超类开始查找方法。

第14–19章：字节码、虚拟机与值

• 字节码块：紧凑的线性指令数组，附带常量和行号。
• Pratt 语法分析器：由每种记号的前缀和中缀函数表驱动的优先级爬升式分析器。
• 带标签联合：在类型标签旁存放各种可能载荷之联合的 C 结构体，用于表示动态值。

第20–25章：哈希表、变量与调用

• 带墓碑的开放寻址：把条目直接存放在桶数组中，并标记已删除的槽位，使探测序列保持完整。
• 字符串驻留：每个不同的字符串只保留一份，使相等比较变成指针比较。
• 上值：虚拟机对被捕获变量的间接引用；变量在栈上时为打开状态，移到堆上后为关闭状态。

第26–30章：垃圾回收、对象与优化

• 三色标记-清除：用白、灰、黑三个集合记录对象是未访问、待处理还是已完全追踪。
• NaN 装箱：把非数字值编码进 IEEE 754 NaN 中未使用的位模式，使每个值都能放进 64 位。
• 先剖析再优化：用基准测试和性能剖析器找到真正的热点，而不是凭猜测。

评析

优点

• 每一步都有完整、可运行的代码。 两个解释器的每一行代码都出现在正文中，每个片段都注明应插入的文件和函数，章节的顺序保证每章结束后程序都能运行。读者最终得到的是两个可用的实现，而不是零散的片段。
• 同一门语言的两种实现。 把 Lox 实现两次，使本书能够直接对比不同设计：环境与栈槽、Java 的垃圾回收器与手写的回收器、构建 AST 的递归下降分析器与单遍 Pratt 编译器。第三部分的各章开头反复说明 jlox 曾经视为理所当然的东西。
• 语法分析之外的工程深度。 关于哈希表、带上值的闭包、垃圾回收和 NaN 装箱的章节，涵盖了许多入门编译器教材略过的运行时主题，并解释了测量结果和取舍（例如以缓存局部性作为放弃 AST 的理由）。
• 挑战题与设计札记。 挑战题把读者推到本章内容之外（添加 break、匿名函数、BETA 式继承、switch 语句），而关于隐式分号、静态与动态类型、"新奇度预算"等主题的设计札记则引入了语言设计方面的判断。

局限

• 有意弱化理论。 正则语言、文法和语法分析只讲到够用为止；LL 与 LR 理论、语法分析器生成器、类型系统和形式语义都没有涉及。需要应付编译原理考试的学生还需要另一本教材。
• 只针对动态的解释型目标。 Lox 没有静态类型，clox 编译成自己的字节码而非机器码，因此寄存器分配、指令选择和静态类型检查都不在讨论范围内。
• 默认读者掌握两门语言。 第二部分需要能用 Java，第三部分需要熟练的 C，包括指针和手动内存管理；作者明确表示，如有必要应先去学 C。
• 篇幅长、推进细。 逐段代码的写法使全书篇幅很长；作者也说明，代码是为了在书页上清晰而写的，并非生产环境的风格。

在课程中的定位

在本课程书单中，Crafting Interpreters 与 Douglas Thain 的 Introduction to Compilers and Language Design 是两本入门教材，覆盖的内容各不相同。Nystrom 为一门动态语言手写每个阶段，并深入运行时实现（闭包、垃圾回收、字节码虚拟机）；Thain 则讲授文法理论、Flex 和 Bison、静态类型检查，以及生成 X86 或 ARM 汇编。先读 Nystrom 可以直观地理解一门语言从头到尾如何运作；再读 Thain 可以补上 Nystrom 略去的形式化语法分析内容和本机代码生成。

课程中内容更全面的教材——Cooper 和 Torczon 的 Engineering a Compiler 以及 Aho、Lam、Sethi 和 Ullman 的 Compilers: Principles, Techniques, and Tools——通常被认为是对编译理论和优化的全面论述；Nystrom 在最后一章中也推荐把 Cooper 和 Torczon 作为学习编译期优化的下一步。Pierce 的 Types and Programming Languages 则适合学习本书刻意回避的形式化类型理论。

如何使用本书

本书面向初次接触语言实现的程序员。不需要编译器背景，但读者应当能熟练编程：第二部分只用到 Java 的一个很小的子集，第三部分则要求扎实的 C 功底。

本书预期的用法是逐章把代码敲进去，并让每个解释器始终保持可运行状态，这正是代码片段的设计初衷。第一部分（第1–3章）可以快速读完。第二部分（第4–13章）是理解扫描、语法分析、求值、作用域和闭包的核心；第11章关于解析的内容篇幅不长但很重要。第三部分（第14–30章）更长也更难；第24–26章（调用、闭包和垃圾回收）难度最大，也值得投入。较短的课程可以在第二部分结束后停止，或者把第三部分学到第26章，把面向对象各章和第30章作为选读。

每章至少尝试几道挑战题，但要在代码副本中完成，因为后续章节假定解释器保持未修改的状态。设计札记可以单独阅读，作为语言设计方面的讨论。本书网站提供全文，jlox 和 clox 的源代码以 MIT 许可证发布，可用于核对自己的实现。

版本与来源

本导读依据 Crafting Interpreters 的免费网络版 https://craftinginterpreters.com/（正文 © 2015–2020 Robert Nystrom；印刷版 2021 年出版）。内容取材于目录、各部分引言、第1章全文，以及全部 30 章的开篇部分、每个小节标题、挑战题和设计札记，其中第14.1节（为何选择字节码）和第30.3–30.4节（NaN 装箱与"下一步"）为全文阅读，另包括两个附录。