手写一门编程语言:SMALL 的解释器三板斧¶

这一章回答一个听起来很大的问题:编程语言是怎么被造出来的? 答案意外地小——一个能跑的语言 = 词法器(把字符切成 token) + 解析器(把 token 排成语法树)+ 求值器(沿着树算出结果)。三个部件各一百来行 Go,合起来就能执行 let x = 10; if x >= 10 { return x + 5; } 这样的程序。读完你会拿到「解释器」这个黑盒的完整图纸——这是全书对「编程语言」这个主题最直接的一章。

1. 这一章在原书里的位置¶

原书第 10 章,第三部分(应用)的开篇。第一部分讲语言、第二部分讲系统, 本章把两者汇合:「造语言是这些概念的自然顶点——想真正理解语法树、作用域、求值策略,没有比从头造一门语言更好的办法」¹。 SMALL 刻意做得极小(没有函数、没有循环、没有布尔),小到来得及在一个章节里全部讲完;第 11 章再给它加功能。

造语言的价值书里给两条:教育上,它逼你打通「高级想法」和「机器操作」之间的缝; 实用上,领域特定语言(DSL)——正则、SQL 就是经典案例——常常比通用语言更优雅地解决特定问题²。

2. 顶层全景:一条三站的流水线¶

  源文本          ① 词法器            ② 解析器              ③ 求值器
  let x = 10;  →  [LET x = 10 ;]  →  LetStatement{        →  env{x:10}
  if x >= 10 {    [IF x >= 10 {]     Name:x, Value:10}       if 真 → 执行块
   return x+5;    [RETURN x + 5 ;]  IfExpression{           return 包装成
  }               [} EOF]            Cond: x>=10,            ReturnValue 传回
                                      Consequence: Block{
                                        return x+5}}

图说:文本变 token、token 变树、树变结果。三个部件的接口都只有一两个函数, 这是本章最该带走的架构感。

3. 第一步之前:用 EBNF 把语法写成蓝图¶

EBNF(扩展巴科斯-瑙尔范式)是描述编程语言语法的标准记号。看 SMALL 的核心规则³:

  Program      = { Statement } ;                                        程序 = 一串语句
  LetStatement = "let" Identifier "=" Expression ";" ;                  let x = 5;
  IfStatement  = "if" Expression Block [ "else" Block ] ;               if … { … } [else { … }]
  Expression   = Equality ;                                             表达式从最低优先级开始
  Equality     = Relational { ("==" | "!=") Relational } ;              == != 最松
  Relational   = Addition { ("<" | ">" | "<=" | ">=") Addition } ;
  Addition     = Multiplication { ("+" | "-") Multiplication } ;
  Multiplication = Primary { ("*" | "/") Primary } ;                    * / 最紧
  Primary      = Number | String | Identifier | "(" Expression ")" ;    原子单位

两条读法。① 优先级藏在分层里:* 所在的层比 + 深,所以 1 + 2 * 3 必然解析成 1 + (2 * 3)——不用任何额外规则。 ② = 读作「定义为」、{ … } 读作「重复 0 次以上」、[ … ] 读作「可选」。注释故意不进语法——注释能出现在几乎任何地方,写进语法会让每条规则都挂上可选注释,臃肿;所以注释交给词法器当杂物跳过,解析器看到的是干净 token 流⁴。「判一个程序合不合法,人看着费劲,计算机永远一秒判完」——这份蓝图就是判据的全部内容⁵。

4. 词法器:两个指针和一张大 switch¶

词法器(lexer,也叫 tokenizer)一次吐一个 token。实现骨架小得惊人: 四个字段(输入串、当前位 position、下一位 readPosition、当前字符 ch) 和 readChar()(前进一格,到尾置 0)⁶。

关键机制是预看 peekChar()——不前进,只看下一个字符:

  当前 ch = '='  →  peek 是 '=' → 吞掉两个,产出 TokenEqual("==")
                 →  peek 不是  →  产出 TokenAssign("=")
  当前 ch = '/'  →  peek 是 '/' → skipComment 跳到底,递归 NextToken()
                 →  peek 不是  →  产出 TokenSlash(除号)
  当前 ch = '!'  →  peek 不是 '=' → 产出 TokenIllegal(! 单独不合法)

图说:== 与 =、!= 与非法、// 与除号,全靠预看一个字符分辨; 没有布尔、没有单独的 ! 运算符,是 SMALL 的语法边界(非法字符不是报错, 而是产出 ILLEGAL token 供下游发现)⁷。

Token 的类型表(TokenType 常量)值得看一眼的组织: 特殊(EOF、ILLEGAL)、标识符与字面量(IDENT/NUMBER/STRING)、关键字(let/if/else/return)、运算符(= + - * / == != <= >= < >)、分隔符(; ( ) { })——总共 20 来个,一门语言的全部词汇量⁸。关键字判定用一张查表(lookupIdent:let/if/else/return 命中即关键字, 否则 IDENT),字符串读取处理 \" 转义⁹。

5. 解析器:Pratt 的「前缀/中缀」查表法¶

解析器把 token 流变成 AST(抽象语法树)。树的类型纪律先立好:Node 基接口(TokenLiteral + String)下分 Statement(做事,如 let x = 5;) 和 Expression(产生值,如 x + 5)两个标记接口——语句和表达式在 Go 类型层面就是两个不相交的集合;每个节点结构体还存着原始的 Token, 给调试和报错留证。String() 递归把 AST 打印回代码形态,是检验解析器的现成工具²⁴。书上选了 Pratt 解析器—— 教科书级技术,优点一句话:把运算符优先级变成数据(两张函数表)而不是一堆 if。给 token 注册两类解析函数¹⁰:

prefixParseFn:token 出现在表达式开头时怎么解析。数字、标识符、字符串、(、if、负号 ——「表达式怎么开始」。
infixParseFn:token 出现在左值之后时怎么解析,参数是左值。所有二元运算符(+、-、*、/、==、<……)共用同一个 parseInfixExpression。

核心循环 parseExpression(precedence) 是所有玄机的所在¹¹:

prefix := p.prefixParseFns[p.curToken.Type]   // ① 先找「开头」
leftExp := prefix()                            //    造出左值
for !p.peekTokenIs(TokenSemicolon) && precedence < p.peekPrecedence() {
    infix := p.infixParseFns[p.peekToken.Type] // ② 右边运算符比当前紧?
    if infix == nil { return leftExp }
    p.nextToken()
    leftExp = infix(leftExp)                   //    包一层新节点,继续循环
}
return leftExp

图说:语句容器(让数学住进盒子里)是笨 switch——见 let 就 parseLet、见 return 就 parseReturn,其余当表达式语句¹²;而盒子里的数学由 parseExpression 递归 ping-pong:找一个开头(prefix),然后问「下一个运算符比我手头这层紧不紧?紧就吃掉右面再来一个开头」,直到遇见分号或优先级太松。

拿 1 + 2 * 3 走一遍:1 是 prefix 开头;看到 +(优先级 4),紧, 左值变成 (1+…);递归解析右值:2 开头,看到 *(优先级 5)比 + 紧, 先吃掉 3——2 * 3 先成子树,然后回到外层完成 (1 + (2*3))¹³。加一个新运算符 = 注册一个优先级 + 两张表各一个函数,其余代码一行不动 ——这是 Pratt 对「语言会长大」这个现实的最大善意。

语句层用 expectPeek(期望的 token) 守结构:let 后面必须是标识符、再后面必须是 =,不对就记错中止——parseLetStatement 是「语法检查发生在建造时」的样板¹⁴。

if 的双风格语法是 parseIfExpression 里值得单独记一笔的机制:SMALL 同时接受 C 风的 if (x > 5) 和 Go 风的 if x > 5——解析器 peek 下一个 token,是 ( 就吞掉括号再解析条件,不是就直接解析;两条路殊途同归到同一个 parseExpression(LOWEST)。原书明说这不是偷懒,而是设计语言的目标:紧凑、少样板、条件逻辑写得直白²³。

6. 求值器:沿着树走,一张 map 当内存¶

求值器(tree-walking evaluator)从根节点出发,一个大 type switch 分派到各节点的处理逻辑¹⁵。三件基础设施:

① Object 系统(「值」在解释器里的形态)。Object 接口要求 Type()(类型标签)+ Inspect()(给人看的字符串); Integer 就是包了一层 int64 的结构体¹⁶。动态类型语言的运行时值, 在静态类型宿主里全靠这样一个接口统一。

② Env(运行时环境 = 变量的家)。store map[string]Object, Get/Set 两个方法;comma ok 让「取未定义的变量」返回失败而不是 panic¹⁷。

③ ReturnValue 包装(return 怎么跳出嵌套块)。ReturnStatement 不求值就完, 它把值裹进 ReturnValue{} 返回;外层 evalProgram / evalBlockStatement 的循环每执行一条语句就查「结果是不是 ReturnValue」——是就立刻停,把里面裹的值往上传。没有这个包装,return 在 if 块里只会被当成普通值,块继续往下跑¹⁸。

其余规则照抄书里:truthiness——整数非 0 为真、字符串非空为真、Null 为假 (SMALL 没有布尔类型);比较运算借 nativeBoolToInteger 把真假映射成 1/0—— 「语言没有布尔类型,所以 < 返回 1 或 0」¹⁹;运算分派是三向的—— 两边都是整数走整数运算、都是字符串走字符串运算(evalStringInfixExpression), 其余组合(整数+字符串)不报错,落底返回 Null²⁰。

7. 主线例子:一个程序走完全程¶

源程序 absDiff.code(书上实测,输出 15)²¹:

  let a = 10;
  let b = 25;
  if a > b {
      return a - b;      // 不会执行
  }
  return b - a;

词法器吐出 23 个 token:LET IDENT(a) ASSIGN NUMBER(10) SEMICOLON LET IDENT(b) … IF IDENT(a) GT NUMBER(25) LBRACE RETURN IDENT(a) MINUS NUMBER(1)… 一路到 EOF。 解析器造出 4 个语句节点:两个 LetStatement、一个 ExpressionStatement 里包 IfExpression(条件 a > b,Consequence 块里是 ReturnStatement)、一个 ReturnStatement。 求值器:Env 里 a=10、b=25;算 If 的条件,a > b → 10 > 25 → 0(假) → 跳过块;最后一句 return b - a = 25 - 10 = 15,裹成 ReturnValue 一路传到顶。

第二个程序 sign.code(let x = -5; 三个 if 分支)输出 "Negative"—— 它演示了 ReturnValue 的急停:进了 if x < 0 的块,return 一出, 后面的 return "Zero" 永远轮不到²²。

8. 作者的判断与证据¶

判断	性质	依据
造语言是理解语言机制的最佳途径	作者的教育主张(业内共识)	章首论证¹
Pratt 解析器适合表达式多的语言	技术判断(教科书级做法)	前缀/中缀表的设计说明¹⁰
注释该由词法器跳过而非写进语法	设计语言的主张	「trivia」段⁴
教学语言先不做布尔,比较返回 1/0	刻意的教学简化	原文明说「we don't have Booleans」¹⁹
类型错误返回 Null 而不是崩溃	语言语义的设计选择(有争议)	evalInfixExpression 的落底分支²⁰

9. 边界与局限¶

没有作用域嵌套:if 块里的 let 会写进全局 Env(第 11 章才加); 「块级作用域」这个现代语言标配,SMALL v1 是缺的。
没有错误对象:isError(val) 检查在代码里出现,但 Error 类型本身在本章没有实现(求值错误怎么表示、怎么带信息,留给 v2)。
除零不检查:a / 0 会触发 Go 的 panic 而不是 SMALL 的错误—— 宿主语言的保护罩直接漏到了用户程序。
Pratt 解析器不处理左递归语法(如语句级歧义),本章靠「语句简单 switch + 表达式 Pratt」的分工绕开;更完整的语言要更系统的错误恢复。
AST 的 String() 用于调试很妙,但书里没演示用它做快照测试—— 那正是第 11 章测试一节补上的。

10. 可带走的¶

解释器 = 词法器 + 解析器 + 求值器;接口各一两个函数,能独立测试。
EBNF 是语言的蓝图:优先级写在语法分层里,合法性一秒可判。
词法器三件套:readChar 前进、peekChar 预看(区分 == / =、// / /)、 skipWhitespace/skipComment 跳过杂物。
Pratt 解析器:每个 token 注册 prefix/infix 两个解析函数; parseExpression 循环问「下一个运算符更紧吗」,紧就递归吃进去。
加运算符 = 加优先级 + 注册两个函数,其余不动——语言长大的成本被压到最低。
求值器的三件套:Object 接口(值)、Env(Get/Set 变量)、 ReturnValue 包装(return 的急停信号)。
没有布尔类型时,真假映射成 1/0、truthiness 规则写在 isTruthy 里。
let x = … 先算右值再绑定;类型不匹配的运算在这里返回 Null 而非报错—— 语言语义是设计出来的,各有取舍。

11. 原文地图¶

主题	原书章	原文位置
造语言的价值	Writing a Programming Language	`text/104-ch10.txt:5`(搜「natural culmination」)
SMALL EBNF 全语法	Defining the syntax of SMALL	`text/105-fm-defining-the-syntax-of-small.txt:21`(搜「Program」)
注释作为 trivia 的处理	Defining the syntax of SMALL	`text/105-fm-defining-the-syntax-of-small.txt:75`(搜「trivia」)
三大组件总览	The lexer	`text/106-fm-the-lexer.txt:2`(搜「key components」)
Token 类型表	The lexer	`text/106-fm-the-lexer.txt:56`(搜「TokenType string」)
readChar/peekChar 机制	The lexer	`text/106-fm-the-lexer.txt:141`(搜「type Lexer struct」) · `:176`(搜「peekChar」)
NextToken 的 lookahead 分支	The lexer	`text/106-fm-the-lexer.txt:196`(搜「NextToken」) · `:264`(搜「skipComment」)
Pratt 解析器原理	The parser	`text/107-fm-the-parser.txt:13`(搜「Pratt parser」) · `:37`(搜「prefix and infix」)
AST 接口三层(Node/Statement/Expression)	The parser	`text/107-fm-the-parser.txt:69`(搜「type Node interface」) · `:99`(搜「Node interface is the base」)
前缀/中缀注册与解析循环	The parser	`text/107-fm-the-parser.txt:151`(搜「NewParser」) · `:285`(搜「parseExpression」)
parseLetStatement 与 expectPeek	The parser	`text/107-fm-the-parser.txt:246`(搜「parseLetStatement」)
if 的双风格语法	The parser	`text/107-fm-the-parser.txt:363`(搜「parseIfExpression」) · `:366`(搜「peekTokenIs(TokenLParen)」) · `:409`(搜「compact and readable」)
Object 系统与 Env	The evaluator	`text/108-fm-the-evaluator.txt:86`(搜「ObjectType」) · `:160`(搜「type Env struct」)
Eval 的 type switch 与 ReturnValue	The evaluator	`text/108-fm-the-evaluator.txt:195`(搜「func Eval」) · `:250`(搜「ReturnValue」)
无布尔的 1/0 比较	The evaluator	`text/108-fm-the-evaluator.txt:389`(搜「Comparisons return 1 or 0」)
运算的三向分派(整数/字符串/Null)	The evaluator	`text/108-fm-the-evaluator.txt:350`(搜「evalInfixExpression」) · `:357`(搜「evalStringInfixExpression」)
absDiff 与 sign 实测	Using SMALL	`text/109-fm-using-small.txt:24`(搜「absDiff.code」) · `:33`(搜「15」) · `text/110-fm-summary.txt:4`(搜「let x = -5」) · `:14`(搜「Negative」)
v1 的缺口清单	Summary	`text/110-fm-summary.txt:33`(搜「lacks fundamental capabilities」)

出处:「Writing a Programming Language」第 3–11 段(text/104-ch10.txt:5,搜「natural culmination」)。「There is no better way to understand core principles such as syntax trees, scope, and evaluation strategies」。 ↩↩
出处:「Why create a new programming language?」(text/104-ch10.txt:23,搜「deepen your understanding」;text/105-fm-defining-the-syntax-of-small.txt:1,搜「regular expressions and SQL」)。 ↩
出处:「Defining the syntax of SMALL」(text/105-fm-defining-the-syntax-of-small.txt:21,搜「Program」)。EBNF 全表见第 21–48 行;优先级分层解读见第 53–57 行。 ↩
出处:「Defining the syntax of SMALL」第 72–77 段(text/105-fm-defining-the-syntax-of-small.txt:75,搜「trivia」)。「comments are treated as trivia and handled entirely by the lexer」。 ↩↩
出处:「Defining the syntax of SMALL」第 69–71 段(text/105-fm-defining-the-syntax-of-small.txt:71,搜「always easy for a computer」)。 ↩
出处:「The lexer」(text/106-fm-the-lexer.txt:141,搜「type Lexer struct」;:152,搜「readChar」)。四字段与到尾置 0 的语义见同段。 ↩
出处:「The lexer」(text/106-fm-the-lexer.txt:196,搜「NextToken」;:202,搜「peekChar() == '='」;:217,搜「TokenIllegal」;:264,搜「skipComment」)。! 无配对即 ILLEGAL 见第 223–224 行。 ↩
出处:「The lexer」(text/106-fm-the-lexer.txt:56,搜「TokenType string」)。20 来个常量的分组见第 57–92 行。 ↩
出处:「The lexer」(text/106-fm-the-lexer.txt:353,搜「readString」;:399,搜「lookupIdent」)。转义引号的处理见第 357–359 行。 ↩
出处:「The parser」第 13–31 段(text/107-fm-the-parser.txt:13,搜「Pratt parser」)。「associates parsing behavior directly with tokens」。 ↩↩
出处:「The parser」(text/107-fm-the-parser.txt:138,搜「prefixParseFn」;:151,搜「NewParser」;:285,搜「parseExpression」)。注册表初始化见第 159–177 行。 ↩
出处:「The parser」(text/107-fm-the-parser.txt:224,搜「parseStatement」)。「simple statement matching on the outside, complex precedence logic on the inside」见第 55–57 行。 ↩
出处:「The parser」第 13–31 段(text/107-fm-the-parser.txt:26,搜「1 + 2 * 3」)。「groups 2 * 3 into a subexpression before combining it with 1」。 ↩
出处:「The parser」(text/107-fm-the-parser.txt:246,搜「parseLetStatement」;:269,搜「expectPeek」)。 ↩
出处:「The evaluator」第 37–61 段(text/108-fm-the-evaluator.txt:40,搜「walking the tree」);Eval 的 type switch 见 :195(搜「func Eval」)。 ↩
出处:「The evaluator」(text/108-fm-the-evaluator.txt:86,搜「ObjectType」;:115,搜「type Integer struct」)。 ↩
出处:「The evaluator」(text/108-fm-the-evaluator.txt:160,搜「type Env struct」;:166,搜「comma OK」)。 ↩
出处:「The evaluator」(text/108-fm-the-evaluator.txt:255,搜「ReturnValue」)。 ↩
出处:「The evaluator」(text/108-fm-the-evaluator.txt:130,搜「isTruthy」;:389,搜「we don't have Booleans」;text/109-fm-using-small.txt:4,搜「nativeBoolToInteger」)。 ↩↩
出处:「The evaluator」(text/108-fm-the-evaluator.txt:350,搜「evalInfixExpression」;:373,搜「returns a &Null{} object」)。 ↩↩
出处:「Using SMALL」(text/109-fm-using-small.txt:24,搜「absDiff.code」;:33,搜「go run ch10/evaluator.go」;:36,搜「25 - 10」)。 ↩
出处:「Using SMALL」(text/110-fm-summary.txt:4,搜「let x = -5」;:14,搜「Negative」;:16,搜「immediate halt」)。 ↩
出处:「The parser」(text/107-fm-the-parser.txt:363,搜「parseIfExpression」;:366,搜「peekTokenIs(TokenLParen)」)。双风格的设计理由见同段「keeping the language compact and readable」。 ↩
出处:「The parser」(text/107-fm-the-parser.txt:69,搜「type Node interface」;:99,搜「Node interface is the base」)。语句与表达式的区分及「每个节点存原始 Token」的说明见第 99–132 行。 ↩