自制编程语言实战：从Python解释器到栈式虚拟机全解析

简介对自制编程语言感兴趣的开发者这份PDF资料提供了从语言设计到实际实现的完整思路适合作为编译原理课程的补充学习材料。包内仅含1个文件大小约2.38MB内容系统覆盖编程语言设计、实现与使用三大环节详细讲解词法与语法分析生成工具、运行时环境、内存管理以及跨平台编译等知识。目前已有869人浏览学习是该领域较受关注的入门资料。资料以两个自制语言案例为主线完整演示了从语法规范、解析器编写到可运行程序生成的各个阶段并给出不同版本的演进过程与常见排错思路能帮助读者建立对编译器整体架构的直观理解同时为跨平台环境下的动手实践提供具体参考两个案例的代码对照也有助于理解不同设计取舍。1. 自制编程语言资料入门先分清一本书该读哪里、代码该怎么跑打开《自制编程语言》的配套资料很多人是冲着自己设计一门编程语言的念头来的结果面对一堆.c、.h、Makefile、工具链配置第一反应往往是——该从哪个文件开始读这其实是资料学习的第一个分水岭。这本书和它的资料要解决的不是设计出一门登上编程语言排行榜的工业级语言而是带你走通从零把一个能跑的语言做出来这条完整技术链路。适合的人群是有 C 或 Python 基础、读过数据结构、却一直没把编译原理真正落地过的人。资料的正确打开方式是先搭好环境把随书代码跑起来再拿最小例子逐段改最后才是读整本设计思路。2. 用 Python 手写最小解释器词法、语法树与求值器的第一版代码很多人在资料里一上来就直接啃 C 版编译器边看边卡。我的经验是先用 Python 写一个 200 行的最小解释器把词法分析、语法分析、求值这三块的真实手感找到再回头读 C 工程里的对应源码理解成本会低很多。这一章的代码不是玩具它是后面所有讨论的地基。2.1 词法分析把源码切成 token 流这是最容易抄错的第一关词法分析的目标很简单把一串字符串变成有类型的 token 序列。常见的坑是把识别关键字和识别标识符混在一起或者在正则顺序上出错。import re def tokenize(src): tokens [] pos 0 # 注意规则顺序就是优先级顺序PRINT 必须放在 ID 之前 rules [ (PRINT, rprint), (NUM, r\d), (ID, r[A-Za-z_]\w*), (ASSIGN, r), (OP, r[\-*/]), (LPAREN, r\(), (RPAREN, r\)), (SKIP, r[ \t]), (NL, r\n), ] while pos len(src): for name, pat in rules: m re.match(pat, src[pos:]) if m: text m.group(0) pos len(text) if name SKIP: break tokens.append((name, text)) break else: raise SyntaxError(f无法识别的字符: {src[pos:pos1]!r}) return tokens这段代码里有三个参数和顺序细节值得记住。rules列表的顺序就是匹配优先级print必须出现在普通标识符规则之前否则会被识别成 IDSKIP专门吞掉空格和制表符但它不能返回给语法层NL在这里先保留后面你会发现换行符处理是自制语言里最容易做坏的部分。src[pos:]每次切片不是最高效的写法但对于教学语言可读性远大于性能等 C 版再优化也不迟。2.2 递归下降语法分析手写 parser 为什么比生成器更适合入门AST 用节点类表示每个节点只承担存储结构这一个职责。这里不引入任何第三方库语法分析用递归下降手写因为生成器会把你和真实的调用关系隔离开出错时更难排查。class ASTNode: pass class Num(ASTNode): def __init__(self, val): self.val val class Var(ASTNode): def __init__(self, name): self.name name class BinOp(ASTNode): def __init__(self, op, left, right): self.op, self.left, self.right op, left, right class Assign(ASTNode): def __init__(self, name, expr): self.name, self.expr name, expr class Print(ASTNode): def __init__(self, expr): self.expr expr class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] if self.pos len(self.tokens) else (EOF, ) def take(self, nameNone): tok self.peek() if name and tok[0] ! name: raise SyntaxError(f期望 {name}实际 {tok[0]}) self.pos 1 return tok def parse_stmt(self): tok self.peek() if tok[0] ID and self.tokens[self.pos 1][0] ASSIGN: name self.take(ID)[1] self.take(ASSIGN) return Assign(name, self.parse_expr()) if tok[0] PRINT: self.take(PRINT) return Print(self.parse_expr()) raise SyntaxError(f不支持的语句: {tok}) def parse_expr(self): node self.parse_term() while self.peek() (OP, ) or self.peek() (OP, -): op self.take()[1] right self.parse_term() node BinOp(op, node, right) return node def parse_term(self): node self.parse_factor() while self.peek() (OP, *) or self.peek() (OP, /): op self.take()[1] right self.parse_factor() node BinOp(op, node, right) return node def parse_factor(self): tok self.peek() if tok[0] NUM: self.take() return Num(int(tok[1])) if tok[0] ID: self.take() return Var(tok[1]) if tok[0] LPAREN: self.take() node self.parse_expr() self.take(RPAREN) return node raise SyntaxError(f无法解析: {tok})这里最重要的设计是parse_expr和parse_term的分层。expr层只处理加减term层只处理乘除factor处理原子值。这个分层直接决定了运算符优先级1 2 * 3会先走parse_term把2 * 3归并成一个节点再加1。如果你把加法和乘法写在同一个函数里得到的就是从左到右平级运算优先级全乱。take方法的name参数是语法层的边界守门员能提前拦截缺右括号这类错误。2.3 求值器用 tree-walking 方式遍历 AST理解程序即数据有了 AST 之后求值器只需要做一件事根据节点类型执行对应动作。这个阶段不求快只求逻辑清晰。def eval(node, env): if isinstance(node, Num): return node.val if isinstance(node, Var): return env[node.name] if isinstance(node, BinOp): l eval(node.left, env) r eval(node.right, env) if node.op : return l r if node.op -: return l - r if node.op *: return l * r if node.op /: return l / r raise RuntimeError(f未知运算符: {node.op}) if isinstance(node, Assign): v eval(node.expr, env) env[node.name] v return v if isinstance(node, Print): print(eval(node.expr, env)) return None raise RuntimeError(f未知节点: {type(node)})注意Assign求值时先算右侧表达式再写入环境。这个顺序不是随便定的a a 1必须保证读a发生在写a之前。另一处细节是Print返回None这对应了print 语句不是表达式、没有值的语义后面做 REPL 时会依赖这个约定判断要不要打印结果。运行整个程序只需要把输入按行拆开逐行 tokenize、parse、eval环境env用同一个字典贯穿所有语句。3. 给语言加上函数与闭包作用域链和 REPL 的落地实现如果你只看资料里的 C 代码很容易被函数调用、局部变量、闭包这些概念绕晕。其实函数就三件事定义时记住参数名和函数体调用时新建一个环境执行函数体。这一章用 Python 把这套机制做出来你就知道 C 版里的Environment结构体到底在维护什么了。3.1 环境链为什么每个函数调用都必须有独立的环境JS、Python、Lua 里的函数能访问外部变量靠的就是环境链。每个函数调用创建一个新的Env它的parent指向定义时所在的环境。变量查找从当前环境开始逐级往上找。class Env: def __init__(self, parentNone): self.vars {} self.parent parent def get(self, name): if name in self.vars: return self.vars[name] if self.parent: return self.parent.get(name) raise NameError(f未定义变量: {name}) def set(self, name, value): if name in self.vars: self.vars[name] value elif self.parent: self.parent.set(name, value) else: self.vars[name] valueget的递归逻辑好懂但set的写法是个隐藏考点。我见过不少实现把set直接写成self.vars[name] value结果函数内给外部变量赋值永远写不进父环境。正确的语义是先沿环境链找找到就改找不到才在当前环境新建变量。这个设计直接决定了你是否能在语言里做出函数修改全局变量的效果。函数对象也不需要花哨的类层级class Function(ASTNode): def __init__(self, name, params, body, env): self.name name self.params params self.body body self.env envenv是函数被创建时所在的环境。调用这个函数时新建的调用环境以fn.env为父而不是以调用处环境为父这一条就是闭包能工作的根本原因。3.2 闭包踩坑循环变量共享是怎么发生的闭包最常见的翻车现场是循环里创建多个函数最后所有函数返回同一个值。用环境链模型可以精确解释如果循环变量存放在外层环境里所有闭包捕获到的都是同一个环境循环结束后这个变量停在最后一个值所有函数读到的自然都是它。def eval_call(fn, args, env): call_env Env(fn.env) for p, a in zip(fn.params, args): call_env.vars[p] a result None for stmt in fn.body: result eval(stmt, call_env) if isinstance(stmt, Return): return stmt.value return result这段代码里call_env Env(fn.env)是核心新环境的父是fn.env而不是当前调用处的env。如果你写成Env(env)函数就只能访问调用处变量闭包直接失效。Return的检查放在每条语句之后一旦碰到返回语句立刻中止执行避免后面的代码覆盖结果。3.3 REPL每敲一行立刻求值调试体验的转折点有了函数之后REPL 就是水到渠成的事。它的机制是读一行、解析一行、求值一行。def repl(): env Env() print(mini-lang REPL输入 :q 退出) while True: line input( ) if line.strip() :q: break if not line.strip(): continue try: tokens tokenize(line) node Parser(tokens).parse_stmt() result eval(node, env) if result is not None: print(result) except (SyntaxError, NameError, RuntimeError) as e: print(error:, e)REPL 的关键参数有两个env必须在循环外创建一次否则每输入一行就丢一次状态result is not None的判断用来决定是否打印表达式的值。这个设计对应的是a 1不打印、1 2打印3的交互习惯。调试函数时REPL 比写文件再执行快太多你可以在一个会话里反复定义函数并调用环境状态始终保留。4. 从解释器走向虚拟机C 语言实现里的栈式指令与内存回收当你把 Python 版解释器跑顺后再回头看《自制编程语言》里的 C 工程会发现它不是直接遍历 AST而是先把程序编译成一套栈式虚拟机指令再执行指令。这条路比 AST 求值麻烦但换来的是性能、可控内存和后续优化的空间。4.1 为什么 AST 求值不是终点指令分发与数据布局AST 求值慢主要慢在每个节点的isinstance判型和递归调用。栈式虚拟机把语法分析产物编译成线性指令序列执行时只需要一个switch分发。这正是自制编程语言资料里编译器部分做的事也是你理解解释器 vs 编译器差异最好的切入角度。指令集不需要多核心指令一张表就能说清指令操作数语义PUSH整数把常量压入操作数栈ADD无弹出两个数相加后压回STORE全局槽位弹出栈顶写入全局变量槽LOAD全局槽位读取全局变量并压栈CALL函数编号调用函数RET无从函数返回PRINT无弹出栈顶并输出HALT无停机这套指令集最妙的地方是指令本身不关心语法只关心栈的平衡。C 语言实现虚拟机核心循环长这样typedef struct { int stack[1024]; int sp; } VM; #define PUSH(v) do { vm-stack[vm-sp] (v); } while(0) #define POP() (vm-stack[--vm-sp]) #define BINOP(op) do { int b POP(); int a POP(); PUSH(a op b); } while(0) void run(VM *vm, int *code, int *globals) { int ip 0; for (;;) { int op code[ip]; switch (op) { case OP_PUSH: PUSH(code[ip]); break; case OP_ADD: BINOP(); break; case OP_SUB: BINOP(-); break; case OP_STORE: globals[code[ip]] POP(); break; case OP_LOAD: PUSH(globals[code[ip]]); break; case OP_PRINT: printf(%d\n, POP()); break; case OP_HALT: return; } } }这段代码里vm-stack[vm-sp] (v)先赋值后自增POP先自减再读两者严格配对了操作数栈的压入/弹出闭环。BINOP宏里的int b POP(); int a POP();顺序不能写反因为栈是后进先出3 2 ADD必须要让3作为被加数。写完这个循环你最大的收益是任何一条指令执行完程序状态只有ip、sp、常量区、全局区这几处变化调试时盯住这四个量就够了。4.2 内存回收先上引用计数还是直接写标记清除自制语言一旦支持字符串、列表等堆对象内存回收就回避不了。常见做法是先做引用计数因为它实现简单、对象立即释放。但引用计数最著名的坑是环形引用两个对象互相持有对方引用计数永远不为零。因此很多教学虚拟机会直接上标记清除mark-sweep原理就是两个字标记从根集合可达的所有对象再清扫所有不可达对象。typedef struct Obj { struct Obj *next; int marked; int type; /* 对象字段 */ } Obj; static void markObject(Obj *o) { if (!o || o-marked) return; o-marked 1; /* 按 type 递归标记子对象 */ } static void markRoots(VM *vm) { for (int i 0; i vm-sp; i) { if (isObject(vm-stack[i])) markObject(asObject(vm-stack[i])); } } static void sweep(VM *vm) { Obj **p vm-objects; while (*p) { if ((*p)-marked) { (*p)-marked 0; p (*p)-next; } else { Obj *dead *p; *p dead-next; free(dead); } } }markRoots里的根集合在栈式虚拟机里就是操作数栈。这里最容易被忽略的是sweep的双重指针技巧Obj **p维护的是当前指针的上一个节点的 next 地址链表删除节点时才不用专门处理头节点。实际项目里一个对象是否可达可能有多个字段持有引用递归标记时必须把所有字段都覆盖到漏一个字段就是一场内存泄漏。资料里的 C 版通常会在对象结构里专门放一个next字段维护全部对象链表这就是上面Obj结构体的来源。4.3 垃圾回收的触发时机别等到内存耗尽才动手收集器写完了什么时候调用它这决定了整个语言的运行节奏。常见策略是在分配对象时检查已分配内存总量超过阈值就触发一次 GC。阈值不能设太小否则程序会在分配热点上反复全量扫描也不能设太大否则内存峰值高得吓人。一个实用的做法是初始阈值设为堆的 1/4每次 GC 后根据存活对象比例动态调整存活少就调低阈值存活多就调高。这个参数直接关系到你的语言在递归或循环里被 GC 拖慢多少。5. 自制编程语言自学避坑五个高频翻车点与排查思路这个项目方向我从入门到能做完整实现踩过的坑比资料里任何一章都值得记录。下面五条是最常出现的按现象 → 原因 → 解决写清楚。5.1 现象随书 C 代码在 Windows 上编译失败报错成堆原因资料里的构建脚本和头文件依赖是按 Linux GCC 环境写的Windows 上哪怕装了 MinGWMakefile 的换行、路径分隔符、动态链接行为也会不一样。这不是你代码写错了是环境不匹配。解决不要执着于原生 Windows 环境用 WSL 或 Docker 起一个 Ubuntu 容器装好 build-essential 后直接 make或者把项目导入 VS Code Remote 容器。环境一致后编译问题会消失大半。5.2 现象源码里写中文注释词法分析突然抛错原因tokenize按单字节 ASCII 处理字符中文字符在 UTF-8 里是多字节编码每个字节都大于 127被当成非法字符。解决源码文件统一保存为 UTF-8 无 BOM词法分析里把非 ASCII 字节直接跳过或报错时携带行号。更隐蔽的是某些 Windows 编辑器会加 BOM 头BOM 字节一旦进入 tokenizer第一个 token 就废了。5.3 现象函数内修改外部变量回到顶层发现值没变原因环境链的set实现写错了只往当前环境写没有沿父环境查找。解决按第三章的Env.set实现先在环境链上找找到就更新找不到才在当前环境新建绑定。写完之后用一个最简单的计数函数验证顶层count 0函数内count count 1调用十次后检查顶层值是否为 10。5.4 现象递归函数一跑就栈溢出或者卡死无输出原因CALL 和 RET 没有严格配对或者递归深度超过操作数栈上限。有时是参数压栈顺序错误导致函数读到的参数不对表现为死循环。解决给虚拟机加一个 trace 开关每条指令打印ip、opcode、sp三个值跑一个深度 3 的小递归用例逐条对照。这个 trace 开关是自制语言调试里性价比最高的一个功能。5.5 现象加上字符串对象后循环拼接字符串慢到无法忍受原因字符串是不可变对象每一次就把两个字符数组整个拷贝一遍循环 N 次拼接是 O(N²) 复杂度。解决先不要给字符串重载加号提供StringBuilder之类的累积接口或者让字符串类型内部持有可变缓冲区和长度字段。这个坑很多人只在 C 版里遇到因为 Python 字符串拼接有运行时优化C 里只能自己处理。6. 验证这门外语能干活三个小实验确认你的语言可维护可用语言实现完不等于项目结束。我给自己定了一条规矩必须用这门语言写完三个实验才允许往资料里加新特性。第一个实验是递归性能冒烟测试。用你自己的语言写斐波那契数列fib(25)能顺利跑完且结果正确说明函数调用栈和整数运算没有硬伤。第二步是给语言加脚本文件入口让它能处理命令行参数./minilang fib.ml 25这个入口用到的就是最简单的主函数逻辑读文件、编译、运行、退出。第三个实验是写一个极简断言框架把测试用例收进来def assert_equal(actual, expected, name): if actual ! expected: print(FAIL:, name, 期望, expected, 实际, actual) else: print(PASS:, name)这个 6 行的小工具看起来简陋但它改变了开发节奏每加一个新的内建函数先追加断言再跑回归而不是靠肉眼在 REPL 里点来点去。我的习惯是每改完一个特性必须让全部测试通过才继续下一步这是做过太多加了新指令结果老脚本翻车之后换来的教训。希望你也能把测试前置到开发流程里这比任何优化技巧都省时间。希望帮到你。本文还有配套的精品资源点击获取