来源书籍

用Go语言自制解释器

Skill 版本:v24 经典原理(高浓度、高稳定性) 89 张卡片

高浓度、高稳定性(经典原理,全文阅读确认)。词法、Pratt解析、运行时对象、环境闭包与语法宏贯穿全书;讲清输入输出与约束。具体工具命令和性能历史案例按成书版本看待,教学实现的碰撞、错误诊断和宏卫生边界已明确。 **来源**:见 [_source_manifest.json](_source_manifest.json),EPUB 与当前解包文件已逐字节哈希绑定。 [整书笔记](_book_note.md)

索斯藤·鲍尔(Thorsten Ball) · 孙波翔 译 · 人民邮电出版社 · 2022-06-01 · ISBN 9787115588289

全书导读

本书以 Monkey 教学语言为对象,从字符识别逐步建立语法结构和运行含义,最终加入集合与宏。Go 是实现载体;解释器的设计原理是学习主线。全文从前言到宏系统依次展开。它用可以看见输入输出的测试推进每一层,但最终交付的是教学解释器:诊断、字符集、哈希碰撞、宏卫生和若干错误路径仍有限制。学习时应区分机制已经成立与生产防御已经完整。

全书主线

源代码最初只是字符。词法分析为字符片段赋予类别,使语法分析器不必反复识别名称和符号。语法分析器再依据优先级和语法规则把这些片段组织成AST;树的嵌套保存“谁属于谁”,而不是直接给出计算结果。

求值器沿树解释每类节点。运行时对象表示结果,环境把名称与对象联系起来。函数除代码外还保存定义环境,这使离开外层调用后的函数仍能访问捕获的绑定,形成闭包。返回值与错误则是需要改变执行方向的信号,必须传播到恰当的边界。

字符串、数组和哈希展示了如何扩展这条链路:新语法必须被识别和解析,新值必须有表示与运算规则。宏进一步利用已经建立的AST与求值器,在运行前生成新的程序结构。因此宏不是普通函数换一个关键字,而是改变实参何时执行、哪些代码进入最终程序。

flowchart LR
A[字符] --> B[词法单元]
B --> C[AST]
C --> D[可选宏展开]
D --> E[求值器]
F[环境中的名称绑定] --> E
E --> G[运行时对象与副作用]

前言

本部分解释为什么从零构建树遍历解释器。程序先变成结构,再取得运行含义;函数既是值,也可以接受其他函数。顺序学习使每一步都依赖前一步的输出。

  • 树遍历解释器:树遍历解释器先把源代码转换成抽象语法树(AST),再按树的结构逐节点计算结果。AST 表示程序结构,求值器为结构赋予运行含义。Monkey 的教学实现把词法分析、语法分析、内部对象系统和求值器分开,便于观察字符如何逐步变成结果。这个结构只是解释器的一种实现:不能据此断言所有解释器都会先生成 AST。
  • 头等函数与高阶函数:头等函数是可以像整数或字符串一样被传递的函数值。高阶函数则把函数作为参数,或者以函数为结果。Monkey 的 twice 接受函数 f 和数据 x,再计算 f(f(x)),因此是高阶函数。两者关联在于:当函数能作为值传递,函数就可以组合别的函数的行为,而不必把每一种操作写死在调用者中。
原书依据 · 2 处

第 1 章 词法分析

本部分解释如何把字符转为可供解析器使用的符号序列。首先确定 token 的表示,再给扫描器建立位置不变量,最后加入名称、数字、双字符符号和交互入口。下面各项分别解释职责、边界与实现约定。

  • 词法与语法的分工:词法分析把字符流切成带类型的词法单元;语法分析再把这些单元组织成抽象语法树。词法分析识别“这是什么符号”,不负责证明这些符号组成了合法程序。因此,词法测试可以使用包含各种运算符的乱码,检查每个符号是否被识别;不能因词法分析成功就认定程序能运行。
  • 空白处理取决于语言:空白是否可以丢弃,由被解释语言的语义决定。Monkey 里,空格和换行仅分隔词法单元,连续空白不改变代码含义,因此可以统一跳过;Python 等语言会让缩进或换行参与程序结构,扫描时就必须保留相应信息。迁移词法分析器时,应先确认语言规范,不能把“忽略空白”当成通用规则。
  • 词法单元的类型与字面量:词法单元需要同时保留类型与字面量。类型告诉后续阶段应该怎样处理它,例如整数、标识符或右括号;字面量保留源代码中的具体文本,区分整数 5 与 10、名称 x 与 y。Monkey 的 Token.Literal 使用字符串,因此本章的整数 token 仍保存数字文本,数值转换留到后续阶段。不要把本章最初的概念示意误当成实现字段类型。
  • EOF与非法字符:EOF 表示输入结束,后续解析器据此停止取词法单元;ILLEGAL 表示扫描到了当前语言无法识别的字符。结束是正常边界,非法字符是无法分类的输入,两者不能混成同一信号。即使当前演示程序忽略详细错误位置,保留这种区分也能让下一阶段知道是正常收尾还是遇到了未知输入。
  • 扫描游标的推进约定:扫描器必须明确辅助函数返回时停在哪里。Monkey 的 readIdentifier 和 readNumber 会持续推进,直到当前字符已经不是该词法单元的一部分;所以 NextToken 应直接返回,不能再执行结尾的统一前移,否则会漏掉紧跟的分号或运算符。反之,单字符分支尚未消费下一个字符,需要统一前移。组合扫描函数时,返回位置约定比“每次都前移”更可靠。
  • 前瞻不消费输入:前瞻是在不改变扫描状态的前提下观察后续字符。Monkey 的 peekChar 查看下一个字节,帮助区分 = 与 ==、! 与 !=;确认双字符词法单元后,才调用 readChar 消费第二个字符。把观察与消费分开,可以避免为了判断符号而提前移动游标,使下一次 NextToken 从错误位置开始。到达末尾时也要返回明确的结束哨兵。
  • ASCII扫描器的边界:按字节递增的扫描器适用于本书限定的 ASCII 字符,却不能直接用来识别完整 Unicode 字符。UTF-8 中一个字符可能占多个字节,若仍按 input[i] 取得单字节,就可能把一个字符拆坏。支持 Unicode 不只是把 ch 改为 rune,还要改变读取与推进规则,并同步检查标识符判定等辅助函数。实现的简洁来自范围约束,不能把教学限制误写成语言通用能力。
  • 关键字与标识符判别:关键字与标识符可能具有相同的字符形状,适合先按共同规则读取完整名称,再查关键字表。命中 let 或 fn 就返回对应的关键字类型,未命中则返回 IDENT。这样新增关键字通常只需增加表项及 token 类型,而不必复制读取名称的扫描循环。字符规则本身仍限制名称范围:本书的 isLetter 接受英文字母与下划线,不能自动推断它支持任意 Unicode 名称。
  • REPL连接交互与执行:REPL 重复执行读取输入、求值、打印结果。第1章先搭建交互外壳:每次读一行,把该行交给词法分析器,打印词法单元直到 EOF;此时还没有真正的求值能力。之后可以沿用这个外壳加入语法分析与求值。分步搭建的用途是尽早获得可观察输出,不能把“能交互打印 token”当作完整解释器已经完成。
  • 词法测试检查符号边界:词法分析测试可以把全部符号集中在不符合语言语法的输入里,因为它验证的是 token 序列,而非程序求值。检查项应包括类型和字面量,还要覆盖多位数字、换行、双字符运算符以及输入末尾;这些组合能够暴露游标偏移一位的问题。测试对象的职责决定预期:若强制每个测试输入都能执行,反而会限制对扫描边界的观察。
  • 当前字符与读取位置:Monkey 的扫描器保留当前字符位置 position,以及下一次读取的位置 readPosition。readChar 先从后者取字符,再令 position 指向刚读取的位置,最后把 readPosition 加一。这样当前字符和下一字符的角色清楚分离,后续可实现不移动状态的前瞻。输入结束后使用零字节作哨兵,是这个教学实现的约定;它不是通用字符集方案。
  • 错误位置改善诊断:将文件名、行号和列号保存在词法单元中,可以让后续语法错误报告指出具体位置。例如,“缺少分号”只能说明错误种类,而附带文件与位置后,使用者才能迅速定位。教学版省略这些信息以减少实现负担;在生产设计中应把诊断需要作为 token 表示的输入,不能因为演示代码省略了位置,就认为解析器不需要来源坐标。
原书依据 · 12 处

第 2 章 语法分析

词法分析只给出符号序列,本章把它变成可求值的结构。先用语句确立程序骨架,再用Pratt算法安排表达式的组合,最后把条件、函数和调用纳入同一体系。以下按这一依赖关系展开。

  • 抽象语法树保留结构:抽象语法树用节点和嵌套关系表示程序结构,省略只用于指导解析的某些标点、空白和括号。省略这些字符不等于丢掉求值顺序:顺序已经体现在树的父子关系中。AST没有适合所有语言的统一格式,节点的具体形状必须服务于该语言的语义。
  • 解析生成器的输入输出:语法分析器生成器把语言的正式描述转换成解析器代码,后者运行时再把源代码变成语法树。上下文无关文法描述语句的构成规则,BNF或EBNF是书中提到的规则记法。生成器与解析器处在不同层次:前者生成处理程序,后者处理被解释语言的输入。
  • 手写解析器的学习边界:手写解析器可以让学习者观察构造AST、推进token和报告错误的每一步,从而理解生成器解决什么问题。这个学习价值不保证生成的解析器适合生产;书中明确承认其正确性证明、错误检测和恢复存在限制。选择工具时,应区分理解机制的目标与生产正确性、健壮性的目标。
  • 语句与表达式:本书以是否产生值区分表达式与语句。表达式可嵌入需要值的位置,例如字面量、调用和Monkey的if;let与return则承载绑定或控制动作。这个划分属于具体语言的设计,不应把其他语言的分类机械移植过来。判断一段语法能否出现在等号右边,需要看Monkey是否把它定义为表达式。
  • 名称节点的语境复用:同一个名称表示可以出现在绑定处,也可以出现在取值处。Monkey用Identifier节点表示两者,减少节点种类;let中的Name用来记录绑定名称,而在表达式位置,Identifier表示读取对应的值。节点形状相同并不意味着执行行为相同,具体职责由它所在的语法位置决定。
  • 递归下降构造语法树:递归下降从程序根开始,按当前token选择解析函数,再由这些函数递归构造子节点。解析函数返回局部AST后,外层循环把它接到程序中并继续处理输入。它自然地映射“整体包含哪些部分”的结构,但表达式还需要处理优先级,不能只靠按关键词依次分派。
  • 匹配后再推进:expectPeek检查下一个token是否符合当前语法要求,只有匹配时才推进当前位置。这个动作同时确认语法并维护游标:例如let之后应是名称,名称之后应是等号。不匹配时记录预期与实际类型,使调用方可以拒绝构造不完整节点。不要把普通的无副作用前瞻与这种成功时会消费token的断言混淆。
  • 解析错误需要显式检查:若解析失败只返回nil,顶层循环可能忽略该语句,使错误输入看起来只是少了一个节点。Monkey另外维护错误列表,解析器调用方和测试先检查该列表,再使用AST。错误与部分结果可以同时存在,因此“有返回树”不足以证明解析成功。书中累积多个错误的演示也不构成完备错误恢复的证明。
  • 表达式语句的包装:表达式语句把一个表达式包装成能放入程序语句序列的节点,使x+10这样单独出现的表达式合法。包装不改变表达式产生值的性质,只解决顶层结构如何统一存放的问题。这样Program可以保持语句列表,同时容纳let、return和独立表达式。
  • AST打印用于结构测试:为AST节点实现递归的String表示,可以用带括号的文本观察实际分组,例如把a+b*c显示为(a+(b*c))。这种输出适合测试优先级与结合方向,而不是重建源文件的原始格式;AST已经省略部分空白和标点。结构化字段断言仍用于检查具体节点类型和内容。
  • Pratt按位置选择处理:Pratt解析把处理函数关联到token类型,并按该token处于表达式开头还是已有左表达式之后选择处理方式。前缀函数不接收左操作数,中缀函数接收已经构造好的左表达式。同一个减号因此既能表示负号,也能表示减法,而不需要词法分析器区分这两种语法角色。
  • 解析函数的游标协议:本书的解析协议要求:进入处理函数时,当前token是该表达式开始处理的位置;返回时,当前token停在已解析表达式的最后一个token。调用者根据这个约定决定是否继续推进,避免重复消费或漏读。单个标识符无需前移,复合表达式则可能递归消费多个token,但返回位置约定一致。
  • 整数文本到数值的转换:词法阶段保存数字文本,语法阶段的parseIntegerLiteral再把文本转换为int64,并把结果存入AST节点。转换失败写入解析错误列表,不能只保存一个看似整数的节点而忽略错误。这种分层让扫描规则和数值表示分别处理;具体可接受范围仍受词法扫描规则与转换函数共同约束。
  • 优先级表示相对关系:优先级常量的具体整数通常不重要,重要的是大小关系:本书让乘除高于加减、前缀运算高于普通算术、函数调用更高。解析器据此决定哪些子表达式应先组合。优先级决定语法结构,求值器随后依照该结构执行;它不是在词法阶段直接计算数值。
  • Pratt循环扩展左表达式:Pratt先用前缀函数取得一个左表达式,再比较本层阈值与下一个运算符的优先级。只有后者更高时,才进入对应中缀函数,用已解析结果作左操作数继续组合。于是加法右边的乘法能在递归中先组成子树,外层再把它接到加法节点上。若无可用的中缀函数,则返回已有结果。
  • 相等优先级产生左结合:解析1+2+3时,第一个加号递归解析右侧,并以加法优先级作阈值;下一个加号优先级相等,严格小于比较不成立,内层只返回2。外层再把1+2作为左侧接上第二个加号,得到(1+2)+3。结合方向来自递归阈值和比较规则,不能只看运算符的优先级排名。
  • 右结合降低递归阈值:若希望a+b+c形成a+(b+c),需要让右侧递归继续接纳相同优先级的运算符。书中演示在解析加号右侧时把阈值减一,从而使后续加号进入内层。这个修改会改变原有左结合测试结果;它是说明机制的演示,不是Monkey默认加法规则。
  • 分组表达式重置阈值:括号可改变表达式的组合方式,却不必对应一个独立AST节点。Monkey遇到表达式开头的左括号后,在括号内部以LOWEST重新解析,再要求匹配右括号,直接返回内部表达式树。括号的作用已经由嵌套树形保存,外层继续按自己的阈值处理,因此(5+5)*2的加法能先组合。
  • 条件与块语句:块语句是一系列被大括号围住的语句,供if分支和函数体复用。if表达式包含条件、成立时的块和可选的else块;可选分支不存在时不应按缺失必需语法报错。块解析遇到右大括号或EOF停止,但提前遇到EOF只能说明已无输入,不能据此证明括号完整。
  • 定义参数与调用参数:函数定义的参数列表是名称列表,函数调用的参数列表则是任意表达式列表。两者都需处理空列表、逗号和结束括号,但生成的节点类型不同。调用表达式的目标也可以是表达式,例如函数字面量,所以解析调用不能只接受一个固定函数名。
  • 括号按位置区分职责:位于表达式开头的左括号启动分组解析;位于已解析表达式之后的左括号启动函数调用解析。Pratt把两种处理分别注册为同一token的前缀和中缀函数。调用还必须配置CALL优先级,仅注册处理函数不够,否则主循环可能不会进入该分支。语法角色取决于位置及绑定规则,而不只取决于字符。
  • 交互解析不等于求值:RPPL读取一行代码,将其解析成AST,再打印AST的结构表示;它还没有计算程序的运行结果。交互入口先检查解析错误,有错误时输出诊断并继续下一轮,避免把不可靠的部分树当成成功结果。这个阶段可帮助观察优先级,但变量绑定与函数调用的运行语义要由后续求值器实现。
原书依据 · 22 处

第 3 章 求值

语法树确定程序的组合方式,求值器则决定这些组合在运行时意味着什么。先建立值表示,再支持运算、分支和控制信号,随后用环境保存绑定,最后把环境与函数组合成闭包。错误和返回不是普通数值,它们需要沿递归传播到恰当边界。

  • 求值决定运行语义:求值把AST结构变成运行行为:算术节点产生数值,条件节点选择分支,调用节点执行函数。语法正确的树本身并没有规定所有行为,例如参数先算左边还是右边、整数能否作为条件,都需要语言语义作出选择,并由求值器落实。测试应明确这些选择,避免把宿主语言的默认行为无意间当成被解释语言的规则。
  • 求值策略的实现取舍:树遍历解释器直接访问AST并执行节点含义,容易构建和扩展,但执行结构不一定紧凑。字节码方案先转换成另一种中间表示,再由虚拟机执行;JIT进一步生成机器代码。后两种方式可能改善执行效率,却增加实现复杂度及体系结构适配工作。性能优势需要具体实现与测量支持,不能把书中的总体比较当成所有程序都成立的速度保证。
  • 字节码需要虚拟机:字节码是一组供特定虚拟机理解的指令,可以包含入栈、出栈等操作。它不同于源语言的AST,也不同于CPU可以直接执行的本地机器码。虚拟机在这里模拟的是这套指令的执行规则,而不是必然模拟完整硬件。设计字节码时,表示密度、操作集合与执行器必须互相配合。
  • 运行时值与语法节点:AST节点表示程序写了什么,运行时对象表示执行得到了什么。整数字面量节点可以转换成保存int64的整数对象,而名称随后绑定的是这个运行时值。对象系统在这里是“值的表示系统”,并不意味着Monkey是面向对象语言。把语法结构与运行时结果分开,求值器才能统一传递不同类型的值。
  • 对象表示的设计约束:运行时值可以直接使用宿主语言原生类型,也可以包装成结构体或用其他编码表示。选择受宿主语言、被解释语言需要的数据种类、内存开销和执行速度共同约束。Monkey优先可读性,使用统一接口包住不同值;这个教学选择不能证明包装对象在所有解释器中都是性能最优方案。
  • 字面量自求值:自求值表达式不需要查询名称绑定就能确定自己的值,例如整数5和布尔true。求值器把对应的AST字面量转为运行时对象。即使测试输入只有5,仍需从Program根经过表达式语句到达字面量;只实现处理整数节点的分支而不遍历外层结构,整程序求值仍会得到空结果。
  • 单例布尔与空值:布尔值只有真、假两种,因此Monkey复用TRUE和FALSE对象,而不在每次求值时重新分配;空值同样复用NULL。这里的NULL是被解释语言中的一个明确值,不等同于求值器尚无结果的Go nil。复用减少了重复分配,也成为后面按对象身份判别布尔值的前提。
  • 值相等与对象身份:对象身份相等是“是否同一个对象”,值相等则是“内容是否相同”。Monkey布尔值只有两个单例,可以用指针身份比较;两个整数5却可能来自不同分配,必须比较封装的int64。若把所有相等判断都写成指针比较,5==5可能错误地为假。分派顺序也重要:先处理整数内容比较,再处理可按单例身份比较的值。
  • 真值与条件分支:Monkey把NULL和FALSE视为假,其余运行时值视为真;条件不要求本身就是布尔对象。条件表达式先求值,再只执行被选中的分支,避免另一分支的副作用。条件为假且没有else时返回NULL。这个真值规则属于Monkey的选择,不能直接套用到其他语言或把整数零默认视为假。
  • 返回值需要穿过嵌套块:return不仅携带一个值,还要求停止当前语句序列。Monkey用ReturnValue包装该值,嵌套块遇到它时原样向上传播;如果内层块立即解包,外层会把它误当普通结果继续运行,覆盖真正应返回的值。程序边界或函数调用边界才负责解包,从而在正确的范围内结束执行。
  • 错误创建与停止执行:运行时错误既要表达失败原因,也要阻止后续求值。Monkey将错误封装成Error对象,程序和块的求值循环遇到它就返回;每次递归求值子表达式后也要检查,避免把错误当普通操作数继续运算。只验证错误消息正确不够,还须检查错误之后的语句没有覆盖结果或产生副作用。
  • 空值不能掩盖运算错误:“没有值”与“不支持这个操作”含义不同。Monkey早期为了搭骨架,把未知运算返回NULL;加入错误系统后,类型不匹配或未知运算应返回包含原因的Error。否则调用者无法区分合法的空结果与运算失败。这个演进提醒实现者:临时占位行为需要在完成错误协议时一并替换。
  • 环境保存名称绑定:环境维护名称到运行时对象的映射。let先求出右侧表达式的值,确认无错误后才写入环境;标识符求值则查环境,找不到时报告名称未定义。环境传给递归Eval调用,使表达式能够访问同一组绑定。名称字符串与它当前绑定的值不是同一个东西,解析阶段识别出名称不代表运行时已经定义。
  • 交互状态与测试隔离:交互解释器在输入循环外建立环境,使一行定义的名称能被后面的输入使用。测试辅助函数则每次创建新环境,避免前一个用例留下的绑定影响后一个用例。两者需要的生命周期不同:交互需要持续状态,独立测试需要隔离;不能为了统一调用方式把环境机械地做成全局变量。
  • 调用先计算实参:Monkey调用时先求出函数目标,再从左到右求值实参,最后把所得对象交给函数。add(2+2,5+5)传入的是4和10,而不是两棵表达式树。某个实参出错后应停止,不再计算后续实参。这种顺序会影响包含副作用的程序,因此属于可观察的语言语义,而非随意的内部循环细节。
  • 扩展环境保护外层绑定:函数调用需要把实参绑定到形参,但不能直接写进外层已有环境,否则同名形参会覆盖外面的变量。Monkey为每次调用建立一个新的空环境,放入形参绑定,并保留指向外层环境的引用;读取名称先查本层,缺失再向外查。这样局部名称能遮蔽外部名称,同时保留外层原来的值。
  • 闭包保留定义时环境:闭包由函数代码及其定义时可访问的环境共同构成。Monkey求值函数字面量时,把当前环境引用放进Function.Env;调用时扩展这个定义环境,而不是调用者当前的环境。因此newAdder(2)返回的函数即使离开外层调用,仍可读取x=2。保存的是环境引用,不应把这个实现描述成自动复制所有变量的值。
  • 函数边界解包返回值:块语句要传播ReturnValue,函数调用结束时则必须解包。如果让返回包装继续穿过调用边界,它会被外层函数误认为自己的return,导致外层提前停止。applyFunction因此先在扩展环境中求值函数体,再取出返回包装里的普通值。传播与解包各有职责,边界位置决定控制流是否正确。
  • 宿主GC管理解释器对象:Monkey运行时对象由Go对象承载,因此当前教学实现借用Go的垃圾回收。临时整数和调用环境失去可达引用后,可以由宿主GC回收;闭包保留的环境仍可达,不能只因函数已经返回就宣称该环境可释放。GC减少手工管理负担,却不保证任何程序都不会耗尽内存:持续保留可达对象仍会增加内存占用。
原书依据 · 19 处

第 4 章 扩展解释器

本章沿词法、语法、对象系统与求值器的路径接入字符串、数组和哈希,再用内置函数连接宿主能力。扩展复用了前面建立的表达式与调用框架,但各类型仍有自己的操作契约和失败边界。

  • 扩展类型需要贯穿各层:新增语言类型通常不只是增加一个运行时结构体:还需要识别字面量token、构造AST节点、定义运行时值,并让求值器完成转换。字符串、数组与哈希沿同一链路接入,因此可用这条链路检查是否漏掉某层。已有词法符号或表达式列表解析可以复用,不应为了新类型重复整个前端。
  • 字符串扫描的结束边界:Monkey用一个STRING token承载引号中的整段文本,避免后续解析器重新拼接文字与空白。扫描器遇到闭引号或输入结束时停止,但本书实现没有把缺少闭引号报告为错误,也没有完成转义字符支持。这是教学边界,不能把能够识别普通字符串等同于完整实现通用字符串字面量。
  • 字符串运算比较内容:Monkey字符串求值复用Go字符串表示;连接操作先检查运算符,再取出两端字符串内容,产生一个新字符串对象。默认实现只支持加号连接,其他运算报错。如果扩展相等比较,应比较字符串内容,不能比较两个独立分配的对象指针。类型可以复用宿主表示,但运算语义仍须显式定义。
  • 内置函数连接宿主能力:内置函数由解释器实现者用Go提供,接受运行时对象并返回运行时对象,把Monkey自身尚不能表达的能力暴露给用户。名称查找先检查用户环境,再查内置表,因此普通绑定可以遮蔽内置名称。调用分派区分用户函数和内置函数:前者建立环境并求值函数体,后者直接调用宿主函数。
  • 内置函数校验调用契约:内置len先验证参数数量,再按对象类型分派,最后返回长度对象;错误数量和不支持的类型要产生Error。字符串分支实际调用Go的len,计算的是字节长度,不应凭英文示例概括成Unicode字符数;数组分支计算元素个数。同一函数名覆盖不同类型时,结果单位也需要解释清楚。
  • 终止符参数复用列表解析:数组字面量和函数调用参数都是逗号分隔的表达式列表。把结束token作为parseExpressionList的参数,就能在方括号与圆括号之间复用解析循环,同时保留空列表、分隔符和闭合检查。这里复用的是相同语法结构,而不是因为两个功能名称相近就强行共享。
  • 索引表达式的语义检查:数组索引的左侧与下标都可以先解析成表达式,例如returnsArray()[1]或a[1+1]。语法合法不代表运行时类型合格:求值器先计算左右表达式并传播错误,再要求数组配整数索引。Pratt还需给左方括号注册中缀函数并配置INDEX优先级,仅注册处理函数并不能保证索引被正确组合。
  • 数组越界返回空值:Monkey选择对数组负下标和大于末尾的下标返回NULL,而不是抛出错误。实现先确认索引为整数,再比较0与len-1;空数组也会自然落入越界分支。这是一项语言语义选择,测试须覆盖首项、末项、负数和恰好等于长度,不能把其他语言的越界行为当作默认要求。
  • 数组首尾与余项:first和last分别取数组首尾元素,空数组返回NULL。rest去掉第一个元素并返回新分配的数组:单元素数组得到空数组,空数组才得到NULL。这两个结果含义不同,递归处理列表时需要先用长度判断完成条件,避免把无剩余元素与无结果混为一谈。
  • 复制数组保持原值:push分配长度多一的新数组,复制原元素,再加入新元素;rest也复制剩余元素。两者都不修改传入数组,因此同一个旧绑定仍可看到原有元素序列。这里复制的是元素对象引用,不是递归深拷贝所有对象;不可变接口与底层对象共享的区别需要保留。每次复制也有与数组长度相关的成本。
  • 用基本数组操作组合高阶函数:map逐项取first,把函数作用于元素后push到累计数组,再对rest递归;reduce则把当前元素与累计值交给组合函数。空数组是结束条件。少量基础操作与头等函数就能组合出更高层行为,但这组教学实现会反复复制数组,不能仅因表达简洁就推断适合大数据量或具有线性总成本。
  • 哈希键类型在运行时验证:哈希字面量的键和值在语法阶段都允许表达式。键最终能否使用,要看求值后的对象是否可哈希;否则名称表达式即使最终得到字符串,也会被过早拒绝。Monkey支持字符串、整数和布尔结果作键,其他对象报错。解析结构与判断运行时能力应分层处理。
  • 哈希键不能使用对象身份:两个独立字符串对象即使内容相同,也有不同的指针身份。直接用对象指针作哈希键,会让插入时的name与查找时新建的name不能匹配。逐项比较内容可以补救,却退化为线性查找;Monkey改为从值生成可比较的HashKey,使等值对象能进入同一索引位置。
  • 类型参与哈希键身份:Monkey的HashKey由对象类型和uint64值组成:布尔映射为0或1,整数转为uint64,字符串使用FNV结果。类型字段使布尔true与整数1即使数值部分相同也不会成为同一个键。复合键必须保留决定语义身份的维度,不能只比较一个散列数字。
  • 哈希碰撞仍需处理:不同字符串仍可能产生相同的有限位宽哈希值。Monkey教学实现只用类型和哈希数字作map键,没有在命中后进一步区分碰撞的原始字符串,因此不能承诺所有不同字符串都能正确共存。书中提到链式法与开放寻址但未实现;这是适用边界,不应写成哈希函数已经消除碰撞。
  • 原始键用于可读投影:HashKey适合索引查找,却不能替代用户原始键的展示。Monkey在HashPair里同时保存原始键对象和值对象,让Inspect能够打印可理解的键值内容。内部检索标识与外部可读表示各有职责;只存哈希数字会使展示或未来遍历接口丢失原始语义。
  • 哈希缺键与不可哈希分开:哈希索引先要求下标对象实现Hashable,再计算HashKey查询映射。对象不能作键时返回Error;键合法但不存在时返回NULL。两种情况不能合并,因为前者违反调用契约,后者是合法查找的空结果。空表查询、不同支持类型与函数作键都需要独立观察。
  • 打印副作用与返回值:puts逐个调用参数对象的Inspect并输出,每个参数独占一行;随后返回NULL。打印的文字是副作用,并不是函数返回的字符串。因此交互环境既可能显示Hello,又显示求值结果null。理解返回值与可观察副作用的区别,才能避免把屏幕输出误当成可绑定和继续计算的值。
原书依据 · 18 处

第 5 章 遗失的篇章:Monkey的宏系统

宏把源代码当成结构化数据处理。本章先用quote暂停求值,用unquote局部恢复求值,再建立AST修改器,最终在运行前把宏调用替换成生成的代码。控制代码的构造与执行阶段是理解宏的主线。

  • 文本宏与语法宏:文本宏主要在字符层面替换或生成代码;语法宏处理代码的结构化表示。Monkey已经把源程序解析成AST,因此语法宏可以把表达式作为数据传递、修改或生成,再交给求值器执行。两者的操作对象不同,不能把所有宏都理解成字符串拼接;语法宏的能力也取决于语言如何开放AST操作。
  • quote阻止通常求值:quote返回表示参数代码的对象,而不是参数执行后的值。例如quote(4+4)保留加法AST,不计算为8。它必须在普通函数调用的实参求值之前被特殊处理;若仅注册成普通内置函数,实参已经求值,原始结构就丢失了。表面像调用的语法不保证具有普通函数的求值规则。
  • unquote局部恢复求值:unquote在quote保留的代码中打开一个局部求值位置。quote(8+unquote(4+4))产生表示8+8的AST,外层加法仍不执行。unquote求值时使用当前环境,因此可读取名称绑定;它改变的是局部节点,不等于取消整段代码的引用状态。
  • 值转回语法节点:Eval返回运行时对象,而AST修改器需要语法节点,所以unquote的结果不能直接塞回语法树。转换函数把整数、布尔值重建为对应字面量节点;如果结果本来就是Quote,则取出其中的节点。转换支持哪些类型,决定了哪些值可以被注入代码;不支持的情况需要明确错误处理。
  • 引用代码可再次组合:Quote对象保存的AST可以通过unquote插入另一个quote,从已有结构构造新结构。例如一个分支注入计算所得8,另一个分支注入被引用的4+4,最终形成8+(4+4)的树。后者仍是代码而非已求出的8,理解这种阶段差异才能准确区分构造代码与执行代码。
  • AST修改器遍历再替换:AST修改器先递归处理子节点,再把当前节点交给modifier,并返回modifier产生的节点。父节点必须接住递归返回值,才能支持将原节点替换成新节点;只调用modifier后仍返回旧节点,只能覆盖部分原地修改情形。叶节点虽无子节点,也仍需经过modifier处理。
  • 结构遍历需要覆盖每个子项:树遍历的正确范围由每种节点的组成决定。条件表达式要访问条件、成立分支与可选分支;数组要访问全部元素;索引要访问对象与下标;函数要访问函数体及约定处理的参数。某种节点能正常打印不代表其内部已遍历,测试须在不同子项放入待替换节点来观察是否遗漏。
  • 修改映射键需要重建:哈希字面量的键和值都是表达式,两边都可能包含待替换节点。Monkey修改器建立新的映射,将修改后的键和值重新插入,再替换原Pairs。不能只更新映射的值而忽略键中的表达式。测试也需检查实际键值内容,避免对指针键直接做深比较时误判结果。
  • 宏展开位于解析与求值之间:Monkey宏展开在解析得到AST之后、运行时求值之前修改AST。这个位置让宏既能访问结构化代码,又能影响最终执行的程序。本章的实现先提取宏定义,再替换宏调用,最后求值修改后的树。这里描述的是Monkey管线,不应推断所有语言都只能采用同一种宏处理阶段。
  • 宏定义提取与删除:DefineMacros识别顶层let绑定宏字面量的语句,把参数、函数体和定义环境存为宏对象,并从待运行AST中移除这些定义。删除时从末尾向前处理记录下标,避免前一次删除改变后续位置。此实现仅识别顶层字面量绑定,不会把另一个名称绑定到已有宏的别名语句当成新宏定义。
  • 宏实参保留代码形态:普通函数调用先计算实参,宏调用则把实参AST包进Quote,绑定到扩展的宏环境,再求值宏体。宏体用quote构造新代码,用unquote取出参数代码,将结果替换原调用节点。这使宏能决定哪些实参代码进入最终程序,而非被迫在调用前执行全部实参。
  • 宏返回值必须是代码:本章宏协议要求宏体求值结果为Quote对象,展开器取其Node替换调用。这样宏可直接返回复杂AST,不受“普通运行时值转字面量”能力的限制。教学实现对非Quote结果直接panic,说明错误协议尚不完善;不能把示例测试通过等同于可安全处理任意宏输入。
  • 宏可以生成条件控制:unless宏生成取反条件的if树,再把两段分支代码插入对应位置,运行时只执行被选中的分支。如果写成普通函数,两个分支中的puts会在函数执行前作为实参先求值,无法保持条件执行。这说明扩展控制结构需要控制求值时机,而不只是把相同代码藏进一个函数。
  • 宏环境与运行环境分开:REPL维护macroEnv保存宏定义,另用env保存运行时绑定。每行解析成Program后,先定义和展开宏,再把展开结果交给Eval。两个环境都要跨交互行保留,但用途和执行阶段不同;把宏定义当普通运行时对象处理会模糊代码构造与程序执行的边界。
  • 语法规则限制宏表现力:Monkey把quote与unquote写成普通调用表达式的形状,因此参数只能是Expression,不能直接接收let或return语句。若要引用整个块,需要扩展语法并提供相应AST节点。宏能力不只由展开函数决定,前端允许表达哪些结构同样决定用户能生成哪些代码。
  • 生成代码需要来源与诊断:AST改写不仅涉及替换子节点,还涉及父节点的token与来源信息是否一致。教学修改器不更新这些信息,可能使打印与节点内容不一致;动态生成的token也缺少可靠的原始位置。当前系统还忽略多处类型断言和转换失败,未讨论卫生宏,因此只能作为理解宏机制的起点。
原书依据 · 16 处

跨章综合

第一条共同约束是边界协议。词法扫描要约定返回时游标停在哪,表达式解析要约定进入和返回时当前token的位置,求值要约定普通结果、返回包装和错误如何传播。各局部函数都可能看起来正确,但只要边界约定不一致,组合后就会漏字符、重复解析或错误地继续执行。

第二条约束是结构、值与身份不能混淆。AST保存程序结构,运行时对象保存执行结果;两个字符串对象可以内容相同却不是同一指针,因此哈希查找与相等运算必须按语义选择比较方式。quote与unquote又在这两个层次之间建立受控转换:先保留结构,再局部求值,必要时把结果变回结构。

第三条约束是阶段决定能力。用户函数通过运行时环境组合计算;宏通过展开环境组合代码。unless展示为什么普通函数无法接管实参的求值时机:调用之前两侧实参已经执行。宏先改写成if结构,让已有求值器负责只执行一个分支。语法、对象表示与阶段安排共同决定语言能表达什么。

这些联系也提示了实现边界:示例中可观察的成功路径不是通用正确性的证明。字符串未闭合、哈希碰撞、参数数量、AST来源和宏错误都需要单独的规则与验证。

发散与实践

以下为读者延伸和未执行的实践计划,不能作为作者已经验证的生产建议。优先阅读成熟实现以比较词法与语法边界,再用书中案例建立闭包和宏求值时机的观察矩阵。实践材料、限定范围及完成判据见ideas目录;本阶段交付计划,不声称已完成实测。

生成进度与管理记录

用Go语言自制解释器

Skill 版本:v24

执行模式:light

建档进度:done

四象限:经典原理(高浓度、高稳定性)

理由:高浓度、高稳定性(经典原理,全文阅读确认)。词法、Pratt解析、运行时对象、环境闭包与语法宏贯穿全书;讲清输入输出与约束。具体工具命令和性能历史案例按成书版本看待,教学实现的碰撞、错误诊断和宏卫生边界已明确。

来源:见 _source_manifest.json,EPUB 与当前解包文件已逐字节哈希绑定。

整书笔记

章节进度追踪表

章节号 章节标题 状态(pending/done) 卡片数
04 前言 done 2
05 第 1 章 词法分析 done 12
06 第 2 章 语法分析 done 22
07 第 3 章 求值 done 19
08 第 4 章 扩展解释器 done 18
09 第 5 章 遗失的篇章:Monkey的宏系统 done 16

非正文排除

spine项 类型 排除理由
1 cover.xhtml 封面 无文本,书名由版权页核验
2 copyright.xhtml 版权 出版信息,无实质论述;已读取用于元数据
3 epub_0003.html 致谢 仅感谢亲友审稿和支持,无知识论述;已全文读取
10 epub_0010.html 作者简介 仅职业履历,不涉及解释器机制;已全文读取

待关联术语

术语名 出现章节 一句话语境
JIT 04 前言 只概述即时转机器码,没有展开实现
direnv 04 前言 旧版无模块工具链的环境辅助工具

引用文献

标题 类型(书/论文/框架/源码项目) 出现章节 一句话语境
Top Down Operator Precedence 论文 06 Pratt解析法的来源;机制已成卡,文献入口登记
自上而下的运算符优先级(Douglas Crockford) 论文 06 JavaScript实现参考入口
Pratt Parsers: Expression Parsing Made Easy 论文 06 Java示例文章,延伸阅读
JavaScript语言精粹 书 06 介绍参考文章作者时纯提名
游戏编程模式 书 06 介绍文章作者时纯提名
yacc 框架 06 生成器举例,机制由生成器卡承接
bison 框架 06 生成器举例
ANTLR 框架 06 生成器举例
计算机程序的构造和解释 书 07 环境设计灵感来源,未展开该书内容
Wren 源码项目 07 建议阅读两种值表示,未在本书展开实现
Ruby解释器 源码项目 07 树遍历到字节码的历史案例并入求值策略
JavaScriptCore 源码项目 07 求值策略历史案例,不作为当前版本事实
LuaJIT 源码项目 07 JIT历史比较示例,不据此承诺性能
Elixir 框架 09 语法宏示例并入引用及宏实参卡
Clojure、Racket、Guile、Julia 框架 09 仅作后续宏学习方向,不扩写实现

资金安全问题案例

问题标题 问题卡 解决方案卡(如有) 出现章节 一句话说明

实践卡进度

序号 实践标题 实践方式 状态(pending/done) 关联章节 产出
1 成熟解析器边界深读 实现深读 done 05–06 ideas/idea-001-成熟解析器边界深读.md;首轮映射已准备
2 闭包与宏边界观察 其他(测试与故障案例观察) done 07、09 ideas/idea-002-闭包与宏边界观察.md

实践候选筛选:done

筛选取舍:未选从零重写完整解释器(目标为理解,不是重复造轮子);未选全量GC实现和生产宏系统(超出本书展开及本轮可执行范围)。两项均为计划交付,后续实际实践尚未执行。

轻量模式未执行生成后的笔记复核、独立审查及审查结果优化。知识卡、章节讲解和两项实践计划已生成;导入、归档及验收证据见_workflow.md。

相关主题

从本书的主题进入跨书阅读,对照其他书籍的讲解。下方数量包含主题关联的全部卡片与书籍。

暂无公开主题。