简介这是一份面向编程语言学习者与初学者的自制编程语言专题文档文件格式为PDF容量约2.38MB。文档系统讲解编程语言的设计、实现与使用覆盖语法与语义的设计原则并借助yacc/lex、bison/flex等经典工具演示词法分析器与解析器的生成过程。内容以Crowbar和Diksam两款示例语言为主线从简易计算器逐步演进到完整语言实现清晰展示语法分析、抽象语法树、虚拟机和垃圾回收等核心概念同时补充Windows下MinGW、Cygwin及Linux下make等环境配置要点便于读者边读边动手验证。整份资料共1个PDF文件目前已有869人学习适合希望亲手实现一门小型编程语言、或对编译原理感兴趣的中初级开发者作为入门参考。1. 自制编程语言别被“编译器”三个字吓退先想清楚要做哪一种一提到自制编程语言多数人第一反应是“那是编译器专家干的事”。但真实世界的出发点没那么宏大有人想在业务里嵌入一个规则引擎有人给自己的小游戏写脚本系统也有人只是受够了读理论书时满眼的符号想亲手把一个能跑的最小解释器从零写出来把黑匣子变成自己注释过的代码。这个方向能解决的问题只有一个——真正搞懂一门语言从前端到运行时到底发生了什么。适合三种人想用明白 Lua 这类嵌入式脚本的开发者、需要给项目做 DSL 的工程师、以及不想永远只会调用别人接口的从业者。这篇按“前端→运行时→踩坑→资料”的顺序讲目标是让你读完后能照着把最小语言跑通。2. 先定语言边界再写前端词法分析与语法分析的落地主线自制编程语言最容易翻车的地方不在后面的运行时而在开头。很多人拿到资料就急着写代码写出来的 lexer 和 parser 满屏 if改一个运算符要动三个地方。我一般会先用半页纸定清楚这门语言长什么样支持哪几种字面量、有哪些中缀运算符、有没有变量声明、函数是不是一等公民。这套边界决定了前端采用什么策略也决定了后面 AST 怎么建模。前端这条路拆开就三步把源码切成 Token 流把 Token 流按文法组织成树再把树建模成方便遍历的节点结构。三步各有一条主线串起来就是一个能解析表达式、变量和函数定义的前端。2.1 词法分析先把源码切成 Token 流再谈语法词法分析这段常见做法是手写一个 tokenizer输入字符串输出带类型的 Token 列表。不要在词法阶段做任何语法判断也不要把注释跳过和字符串转义塞进同一个分支。下面是一个最小词法分析器的核心循环用 Python 写目标语言只支持数字、变量名和加减乘除。class Token: def __init__(self, kind, text, valueNone): self.kind kind # TokenType 枚举NUMBER / IDENT / PLUS / MINUS ... self.text text # 原始文本报错时用于回显 self.value value # 数字类型的实际数值语法分析阶段直接取用 def tokenize(src: str) - list[Token]: tokens [] i 0 n len(src) while i n: ch src[i] if ch.isspace(): i 1 continue if ch.isdigit(): start i while i n and (src[i].isdigit() or src[i] .): i 1 text src[start:i] tokens.append(Token(TokenType.NUMBER, text, float(text))) continue if ch.isalpha() or ch _: start i while i n and (src[i].isalnum() or src[i] _): i 1 tokens.append(Token(TokenType.IDENT, src[start:i], None)) continue if ch : tokens.append(Token(TokenType.PLUS, , None)) i 1 continue if ch -: tokens.append(Token(TokenType.MINUS, -, None)) i 1 continue raise SyntaxError(f无法识别的字符 {ch!r} at index {i}) tokens.append(Token(TokenType.EOF, , None)) return tokens这段代码有三个参数值得说。第一数字扫描里加了小数点的支持但1.2.3这种输入会被整个扫进来正确做法是留在语法分析阶段报错不要在词法层做语义判断。第二每个 Token 都保留text原始文本和行号列号后续报错信息才能直接指出“第几行第几列长什么样”。第三一条输入结束后必须人为追加 EOF Token否则 parser 会在读空列表时反复判断边界代码里到处都是if index len(tokens)难看且易错。词法分析做到这一步就够了不要在这里处理2 3 * 4的优先级那是语法层的事。词法阶段最常见的误用是拿一长串正则去匹配所有 token 种类。正则适合做原型但自制语言迭代很快今天加一个明天加一个字符串插值每加一个特性就要改一遍正则的交替顺序优先级错一个字符就全盘错。我一般只把正则用于数字和标识符的初筛控制流全部用if/else手写看起来啰嗦改起来半小时以内能收工。2.2 语法分析递归下降加一张优先级表是默认解语法分析是前端真正的硬骨头。自制语言的 parser 默认解是递归下降加优先级表递归下降负责语句结构和括号优先级表只处理中缀表达式。原因是它跟语法定义一一对应报错时能直接说“在解析哪个非终结符时挂掉”比生成器生成的表驱动 parser 好调试得多。下面是最小表达式解析器用 Pratt 解析处理优先级。class Parser: def __init__(self, tokens: list[Token]): self.tokens tokens self.pos 0 self.prec { TokenType.OR: 1, TokenType.AND: 2, TokenType.EQ: 3, TokenType.NEQ: 3, TokenType.LT: 4, TokenType.GT: 4, TokenType.PLUS: 5, TokenType.MINUS: 5, TokenType.MUL: 6, TokenType.DIV: 6, } def parse_expression(self): return self.parse_binary(0) def parse_binary(self, min_prec): left self.parse_primary() while True: cur self.peek() prec self.prec.get(cur.kind, -1) if prec min_prec: break self.advance() right self.parse_binary(prec 1) left BinaryExpr(cur.kind, left, right) return left def parse_primary(self): tk self.advance() if tk.kind TokenType.NUMBER: return NumberExpr(tk.value) if tk.kind TokenType.IDENT: return VarExpr(tk.text) raise SyntaxError(f意外的 token {tk.kind})优先级表里最关键的是右递归的parse_binary(prec 1)这一步。以1 2 * 3为例外层解析时优先级 5右操作数用parse_binary(6)进入*优先级 6 不小于 6于是先吃掉2 * 3结果正确。反过来如果改成prec而不是prec 1和*会全部变成右结合1 2 3被解析成1 (2 3)行为就错了。左结合运算符必须让递归深度加一。另一个小参数是self.prec.get(cur.kind, -1)里的-1它保证未登记优先级的 token 一律不参加二元运算直接跳出循环交给上层处理。写完 parser 后我习惯先打印 AST不要省这一步。后面求值器跑出错误结果时你要先区分是“解析错”还是“求值错”AST dump 是区分二者的唯一手段。调试信息要从第一天就配好等语言规模大了再补成本会线性上升。2.3 AST 设计节点类型宁可多一层不要省那一次遍历AST 设计是前端最容易偷懒又最影响后期的地方。常见错误是只建 Number、Binary、Variable 三种节点后面加 if、while、函数调用时全堆到 Binary 节点里靠一个 type 字段区分。一两个特性还能撑等闭包和面向对象进来那个节点变成改一次崩三处。我的习惯是每种语法结构一个节点类哪怕它只有两个字段。下面是一个最小语言所需的节点清单节点类型字段用途NumberExprvalue数字字面量VarExprname变量引用BinaryExprop, left, right中缀运算AssignExprname, value变量赋值IfExprcond, then_branch, else_branch条件分支FuncExprparams, body函数字面量CallExprcallee, args函数调用这张表够写一个带函数和条件分支的脚本语言。等要支持面向对象时再往上加 MemberExpr 和 MethodExpr每个节点只负责自己的规则。另一个实用原则是所有节点实现一个accept(visitor)方法后面做 AST 打印、优化和编译时不会因为到处isinstance而崩掉。前端到这里收口后面所有逻辑都建立在这棵树上。3. 运行时选型树遍历、字节码还是直接翻译定位决定答案前端做完接下来是运行时。很多人在这里又踩进一个误区一上来就追求字节码虚拟机觉得那样才“专业”。实际上自制语言阶段运行时选型应该取决于语言最终要跑在哪里脚本解释器用树遍历足够需要性能再上字节码想编译成原生码那是另一个量级的工程。这章先把三条路线的取舍讲清楚再给出一条能跑通的最小求值器实现最后补上字节码路线的关键参数方便你判断下一步往哪走。3.1 三条路线怎么选跟语言定位走别跟风树遍历是理解成本最低的方案parser 产出 AST 后求值器直接递归遍历节点每个节点对应一段求值逻辑。它的优点是实现快、报错准缺点是每条表达式都要走一遍节点分发性能慢一个量级。但自制语言阶段代码规模通常在千行以内这点性能损耗完全可以接受。字节码 VM 是第二档先把 AST 编译成扁平的指令序列再在一个循环里逐个 dispatch。它的性能比树遍历好但需要同时维护操作码表、常量池、操作数栈、调用帧四块结构复杂度是线性上升的。直接翻译成 C 或其他中间表示则是最重的一条路要处理内存管理和平台 ABI不适合第一版。我一般建议第一版走树遍历跑通全链路后再根据性能报告决定要不要引入字节码。判断标准很简单你的语言是不是要作为正式脚本嵌入到生产环境里如果是直接上字节码如果只是工具链或教学项目树遍历够你玩半年。自制语言的第一个版本最怕的不是慢而是做不出来。3.2 最小求值器AST 节点、环境字典与作用域链树遍历求值器的核心就两个东西节点类型分发的求值函数和一个环境字典。环境字典负责变量名到值的映射同时挂一个 parent 指针形成作用域链。下面是基于 2.3 节点清单写的最小求值器。class Env: def __init__(self, parentNone): self.store {} self.parent parent def get(self, name): if name in self.store: return self.store[name] if self.parent is not None: return self.parent.get(name) raise NameError(f未定义变量 {name}) def set(self, name, value): self.store[name] value def eval_node(node, env): if isinstance(node, NumberExpr): return node.value if isinstance(node, VarExpr): return env.get(node.name) if isinstance(node, BinaryExpr): left eval_node(node.left, env) right eval_node(node.right, env) if node.op TokenType.PLUS: return left right if node.op TokenType.MINUS: return left - right if node.op TokenType.MUL: return left * right if node.op TokenType.DIV: return left / right raise TypeError(f未知运算符 {node.op}) if isinstance(node, AssignExpr): value eval_node(node.value, env) # set 只写当前层不向上查找这是 let 语义 env.set(node.name, value) return value raise TypeError(f无法对 {type(node)} 求值)这里的 Env.get 沿 parent 链向上查找Env.set 只写当前层这一对行为正好对应脚本语言里“读变量看作用域链声明变量只属于当前层”的惯例。很多自制语言在这里会搞错赋值时也用 get 向上找导致内层函数给外层变量赋值的行为不可控。如果你想要的就是这种效果那不是 Env.set 的问题而是风格问题但一定要在文档里写明。第二个细节是 BinaryExpr 求值先递归子节点再运算运算前不做类型检查。一旦传入字符串和数字做加法Python 会抛 TypeError 直接中断这个行为要留到后面做类型系统时统一处理现阶段不要塞进求值器。3.3 字节码路线的关键参数操作码表、常量池与调用帧如果决定上字节码有三个参数要提前定死。一是操作码表它决定指令编码方式。常见做法是一字节操作码加可变长操作数操作数指向常量池索引或跳转目标。二是常量池所有数字、字符串和函数对象的字面量都收进常量池编译期只是把常量池索引写进指令流运行期不再持有原始 AST 节点。三是调用帧每个函数调用压一个帧帧里保存返回地址、局部变量区、操作数栈基址。下面是一张最小指令表操作码操作数含义PUSH_CONST常量池索引把常量压栈LOAD_VAR变量名读变量压栈STORE_VAR变量名弹栈写入当前帧局部区ADD无弹出两个数求和压回JMP_IF_FALSE跳转目标弹栈为假则跳转CALL参数个数按参数个数取实参调用函数RET无弹出返回值还原调用帧字节码 VM 的第一个坑是操作数栈大小。递归很深的程序会直接撑爆操作数栈多数自制语言在这里选择静态定长栈比如 65536 个槽位栈溢出时报“调用过深”。第二个坑是 CALL 指令的帧布局调用前要把实参压栈进入函数后实参正好是局部变量区的前 N 个槽位这样函数体里的 LOAD_VAR 就不用区分参数和局部变量了。第三个坑是异常处理一旦运行期抛错VM 要能沿着调用帧链逐层清理栈同时保留出错时机和调用链。这三块是字节码路线最容易反复返工的地方。4. 自制语言避坑记录5 个常见问题与排查思路这章写的是我做过自制语言后沉淀下来的踩坑记录。问题都很典型现象、原因、解决三条线拆开每一个都能省你两三天查错时间。前两条来自词法和 AST 的隐蔽共享状态中间一条来自递归深度最后两条来自环境语义和对象模型没定清楚。4.1 同样的表达式两次求值结果不一致现象解析同一个表达式两次第一次结果正确第二次结果错乱甚至报出“未定义变量”。原因Token 对象或 AST 节点在解析时被复用了第二次解析时某个字段被原地修改。最常见的是数字 Token 的 value 字段被求值器改写或变量名节点被当成共享缓存。解决Token 和 AST 节点一律不可变。解析阶段只负责创建节点求值阶段只读节点字段如果要做优化复制一份再改写绝不在原节点上打补丁。排查技巧是写一个assert校验遍历完整 AST 后重新打印一次字段值与初始 dump 比对。4.2 闭包捕获的变量全指向最后一个值现象循环里创建多个函数每个函数捕获循环变量结果所有函数拿到的都是循环结束后的终值。原因所有函数闭包共享了同一个 Env 对象循环变量在这个 Env 里被反复覆盖。这是脚本语言实现里最经典的坑本质是“捕获环境”的粒度错了。解决每次循环迭代新建一个 Env 帧把循环变量存进新建帧函数创建时捕获当前环境引用而不是全局环境。在实现上for循环的求值代码里要有loop_env Env(env)这一步再把迭代变量写进 loop_env。这一条不修好后面的生成器、迭代器全部会跟着错。4.3 递归太深直接栈溢出现象写一个fib(30)就崩报错信息是宿主语言的 RecursionError 或线段错误。原因求值器本身的递归嵌套与宿主语言的调用栈叠加了。每个 AST 节点递归调用一次 eval_node就多占一层宿主栈语言层递归 500 层宿主层可能已经上千层。解决治标是调宿主语言的递归限制但我不建议这么做它会掩盖问题。真正的解有两个方向一是给语法分析阶段加“最大嵌套深度”限制比如 256 层超限报编译错误二是把求值器的递归模式改成显式栈驱动的循环这是往字节码 VM 迁移的必经一步。如果你只是做树遍历版本先限深度别硬扛。4.4 Token 报错位置对不上源码行号现象运行期报“第 3 行变量未定义”但源码第 3 行根本不是那个变量。原因Token 在词法阶段记录了行号列号但 parser 构造 AST 节点时没有把位置信息透传过去运行期报错拿的是某个默认值或上一次解析残留的值。解决Token 里带line和columnAST 节点的基类里也放line和columnparser 创建节点时从当前 Token 拷贝。这个信息还在后续类型检查、报 warning、生成调试信息时反复用到前端阶段一次性加好比后面补要便宜得多。报错信息里带上源码片段能大幅提高排查效率尤其是表达式嵌套很深的时候。4.5 变量是按值传还是按引用传行为随写法飘忽现象把列表传给函数函数里改了列表内容外层居然也变了但传数字时又没变。原因对象模型没有定清楚。脚本语言里常见的做法是“值类型按值、对象类型按引用”但很多自制语言在实现 Env 时把所有变量都存成 Python 引用导致数字不可变所以像按值列表可变所以像按引用用户写起来行为不一致。解决语言规范里明确写一句“所有对象均按引用传递赋值仅复制引用”然后在实现层面统一变量管理不区分类型所有值都装箱成 Value 对象。等以后做 GC 时这个统一装箱正好是第一步。这一条不解决你的语言会不断收到“为什么这个函数会改我的数据”的 bug 反馈。5. 资料怎么读《自制编程语言》相关资料从通读到动手的拆解标题里的“相关资料”落到实际操作上其实就是三件事找一本脉络完整的书通读找一份能跟着敲遍的代码仓库再按需找专项资料补漏。资料太多的时候最怕的不是没得读而是读了一堆碎片串不起来。我的建议是不要同时开三本以上的书以一本为主线其他只做索引。5.1 第一梯队先啃通一本脉络完整的书《自制编程语言》这类书通常按“词法→语法→运行时→实战语言”的顺序组织主线读一本就够。读的时候要带着上一章的小目标去读你要做一个带函数的脚本语言那就先把“函数调用和调用栈”这几章当作地图前面的表达式和语句章节可以快速带过。通读阶段只做两件事画一张语言特性清单标出哪些是你需要的把书中提到的运行时策略单独记一页笔记比如树遍历、字节码、栈帧布局后面选型时对照着看。此时不要急着把每个代码示例都敲一遍先建立全貌再动手。5.2 第二梯队跟着敲代码关键是敲完能跑通读之后必须进入跟敲阶段。此时不要改词法分析器的细节按原样敲一遍能跑通的最小版本哪怕你知道某个地方可以写得更好。为什么因为自制语言的认知难点不是单个语法而是模块与模块之间怎么对接——tokenizer 输出什么格式、parser 期望什么输入、AST 节点字段如何传递。跟敲一遍能让你摸清这些接口协议比抄一百个高深算法都有用。敲完最小版本后再回头做两件事给优先级表加一个%运算符给表达式加一个一元负号。这两个小改动能检验你是不是真的理解了 parser 的递归路径。如果改起来顺畅说明这套前端已经变成你的了。5.3 第三梯队专项资料按需查别整本整本地读遇到问题是最高效的学习入口。闭包捕获不对就去查“lexical scoping 闭包实现”递归栈溢出就去查“树遍历求值器显式栈”想做 GC再去查“标记清除与引用计数”。这些专项资料不建议整本读读对应章节即可。用表格整理一下三梯队的分工梯队资料形态阅读方式目标第一梯队整本书通读一遍记特性清单建立全貌第二梯队配套代码或最小解释器项目原样跟敲再改两个小功能理解模块接口第三梯队专项文章或文档按问题查章节解决具体坑如果你是第一次做自制语言按这个顺序走资料利用率会比“收藏一大堆链接然后从第一篇开始啃”高得多。第 5 章的定位是把资料变成路径而不是变成收藏夹。6. 用最小 REPL 收口跑通主干的验证方法与调试习惯整条链路跑没跑通最有说服力的验证是一个最小 REPL读一行、解析、求值、打印结果。下面这个循环只用前面各章代码就能拼起来。def repl(): env Env() while True: try: line input( ) if not line.strip(): continue tokens tokenize(line) ast Parser(tokens).parse_expression() result eval_node(ast, env) print(repr(result)) except (SyntaxError, NameError, TypeError) as e: print(f错误: {e}) if __name__ __main__: repl()REPL 里要重点验证三组用例优先级是否正确变量是否跨行保持函数的定义与调用是否连续生效。每组用例我都吃过亏优先级错了表现为1 2 * 3输出 9 而不是 7变量跨行失效表现为第一行x 1成功第二行x 1报未定义函数问题表现为定义时正常调用时却找不到环境。每跑通一组就给 REPL 加一条测试样例后面改代码翻车时它能帮你快速定位哪一段链路坏了。我自己养成的习惯是每改完一次解析器或求值器先把这组样例敲一遍再写新特性。这比写几十行测试用例更直接。自制语言这条路不复杂复杂的是模块太多、每个模块又都不难导致你总想跳步。按最小链路慢慢推有一天你会突然发现自己已经能看着报错信息定位是哪一层的问题了。希望帮到你。本文还有配套的精品资源点击获取
简介这是一份面向编程语言学习者与初学者的自制编程语言专题文档文件格式为PDF容量约2.38MB。文档系统讲解编程语言的设计、实现与使用覆盖语法与语义的设计原则并借助yacc/lex、bison/flex等经典工具演示词法分析器与解析器的生成过程。内容以Crowbar和Diksam两款示例语言为主线从简易计算器逐步演进到完整语言实现清晰展示语法分析、抽象语法树、虚拟机和垃圾回收等核心概念同时补充Windows下MinGW、Cygwin及Linux下make等环境配置要点便于读者边读边动手验证。整份资料共1个PDF文件目前已有869人学习适合希望亲手实现一门小型编程语言、或对编译原理感兴趣的中初级开发者作为入门参考。1. 自制编程语言别被“编译器”三个字吓退先想清楚要做哪一种一提到自制编程语言多数人第一反应是“那是编译器专家干的事”。但真实世界的出发点没那么宏大有人想在业务里嵌入一个规则引擎有人给自己的小游戏写脚本系统也有人只是受够了读理论书时满眼的符号想亲手把一个能跑的最小解释器从零写出来把黑匣子变成自己注释过的代码。这个方向能解决的问题只有一个——真正搞懂一门语言从前端到运行时到底发生了什么。适合三种人想用明白 Lua 这类嵌入式脚本的开发者、需要给项目做 DSL 的工程师、以及不想永远只会调用别人接口的从业者。这篇按“前端→运行时→踩坑→资料”的顺序讲目标是让你读完后能照着把最小语言跑通。2. 先定语言边界再写前端词法分析与语法分析的落地主线自制编程语言最容易翻车的地方不在后面的运行时而在开头。很多人拿到资料就急着写代码写出来的 lexer 和 parser 满屏 if改一个运算符要动三个地方。我一般会先用半页纸定清楚这门语言长什么样支持哪几种字面量、有哪些中缀运算符、有没有变量声明、函数是不是一等公民。这套边界决定了前端采用什么策略也决定了后面 AST 怎么建模。前端这条路拆开就三步把源码切成 Token 流把 Token 流按文法组织成树再把树建模成方便遍历的节点结构。三步各有一条主线串起来就是一个能解析表达式、变量和函数定义的前端。2.1 词法分析先把源码切成 Token 流再谈语法词法分析这段常见做法是手写一个 tokenizer输入字符串输出带类型的 Token 列表。不要在词法阶段做任何语法判断也不要把注释跳过和字符串转义塞进同一个分支。下面是一个最小词法分析器的核心循环用 Python 写目标语言只支持数字、变量名和加减乘除。class Token: def __init__(self, kind, text, valueNone): self.kind kind # TokenType 枚举NUMBER / IDENT / PLUS / MINUS ... self.text text # 原始文本报错时用于回显 self.value value # 数字类型的实际数值语法分析阶段直接取用 def tokenize(src: str) - list[Token]: tokens [] i 0 n len(src) while i n: ch src[i] if ch.isspace(): i 1 continue if ch.isdigit(): start i while i n and (src[i].isdigit() or src[i] .): i 1 text src[start:i] tokens.append(Token(TokenType.NUMBER, text, float(text))) continue if ch.isalpha() or ch _: start i while i n and (src[i].isalnum() or src[i] _): i 1 tokens.append(Token(TokenType.IDENT, src[start:i], None)) continue if ch : tokens.append(Token(TokenType.PLUS, , None)) i 1 continue if ch -: tokens.append(Token(TokenType.MINUS, -, None)) i 1 continue raise SyntaxError(f无法识别的字符 {ch!r} at index {i}) tokens.append(Token(TokenType.EOF, , None)) return tokens这段代码有三个参数值得说。第一数字扫描里加了小数点的支持但1.2.3这种输入会被整个扫进来正确做法是留在语法分析阶段报错不要在词法层做语义判断。第二每个 Token 都保留text原始文本和行号列号后续报错信息才能直接指出“第几行第几列长什么样”。第三一条输入结束后必须人为追加 EOF Token否则 parser 会在读空列表时反复判断边界代码里到处都是if index len(tokens)难看且易错。词法分析做到这一步就够了不要在这里处理2 3 * 4的优先级那是语法层的事。词法阶段最常见的误用是拿一长串正则去匹配所有 token 种类。正则适合做原型但自制语言迭代很快今天加一个明天加一个字符串插值每加一个特性就要改一遍正则的交替顺序优先级错一个字符就全盘错。我一般只把正则用于数字和标识符的初筛控制流全部用if/else手写看起来啰嗦改起来半小时以内能收工。2.2 语法分析递归下降加一张优先级表是默认解语法分析是前端真正的硬骨头。自制语言的 parser 默认解是递归下降加优先级表递归下降负责语句结构和括号优先级表只处理中缀表达式。原因是它跟语法定义一一对应报错时能直接说“在解析哪个非终结符时挂掉”比生成器生成的表驱动 parser 好调试得多。下面是最小表达式解析器用 Pratt 解析处理优先级。class Parser: def __init__(self, tokens: list[Token]): self.tokens tokens self.pos 0 self.prec { TokenType.OR: 1, TokenType.AND: 2, TokenType.EQ: 3, TokenType.NEQ: 3, TokenType.LT: 4, TokenType.GT: 4, TokenType.PLUS: 5, TokenType.MINUS: 5, TokenType.MUL: 6, TokenType.DIV: 6, } def parse_expression(self): return self.parse_binary(0) def parse_binary(self, min_prec): left self.parse_primary() while True: cur self.peek() prec self.prec.get(cur.kind, -1) if prec min_prec: break self.advance() right self.parse_binary(prec 1) left BinaryExpr(cur.kind, left, right) return left def parse_primary(self): tk self.advance() if tk.kind TokenType.NUMBER: return NumberExpr(tk.value) if tk.kind TokenType.IDENT: return VarExpr(tk.text) raise SyntaxError(f意外的 token {tk.kind})优先级表里最关键的是右递归的parse_binary(prec 1)这一步。以1 2 * 3为例外层解析时优先级 5右操作数用parse_binary(6)进入*优先级 6 不小于 6于是先吃掉2 * 3结果正确。反过来如果改成prec而不是prec 1和*会全部变成右结合1 2 3被解析成1 (2 3)行为就错了。左结合运算符必须让递归深度加一。另一个小参数是self.prec.get(cur.kind, -1)里的-1它保证未登记优先级的 token 一律不参加二元运算直接跳出循环交给上层处理。写完 parser 后我习惯先打印 AST不要省这一步。后面求值器跑出错误结果时你要先区分是“解析错”还是“求值错”AST dump 是区分二者的唯一手段。调试信息要从第一天就配好等语言规模大了再补成本会线性上升。2.3 AST 设计节点类型宁可多一层不要省那一次遍历AST 设计是前端最容易偷懒又最影响后期的地方。常见错误是只建 Number、Binary、Variable 三种节点后面加 if、while、函数调用时全堆到 Binary 节点里靠一个 type 字段区分。一两个特性还能撑等闭包和面向对象进来那个节点变成改一次崩三处。我的习惯是每种语法结构一个节点类哪怕它只有两个字段。下面是一个最小语言所需的节点清单节点类型字段用途NumberExprvalue数字字面量VarExprname变量引用BinaryExprop, left, right中缀运算AssignExprname, value变量赋值IfExprcond, then_branch, else_branch条件分支FuncExprparams, body函数字面量CallExprcallee, args函数调用这张表够写一个带函数和条件分支的脚本语言。等要支持面向对象时再往上加 MemberExpr 和 MethodExpr每个节点只负责自己的规则。另一个实用原则是所有节点实现一个accept(visitor)方法后面做 AST 打印、优化和编译时不会因为到处isinstance而崩掉。前端到这里收口后面所有逻辑都建立在这棵树上。3. 运行时选型树遍历、字节码还是直接翻译定位决定答案前端做完接下来是运行时。很多人在这里又踩进一个误区一上来就追求字节码虚拟机觉得那样才“专业”。实际上自制语言阶段运行时选型应该取决于语言最终要跑在哪里脚本解释器用树遍历足够需要性能再上字节码想编译成原生码那是另一个量级的工程。这章先把三条路线的取舍讲清楚再给出一条能跑通的最小求值器实现最后补上字节码路线的关键参数方便你判断下一步往哪走。3.1 三条路线怎么选跟语言定位走别跟风树遍历是理解成本最低的方案parser 产出 AST 后求值器直接递归遍历节点每个节点对应一段求值逻辑。它的优点是实现快、报错准缺点是每条表达式都要走一遍节点分发性能慢一个量级。但自制语言阶段代码规模通常在千行以内这点性能损耗完全可以接受。字节码 VM 是第二档先把 AST 编译成扁平的指令序列再在一个循环里逐个 dispatch。它的性能比树遍历好但需要同时维护操作码表、常量池、操作数栈、调用帧四块结构复杂度是线性上升的。直接翻译成 C 或其他中间表示则是最重的一条路要处理内存管理和平台 ABI不适合第一版。我一般建议第一版走树遍历跑通全链路后再根据性能报告决定要不要引入字节码。判断标准很简单你的语言是不是要作为正式脚本嵌入到生产环境里如果是直接上字节码如果只是工具链或教学项目树遍历够你玩半年。自制语言的第一个版本最怕的不是慢而是做不出来。3.2 最小求值器AST 节点、环境字典与作用域链树遍历求值器的核心就两个东西节点类型分发的求值函数和一个环境字典。环境字典负责变量名到值的映射同时挂一个 parent 指针形成作用域链。下面是基于 2.3 节点清单写的最小求值器。class Env: def __init__(self, parentNone): self.store {} self.parent parent def get(self, name): if name in self.store: return self.store[name] if self.parent is not None: return self.parent.get(name) raise NameError(f未定义变量 {name}) def set(self, name, value): self.store[name] value def eval_node(node, env): if isinstance(node, NumberExpr): return node.value if isinstance(node, VarExpr): return env.get(node.name) if isinstance(node, BinaryExpr): left eval_node(node.left, env) right eval_node(node.right, env) if node.op TokenType.PLUS: return left right if node.op TokenType.MINUS: return left - right if node.op TokenType.MUL: return left * right if node.op TokenType.DIV: return left / right raise TypeError(f未知运算符 {node.op}) if isinstance(node, AssignExpr): value eval_node(node.value, env) # set 只写当前层不向上查找这是 let 语义 env.set(node.name, value) return value raise TypeError(f无法对 {type(node)} 求值)这里的 Env.get 沿 parent 链向上查找Env.set 只写当前层这一对行为正好对应脚本语言里“读变量看作用域链声明变量只属于当前层”的惯例。很多自制语言在这里会搞错赋值时也用 get 向上找导致内层函数给外层变量赋值的行为不可控。如果你想要的就是这种效果那不是 Env.set 的问题而是风格问题但一定要在文档里写明。第二个细节是 BinaryExpr 求值先递归子节点再运算运算前不做类型检查。一旦传入字符串和数字做加法Python 会抛 TypeError 直接中断这个行为要留到后面做类型系统时统一处理现阶段不要塞进求值器。3.3 字节码路线的关键参数操作码表、常量池与调用帧如果决定上字节码有三个参数要提前定死。一是操作码表它决定指令编码方式。常见做法是一字节操作码加可变长操作数操作数指向常量池索引或跳转目标。二是常量池所有数字、字符串和函数对象的字面量都收进常量池编译期只是把常量池索引写进指令流运行期不再持有原始 AST 节点。三是调用帧每个函数调用压一个帧帧里保存返回地址、局部变量区、操作数栈基址。下面是一张最小指令表操作码操作数含义PUSH_CONST常量池索引把常量压栈LOAD_VAR变量名读变量压栈STORE_VAR变量名弹栈写入当前帧局部区ADD无弹出两个数求和压回JMP_IF_FALSE跳转目标弹栈为假则跳转CALL参数个数按参数个数取实参调用函数RET无弹出返回值还原调用帧字节码 VM 的第一个坑是操作数栈大小。递归很深的程序会直接撑爆操作数栈多数自制语言在这里选择静态定长栈比如 65536 个槽位栈溢出时报“调用过深”。第二个坑是 CALL 指令的帧布局调用前要把实参压栈进入函数后实参正好是局部变量区的前 N 个槽位这样函数体里的 LOAD_VAR 就不用区分参数和局部变量了。第三个坑是异常处理一旦运行期抛错VM 要能沿着调用帧链逐层清理栈同时保留出错时机和调用链。这三块是字节码路线最容易反复返工的地方。4. 自制语言避坑记录5 个常见问题与排查思路这章写的是我做过自制语言后沉淀下来的踩坑记录。问题都很典型现象、原因、解决三条线拆开每一个都能省你两三天查错时间。前两条来自词法和 AST 的隐蔽共享状态中间一条来自递归深度最后两条来自环境语义和对象模型没定清楚。4.1 同样的表达式两次求值结果不一致现象解析同一个表达式两次第一次结果正确第二次结果错乱甚至报出“未定义变量”。原因Token 对象或 AST 节点在解析时被复用了第二次解析时某个字段被原地修改。最常见的是数字 Token 的 value 字段被求值器改写或变量名节点被当成共享缓存。解决Token 和 AST 节点一律不可变。解析阶段只负责创建节点求值阶段只读节点字段如果要做优化复制一份再改写绝不在原节点上打补丁。排查技巧是写一个assert校验遍历完整 AST 后重新打印一次字段值与初始 dump 比对。4.2 闭包捕获的变量全指向最后一个值现象循环里创建多个函数每个函数捕获循环变量结果所有函数拿到的都是循环结束后的终值。原因所有函数闭包共享了同一个 Env 对象循环变量在这个 Env 里被反复覆盖。这是脚本语言实现里最经典的坑本质是“捕获环境”的粒度错了。解决每次循环迭代新建一个 Env 帧把循环变量存进新建帧函数创建时捕获当前环境引用而不是全局环境。在实现上for循环的求值代码里要有loop_env Env(env)这一步再把迭代变量写进 loop_env。这一条不修好后面的生成器、迭代器全部会跟着错。4.3 递归太深直接栈溢出现象写一个fib(30)就崩报错信息是宿主语言的 RecursionError 或线段错误。原因求值器本身的递归嵌套与宿主语言的调用栈叠加了。每个 AST 节点递归调用一次 eval_node就多占一层宿主栈语言层递归 500 层宿主层可能已经上千层。解决治标是调宿主语言的递归限制但我不建议这么做它会掩盖问题。真正的解有两个方向一是给语法分析阶段加“最大嵌套深度”限制比如 256 层超限报编译错误二是把求值器的递归模式改成显式栈驱动的循环这是往字节码 VM 迁移的必经一步。如果你只是做树遍历版本先限深度别硬扛。4.4 Token 报错位置对不上源码行号现象运行期报“第 3 行变量未定义”但源码第 3 行根本不是那个变量。原因Token 在词法阶段记录了行号列号但 parser 构造 AST 节点时没有把位置信息透传过去运行期报错拿的是某个默认值或上一次解析残留的值。解决Token 里带line和columnAST 节点的基类里也放line和columnparser 创建节点时从当前 Token 拷贝。这个信息还在后续类型检查、报 warning、生成调试信息时反复用到前端阶段一次性加好比后面补要便宜得多。报错信息里带上源码片段能大幅提高排查效率尤其是表达式嵌套很深的时候。4.5 变量是按值传还是按引用传行为随写法飘忽现象把列表传给函数函数里改了列表内容外层居然也变了但传数字时又没变。原因对象模型没有定清楚。脚本语言里常见的做法是“值类型按值、对象类型按引用”但很多自制语言在实现 Env 时把所有变量都存成 Python 引用导致数字不可变所以像按值列表可变所以像按引用用户写起来行为不一致。解决语言规范里明确写一句“所有对象均按引用传递赋值仅复制引用”然后在实现层面统一变量管理不区分类型所有值都装箱成 Value 对象。等以后做 GC 时这个统一装箱正好是第一步。这一条不解决你的语言会不断收到“为什么这个函数会改我的数据”的 bug 反馈。5. 资料怎么读《自制编程语言》相关资料从通读到动手的拆解标题里的“相关资料”落到实际操作上其实就是三件事找一本脉络完整的书通读找一份能跟着敲遍的代码仓库再按需找专项资料补漏。资料太多的时候最怕的不是没得读而是读了一堆碎片串不起来。我的建议是不要同时开三本以上的书以一本为主线其他只做索引。5.1 第一梯队先啃通一本脉络完整的书《自制编程语言》这类书通常按“词法→语法→运行时→实战语言”的顺序组织主线读一本就够。读的时候要带着上一章的小目标去读你要做一个带函数的脚本语言那就先把“函数调用和调用栈”这几章当作地图前面的表达式和语句章节可以快速带过。通读阶段只做两件事画一张语言特性清单标出哪些是你需要的把书中提到的运行时策略单独记一页笔记比如树遍历、字节码、栈帧布局后面选型时对照着看。此时不要急着把每个代码示例都敲一遍先建立全貌再动手。5.2 第二梯队跟着敲代码关键是敲完能跑通读之后必须进入跟敲阶段。此时不要改词法分析器的细节按原样敲一遍能跑通的最小版本哪怕你知道某个地方可以写得更好。为什么因为自制语言的认知难点不是单个语法而是模块与模块之间怎么对接——tokenizer 输出什么格式、parser 期望什么输入、AST 节点字段如何传递。跟敲一遍能让你摸清这些接口协议比抄一百个高深算法都有用。敲完最小版本后再回头做两件事给优先级表加一个%运算符给表达式加一个一元负号。这两个小改动能检验你是不是真的理解了 parser 的递归路径。如果改起来顺畅说明这套前端已经变成你的了。5.3 第三梯队专项资料按需查别整本整本地读遇到问题是最高效的学习入口。闭包捕获不对就去查“lexical scoping 闭包实现”递归栈溢出就去查“树遍历求值器显式栈”想做 GC再去查“标记清除与引用计数”。这些专项资料不建议整本读读对应章节即可。用表格整理一下三梯队的分工梯队资料形态阅读方式目标第一梯队整本书通读一遍记特性清单建立全貌第二梯队配套代码或最小解释器项目原样跟敲再改两个小功能理解模块接口第三梯队专项文章或文档按问题查章节解决具体坑如果你是第一次做自制语言按这个顺序走资料利用率会比“收藏一大堆链接然后从第一篇开始啃”高得多。第 5 章的定位是把资料变成路径而不是变成收藏夹。6. 用最小 REPL 收口跑通主干的验证方法与调试习惯整条链路跑没跑通最有说服力的验证是一个最小 REPL读一行、解析、求值、打印结果。下面这个循环只用前面各章代码就能拼起来。def repl(): env Env() while True: try: line input( ) if not line.strip(): continue tokens tokenize(line) ast Parser(tokens).parse_expression() result eval_node(ast, env) print(repr(result)) except (SyntaxError, NameError, TypeError) as e: print(f错误: {e}) if __name__ __main__: repl()REPL 里要重点验证三组用例优先级是否正确变量是否跨行保持函数的定义与调用是否连续生效。每组用例我都吃过亏优先级错了表现为1 2 * 3输出 9 而不是 7变量跨行失效表现为第一行x 1成功第二行x 1报未定义函数问题表现为定义时正常调用时却找不到环境。每跑通一组就给 REPL 加一条测试样例后面改代码翻车时它能帮你快速定位哪一段链路坏了。我自己养成的习惯是每改完一次解析器或求值器先把这组样例敲一遍再写新特性。这比写几十行测试用例更直接。自制语言这条路不复杂复杂的是模块太多、每个模块又都不难导致你总想跳步。按最小链路慢慢推有一天你会突然发现自己已经能看着报错信息定位是哪一层的问题了。希望帮到你。本文还有配套的精品资源点击获取
