★ FEATURED ARTICLE 简介《自制编程语言》PDF资料面向对编译原理与语言实现感兴趣的开发者、学生帮助读者理解从零设计并实现一门编程语言的完整路径。文档系统梳理了语言设计、实现与使用三大层面涵盖设计原则、编译器与解释器选型、运行时与资源管理等关键主题也给出迪米特法则、单一职责原则等设计准则的落地参考。资源包体为一个PDF文件总大小仅2.38MB便于下载与离线阅读。目前已有869人浏览学习内容实用性获一定认可。PDF以Crowbar和Diksam两款自制语言为主线展示了结合yacc/lex、bison/flex以及MinGW工具链进行词法分析、语法分析、解释器与编译器构建的全过程并覆盖Linux与Windows两种环境下的开发配置与make用法。语言版本从基础计算器逐步演进到带垃圾回收等特性的完整实现目录分层清晰可帮助读者循序渐进地掌握自制编程语言的落地方法是一份兼顾理论与实操的参考资料。1. 自制编程语言到底教什么先把整条技术链路立起来很多人翻开这本《自制编程语言》的第一章看完词法分析、语法树的概念觉得全懂了合上书却写不出一行能跑的代码。这套资料的真正价值不在概念讲解而在于它逼着读者从头到尾亲手做一个能执行自己语法的解释器或编译器。本文想说的就是围绕这套资料的学习路径从词法分析、语法分析、AST 求值一路推进最后让自制的语言真正跑起来。适合读这篇的人不是想看科普的旁观者而是学过基础编程、对解释器和编译器背后的机制有具体好奇、或者想给自己项目做一套 DSL 的从业者。整个过程偏动手资料里给的源码是参考不是答案。跟着走一遍之后你会理解一门语言从字符串到结果的完整链路也知道哪些环节最容易翻车。2. 先立概念框架词法分析、语法树与三条实现路线的选型2.1 自制语言的完整链路从源码到结果要跨过几道门槛先把整条技术链路拆开。不管你要做的是脚本解释器还是编译型语言源码从字符串变成可执行结果至少要经过几个阶段字符流先被切成 tokentoken 序列被组织成语法树语法树要么直接求值要么继续编译成低级指令再执行。词法分析是第一步它把12 34 * (56 - 78)这样的原始文本拆成一串有类型的 token数字、运算符、括号、标识符。这一步的产出是线性列表不关心这些符号之间的结构关系。很多人在这阶段犯的典型错误是想在词法里顺便处理语法问题比如在扫描时判断括号是否匹配结果代码越写越乱错误定位也变得模糊。语法分析是第二步它消费 token 流按照文法规则构建抽象语法树AST。AST 是树状结构节点对应操作符、字面量、变量引用。树的结构天然表达了运算的先后关系比如乘除节点是加减节点的子节点优先级就体现在树的层次里。这块是自制语言最核心的部分也是绝大多数初学者卡住的地方。最后一步是求值或代码生成。树遍历解释器直接递归遍历 AST 算出结果字节码虚拟机先把 AST 编译成指令数组再在一个循环里逐条执行编译到机器码则要把 AST 转成目标平台的汇编。你选择哪条路线决定了后续所有工作量。2.2 三条实现路线怎么选树遍历、字节码、直接编译资料里通常会给出一条主路线但在动手前先想清楚三者的差别会对后面章节的理解有很大帮助。我一般会建议第一次做的人选择树遍历解释器因为它需要的额外概念最少。维度树遍历解释器字节码虚拟机直接编译到机器码新增概念几乎为零操作数栈、指令分派循环寄存器分配、调用约定、链接调试难度低直接打印 AST 就能定位中需要观察指令流高段错误排查成本大执行性能最慢递归开销大中等适合生产级脚本语言最快适合场景教学、DSL 原型验证生产级脚本语言、游戏脚本系统级编译器的最终目标选树遍历解释器的理由不是因为它最好而是因为它能让你在最短时间内把整条链路走通。AST 求值器的核心逻辑很少一个evaluate函数递归处理节点即可。等这条路走顺了再往字节码方向演进你会发现很多在树遍历阶段理解的概念比如作用域、函数调用栈在虚拟机里只是换了一种表达形式。直接编译到机器码是这三条路线里最重的涉及指令选择、寄存器分配、ABI 约定资料里如果涉及也多半是作为扩展阅读。不建议作为第一条路线否则你会被底层细节淹没失去对整体结构的把握。2.3 先写一个 tokenizer 热身最小可运行示例与两个边界坑动手第一步是写词法分析器。这里给一个极简版本只处理整数和四则运算用 Python 实现。# token 类型用常量避免在 parser 里手写字符串比较时拼错 TOKEN_NUMBER NUMBER TOKEN_PLUS PLUS TOKEN_MINUS MINUS TOKEN_MUL MUL TOKEN_DIV DIV TOKEN_LPAREN LPAREN TOKEN_RPAREN RPAREN TOKEN_EOF EOF def tokenize(code: str): tokens [] i 0 n len(code) while i n: ch code[i] if ch.isspace(): i 1 continue if ch.isdigit(): # 用 j 作为第二个指针贪婪读取完整数字 j i while j n and code[j].isdigit(): j 1 tokens.append((TOKEN_NUMBER, int(code[i:j]))) i j continue if ch : tokens.append((TOKEN_PLUS, ch)) elif ch -: tokens.append((TOKEN_MINUS, ch)) elif ch *: tokens.append((TOKEN_MUL, ch)) elif ch /: tokens.append((TOKEN_DIV, ch)) elif ch (: tokens.append((TOKEN_LPAREN, ch)) elif ch ): tokens.append((TOKEN_RPAREN, ch)) else: # 遇到未知字符直接报错跳过会让错误延迟到 parser 阶段才暴露 raise SyntaxError(f无法识别的字符: {ch!r}位置: {i}) i 1 tokens.append((TOKEN_EOF, None)) return tokens if __name__ __main__: print(tokenize(12 34 * (56 - 78)))这段代码的逻辑是单指针扫描i表示当前读到的位置。遇到空白就跳过遇到数字用j从i开始连续读取直到不是数字为止然后整体切出来转成整数。这里用j而不是直接修改i是为了让主循环的游标只在确定消费了 token 后才前进避免索引交错出错。两个边界坑值得单独说。第一个是数字的贪婪匹配12必须整体读成一个 token而不是先读1再读2否则 parser 拿到12两个数字节点会直接爆炸。第二个是未知字符的处理我见过有些实现选择忽略未知字符这会让12 # 34这种输入静静变成12 34错误在语法分析阶段以莫名其妙的方式暴露。直接在词法阶段抛异常报错位置还能精确到字符偏移排错成本低很多。3. 动手跑通最小解释器递归下降解析与 AST 求值3.1 代码骨架怎么搭tokenizer、parser、evaluator 三层的边界真正开始写解释器之前先把三层结构的职责边界划清楚。tokenizer 负责把源码字符串变成 token 列表它不关心 token 之间的组合关系parser 负责消费 token 列表构建 ASTevaluator 负责遍历 AST 并计算结果。三层之间的接口要干净。parser 只依赖 token 列表不直接接触源码字符串AST 里的节点用元组或对象表示不混入 token 类型信息。我见过不少半途放弃的代码问题都出在层与层之间互相渗透parser 里嵌 tokenizer 的逻辑或者 evaluator 里临时去扫描 token。看起来少写了几行代码后续想加一个变量功能时改动面会一下铺到所有文件。AST 的数据结构决定了整个解释器的可读性。用元组是最省事的比如(num, 12)表示数字(add, left, right)表示加法节点。元组不可变打印出来也直观调试时print(ast)就能看到整棵树的嵌套结构。如果要支持更多节点类型再改成类也不迟一开始不必上重量级方案。3.2 用递归下降写 parser优先级是靠函数嵌套实现的递归下降是理解成本最低的语法分析方式它的核心思想是每个文法规则对应一个函数函数之间互相调用调用层级就是优先级层级。先看代码。from tokenize_util import tokenize # 用上一节的 tokenizer class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): # 只看当前 token不消费 return self.tokens[self.pos] def next_token(self): # 消费当前 token游标后移 tok self.tokens[self.pos] self.pos 1 return tok def parse_expression(self): # 加减法优先级最低所以放在最外层 left self.parse_term() while self.peek()[0] in (PLUS, MINUS): op self.next_token()[0] right self.parse_term() left (op.lower(), left, right) return left def parse_term(self): # 乘除法比加减法优先级高往下一层 left self.parse_factor() while self.peek()[0] in (MUL, DIV): op self.next_token()[0] right self.parse_factor() left (op.lower(), left, right) return left def parse_factor(self): # 最底层数字或括号表达式 tok self.next_token() if tok[0] NUMBER: return (num, tok[1]) if tok[0] LPAREN: expr self.parse_expression() if self.next_token()[0] ! RPAREN: raise SyntaxError(缺少右括号) return expr raise SyntaxError(f意外的 token: {tok}) def evaluate(node): # 递归遍历 AST叶子节点直接返回内部节点先算子节点 if node[0] num: return node[1] op, left, right node if op add: return evaluate(left) evaluate(right) if op sub: return evaluate(left) - evaluate(right) if op mul: return evaluate(left) * evaluate(right) if op div: return evaluate(left) // evaluate(right) raise ValueError(f未知节点: {node}) tokens tokenize(2 3 * 4) ast Parser(tokens).parse_expression() print(ast) # (add, (num, 2), (mul, (num, 3), (num, 4))) print(evaluate(ast)) # 14而不是 20优先级是通过函数嵌套实现的这是递归下降最巧妙的地方。parse_expression在处理加减号时左右操作数都用parse_term去解析所以3 * 4会先被组合成一个整体加法拿到的右侧是乘法节点。反过来如果parse_term里调用了parse_expression乘除就会在优先级上低于加减2 3 * 4就会算出 20。括号的处理也在parse_factor里遇到左括号递归调用parse_expression因为括号里的表达式优先级最高需要在整个表达式层级重新解析。这里有一个常见 bug就是消费了左括号之后忘记检查右括号导致解析器越界或产生错误 AST。吃完左括号的内容后必须确认下一个 token 是右括号这不是风格问题是正确性问题。3.3 三个必调参数变量作用域、错误信息和除法语义解释器能算算术表达式只是起点资料里后续章节一定会引入变量。变量引入后第一个要面对的参数就是作用域。常见的做法是用一个字典作为符号表变量名映射到值但真正的语言不可能只有一个全局作用域函数内部的局部变量不能污染全局。我一般会建议从第一天就用作用域栈而不是后期重构。作用域栈是一个 list元素是字典进入函数时 push 新字典退出时 pop。查找变量时从最内层往外层遍历。这个设计后期加函数、加闭包都不需要改结构。如果用单个 dict 顶着函数内赋值会直接覆盖全局变量等做到闭包章节时再改几乎等于把 evaluator 重写一遍。第二个必调参数是错误信息。自制语言最常见的调试痛苦不是逻辑错而是报错没有位置信息。词法阶段的异常要带字符偏移语法阶段的异常要带 token 位置运行时异常要带 AST 节点信息。很多人在 parser 里抛出SyntaxError时只写一句语法错误等于没写。我会在next_token里记录 token 的行列号异常消息里直接拼进去测试时定位快得多。第三个容易忽略的参数是除法语义。用//还是/直接决定测试用例怎么写。你的语言如果是动态类型风格跟随资料用浮点除法比较自然如果是想贴近 C 系语法整数除法也合理。关键是让 evaluator 的语义和文档描述一致不要混用否则同一个表达式在两个版本里结果不同查起来非常痛苦。4. 《自制编程语言》避坑指南新手最容易翻车的四个地方4.1 优先级写反2 3 * 4算出 20现象照着资料写完 parser测试四则运算发现乘法优先级的表达式结果不对。2 3 * 4输出 20 而不是 14但单独测3 * 4又是正确的。原因优先级不是靠代码里的某个标志位实现的而是靠函数调用层次。如果把parse_term放在parse_expression的上一层乘除会先吃掉加减的结果整个文法的层次就反了。这种错误从代码结构上看完全合法AST 打印出来也能看出问题——根节点变成了(mul, (add, 2, 3), 4)。解决检查三个函数的调用关系。加法层级必须调用乘法层级乘法层级必须调用因子层级。口诀是优先级越低的越靠外层。打印 AST 是最快的定位方式根节点如果是乘法而输入里有加减号优先级肯定写反了。4.2 深层嵌套表达式让解析器栈溢出现象写一个递归下降解析器去解析深度嵌套的括号表达式比如((((...1...))))嵌套到几百层时直接抛RecursionError整个解释器崩溃。看资料里的示例代码好像没有这个问题自己一跑就炸感觉像玄学。原因这不是玄学是递归实现的天然边界。每个嵌套层级对应一个俄语函数调用帧解释器语言的默认递归深度一般在 1000 左右超过之后就直接报错。资料里的测试用例通常不会嵌套那么深所以示例代码看起来没问题。解决最省事的办法是在入口处调高递归限制比如sys.setrecursionlimit(10000)但这只能推迟问题不能根治。真正的解法是避免不必要的递归下降比如对循环结构用迭代实现或者把连续运算符的解析写成 while 循环而非递归。至少要在心理上接受一个边界纯递归解析器不适合解析嵌套深度不可控的输入。4.3 字符串转义变成黑匣子现象给语言加入字符串类型后词法分析器把带引号的字符串切开转义字符被当成了普通字符。比如输入a\nb期望是换行实际输出却是反斜杠加字母 n 两个字符。原因字符串扫描需要在遇到反斜杠时特殊处理而不是看到引号就结束。一个只按读字符直到遇到下一个引号实现的扫描器会把\当成普通字符转义序列自然失效。这个问题在算术表达式为主的解释器里不显眼一加字符串就暴露。解决在字符串的词法扫描分支里遇到\时单独读取下一个字符组合成转义对然后继续扫描。同时要处理\这种转义的引号否则字符串内部出现引号时扫描会提前终止。先列一个转义对照表再实现比如\n、\t、\\、\一次性覆盖别等测试用例踩到了才补。4.4 符号表生命周期混乱变量被全局污染现象函数内部给变量赋值后外部同名变量也被改了。或者函数执行结束后函数内的局部变量在全局还能访问到。查 e evaluator 代码发现逻辑上没有问题但就是表现不对。原因整个解释器只用一个 dict 做符号表所有赋值都写进同一个作用域。函数内赋值实际上修改了全局变量函数退出后也没有清理局部变量的动作。这是作用域设计缺失的典型症状。解决改用作用域栈实现很短但能根治问题。class ScopeStack: def __init__(self): self.stack [{}] def push(self): # 进入函数或块时压入新作用域 self.stack.append({}) def pop(self): # 退出时弹出局部变量随之消失 self.stack.pop() def define(self, name, value): # 赋值只写入最内层作用域 self.stack[-1][name] value def lookup(self, name): # 从内往外逐层查找内层优先 for scope in reversed(self.stack): if name in scope: return scope[name] raise NameError(f未定义变量: {name})这里的关键行为是lookup从内层往外层遍历而define永远只写最内层。这样函数内的赋值不会污染外层但函数内可以读取外层已经定义的变量。等你做到闭包章节还需要把定义时的作用域链捕获下来那就是更进阶的玩法了。5. 把书读厚三个验证自己是否真懂的小技巧5.1 加一个匿名函数验证闭包捕获读完语法和求值章节后我建议给自己布置一个额外任务给语言加匿名函数语法。这一步会强迫你思考函数对象在求值器中到底存了什么。如果函数对象只存了参数名和函数体使用它的环境是调用时的环境那闭包就必然写错。正确的做法是函数对象里保存定义时的作用域链调用时把调用参数压入新作用域并让这个新作用域的外层指向保存的那条链。5.2 把树遍历改成字节码量化性能差异这个验证能直接检验你是否真的理解了执行模型。把 evaluator 改成两段式先编译 AST 成指令数组比如LOAD_CONST、ADD、STORE_NAME再写一个while循环做指令分派。然后拿同一个递归求和的程序跑两种实现对比耗时。你会发现树遍历版本慢得明显原因是有大量的函数递归调用来回压栈而字节码版本在一个循环里顺序执行解释开销小得多。5.3 用 golden test 固化语言行为这个东西是我的习惯也是调试自制语言最实用的工具。把输入源程序、期望输出、期望错误信息按编号存成文本文件写一个脚本逐个运行并对比结果。任何一次重构后跑一遍全部用例改坏哪里立刻知道。资料里的每个章节结束我都建议新增对应功能的测试用例而不是只跑书上的示例。说实话我最初读这类资料的时候前三遍都在抄代码抄完觉得懂了。真正觉得入门是某一天合上书从空文件开始重新写卡住了才回翻资料。如果你也在学这套资料不妨试一次关书重写你会发现很多以为懂了的细节其实并没有掌握。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
