简介一份面向编程语言爱好者的《自制编程语言》学习资料以单个PDF文件打包容量仅2.38MB。内容系统介绍编程语言从设计、实现到使用的完整链路涵盖语法与语义设计、编译器与解释器构造详细讲解yacc/lex、bison/flex等经典工具的使用方法并通过Crowbar、Diksam两个自制语言项目演示如何将理论知识落地。资源内含由简单计算器到完整自制语言的多阶段项目目录覆盖词法分析、语法分析、语义分析与代码生成等关键开发环节同时给出MinGW以及Linux与Windows系统下的编译配置说明。资料虽然只有一份PDF但整体脉络清晰、案例完整适合希望动手实现自定义语言的开发者作为系统性参考。目前这份资源已有869人学习下载适合用于编程语言方向的自学与备课场景。整体内容循序渐进便于按需查阅。1. 为什么值得花一个周末做一门自己的编程语言别再对着编程语言排行榜纠结该学哪一门了。等你亲手把一门语言跑起来再看任何语言的文档都会快很多关键字、作用域、闭包、异常这些概念不再是一堆需要背的术语而是你代码里一个个能打断点、能打印的对象。自制编程语言不是要重造一个 Python而是用几百行代码把“源码怎么变成程序”这条链路走通一遍先切词再组句最后求值。一个能处理变量、算术、if 和函数定义的解释器周末就能写完写完你就能回答那个很多人卡住的问题闭包到底捕获的是什么。这套方案适合三类人后端工程师想弄懂作用域与调用栈前端工程师想给业务写一套可配置的 DSL以及准备面试、想在编译器题目里有点底气的候选人。下面我按自己做过的路线从架构拆到代码再讲到坑。2. 拆出前端和后端树解释器是性价比最高的起点2.1 前端后端怎么分责任很多人第一次动手就卡在一个误区里想一口气把源码变成可执行的东西于是把词法、语法、求值全揉在一个文件里出了错也不知道该看哪一段。我一般会先画一条清晰的分界线把整个解释器拆成三段每一段只做一件事输入输出都是普通的数据结构。阶段输入输出职责词法分析源码字符串Token 列表把字符流切成标识符、数字、字符串、运算符语法分析Token 列表AST抽象语法树按优先级和语法规则组装成树求值AST执行结果按节点类型递归计算维护变量环境前端就是前两段后端就是最后一段。这个拆法的好处是每一段都能独立测试你可以直接喂一段 Token 给解析器或者直接构造一棵 AST 给求值器不用每次从源码跑起。等你想加类型检查或者把解释器换成字节码虚拟机也只动后端前端完全不动。2.2 最小可运行骨架从源码到输出先搭一个能跑的最小骨架再往里面填肉。我习惯把入口单独放一个文件让它只负责调度import sys from lexer import Lexer from parser import Parser from evaluator import Evaluator def run_source(src: str, filename: str stdin) - None: tokens Lexer(src, filename).scan() ast Parser(tokens, filename).parse_program() Evaluator().eval_program(ast) def main() - None: if len(sys.argv) 1: with open(sys.argv[1], encodingutf-8) as f: run_source(f.read(), sys.argv[1]) else: print(chip repl: 输入表达式Ctrl-C 退出) while True: try: line input( ) run_source(line) except KeyboardInterrupt: break except Exception as e: print(f错误: {e}) if __name__ __main__: main()这三个类的构造参数说明一下Lexer 需要源码和文件名文件名只用于报错信息让用户知道是哪一行出了问题Parser 接收 Token 列表也带文件名Evaluator 不接收参数它的状态在执行过程中自己维护。这样设计之后后续所有测试都可以用这一行代码来跑不必单独做一层测试入口。2.3 为什么第一版不要碰字节码我知道很多人一搜自制编程语言就蹦出来“编译成字节码”“虚拟机”“栈机”这些词。但第一版我真的不建议直接上字节码原因是调试成本太高你同时要面对解析器和虚拟机两层问题报错时很难定位是 AST 生成错了还是指令序列排错了。树解释器就没有这个困扰。每个节点对应一个 if 分支你可以在任意节点上打印环境、打印子节点值心智负担小。等树解释器稳定跑通之后再考虑把 AST 编译成字节码这时候前端已经验证过了你只需要单独测试编译器和 VM问题域小一半。我的经验是先让语法和语义正确再谈性能顺序不要反。3. 词法与语法用 Pratt 解析器把源码变成可执行树3.1 手写扫描器Token 表与行号定位词法分析这层我建议手写扫描器不要一上来就引正则库。手写的好处是你能精确控制行号、列号的推进遇到非法字符可以给出“第 3 行第 5 列附近出现无法识别的字符”这种具体信息。正则库做批量切词很快但错误信息很粗糙而且多字符运算符的优先级处理会把你绕晕。先定义 Token 结构和全部类型from typing import NamedTuple class Token(NamedTuple): kind: str # 类型: NUMBER / STRING / IDENT / KEYWORD / OP / EOF text: str # 原始文本 line: int col: int KEYWORDS {let, if, else, fn, return, true, false, and, or, not} # 二元运算符及对应的优先级值越大绑定越紧 PRECEDENCE { or: 1, and: 2, : 3, !: 3, : 4, : 4, : 4, : 4, : 5, -: 5, *: 6, /: 6, %: 6, } # 单字符符号 SINGLE_CHARS set(-*/(){},;!)按这个清单扫描器可以直接线性扫描字符流class Lexer: def __init__(self, src: str, filename: str stdin): self.src src self.filename filename self.i 0 self.line 1 self.col 1 def _peek(self, k: int 0) - str: idx self.i k return self.src[idx] if idx len(self.src) else \0 def _advance(self) - str: c self.src[self.i] self.i 1 if c \n: self.line 1 self.col 1 else: self.col 1 return c def scan(self) - list: tokens [] while self.i len(self.src): c self._peek() if c.isspace(): self._advance() elif c.isdigit() or (c . and self._peek(1).isdigit()): tokens.append(self._read_number()) elif c : tokens.append(self._read_string()) elif c #: # 注释: 直到行尾 while self._peek() not in (\n, \0): self._advance() elif c.isalpha() or c _: tokens.append(self._read_ident()) elif c in SINGLE_CHARS: tokens.append(self._read_op()) else: raise SyntaxError(f{self.filename}:{self.line}:{self.col} 无法识别的字符 {c}) tokens.append(Token(EOF, , self.line, self.col)) return tokens这里的_read_number、_read_string、_read_op是关键单独补充实现def _read_number(self) - Token: start_line, start_col self.line, self.col text while self._peek().isdigit() or self._peek() .: text self._advance() return Token(NUMBER, text, start_line, start_col) def _read_string(self) - Token: start_line, start_col self.line, self.col self._advance() # 跳过开头的双引号 chars [] while self._peek() ! : c self._advance() if c \0: raise SyntaxError(f{self.filename}:{start_line}:{start_col} 字符串没有闭合) if c \\: # 转义序列 n self._advance() mapping {n: \n, t: \t, : , \\: \\} chars.append(mapping.get(n, \\ n)) else: chars.append(c) self._advance() # 跳过结尾的双引号 return Token(STRING, .join(chars), start_line, start_col) def _read_ident(self) - Token: start_line, start_col self.line, self.col text while self._peek().isalnum() or self._peek() _: text self._advance() kind KEYWORD if text in KEYWORDS else IDENT return Token(kind, text, start_line, start_col) def _read_op(self) - Token: start_line, start_col self.line, self.col c self._advance() # 两个字符的运算符: ! if c in (, !, , ) and self._peek() : return Token(OP, c self._advance(), start_line, start_col) if c / and self._peek() /: raise SyntaxError(f{self.filename}:{start_line}:{start_col} 除法注释请使用 #) return Token(OP, c, start_line, start_col)这个扫描器有两个地方容易翻车提前说清楚。第一个是_read_number里对小数点的处理1.2.3会被当成一个数字文本真正报错要留给求值阶段。更好的做法是在这里就用float(text)转换转换失败立刻报语法错误行号还准。第二个是字符串转义\n在源码里是两个字符在 Token 里应该是一个换行符我上面的 mapping 就是干这个的它直接影响后面解析器的行号统计。3.2 Pratt 解析优先级表驱动表达式表达式解析是自制语言最容易写乱的地方。传统的递归下降写法里加减乘除各写一个函数还要互相调用处理结合性加一个新运算符要动好几个函数。Pratt 解析器用一个优先级表加一个循环就把这件事收掉了。核心逻辑是parse_expr(min_bp)先解析一个前缀表达式然后看下一个运算符的优先级是否不低于min_bp不低于就继续吃右边的操作数。class Parser: def __init__(self, tokens: list, filename: str stdin): self.tokens tokens self.pos 0 self.filename filename def _peek(self) - Token: return self.tokens[self.pos] def _advance(self) - Token: t self.tokens[self.pos] if t.kind ! EOF: self.pos 1 return t def parse_expr(self, min_bp: int 0): tok self._advance() if tok.kind NUMBER: lhs {type: Number, value: float(tok.text), line: tok.line} elif tok.kind STRING: lhs {type: String, value: tok.text, line: tok.line} elif tok.text (: lhs self.parse_expr(0) self._expect()) elif tok.text -: rhs self.parse_expr(7) # 7 所有二元优先级, 实现一元负号 lhs {type: Unary, op: -, operand: rhs, line: tok.line} elif tok.text not: rhs self.parse_expr(7) lhs {type: Unary, op: not, operand: rhs, line: tok.line} elif tok.kind IDENT and self._peek().text (: lhs self._parse_call(tok) else: raise SyntaxError(f{self.filename}:{tok.line}:{tok.col} 无法解析的表达式起始 {tok.text}) while True: op_tok self._peek() bp PRECEDENCE.get(op_tok.text, 0) if bp min_bp: break self._advance() rhs self.parse_expr(bp 1) # bp1 保证左结合 lhs {type: Binary, op: op_tok.text, left: lhs, right: rhs, line: op_tok.line} return lhs关键参数就是min_bp和bp 1。bp 1表示右操作数里不允许出现优先级小于等于当前运算符的表达式这样2 * 3 4就会把3 4挡在乘法外面。如果你想要右结合运算符比如赋值、幂运算就把bp 1改成bp让右边可以递归消耗同优先级运算符。这两行就是整门语言的表达式求值顺序所在务必写测试锁住。3.3 语句与块let、if、fn 的语法节点表达式解析完成之后语句层就简单了。每条语句都是以分号或者右大括号结尾的顶层结构我只列出三个核心节点。def parse_stmt(self): tok self._peek() if tok.text let: return self._parse_let() if tok.text if: return self._parse_if() if tok.text fn: return self._parse_fn() if tok.text return: self._advance() expr self.parse_expr(0) if self._peek().text ! ; else None self._expect(;) return {type: Return, value: expr, line: tok.line} expr self.parse_expr(0) self._expect(;) return {type: ExprStmt, expr: expr} def _parse_let(self): tok self._advance() # let name self._expect(IDENT) self._expect() expr self.parse_expr(0) self._expect(;) return {type: Let, name: name.text, expr: expr, line: tok.line} def _parse_if(self): tok self._advance() # if cond self.parse_expr(0) self._expect({) body self._parse_block() else_body None if self._peek().text else: self._advance() if self._peek().text if: else_body [self._parse_if()] # else if 就是嵌套 if else: self._expect({) else_body self._parse_block() return {type: If, cond: cond, then: body, else: else_body, line: tok.line} def _parse_block(self): stmts [] while self._peek().text ! }: if self._peek().kind EOF: raise SyntaxError(f{self.filename}: block 未闭合) stmts.append(self.parse_stmt()) self._advance() # 吃掉 } return stmtselse if的处理我直接递归调用了_parse_if这样链式条件不需要额外节点类型求值器也少写一个分支。块语句返回的是语句列表不是单个节点这个决定会让后面的求值器代码更干净。4. 求值器与闭包环境链就是这门语言的运行模型4.1 环境链变量查找的三条规则语法树造好了剩下的就是让树“活”起来。求值器的核心是一个叫环境的东西。环境就是一张名字到值的映射表外加一个指向父环境的指针。变量查找的规则只有三条先在当前环境找找不到就去父环境找一直找到顶层的全局环境还找不到就报未定义错误。class Env: def __init__(self, parent: Env | None None): self.vars {} self.parent parent def define(self, name: str, value): self.vars[name] value def get(self, name: str, line: int): env self while env is not None: if name in env.vars: return env.vars[name] env env.parent raise NameError(f第 {line} 行: 变量 {name} 未定义) def set(self, name: str, value, line: int): env self while env is not None: if name in env.vars: env.vars[name] value return env env.parent raise NameError(f第 {line} 行: 变量 {name} 未定义)这里有一个设计决策要说清楚set是沿着环境链找已有变量并修改而不是只在当前环境新建。这样做的原因是支持“闭包修改外层变量”。如果你只想做纯函数式语言可以把set改成只在当前环境写入但绝大多数实用语言都允许函数修改外层变量所以按这个实现。4.2 函数调用定义时环境与调用时环境函数闭包是自制语言里最容易写错的地方错就错在调用时不知道该绑哪一个环境。正确的规则是函数对象里保存的是“定义这个函数时所在的环境”调用时新建一个子环境父环境指向保存的定义时环境而不是调用方的环境。class Function: def __init__(self, params: list, body: list, closure: Env, name: str anonymous): self.params params self.body body self.closure closure self.name name def __repr__(self): return ffn {self.name} class ReturnSignal(Exception): def __init__(self, value): self.value value求值器的核心分支如下class Evaluator: def __init__(self): self.global_env Env() self.global_env.define(true, True) self.global_env.define(false, False) def eval_program(self, program: dict) - None: for stmt in program[body]: self.eval_stmt(stmt, self.global_env) def eval_stmt(self, stmt, env: Env): kind stmt[type] if kind Let: value self.eval_expr(stmt[expr], env) env.define(stmt[name], value) elif kind ExprStmt: self.eval_expr(stmt[expr], env) elif kind If: cond self.eval_expr(stmt[cond], env) if cond: self.eval_block(stmt[then], Env(env)) elif stmt[else] is not None: self.eval_block(stmt[else], Env(env)) elif kind Return: value self.eval_expr(stmt[value], env) if stmt[value] else None raise ReturnSignal(value) elif kind Fn: fn Function(stmt[params], stmt[body], env, stmt[name]) env.define(stmt[name], fn) def eval_block(self, stmts: list, env: Env): try: for s in stmts: self.eval_stmt(s, env) except ReturnSignal: raise return env.vars.get(block-value)重点看Fn节点创建函数时直接把当前env传进去当闭包。调用函数的时候新建Env(fn.closure)然后遍历参数赋值def eval_expr(self, node, env: Env): kind node[type] if kind Number: return node[value] if kind String: return node[value] if kind Unary: v self.eval_expr(node[operand], env) return -v if node[op] - else (not v) if kind Binary: left self.eval_expr(node[left], env) if node[op] and: return left and self.eval_expr(node[right], env) if node[op] or: return left or self.eval_expr(node[right], env) right self.eval_expr(node[right], env) return self._apply_binop(node[op], left, right, node[line]) if kind Ident: return env.get(node[name], node[line]) if kind Call: fn self.eval_expr(node[callee], env) args [self.eval_expr(a, env) for a in node[args]] if not isinstance(fn, Function): raise TypeError(f第 {node[line]} 行: 尝试调用非函数 {fn}) call_env Env(fn.closure) for p, a in zip(fn.params, args): call_env.define(p, a) try: self.eval_block(fn.body, call_env) except ReturnSignal as sig: return sig.value return None参数传递有一个隐藏细节实参求值发生在call_env创建之前用的是调用方的环境。这个顺序不能反否则实参里的变量会被误解析成函数内部变量。4.3 短路、返回与错误处理and和or必须短路这一点我在eval_expr里单独处理了先求左值根据左值决定要不要求右值。如果先求右值再判断false and (1 / 0 0)就会直接抛除零错误行为跟所有主流语言都不一样。返回值的实现用了异常这是树解释器里最实用的方案。return语句可能出现在嵌套了好几层的 if 块里如果每层都手动传递返回值标记代码会多出一倍。用ReturnSignal异常的好处是它能一路穿透所有中间层直接到达函数调用点。代价是异常本身的创建有一点开销但第一版解释器根本不需要在意这个。等以后换成字节码再改成指令级别的RETURN才是对的。5. 自制语言避坑5 个最容易翻车的实现细节5.1 左结合被写成右结合1-2-3 算成 1-(2-3)现象1 - 2 - 3求值结果是 2而不是 -4。原因parse_expr里右操作数递归用的参数写成了bp而不是bp 1导致同级运算符被右操作数吃掉了。解决左结合运算符必须用bp 1。我建议一上来就写一个断言测试把1-2-3、8/4/2、2*34这几组固定结果锁进测试里比事后肉眼查快得多。5.2 字符串转义吞掉换行报错行号全乱现象源码第 5 行有一个未闭合字符串报错却指向第 8 行。原因扫描器在处理字符串内容时把\n当成普通字符放进了字符串但源码里的反斜杠加 n 是两字符的转义序列你不应该真的去消费换行。解决字符串扫描里碰到反斜杠先看下一个字符是什么如果是 n、t、双引号或反斜杠就按转义处理其余情况保留原始两字符。同时确保字符串内部的换行如果允许的话也要推进self.line否则越到后面行号越不准。5.3 闭包读到的是循环变量的最终值现象在循环里用fn创建一批函数调用时所有函数返回同一个值。原因函数保存的是闭包环境也就是那个变量的宿主环境循环变量每轮都在同一个环境里被set更新。解决让循环体每次迭代创建一个新的子环境而不是复用当前环境。更常见的方式是把循环变量作为参数传给一个立即执行的包裹函数用参数拷贝切断引用。这个坑在树解释器里尤其隐蔽因为所有函数的闭包指针都指向同一个 Env 对象。5.4 and/or 先求值右操作数除零翻车现象false and (1 / 0 0)没有返回 false反而抛了除零错误。原因求值器先求了左右两个操作数再对布尔值做运算把短路语义丢了。解决在Binary分支里对and和or单独处理左值求完直接判断。顺便提醒一句很多建立在 AST 上的静态检查工具也会遇到同样问题分析器要能识别短路分支否则会报出虚假的除零告警。5.5 递归一深就爆栈现象fact(1000)直接 RecursionError。原因树解释器的每个嵌套调用都对应多层 Python 递归Python 默认递归深度限制在 1000 左右你的语言还没炸Python 先炸了。解决最简单的方式是sys.setrecursionlimit(10000)这只是把天花板抬高不是治本。真正治本的方法是尾调用优化或者把求值器改成显式栈的循环结构但函数调用一旦涉及闭包显式栈的复杂度会上升一个量级。第一版建议设置递归上限并给出清晰报错而不是放任不管。6. 把解释器变成语言验证清单与两条进阶路线6.1 用快照测试锁住行为自制语言最大的风险是改了语法分析旧行为悄悄变化。我一般会写一个极小测试助手把解释器的输出重定向到字符串再断言import io import contextlib from chip import run_source def run(code: str) - str: buf io.StringIO() with contextlib.redirect_stdout(buf): run_source(code, test) return buf.getvalue() def test_factorial(): out run( fn fact(n) { if n 0 { return 1; } return n * fact(n-1); } print(fact(5)); ) assert out.strip() 120 def test_left_assoc(): out run(print(1 - 2 - 3);) assert out.strip() -4测试用例先写简单的字面量和算术再写变量与作用域最后才写闭包。每加一个特性先写一个失败测试再实现比写完再补测试省太多时间。6.2 下一步类型检查与字节码 VM 怎么选树解释器稳定之后两条路摆在面前。想做类型系统就在语法分析和求值之间插一层类型检查器遍历 AST 给每个节点标上类型这一步能拦住大多数运行时错误。想做性能就把 AST 编译成字节码写一个栈机执行字节码。我的建议是先做类型检查再做 VM因为类型检查器会逼你把语义彻底想清楚而 VM 只是换一种执行方式不会暴露语义漏洞。深度学习场景里的规则引擎和嵌入式脚本语言基本都是这条路语义正确之后再考虑执行效率。6.3 什么时候值得继续投入如果你只是验证自己对编译原理的理解做到树解释器加几十个测试就足够了。如果你想把它变成团队可用的 DSL至少还要补三件事标准库、错误堆栈、文档。我觉得做这事的最大收获不是“我写了个语言”而是以后再看到别人的语法设计能一眼看出哪里会踩坑哪里是妥协。等你把闭包、短路、环境链这些细节都亲手实现过一遍再去读任何一门语言的官方文档都会有“原来这里是这样”的熟悉感。第一版我最后悔的是没先写测试就加闭包结果环境链共享的问题排查了一下午那个下午本来应该用来跑通斐波那契的。希望你从第一步就把测试垫在脚下希望帮到你。本文还有配套的精品资源点击获取
花一个周末亲手实现一门解释器：从词法分析到闭包
简介一份面向编程语言爱好者的《自制编程语言》学习资料以单个PDF文件打包容量仅2.38MB。内容系统介绍编程语言从设计、实现到使用的完整链路涵盖语法与语义设计、编译器与解释器构造详细讲解yacc/lex、bison/flex等经典工具的使用方法并通过Crowbar、Diksam两个自制语言项目演示如何将理论知识落地。资源内含由简单计算器到完整自制语言的多阶段项目目录覆盖词法分析、语法分析、语义分析与代码生成等关键开发环节同时给出MinGW以及Linux与Windows系统下的编译配置说明。资料虽然只有一份PDF但整体脉络清晰、案例完整适合希望动手实现自定义语言的开发者作为系统性参考。目前这份资源已有869人学习下载适合用于编程语言方向的自学与备课场景。整体内容循序渐进便于按需查阅。1. 为什么值得花一个周末做一门自己的编程语言别再对着编程语言排行榜纠结该学哪一门了。等你亲手把一门语言跑起来再看任何语言的文档都会快很多关键字、作用域、闭包、异常这些概念不再是一堆需要背的术语而是你代码里一个个能打断点、能打印的对象。自制编程语言不是要重造一个 Python而是用几百行代码把“源码怎么变成程序”这条链路走通一遍先切词再组句最后求值。一个能处理变量、算术、if 和函数定义的解释器周末就能写完写完你就能回答那个很多人卡住的问题闭包到底捕获的是什么。这套方案适合三类人后端工程师想弄懂作用域与调用栈前端工程师想给业务写一套可配置的 DSL以及准备面试、想在编译器题目里有点底气的候选人。下面我按自己做过的路线从架构拆到代码再讲到坑。2. 拆出前端和后端树解释器是性价比最高的起点2.1 前端后端怎么分责任很多人第一次动手就卡在一个误区里想一口气把源码变成可执行的东西于是把词法、语法、求值全揉在一个文件里出了错也不知道该看哪一段。我一般会先画一条清晰的分界线把整个解释器拆成三段每一段只做一件事输入输出都是普通的数据结构。阶段输入输出职责词法分析源码字符串Token 列表把字符流切成标识符、数字、字符串、运算符语法分析Token 列表AST抽象语法树按优先级和语法规则组装成树求值AST执行结果按节点类型递归计算维护变量环境前端就是前两段后端就是最后一段。这个拆法的好处是每一段都能独立测试你可以直接喂一段 Token 给解析器或者直接构造一棵 AST 给求值器不用每次从源码跑起。等你想加类型检查或者把解释器换成字节码虚拟机也只动后端前端完全不动。2.2 最小可运行骨架从源码到输出先搭一个能跑的最小骨架再往里面填肉。我习惯把入口单独放一个文件让它只负责调度import sys from lexer import Lexer from parser import Parser from evaluator import Evaluator def run_source(src: str, filename: str stdin) - None: tokens Lexer(src, filename).scan() ast Parser(tokens, filename).parse_program() Evaluator().eval_program(ast) def main() - None: if len(sys.argv) 1: with open(sys.argv[1], encodingutf-8) as f: run_source(f.read(), sys.argv[1]) else: print(chip repl: 输入表达式Ctrl-C 退出) while True: try: line input( ) run_source(line) except KeyboardInterrupt: break except Exception as e: print(f错误: {e}) if __name__ __main__: main()这三个类的构造参数说明一下Lexer 需要源码和文件名文件名只用于报错信息让用户知道是哪一行出了问题Parser 接收 Token 列表也带文件名Evaluator 不接收参数它的状态在执行过程中自己维护。这样设计之后后续所有测试都可以用这一行代码来跑不必单独做一层测试入口。2.3 为什么第一版不要碰字节码我知道很多人一搜自制编程语言就蹦出来“编译成字节码”“虚拟机”“栈机”这些词。但第一版我真的不建议直接上字节码原因是调试成本太高你同时要面对解析器和虚拟机两层问题报错时很难定位是 AST 生成错了还是指令序列排错了。树解释器就没有这个困扰。每个节点对应一个 if 分支你可以在任意节点上打印环境、打印子节点值心智负担小。等树解释器稳定跑通之后再考虑把 AST 编译成字节码这时候前端已经验证过了你只需要单独测试编译器和 VM问题域小一半。我的经验是先让语法和语义正确再谈性能顺序不要反。3. 词法与语法用 Pratt 解析器把源码变成可执行树3.1 手写扫描器Token 表与行号定位词法分析这层我建议手写扫描器不要一上来就引正则库。手写的好处是你能精确控制行号、列号的推进遇到非法字符可以给出“第 3 行第 5 列附近出现无法识别的字符”这种具体信息。正则库做批量切词很快但错误信息很粗糙而且多字符运算符的优先级处理会把你绕晕。先定义 Token 结构和全部类型from typing import NamedTuple class Token(NamedTuple): kind: str # 类型: NUMBER / STRING / IDENT / KEYWORD / OP / EOF text: str # 原始文本 line: int col: int KEYWORDS {let, if, else, fn, return, true, false, and, or, not} # 二元运算符及对应的优先级值越大绑定越紧 PRECEDENCE { or: 1, and: 2, : 3, !: 3, : 4, : 4, : 4, : 4, : 5, -: 5, *: 6, /: 6, %: 6, } # 单字符符号 SINGLE_CHARS set(-*/(){},;!)按这个清单扫描器可以直接线性扫描字符流class Lexer: def __init__(self, src: str, filename: str stdin): self.src src self.filename filename self.i 0 self.line 1 self.col 1 def _peek(self, k: int 0) - str: idx self.i k return self.src[idx] if idx len(self.src) else \0 def _advance(self) - str: c self.src[self.i] self.i 1 if c \n: self.line 1 self.col 1 else: self.col 1 return c def scan(self) - list: tokens [] while self.i len(self.src): c self._peek() if c.isspace(): self._advance() elif c.isdigit() or (c . and self._peek(1).isdigit()): tokens.append(self._read_number()) elif c : tokens.append(self._read_string()) elif c #: # 注释: 直到行尾 while self._peek() not in (\n, \0): self._advance() elif c.isalpha() or c _: tokens.append(self._read_ident()) elif c in SINGLE_CHARS: tokens.append(self._read_op()) else: raise SyntaxError(f{self.filename}:{self.line}:{self.col} 无法识别的字符 {c}) tokens.append(Token(EOF, , self.line, self.col)) return tokens这里的_read_number、_read_string、_read_op是关键单独补充实现def _read_number(self) - Token: start_line, start_col self.line, self.col text while self._peek().isdigit() or self._peek() .: text self._advance() return Token(NUMBER, text, start_line, start_col) def _read_string(self) - Token: start_line, start_col self.line, self.col self._advance() # 跳过开头的双引号 chars [] while self._peek() ! : c self._advance() if c \0: raise SyntaxError(f{self.filename}:{start_line}:{start_col} 字符串没有闭合) if c \\: # 转义序列 n self._advance() mapping {n: \n, t: \t, : , \\: \\} chars.append(mapping.get(n, \\ n)) else: chars.append(c) self._advance() # 跳过结尾的双引号 return Token(STRING, .join(chars), start_line, start_col) def _read_ident(self) - Token: start_line, start_col self.line, self.col text while self._peek().isalnum() or self._peek() _: text self._advance() kind KEYWORD if text in KEYWORDS else IDENT return Token(kind, text, start_line, start_col) def _read_op(self) - Token: start_line, start_col self.line, self.col c self._advance() # 两个字符的运算符: ! if c in (, !, , ) and self._peek() : return Token(OP, c self._advance(), start_line, start_col) if c / and self._peek() /: raise SyntaxError(f{self.filename}:{start_line}:{start_col} 除法注释请使用 #) return Token(OP, c, start_line, start_col)这个扫描器有两个地方容易翻车提前说清楚。第一个是_read_number里对小数点的处理1.2.3会被当成一个数字文本真正报错要留给求值阶段。更好的做法是在这里就用float(text)转换转换失败立刻报语法错误行号还准。第二个是字符串转义\n在源码里是两个字符在 Token 里应该是一个换行符我上面的 mapping 就是干这个的它直接影响后面解析器的行号统计。3.2 Pratt 解析优先级表驱动表达式表达式解析是自制语言最容易写乱的地方。传统的递归下降写法里加减乘除各写一个函数还要互相调用处理结合性加一个新运算符要动好几个函数。Pratt 解析器用一个优先级表加一个循环就把这件事收掉了。核心逻辑是parse_expr(min_bp)先解析一个前缀表达式然后看下一个运算符的优先级是否不低于min_bp不低于就继续吃右边的操作数。class Parser: def __init__(self, tokens: list, filename: str stdin): self.tokens tokens self.pos 0 self.filename filename def _peek(self) - Token: return self.tokens[self.pos] def _advance(self) - Token: t self.tokens[self.pos] if t.kind ! EOF: self.pos 1 return t def parse_expr(self, min_bp: int 0): tok self._advance() if tok.kind NUMBER: lhs {type: Number, value: float(tok.text), line: tok.line} elif tok.kind STRING: lhs {type: String, value: tok.text, line: tok.line} elif tok.text (: lhs self.parse_expr(0) self._expect()) elif tok.text -: rhs self.parse_expr(7) # 7 所有二元优先级, 实现一元负号 lhs {type: Unary, op: -, operand: rhs, line: tok.line} elif tok.text not: rhs self.parse_expr(7) lhs {type: Unary, op: not, operand: rhs, line: tok.line} elif tok.kind IDENT and self._peek().text (: lhs self._parse_call(tok) else: raise SyntaxError(f{self.filename}:{tok.line}:{tok.col} 无法解析的表达式起始 {tok.text}) while True: op_tok self._peek() bp PRECEDENCE.get(op_tok.text, 0) if bp min_bp: break self._advance() rhs self.parse_expr(bp 1) # bp1 保证左结合 lhs {type: Binary, op: op_tok.text, left: lhs, right: rhs, line: op_tok.line} return lhs关键参数就是min_bp和bp 1。bp 1表示右操作数里不允许出现优先级小于等于当前运算符的表达式这样2 * 3 4就会把3 4挡在乘法外面。如果你想要右结合运算符比如赋值、幂运算就把bp 1改成bp让右边可以递归消耗同优先级运算符。这两行就是整门语言的表达式求值顺序所在务必写测试锁住。3.3 语句与块let、if、fn 的语法节点表达式解析完成之后语句层就简单了。每条语句都是以分号或者右大括号结尾的顶层结构我只列出三个核心节点。def parse_stmt(self): tok self._peek() if tok.text let: return self._parse_let() if tok.text if: return self._parse_if() if tok.text fn: return self._parse_fn() if tok.text return: self._advance() expr self.parse_expr(0) if self._peek().text ! ; else None self._expect(;) return {type: Return, value: expr, line: tok.line} expr self.parse_expr(0) self._expect(;) return {type: ExprStmt, expr: expr} def _parse_let(self): tok self._advance() # let name self._expect(IDENT) self._expect() expr self.parse_expr(0) self._expect(;) return {type: Let, name: name.text, expr: expr, line: tok.line} def _parse_if(self): tok self._advance() # if cond self.parse_expr(0) self._expect({) body self._parse_block() else_body None if self._peek().text else: self._advance() if self._peek().text if: else_body [self._parse_if()] # else if 就是嵌套 if else: self._expect({) else_body self._parse_block() return {type: If, cond: cond, then: body, else: else_body, line: tok.line} def _parse_block(self): stmts [] while self._peek().text ! }: if self._peek().kind EOF: raise SyntaxError(f{self.filename}: block 未闭合) stmts.append(self.parse_stmt()) self._advance() # 吃掉 } return stmtselse if的处理我直接递归调用了_parse_if这样链式条件不需要额外节点类型求值器也少写一个分支。块语句返回的是语句列表不是单个节点这个决定会让后面的求值器代码更干净。4. 求值器与闭包环境链就是这门语言的运行模型4.1 环境链变量查找的三条规则语法树造好了剩下的就是让树“活”起来。求值器的核心是一个叫环境的东西。环境就是一张名字到值的映射表外加一个指向父环境的指针。变量查找的规则只有三条先在当前环境找找不到就去父环境找一直找到顶层的全局环境还找不到就报未定义错误。class Env: def __init__(self, parent: Env | None None): self.vars {} self.parent parent def define(self, name: str, value): self.vars[name] value def get(self, name: str, line: int): env self while env is not None: if name in env.vars: return env.vars[name] env env.parent raise NameError(f第 {line} 行: 变量 {name} 未定义) def set(self, name: str, value, line: int): env self while env is not None: if name in env.vars: env.vars[name] value return env env.parent raise NameError(f第 {line} 行: 变量 {name} 未定义)这里有一个设计决策要说清楚set是沿着环境链找已有变量并修改而不是只在当前环境新建。这样做的原因是支持“闭包修改外层变量”。如果你只想做纯函数式语言可以把set改成只在当前环境写入但绝大多数实用语言都允许函数修改外层变量所以按这个实现。4.2 函数调用定义时环境与调用时环境函数闭包是自制语言里最容易写错的地方错就错在调用时不知道该绑哪一个环境。正确的规则是函数对象里保存的是“定义这个函数时所在的环境”调用时新建一个子环境父环境指向保存的定义时环境而不是调用方的环境。class Function: def __init__(self, params: list, body: list, closure: Env, name: str anonymous): self.params params self.body body self.closure closure self.name name def __repr__(self): return ffn {self.name} class ReturnSignal(Exception): def __init__(self, value): self.value value求值器的核心分支如下class Evaluator: def __init__(self): self.global_env Env() self.global_env.define(true, True) self.global_env.define(false, False) def eval_program(self, program: dict) - None: for stmt in program[body]: self.eval_stmt(stmt, self.global_env) def eval_stmt(self, stmt, env: Env): kind stmt[type] if kind Let: value self.eval_expr(stmt[expr], env) env.define(stmt[name], value) elif kind ExprStmt: self.eval_expr(stmt[expr], env) elif kind If: cond self.eval_expr(stmt[cond], env) if cond: self.eval_block(stmt[then], Env(env)) elif stmt[else] is not None: self.eval_block(stmt[else], Env(env)) elif kind Return: value self.eval_expr(stmt[value], env) if stmt[value] else None raise ReturnSignal(value) elif kind Fn: fn Function(stmt[params], stmt[body], env, stmt[name]) env.define(stmt[name], fn) def eval_block(self, stmts: list, env: Env): try: for s in stmts: self.eval_stmt(s, env) except ReturnSignal: raise return env.vars.get(block-value)重点看Fn节点创建函数时直接把当前env传进去当闭包。调用函数的时候新建Env(fn.closure)然后遍历参数赋值def eval_expr(self, node, env: Env): kind node[type] if kind Number: return node[value] if kind String: return node[value] if kind Unary: v self.eval_expr(node[operand], env) return -v if node[op] - else (not v) if kind Binary: left self.eval_expr(node[left], env) if node[op] and: return left and self.eval_expr(node[right], env) if node[op] or: return left or self.eval_expr(node[right], env) right self.eval_expr(node[right], env) return self._apply_binop(node[op], left, right, node[line]) if kind Ident: return env.get(node[name], node[line]) if kind Call: fn self.eval_expr(node[callee], env) args [self.eval_expr(a, env) for a in node[args]] if not isinstance(fn, Function): raise TypeError(f第 {node[line]} 行: 尝试调用非函数 {fn}) call_env Env(fn.closure) for p, a in zip(fn.params, args): call_env.define(p, a) try: self.eval_block(fn.body, call_env) except ReturnSignal as sig: return sig.value return None参数传递有一个隐藏细节实参求值发生在call_env创建之前用的是调用方的环境。这个顺序不能反否则实参里的变量会被误解析成函数内部变量。4.3 短路、返回与错误处理and和or必须短路这一点我在eval_expr里单独处理了先求左值根据左值决定要不要求右值。如果先求右值再判断false and (1 / 0 0)就会直接抛除零错误行为跟所有主流语言都不一样。返回值的实现用了异常这是树解释器里最实用的方案。return语句可能出现在嵌套了好几层的 if 块里如果每层都手动传递返回值标记代码会多出一倍。用ReturnSignal异常的好处是它能一路穿透所有中间层直接到达函数调用点。代价是异常本身的创建有一点开销但第一版解释器根本不需要在意这个。等以后换成字节码再改成指令级别的RETURN才是对的。5. 自制语言避坑5 个最容易翻车的实现细节5.1 左结合被写成右结合1-2-3 算成 1-(2-3)现象1 - 2 - 3求值结果是 2而不是 -4。原因parse_expr里右操作数递归用的参数写成了bp而不是bp 1导致同级运算符被右操作数吃掉了。解决左结合运算符必须用bp 1。我建议一上来就写一个断言测试把1-2-3、8/4/2、2*34这几组固定结果锁进测试里比事后肉眼查快得多。5.2 字符串转义吞掉换行报错行号全乱现象源码第 5 行有一个未闭合字符串报错却指向第 8 行。原因扫描器在处理字符串内容时把\n当成普通字符放进了字符串但源码里的反斜杠加 n 是两字符的转义序列你不应该真的去消费换行。解决字符串扫描里碰到反斜杠先看下一个字符是什么如果是 n、t、双引号或反斜杠就按转义处理其余情况保留原始两字符。同时确保字符串内部的换行如果允许的话也要推进self.line否则越到后面行号越不准。5.3 闭包读到的是循环变量的最终值现象在循环里用fn创建一批函数调用时所有函数返回同一个值。原因函数保存的是闭包环境也就是那个变量的宿主环境循环变量每轮都在同一个环境里被set更新。解决让循环体每次迭代创建一个新的子环境而不是复用当前环境。更常见的方式是把循环变量作为参数传给一个立即执行的包裹函数用参数拷贝切断引用。这个坑在树解释器里尤其隐蔽因为所有函数的闭包指针都指向同一个 Env 对象。5.4 and/or 先求值右操作数除零翻车现象false and (1 / 0 0)没有返回 false反而抛了除零错误。原因求值器先求了左右两个操作数再对布尔值做运算把短路语义丢了。解决在Binary分支里对and和or单独处理左值求完直接判断。顺便提醒一句很多建立在 AST 上的静态检查工具也会遇到同样问题分析器要能识别短路分支否则会报出虚假的除零告警。5.5 递归一深就爆栈现象fact(1000)直接 RecursionError。原因树解释器的每个嵌套调用都对应多层 Python 递归Python 默认递归深度限制在 1000 左右你的语言还没炸Python 先炸了。解决最简单的方式是sys.setrecursionlimit(10000)这只是把天花板抬高不是治本。真正治本的方法是尾调用优化或者把求值器改成显式栈的循环结构但函数调用一旦涉及闭包显式栈的复杂度会上升一个量级。第一版建议设置递归上限并给出清晰报错而不是放任不管。6. 把解释器变成语言验证清单与两条进阶路线6.1 用快照测试锁住行为自制语言最大的风险是改了语法分析旧行为悄悄变化。我一般会写一个极小测试助手把解释器的输出重定向到字符串再断言import io import contextlib from chip import run_source def run(code: str) - str: buf io.StringIO() with contextlib.redirect_stdout(buf): run_source(code, test) return buf.getvalue() def test_factorial(): out run( fn fact(n) { if n 0 { return 1; } return n * fact(n-1); } print(fact(5)); ) assert out.strip() 120 def test_left_assoc(): out run(print(1 - 2 - 3);) assert out.strip() -4测试用例先写简单的字面量和算术再写变量与作用域最后才写闭包。每加一个特性先写一个失败测试再实现比写完再补测试省太多时间。6.2 下一步类型检查与字节码 VM 怎么选树解释器稳定之后两条路摆在面前。想做类型系统就在语法分析和求值之间插一层类型检查器遍历 AST 给每个节点标上类型这一步能拦住大多数运行时错误。想做性能就把 AST 编译成字节码写一个栈机执行字节码。我的建议是先做类型检查再做 VM因为类型检查器会逼你把语义彻底想清楚而 VM 只是换一种执行方式不会暴露语义漏洞。深度学习场景里的规则引擎和嵌入式脚本语言基本都是这条路语义正确之后再考虑执行效率。6.3 什么时候值得继续投入如果你只是验证自己对编译原理的理解做到树解释器加几十个测试就足够了。如果你想把它变成团队可用的 DSL至少还要补三件事标准库、错误堆栈、文档。我觉得做这事的最大收获不是“我写了个语言”而是以后再看到别人的语法设计能一眼看出哪里会踩坑哪里是妥协。等你把闭包、短路、环境链这些细节都亲手实现过一遍再去读任何一门语言的官方文档都会有“原来这里是这样”的熟悉感。第一版我最后悔的是没先写测试就加闭包结果环境链共享的问题排查了一下午那个下午本来应该用来跑通斐波那契的。希望你从第一步就把测试垫在脚下希望帮到你。本文还有配套的精品资源点击获取
