简介一份编译原理课程设计“实现一个小型编译程序”的完整资源包适合计算机专业本科生或需要完成SLR(1)语法分析实验的开发者。项目基于C语言在Win10VS2019环境下开发实现将高级语言源程序翻译为四元式程序必做阶段及汇编语言程序选做阶段并参考胡元义《编译教程第四版》及配套习题解析上机指导。压缩包共14个文件大小约22KB包含C源程序、dat测试数据、txt说明文档、asm汇编输出及med中间结果文件覆盖了从源码到四元式再到汇编的完整产物。目前已有2777人学习下载资源内有可运行的源代码、四元式与汇编程序结果以及表达式分析过程文本可辅助理解SLR(1)分析表构建和翻译流程也便于在参考代码基础上做进一步改进。1. 一个「小型编译程序」能做什么把源码变成可运行结果的最小闭环打开一份名为「实现一个小型编译程序.zip」的项目里面通常是一个能跑通“源码 → 可运行结果”全流程的最小工程。它不需要像生产级编译器那样处理复杂的优化、链接和错误恢复核心目标只有一个让你亲眼看见输入一段自定义语法输出一串可运行结果并且过程每一步都可以打印出来检查。我见过不少学完编译原理的人能答出词法分析、语法分析、中间代码生成的定义但给他一个空目录却不知道第一行代码该写在哪。这个“小型编译程序”的价值就在于此用两三百行代码把一条完整翻译管线立起来。它适合正在学编译原理的初学者、准备面试的开发者以及想搞清解释器与编译器边界的人这也是这篇笔记要完整拆开的内容。2. 拆出四个能独立交付的模块从目标程序反推架构2.1 选一个“小但完整”的语言目标而不是一上来读龙书“小型”不等于功能残缺而是语言特性收敛只保留一种数据类型、一种赋值语句、一种输出语句、一个算术表达式层级。下面这段代码就是我给这类项目定义的最小目标int a; a 1 2 * 3; print a;它涵盖了变量声明、赋值、算术运算、括号和打印基本覆盖编译课堂前几章的核心阶段又不需要处理字符串、数组和函数调用。选int类型而不是float或string是因为整数最容易实现词法分析只需要识别数字字面量虚拟机只需要做整数运算连字符串的内存管理都直接省掉。语法元素示例说明变量声明int a;只支持 32 位有符号整数赋值语句a 1 2 * 3;右侧为算术表达式打印语句print a;打印表达式求值结果算术表达式1 2 * 3支持 - * /与括号做这样的小语言有一条很实用的原则先列用力例再写语法。不需要在一开始完整定义语法规则而是先写 5 到 10 个“这个语言必须能跑的代码片段”让这些用例驱动语法设计。int a; a 1; print a;是最小闭环print (1 2) * 3;用来验证优先级和括号int x; int y; y x 1;用来验证多变量和多语句。2.2 编译管线的五个阶段与每一层的验证方法常见做法是把这条管线拆成五个阶段词法分析、语法分析、语义检查、代码生成、目标执行。在这个小项目里语义检查可以并到代码生成阶段做但分界线要在脑子里保持清晰。源码 → 词法分析 → token 列表token 列表 → 语法分析 → ASTAST → 语义检查 → 带符号表信息的 ASTAST → 代码生成 → 字节码字节码 → 虚拟机执行 → 输出结果每个阶段都有可独立观察的中间产物这是整个项目最值钱的地方。文件设计上我习惯把这些阶段拆成tokenizer.py、parser.py、codegen.py、vm.py四个模块入口文件只负责把它们串起来。不喜欢拆文件的也可以全部写进一个文件里但每个阶段至少要有单独的“打印函数”因为调试一个编译器靠的就是不断打印中间产物来定位哪一层出问题。调试顺序也很有讲究先跑最小的源代码验证 token 列表是否正确再验证 AST 形状是否正确最后才验证字节码与执行结果。如果 token 阶段就错了后面的对错根本没有意义。很多翻车现场都发生在“看起来能跑但中间产物从没认真看过”。这个项目里token 列表打印出来应该类似[INT(int), IDENT(a), SEMI(;), ...]AST 打印出来是一个缩进的树形结构字节码打印出来是一行行指令。这三个中间产物对应三份“调试视角”缺一个都会让人在问题定位时抓瞎。2.3 为什么栈式字节码是最适合小项目的中间表示中间表示有三种常见选择AST 直接解释执行、三地址码、栈式字节码。AST 解释器最省事但“编译”的感觉很弱因为根本没有生成任何可检查的编译产物三地址码贴近真实编译器但需要引入临时变量分配和基本块栈式字节码的实现量最小且每个指令都直接对应一个简单动作。中间表示形态实现难度调试友好度适合场景AST 直接解释树形低一般教学演示三地址码线性高中优化编译器栈式字节码线性最低高小型编译程序栈式字节码的核心思路是所有计算都通过一个栈完成。a 1 2 * 3被翻译成“把 1 压栈、把 2 压栈、把 3 压栈、乘法弹两个算一个压回、加法弹两个算一个压回、把结果存入变量”每一步执行前后栈的深度都清清楚楚。这也让虚拟机代码极其简短后面你会看到执行器主体只有二三十行。寄存器分配是新手最容易陷入的泥潭。一旦选择生成真实汇编或三地址码就会遇到“这个值该放哪个寄存器、什么时候溢出到内存”这类问题。栈式字节码天然回避了寄存器分配因为临时值都在栈上。这个取舍在小项目阶段非常合理先把完整的翻译管线和执行器跑通以后再往寄存器机器迁移时替换的只是代码生成部分。2.4 先写虚拟机再写编译器用手工字节码把“最终形态”钉死很多人在写编译器时都栽过一个跟头先写了词法分析又写了语法分析最后发现虚拟机指令集设计不合理被迫回头改解析器。为了避免这种返工我一般会采用“倒着做”的方式先不碰词法分析和语法分析直接手工把目标程序的字节码写出来然后写一个最简单的虚拟机把它跑通。以上面的目标程序为例手工翻译的字节码长这样program [ (PUSH, 1), (PUSH, 2), (PUSH, 3), (MUL,), (ADD,), (STORE, 0), (LOAD, 0), (PRINT,), (HALT,), ]这段字节码对应的逻辑是计算1 2 * 3得到 7存入 0 号变量槽再取出来打印。虚拟机的任务只是按顺序执行这些指令遇到PUSH就把数字压栈遇到MUL就从栈上弹两个数相乘再压回遇到STORE就把栈顶弹出来存入指定槽位。这个“先手工跑通执行器”的步骤相当于把编译器的输出格式提前固化。一个人手工翻译出的字节码和后面自动生成的字节码必须完全一致这样才能在调试时逐条对比。这也是最稳妥的 TDD 思路先定义一个“正确的输出”再让编译器逐渐逼近它。等到词法分析和语法分析写完只要把自动生成的字节码和手工字节码逐条比对就能快速定位是扫描的问题、解析的问题还是生成逻辑的问题。3. 词法分析与递归下降语法分析让编译器第一次吞下源码3.1 手写词法分析器关键字、标识符、数字与运算符的扫描顺序词法分析器要做的只有一件事把源码字符串切成一串有类型的 token。手写比用工具生成更适合这个小项目因为语言规则少手写代码量小报错时可以精确控制行列号。下面是一个完整的扫描器实现语言符号集只有整数、标识符、int/print关键字、四则运算符、赋值号、分号和括号。class Token: def __init__(self, kind, valueNone, line0, col0): self.kind kind self.value value self.line line self.col col def __repr__(self): return f{self.kind}({self.value}){self.line}:{self.col} KEYWORDS {int, print} def tokenize(code): tokens [] i 0 line, col 1, 1 n len(code) while i n: ch code[i] if ch in \t: i 1 col 1 continue if ch \n: i 1 line 1 col 1 continue if ch.isdigit(): start_col col val while i n and code[i].isdigit(): val code[i] i 1 col 1 tokens.append(Token(NUMBER, int(val), line, start_col)) continue if ch.isalpha() or ch _: start_col col name while i n and (code[i].isalnum() or code[i] _): name code[i] i 1 col 1 if name in KEYWORDS: tokens.append(Token(name.upper(), name, line, start_col)) else: tokens.append(Token(IDENT, name, line, start_col)) continue if ch in -*/: tokens.append(Token(OP, ch, line, col)) i 1 col 1 continue if ch : tokens.append(Token(ASSIGN, ch, line, col)) i 1 col 1 continue if ch ;: tokens.append(Token(SEMI, ch, line, col)) i 1 col 1 continue if ch in (): tokens.append(Token(LPAREN if ch ( else RPAREN, ch, line, col)) i 1 col 1 continue raise SyntaxError(f无法识别的字符 {ch!r} 位于 {line}:{col}) tokens.append(Token(EOF, None, line, col)) return tokens扫描顺序是这里最容易出问题的地方先跳过空白和换行再识别多字符的整数再识别标识符和关键字最后才匹配单字符运算符。这个顺序不能随意调换。如果把运算符判断放在字母判断之前a1会被错误地切成一个名为a的标识符加上加号如果把数字判断放在标识符判断之后123abc会被当成一个合法的标识符。关键字的处理有个细节这里先把整个词读出来再判断它是不是关键字。关于这个边界问题第 5 章会专门展开。Token里携带的行列号是调试解析错误的关键信息后面的解析器抛出SyntaxError时必须带着行列号一起抛。3.2 定义 AST 节点与递归下降解析器语法优先级靠层级表达词法分析把源码变成了 token 列表语法分析的任务是把 token 列表变成树形结构的 AST。这里选递归下降解析因为它是手写解析器里最自然、最容易控制错误信息的一种方式而且完全不需要引入额外依赖。class Program: def __init__(self, stmts): self.stmts stmts class Declare: def __init__(self, name): self.name name class Assign: def __init__(self, name, expr): self.name name self.expr expr class Print: def __init__(self, expr): self.expr expr class BinOp: def __init__(self, op, left, right): self.op op self.left left self.right right class Number: def __init__(self, value): self.value value class Variable: def __init__(self, name): self.name nameAST 节点刻意保持简单每个类只存构造自己的必要字段。Program只存语句列表Assign只存变量名和右侧表达式BinOp只存操作符和两个子节点。后续语义检查和代码生成全部只需要访问这些字段。解析器的核心是表达式层级。加减和乘除必须用两个不同的函数层级来处理才能保证优先级正确。下面这个实现把表达式拆成了三层parse_expr处理加减parse_term处理乘除parse_factor处理最基础的数字、变量和括号。class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] def next_token(self): tok self.tokens[self.pos] self.pos 1 return tok def expect(self, kind): tok self.next_token() if tok.kind ! kind: raise SyntaxError(f{tok.line}:{tok.col} 期望 {kind}实际得到 {tok.kind}) return tok def parse_program(self): stmts [] while self.peek().kind ! EOF: stmts.append(self.parse_statement()) return Program(stmts) def parse_statement(self): tok self.peek() if tok.kind INT: self.next_token() name self.expect(IDENT).value self.expect(SEMI) return Declare(name) if tok.kind PRINT: self.next_token() expr self.parse_expr() self.expect(SEMI) return Print(expr) if tok.kind IDENT: self.next_token() self.expect(ASSIGN) expr self.parse_expr() self.expect(SEMI) return Assign(tok.value, expr) raise SyntaxError(f{tok.line}:{tok.col} 无法识别语句开头 {tok.kind}) def parse_expr(self): node self.parse_term() while self.peek().kind OP and self.peek().value in -: op self.next_token().value right self.parse_term() node BinOp(op, node, right) return node def parse_term(self): node self.parse_factor() while self.peek().kind OP and self.peek().value in */: op self.next_token().value right self.parse_factor() node BinOp(op, node, right) return node def parse_factor(self): tok self.peek() if tok.kind NUMBER: self.next_token() return Number(tok.value) if tok.kind IDENT: self.next_token() return Variable(tok.value) if tok.kind LPAREN: self.next_token() node self.parse_expr() self.expect(RPAREN) return node raise SyntaxError(f{tok.line}:{tok.col} 无法解析表达式因子)parse_expr和parse_term里的while循环处理的是左结合。1 2 3会被解析成(1 2) 3而不是1 (2 3)这对整数加减法结果虽然没有影响但遇到右结合运算符时就要特别小心。这组函数的调用关系就是精确的优先级表parse_expr能接受的运算符优先级最低parse_factor最高。如果想加一元运算符、比较运算符或逻辑运算符只需要在这个层级链条中插入新的函数。3.3 打印 AST 与错误定位调试解析器最省力的两个工具解析器写完的第一件事不是跑代码而是写一个dump_ast函数把所有 AST 节点打印成缩进树。因为解析器是一个纯函数式的树构建过程唯一有效的检查方式就是看树长什么样。下面是这个小语言可用的 AST 打印函数def dump_ast(node, indent0): pad * indent if isinstance(node, Program): print(pad Program) for stmt in node.stmts: dump_ast(stmt, indent 1) elif isinstance(node, Declare): print(pad fDeclare {node.name}) elif isinstance(node, Assign): print(pad fAssign {node.name}) dump_ast(node.expr, indent 1) elif isinstance(node, Print): print(pad Print) dump_ast(node.expr, indent 1) elif isinstance(node, BinOp): print(pad fBinOp {node.op}) dump_ast(node.left, indent 1) dump_ast(node.right, indent 1) elif isinstance(node, Number): print(pad fNumber {node.value}) elif isinstance(node, Variable): print(pad fVariable {node.name})对a 1 2 * 3;执行打印正确输出应该是BinOp 下面左边是一个Number 1右边是一个BinOp *。如果看到BinOp *变成了顶层节点说明优先级的层级结构写反了这是解析器最典型的错误形态。错误定位方面小型编译程序通常采用“遇到第一个错误就停止”的策略不做错误恢复。但第一错误必须报得准不然用户改一个错又来一个错体验非常差。我一般在except SyntaxError里除了打印错误信息还会把当前位置前后的 token 打出来def parse_debug(tokens, parser): try: return parser.parse_program() except SyntaxError as e: start max(0, parser.pos - 2) end min(len(tokens), parser.pos 3) print(错误附近的 token 序列:, tokens[start:end]) raise这个技巧能快速区分两类问题一类是 token 序列本身不符合预期说明词法分析扫错了另一类是 token 序列正常但解析器不认说明语法规则没有覆盖到这种写法。如果附近打印出来的是预期外的 token 类型优先检查词法如果 token 都正常但抛错优先检查语法层级。4. 从 AST 到字节码符号表、指令生成与 30 行的虚拟机4.1 指令集设计9 条指令覆盖表达式与赋值不多也不少代码生成阶段的输入是 AST 和符号表输出是一串线性字节码。最小指令集可以控制在 9 条每条指令只做一个简单操作。指令设计的原则在编译器领域常常被概括为“等需求出现再添加指令”这意味着不追求一次到位而是让现有语言的每个语法元素都被恰好覆盖。指令参数作用PUSH整数常量将立即数压入操作数栈LOAD变量槽位读取变量值并压栈STORE变量槽位弹出栈顶值写入变量ADD无弹出两个数相加结果压回SUB无弹出两个数相减结果压回MUL无弹出两个数相乘结果压回DIV无弹出两个数相除结果压回PRINT无弹出栈顶值并打印HALT无结束执行这套指令集里没有POP也没有跳转指令。不设计POP是因为目前的语法保证每一条语句执行后栈都是干净的临时值都会被消费掉不设计跳转是因为当前语言没有控制流。等第 6 章加入while循环时再补充LT、JMP、JMPZ三条指令即可。有一个和有真实寄存器机器明显不同的地方STORE的参数不是变量名而是变量槽位编号。变量在代码生成阶段就已经被映射成一个整数地址虚拟机的vars直接用这个整数作键。这样设计有两个好处一是缩短字节码长度二是把“变量名”到“运行位置”的映射完全留在编译期让语义检查和代码生成的分工更清晰。4.2 用后序遍历生成字节码先算子表达式再执行操作符AST 生成字节码采用的是后序遍历先处理左右子树再处理当前节点。对BinOp来说就是先为左子树生成字节码再为右子树生成字节码最后生成运算符指令。这也被称为把 AST 线性化成逆波兰表示直接映射到栈式虚拟机的求值模型。def gen_program(ast, symbols): code [] for stmt in ast.stmts: gen_stmt(stmt, symbols, code) code.append((HALT,)) return code def gen_stmt(stmt, symbols, code): if isinstance(stmt, Declare): symbols.register(stmt.name) elif isinstance(stmt, Assign): gen_expr(stmt.expr, symbols, code) code.append((STORE, symbols.lookup(stmt.name))) elif isinstance(stmt, Print): gen_expr(stmt.expr, symbols, code) code.append((PRINT,)) else: raise TypeError(f未知语句节点 {stmt}) def gen_expr(expr, symbols, code): if isinstance(expr, Number): code.append((PUSH, expr.value)) elif isinstance(expr, Variable): code.append((LOAD, symbols.lookup(expr.name))) elif isinstance(expr, BinOp): gen_expr(expr.left, symbols, code) gen_expr(expr.right, symbols, code) ops {: ADD, -: SUB, *: MUL, /: DIV} code.append((ops[expr.op],)) else: raise TypeError(f未知表达式节点 {expr})gen_stmt和gen_expr的职责划分是语句节点负责控制流程表达式节点负责生成计算指令。Declare语句没有生成任何字节码只在符号表里登记变量槽位这是有意为之的结果——变量声明是一个编译期行为运行时不产生任何动作。赋值语句先递归生成右侧表达式的字节码等求值结果留在栈顶后再生成STORE指令把它存入对应槽位。gen_expr对BinOp的处理严格遵循“左子树 → 右子树 → 自身”的顺序。字节码中的ADD会从栈上弹出两个数这意味着栈顶必须是右操作数栈顶下一个是左操作数。这也是为什么 2.4 节的手工字节码里2和3先被压栈并执行MUL然后才和1做加法。4.3 符号表登记变量槽位顺手完成唯一性检查符号表在最小项目里就是一个变量名到槽位的映射。槽位编号从 0 开始每登记一个新变量就加一。这个设计完全对应真实编译器中的“为局部变量分配栈帧偏移量”只是这里分配的是虚拟机的vars字典键。class SymbolTable: def __init__(self): self.slots {} self.next_slot 0 def register(self, name): if name in self.slots: raise SyntaxError(f变量 {name} 重复声明) self.slots[name] self.next_slot self.next_slot 1 def lookup(self, name): if name not in self.slots: raise NameError(f变量 {name} 未声明) return self.slots[name]register抛出SyntaxError是因为重复声明属于“源代码写错了”问题和字符串文本强相关而lookup抛出NameError是因为使用未声明变量属于“名字解析失败”在语义上更接近运行期问题。这个区分并不绝对但合理。不过第 5 章会指出真正严谨的做法是把声明检查和代码生成分开。符号表在这里还承担了一个容易被忽略的职责它决定了int a; int b;中a是 0 号槽、b是 1 号槽。如果声明顺序变了生成的字节码里STORE和LOAD的参数也会变。这意味着 AST 打印、符号表打印、字节码打印三份信息必须能互相印证任何一份对不上问题就出在从上一份到这一份的转换过程中。对于只有一层的语言符号表不需要维护作用域嵌套。如果以后加入花括号和if/while就要改成栈式作用域进入作用域时压入一层新表离开时弹出。现在的实现作为起步是非常合适的。4.4 一个 30 行的栈式虚拟机执行字节码并打印结果虚拟机的实现很短但却是整个管线的终点。它维护一个操作数栈和一个变量存储字典逐条执行字节码指令。每条指令的实现对应 4.1 节表格里的一行说明class VM: def __init__(self): self.stack [] self.vars {} def run(self, code): ip 0 while ip len(code): instr code[ip] op instr[0] if op PUSH: self.stack.append(instr[1]) elif op LOAD: self.stack.append(self.vars[instr[1]]) elif op STORE: self.vars[instr[1]] self.stack.pop() elif op in (ADD, SUB, MUL, DIV): b self.stack.pop() a self.stack.pop() if op ADD: self.stack.append(a b) elif op SUB: self.stack.append(a - b) elif op MUL: self.stack.append(a * b) elif op DIV: self.stack.append(a // b) elif op PRINT: print(self.stack.pop()) elif op HALT: break else: raise RuntimeError(f未知指令 {op}) ip 1ADD/SUB/MUL/DIV分支先pop出右侧操作数再从栈顶取出左侧操作数这个顺序不能反。因为压栈顺序是左操作数先压、右操作数后压弹栈时右操作数自然先出。a // b是整数除法向零取整这个语义要在语言规范里写明。真实编译器的做法是在代码生成阶段就把除法语义固定下来而不是让虚拟机的实现来决定。入口函数把四个阶段串起来形成完整调用链def main(src): tokens tokenize(src) ast Parser(tokens).parse_program() symbols SymbolTable() code gen_program(ast, symbols) VM().run(code)到这个入口能跑通一个最小编译程序就真正立住了。后面所有的功能扩展都是在这条调用链上增加新的语法元素和新的指令分支。5. 五个高频踩坑记录现象、原因与排查方法5.1 优先级反转12*3算出 9而不是 7现象同一段源码1 2 * 3打印出 9而给乘号加括号的(1 2) * 3也打印出 9。看 AST 打印结果发现语法树的顶层节点是*加法和乘法完全同级了。原因递归下降解析器中运算符优先级靠“调用层级”体现谁在最内层谁优先。最内层的parse_factor只处理数字、变量和括号乘除必须单独放在一层parse_term中而加减放在最外层parse_expr。如果图省事把parse_expr写成一个循环直接调用parse_factor所有运算符都被当成同级优先级自然失效。解决先确认层级关系再写代码parse_expr调用parse_termparse_term调用parse_factor。调试时直接打印 AST看见BinOp *挂在BinOp 的右子树就说明乘法层级是对的。这个坑看似基础但每次调整语法时都很容易重新踩进去尤其是添加新运算符的时候。5.2 关键字边界被吞printx被解析成printx现象源代码某处写了一个名叫printx的变量编译器没有报错把它的第一次出现当成了print语句处理后面报出“变量 x 未声明”之类的奇怪错误或者干脆把后续内容当表达式解析到行尾。原因词法分析器如果在读到p、r、i、n、t五个字符后就立刻返回PRINT关键字没有检查printx中紧随其后的x字符就会把一整个标识符切成两个 token。这种问题在关键字恰好是另一个标识符前缀时一定会出现比如print、int这类短单词。解决词法分析时必须先把一整个字母数字串读完再判断这整个串是否为关键字。也就是始终先读完整标识符、再查表而不是在读的过程中逐字符匹配关键字。第 3.1 节代码中if name in KEYWORDS的写法就是为了修这个坑把printx和print的区分彻底交给标识符的完整匹配。5.3x -3直接报语法错误factor 没有处理一元负号现象a 0 - 3;能正常编译执行a -3;却在解析阶段报错。错误信息指向-号说明解析器在factor层看到负号时不知道该怎么处理。原因parse_factor只接受数字、标识符和括号负号没有被纳入表达式语法。负号在表达式中是“一元运算符”与被减数缺失的二元减号不同。很多人在设计表达式语法时只考虑了常见的二元运算符忽略了一元负号这个看起来很小但无处不在的语法元素。解决在parse_factor开头增加一个分支如果当前 token 是-就跳过它、解析后面的因子然后构造一个等价的BinOp(-, Number(0), factor)让代码生成阶段完全复用现有的减法指令。也可以新增一条NEG指令但小项目用零减因子更省事不需要动指令集和虚拟机。5.4 除零让整个 VM 直接崩溃执行期错误要有明确出口现象运行a 1 / 0;时 Python 解释器爆出ZeroDivisionError报错堆栈指向虚拟机的DIV分支。更麻烦的是此时操作数栈里残留着两个未消费的操作数后续的PRINT会打出一个完全不可预期的数。原因栈式虚拟机把算术运算暴露给了执行期所有运行期错误都发生在DIV执行的那一瞬间。没有检查除数是否为零也没有人定义“除零后虚拟机应该做什么”系统默认的异常就这样直接透传上来了。解决至少要处理两层。第一层在DIV分支中先检查除数是否为零为零时抛出一个带明确语义的RuntimeError(除零错误)同时保证不会向栈写入半成品。第二层如果希望编译期就拦截可以在gen_expr中检查除号右子树是否为Number(0)常量并直接扔出编译错误。后者只能查出常量除零但覆盖面已经不小。执行器的健壮性和编译器的报错质量往往就是在这种细节上拉开差距。5.5 变量未声明也能通过语义检查不能只依赖代码生成现象源代码里写了x 1;但前面根本没有int x;程序居然通过了编译虚拟机能跑到某一步才报 KeyError。还有另一种现象更隐蔽int a; int a;没有报重复声明两个声明各自分配了不同的槽位。原因代码生成阶段的SymbolTable.register确实会做查重但如果语义检查没有在代码生成前完整跑一遍 AST某些路径就会漏检。尤其是当语言开始加入if、while后未被执行的语句块同样需要检查漏检的场景会迅速变多。解决把“检查变量是否声明、是否重复声明”从代码生成中抽成一个独立函数在gen_program之前对 AST 显式遍历一遍。这个函数只检查名字相关的规则不生成任何指令。它的存在让编译器能够在生成字节码之前就拒绝非法程序而不是把错误留到 VM 运行期。哪怕目前只是给codegen增加一个前置调用也要保证这条链路是显式可见的这一点在以后扩展控制流时尤其重要。6. 加两个功能让编译器「毕业」控制流与两趟处理6.1 用 while 循环引入跳转指令与地址回填表达式和赋值跑通后控制流是让这个编译器“毕业”的第一步。以while (i 10) { i i 1; }为例需要新增三条指令LT比较两个数并压入 0 或 1JMPZ在栈顶为 0 时跳转JMP无条件跳转。对应字节码形状是LOOP: LOAD 0 PUSH 10 LT JMPZ END LOAD 0 PUSH 1 ADD STORE 0 JMP LOOP END: HALT执行到这里LOOP和END都是逻辑标签本质就是要填入的数字。生成代码时先记下每个标签在指令列表中的位置遇到JMPZ和JMP时先写占位符等全部指令生成完再把占位符替换成真实的目标地址。这就是编译器领域常说的“跳转目标回填”也是从玩具编译器走向真实编译器的一道重要分水岭。6.2 两趟处理与调试习惯有了控制流语义检查就不该再和代码生成挤在一起。我一般会在解析和代码生成之间加一个独立的第一趟遍历 AST收集所有变量声明并构建完整符号表再跑一遍检查所有使用都合法。这一趟完成后代码生成阶段遇到任何变量都直接从符号表查槽位不需要边生成边注册。好处是“先使用后声明”这类规则可以在语言层直接支持所有语义错误也都集中在同一阶段暴露。我还有一个坚持了很久的调试习惯无论编译器做得多小都必须保留 AST 打印和字节码打印两个函数。遇到任何怪异行为先打印 AST 看树形结构对不对再打印字节码看指令流对不对最后才去看 VM 的栈变化。绝大多数问题在第一步或第二步就能暴露出来真正需要单步调试虚拟机的机会少之又少。这个习惯救过我很多次每次写完一个语法扩展我都会重新跑一遍 dump 流程确认中间产物没有变形。希望帮到你。本文还有配套的精品资源点击获取
简介一份编译原理课程设计“实现一个小型编译程序”的完整资源包适合计算机专业本科生或需要完成SLR(1)语法分析实验的开发者。项目基于C语言在Win10VS2019环境下开发实现将高级语言源程序翻译为四元式程序必做阶段及汇编语言程序选做阶段并参考胡元义《编译教程第四版》及配套习题解析上机指导。压缩包共14个文件大小约22KB包含C源程序、dat测试数据、txt说明文档、asm汇编输出及med中间结果文件覆盖了从源码到四元式再到汇编的完整产物。目前已有2777人学习下载资源内有可运行的源代码、四元式与汇编程序结果以及表达式分析过程文本可辅助理解SLR(1)分析表构建和翻译流程也便于在参考代码基础上做进一步改进。1. 一个「小型编译程序」能做什么把源码变成可运行结果的最小闭环打开一份名为「实现一个小型编译程序.zip」的项目里面通常是一个能跑通“源码 → 可运行结果”全流程的最小工程。它不需要像生产级编译器那样处理复杂的优化、链接和错误恢复核心目标只有一个让你亲眼看见输入一段自定义语法输出一串可运行结果并且过程每一步都可以打印出来检查。我见过不少学完编译原理的人能答出词法分析、语法分析、中间代码生成的定义但给他一个空目录却不知道第一行代码该写在哪。这个“小型编译程序”的价值就在于此用两三百行代码把一条完整翻译管线立起来。它适合正在学编译原理的初学者、准备面试的开发者以及想搞清解释器与编译器边界的人这也是这篇笔记要完整拆开的内容。2. 拆出四个能独立交付的模块从目标程序反推架构2.1 选一个“小但完整”的语言目标而不是一上来读龙书“小型”不等于功能残缺而是语言特性收敛只保留一种数据类型、一种赋值语句、一种输出语句、一个算术表达式层级。下面这段代码就是我给这类项目定义的最小目标int a; a 1 2 * 3; print a;它涵盖了变量声明、赋值、算术运算、括号和打印基本覆盖编译课堂前几章的核心阶段又不需要处理字符串、数组和函数调用。选int类型而不是float或string是因为整数最容易实现词法分析只需要识别数字字面量虚拟机只需要做整数运算连字符串的内存管理都直接省掉。语法元素示例说明变量声明int a;只支持 32 位有符号整数赋值语句a 1 2 * 3;右侧为算术表达式打印语句print a;打印表达式求值结果算术表达式1 2 * 3支持 - * /与括号做这样的小语言有一条很实用的原则先列用力例再写语法。不需要在一开始完整定义语法规则而是先写 5 到 10 个“这个语言必须能跑的代码片段”让这些用例驱动语法设计。int a; a 1; print a;是最小闭环print (1 2) * 3;用来验证优先级和括号int x; int y; y x 1;用来验证多变量和多语句。2.2 编译管线的五个阶段与每一层的验证方法常见做法是把这条管线拆成五个阶段词法分析、语法分析、语义检查、代码生成、目标执行。在这个小项目里语义检查可以并到代码生成阶段做但分界线要在脑子里保持清晰。源码 → 词法分析 → token 列表token 列表 → 语法分析 → ASTAST → 语义检查 → 带符号表信息的 ASTAST → 代码生成 → 字节码字节码 → 虚拟机执行 → 输出结果每个阶段都有可独立观察的中间产物这是整个项目最值钱的地方。文件设计上我习惯把这些阶段拆成tokenizer.py、parser.py、codegen.py、vm.py四个模块入口文件只负责把它们串起来。不喜欢拆文件的也可以全部写进一个文件里但每个阶段至少要有单独的“打印函数”因为调试一个编译器靠的就是不断打印中间产物来定位哪一层出问题。调试顺序也很有讲究先跑最小的源代码验证 token 列表是否正确再验证 AST 形状是否正确最后才验证字节码与执行结果。如果 token 阶段就错了后面的对错根本没有意义。很多翻车现场都发生在“看起来能跑但中间产物从没认真看过”。这个项目里token 列表打印出来应该类似[INT(int), IDENT(a), SEMI(;), ...]AST 打印出来是一个缩进的树形结构字节码打印出来是一行行指令。这三个中间产物对应三份“调试视角”缺一个都会让人在问题定位时抓瞎。2.3 为什么栈式字节码是最适合小项目的中间表示中间表示有三种常见选择AST 直接解释执行、三地址码、栈式字节码。AST 解释器最省事但“编译”的感觉很弱因为根本没有生成任何可检查的编译产物三地址码贴近真实编译器但需要引入临时变量分配和基本块栈式字节码的实现量最小且每个指令都直接对应一个简单动作。中间表示形态实现难度调试友好度适合场景AST 直接解释树形低一般教学演示三地址码线性高中优化编译器栈式字节码线性最低高小型编译程序栈式字节码的核心思路是所有计算都通过一个栈完成。a 1 2 * 3被翻译成“把 1 压栈、把 2 压栈、把 3 压栈、乘法弹两个算一个压回、加法弹两个算一个压回、把结果存入变量”每一步执行前后栈的深度都清清楚楚。这也让虚拟机代码极其简短后面你会看到执行器主体只有二三十行。寄存器分配是新手最容易陷入的泥潭。一旦选择生成真实汇编或三地址码就会遇到“这个值该放哪个寄存器、什么时候溢出到内存”这类问题。栈式字节码天然回避了寄存器分配因为临时值都在栈上。这个取舍在小项目阶段非常合理先把完整的翻译管线和执行器跑通以后再往寄存器机器迁移时替换的只是代码生成部分。2.4 先写虚拟机再写编译器用手工字节码把“最终形态”钉死很多人在写编译器时都栽过一个跟头先写了词法分析又写了语法分析最后发现虚拟机指令集设计不合理被迫回头改解析器。为了避免这种返工我一般会采用“倒着做”的方式先不碰词法分析和语法分析直接手工把目标程序的字节码写出来然后写一个最简单的虚拟机把它跑通。以上面的目标程序为例手工翻译的字节码长这样program [ (PUSH, 1), (PUSH, 2), (PUSH, 3), (MUL,), (ADD,), (STORE, 0), (LOAD, 0), (PRINT,), (HALT,), ]这段字节码对应的逻辑是计算1 2 * 3得到 7存入 0 号变量槽再取出来打印。虚拟机的任务只是按顺序执行这些指令遇到PUSH就把数字压栈遇到MUL就从栈上弹两个数相乘再压回遇到STORE就把栈顶弹出来存入指定槽位。这个“先手工跑通执行器”的步骤相当于把编译器的输出格式提前固化。一个人手工翻译出的字节码和后面自动生成的字节码必须完全一致这样才能在调试时逐条对比。这也是最稳妥的 TDD 思路先定义一个“正确的输出”再让编译器逐渐逼近它。等到词法分析和语法分析写完只要把自动生成的字节码和手工字节码逐条比对就能快速定位是扫描的问题、解析的问题还是生成逻辑的问题。3. 词法分析与递归下降语法分析让编译器第一次吞下源码3.1 手写词法分析器关键字、标识符、数字与运算符的扫描顺序词法分析器要做的只有一件事把源码字符串切成一串有类型的 token。手写比用工具生成更适合这个小项目因为语言规则少手写代码量小报错时可以精确控制行列号。下面是一个完整的扫描器实现语言符号集只有整数、标识符、int/print关键字、四则运算符、赋值号、分号和括号。class Token: def __init__(self, kind, valueNone, line0, col0): self.kind kind self.value value self.line line self.col col def __repr__(self): return f{self.kind}({self.value}){self.line}:{self.col} KEYWORDS {int, print} def tokenize(code): tokens [] i 0 line, col 1, 1 n len(code) while i n: ch code[i] if ch in \t: i 1 col 1 continue if ch \n: i 1 line 1 col 1 continue if ch.isdigit(): start_col col val while i n and code[i].isdigit(): val code[i] i 1 col 1 tokens.append(Token(NUMBER, int(val), line, start_col)) continue if ch.isalpha() or ch _: start_col col name while i n and (code[i].isalnum() or code[i] _): name code[i] i 1 col 1 if name in KEYWORDS: tokens.append(Token(name.upper(), name, line, start_col)) else: tokens.append(Token(IDENT, name, line, start_col)) continue if ch in -*/: tokens.append(Token(OP, ch, line, col)) i 1 col 1 continue if ch : tokens.append(Token(ASSIGN, ch, line, col)) i 1 col 1 continue if ch ;: tokens.append(Token(SEMI, ch, line, col)) i 1 col 1 continue if ch in (): tokens.append(Token(LPAREN if ch ( else RPAREN, ch, line, col)) i 1 col 1 continue raise SyntaxError(f无法识别的字符 {ch!r} 位于 {line}:{col}) tokens.append(Token(EOF, None, line, col)) return tokens扫描顺序是这里最容易出问题的地方先跳过空白和换行再识别多字符的整数再识别标识符和关键字最后才匹配单字符运算符。这个顺序不能随意调换。如果把运算符判断放在字母判断之前a1会被错误地切成一个名为a的标识符加上加号如果把数字判断放在标识符判断之后123abc会被当成一个合法的标识符。关键字的处理有个细节这里先把整个词读出来再判断它是不是关键字。关于这个边界问题第 5 章会专门展开。Token里携带的行列号是调试解析错误的关键信息后面的解析器抛出SyntaxError时必须带着行列号一起抛。3.2 定义 AST 节点与递归下降解析器语法优先级靠层级表达词法分析把源码变成了 token 列表语法分析的任务是把 token 列表变成树形结构的 AST。这里选递归下降解析因为它是手写解析器里最自然、最容易控制错误信息的一种方式而且完全不需要引入额外依赖。class Program: def __init__(self, stmts): self.stmts stmts class Declare: def __init__(self, name): self.name name class Assign: def __init__(self, name, expr): self.name name self.expr expr class Print: def __init__(self, expr): self.expr expr class BinOp: def __init__(self, op, left, right): self.op op self.left left self.right right class Number: def __init__(self, value): self.value value class Variable: def __init__(self, name): self.name nameAST 节点刻意保持简单每个类只存构造自己的必要字段。Program只存语句列表Assign只存变量名和右侧表达式BinOp只存操作符和两个子节点。后续语义检查和代码生成全部只需要访问这些字段。解析器的核心是表达式层级。加减和乘除必须用两个不同的函数层级来处理才能保证优先级正确。下面这个实现把表达式拆成了三层parse_expr处理加减parse_term处理乘除parse_factor处理最基础的数字、变量和括号。class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] def next_token(self): tok self.tokens[self.pos] self.pos 1 return tok def expect(self, kind): tok self.next_token() if tok.kind ! kind: raise SyntaxError(f{tok.line}:{tok.col} 期望 {kind}实际得到 {tok.kind}) return tok def parse_program(self): stmts [] while self.peek().kind ! EOF: stmts.append(self.parse_statement()) return Program(stmts) def parse_statement(self): tok self.peek() if tok.kind INT: self.next_token() name self.expect(IDENT).value self.expect(SEMI) return Declare(name) if tok.kind PRINT: self.next_token() expr self.parse_expr() self.expect(SEMI) return Print(expr) if tok.kind IDENT: self.next_token() self.expect(ASSIGN) expr self.parse_expr() self.expect(SEMI) return Assign(tok.value, expr) raise SyntaxError(f{tok.line}:{tok.col} 无法识别语句开头 {tok.kind}) def parse_expr(self): node self.parse_term() while self.peek().kind OP and self.peek().value in -: op self.next_token().value right self.parse_term() node BinOp(op, node, right) return node def parse_term(self): node self.parse_factor() while self.peek().kind OP and self.peek().value in */: op self.next_token().value right self.parse_factor() node BinOp(op, node, right) return node def parse_factor(self): tok self.peek() if tok.kind NUMBER: self.next_token() return Number(tok.value) if tok.kind IDENT: self.next_token() return Variable(tok.value) if tok.kind LPAREN: self.next_token() node self.parse_expr() self.expect(RPAREN) return node raise SyntaxError(f{tok.line}:{tok.col} 无法解析表达式因子)parse_expr和parse_term里的while循环处理的是左结合。1 2 3会被解析成(1 2) 3而不是1 (2 3)这对整数加减法结果虽然没有影响但遇到右结合运算符时就要特别小心。这组函数的调用关系就是精确的优先级表parse_expr能接受的运算符优先级最低parse_factor最高。如果想加一元运算符、比较运算符或逻辑运算符只需要在这个层级链条中插入新的函数。3.3 打印 AST 与错误定位调试解析器最省力的两个工具解析器写完的第一件事不是跑代码而是写一个dump_ast函数把所有 AST 节点打印成缩进树。因为解析器是一个纯函数式的树构建过程唯一有效的检查方式就是看树长什么样。下面是这个小语言可用的 AST 打印函数def dump_ast(node, indent0): pad * indent if isinstance(node, Program): print(pad Program) for stmt in node.stmts: dump_ast(stmt, indent 1) elif isinstance(node, Declare): print(pad fDeclare {node.name}) elif isinstance(node, Assign): print(pad fAssign {node.name}) dump_ast(node.expr, indent 1) elif isinstance(node, Print): print(pad Print) dump_ast(node.expr, indent 1) elif isinstance(node, BinOp): print(pad fBinOp {node.op}) dump_ast(node.left, indent 1) dump_ast(node.right, indent 1) elif isinstance(node, Number): print(pad fNumber {node.value}) elif isinstance(node, Variable): print(pad fVariable {node.name})对a 1 2 * 3;执行打印正确输出应该是BinOp 下面左边是一个Number 1右边是一个BinOp *。如果看到BinOp *变成了顶层节点说明优先级的层级结构写反了这是解析器最典型的错误形态。错误定位方面小型编译程序通常采用“遇到第一个错误就停止”的策略不做错误恢复。但第一错误必须报得准不然用户改一个错又来一个错体验非常差。我一般在except SyntaxError里除了打印错误信息还会把当前位置前后的 token 打出来def parse_debug(tokens, parser): try: return parser.parse_program() except SyntaxError as e: start max(0, parser.pos - 2) end min(len(tokens), parser.pos 3) print(错误附近的 token 序列:, tokens[start:end]) raise这个技巧能快速区分两类问题一类是 token 序列本身不符合预期说明词法分析扫错了另一类是 token 序列正常但解析器不认说明语法规则没有覆盖到这种写法。如果附近打印出来的是预期外的 token 类型优先检查词法如果 token 都正常但抛错优先检查语法层级。4. 从 AST 到字节码符号表、指令生成与 30 行的虚拟机4.1 指令集设计9 条指令覆盖表达式与赋值不多也不少代码生成阶段的输入是 AST 和符号表输出是一串线性字节码。最小指令集可以控制在 9 条每条指令只做一个简单操作。指令设计的原则在编译器领域常常被概括为“等需求出现再添加指令”这意味着不追求一次到位而是让现有语言的每个语法元素都被恰好覆盖。指令参数作用PUSH整数常量将立即数压入操作数栈LOAD变量槽位读取变量值并压栈STORE变量槽位弹出栈顶值写入变量ADD无弹出两个数相加结果压回SUB无弹出两个数相减结果压回MUL无弹出两个数相乘结果压回DIV无弹出两个数相除结果压回PRINT无弹出栈顶值并打印HALT无结束执行这套指令集里没有POP也没有跳转指令。不设计POP是因为目前的语法保证每一条语句执行后栈都是干净的临时值都会被消费掉不设计跳转是因为当前语言没有控制流。等第 6 章加入while循环时再补充LT、JMP、JMPZ三条指令即可。有一个和有真实寄存器机器明显不同的地方STORE的参数不是变量名而是变量槽位编号。变量在代码生成阶段就已经被映射成一个整数地址虚拟机的vars直接用这个整数作键。这样设计有两个好处一是缩短字节码长度二是把“变量名”到“运行位置”的映射完全留在编译期让语义检查和代码生成的分工更清晰。4.2 用后序遍历生成字节码先算子表达式再执行操作符AST 生成字节码采用的是后序遍历先处理左右子树再处理当前节点。对BinOp来说就是先为左子树生成字节码再为右子树生成字节码最后生成运算符指令。这也被称为把 AST 线性化成逆波兰表示直接映射到栈式虚拟机的求值模型。def gen_program(ast, symbols): code [] for stmt in ast.stmts: gen_stmt(stmt, symbols, code) code.append((HALT,)) return code def gen_stmt(stmt, symbols, code): if isinstance(stmt, Declare): symbols.register(stmt.name) elif isinstance(stmt, Assign): gen_expr(stmt.expr, symbols, code) code.append((STORE, symbols.lookup(stmt.name))) elif isinstance(stmt, Print): gen_expr(stmt.expr, symbols, code) code.append((PRINT,)) else: raise TypeError(f未知语句节点 {stmt}) def gen_expr(expr, symbols, code): if isinstance(expr, Number): code.append((PUSH, expr.value)) elif isinstance(expr, Variable): code.append((LOAD, symbols.lookup(expr.name))) elif isinstance(expr, BinOp): gen_expr(expr.left, symbols, code) gen_expr(expr.right, symbols, code) ops {: ADD, -: SUB, *: MUL, /: DIV} code.append((ops[expr.op],)) else: raise TypeError(f未知表达式节点 {expr})gen_stmt和gen_expr的职责划分是语句节点负责控制流程表达式节点负责生成计算指令。Declare语句没有生成任何字节码只在符号表里登记变量槽位这是有意为之的结果——变量声明是一个编译期行为运行时不产生任何动作。赋值语句先递归生成右侧表达式的字节码等求值结果留在栈顶后再生成STORE指令把它存入对应槽位。gen_expr对BinOp的处理严格遵循“左子树 → 右子树 → 自身”的顺序。字节码中的ADD会从栈上弹出两个数这意味着栈顶必须是右操作数栈顶下一个是左操作数。这也是为什么 2.4 节的手工字节码里2和3先被压栈并执行MUL然后才和1做加法。4.3 符号表登记变量槽位顺手完成唯一性检查符号表在最小项目里就是一个变量名到槽位的映射。槽位编号从 0 开始每登记一个新变量就加一。这个设计完全对应真实编译器中的“为局部变量分配栈帧偏移量”只是这里分配的是虚拟机的vars字典键。class SymbolTable: def __init__(self): self.slots {} self.next_slot 0 def register(self, name): if name in self.slots: raise SyntaxError(f变量 {name} 重复声明) self.slots[name] self.next_slot self.next_slot 1 def lookup(self, name): if name not in self.slots: raise NameError(f变量 {name} 未声明) return self.slots[name]register抛出SyntaxError是因为重复声明属于“源代码写错了”问题和字符串文本强相关而lookup抛出NameError是因为使用未声明变量属于“名字解析失败”在语义上更接近运行期问题。这个区分并不绝对但合理。不过第 5 章会指出真正严谨的做法是把声明检查和代码生成分开。符号表在这里还承担了一个容易被忽略的职责它决定了int a; int b;中a是 0 号槽、b是 1 号槽。如果声明顺序变了生成的字节码里STORE和LOAD的参数也会变。这意味着 AST 打印、符号表打印、字节码打印三份信息必须能互相印证任何一份对不上问题就出在从上一份到这一份的转换过程中。对于只有一层的语言符号表不需要维护作用域嵌套。如果以后加入花括号和if/while就要改成栈式作用域进入作用域时压入一层新表离开时弹出。现在的实现作为起步是非常合适的。4.4 一个 30 行的栈式虚拟机执行字节码并打印结果虚拟机的实现很短但却是整个管线的终点。它维护一个操作数栈和一个变量存储字典逐条执行字节码指令。每条指令的实现对应 4.1 节表格里的一行说明class VM: def __init__(self): self.stack [] self.vars {} def run(self, code): ip 0 while ip len(code): instr code[ip] op instr[0] if op PUSH: self.stack.append(instr[1]) elif op LOAD: self.stack.append(self.vars[instr[1]]) elif op STORE: self.vars[instr[1]] self.stack.pop() elif op in (ADD, SUB, MUL, DIV): b self.stack.pop() a self.stack.pop() if op ADD: self.stack.append(a b) elif op SUB: self.stack.append(a - b) elif op MUL: self.stack.append(a * b) elif op DIV: self.stack.append(a // b) elif op PRINT: print(self.stack.pop()) elif op HALT: break else: raise RuntimeError(f未知指令 {op}) ip 1ADD/SUB/MUL/DIV分支先pop出右侧操作数再从栈顶取出左侧操作数这个顺序不能反。因为压栈顺序是左操作数先压、右操作数后压弹栈时右操作数自然先出。a // b是整数除法向零取整这个语义要在语言规范里写明。真实编译器的做法是在代码生成阶段就把除法语义固定下来而不是让虚拟机的实现来决定。入口函数把四个阶段串起来形成完整调用链def main(src): tokens tokenize(src) ast Parser(tokens).parse_program() symbols SymbolTable() code gen_program(ast, symbols) VM().run(code)到这个入口能跑通一个最小编译程序就真正立住了。后面所有的功能扩展都是在这条调用链上增加新的语法元素和新的指令分支。5. 五个高频踩坑记录现象、原因与排查方法5.1 优先级反转12*3算出 9而不是 7现象同一段源码1 2 * 3打印出 9而给乘号加括号的(1 2) * 3也打印出 9。看 AST 打印结果发现语法树的顶层节点是*加法和乘法完全同级了。原因递归下降解析器中运算符优先级靠“调用层级”体现谁在最内层谁优先。最内层的parse_factor只处理数字、变量和括号乘除必须单独放在一层parse_term中而加减放在最外层parse_expr。如果图省事把parse_expr写成一个循环直接调用parse_factor所有运算符都被当成同级优先级自然失效。解决先确认层级关系再写代码parse_expr调用parse_termparse_term调用parse_factor。调试时直接打印 AST看见BinOp *挂在BinOp 的右子树就说明乘法层级是对的。这个坑看似基础但每次调整语法时都很容易重新踩进去尤其是添加新运算符的时候。5.2 关键字边界被吞printx被解析成printx现象源代码某处写了一个名叫printx的变量编译器没有报错把它的第一次出现当成了print语句处理后面报出“变量 x 未声明”之类的奇怪错误或者干脆把后续内容当表达式解析到行尾。原因词法分析器如果在读到p、r、i、n、t五个字符后就立刻返回PRINT关键字没有检查printx中紧随其后的x字符就会把一整个标识符切成两个 token。这种问题在关键字恰好是另一个标识符前缀时一定会出现比如print、int这类短单词。解决词法分析时必须先把一整个字母数字串读完再判断这整个串是否为关键字。也就是始终先读完整标识符、再查表而不是在读的过程中逐字符匹配关键字。第 3.1 节代码中if name in KEYWORDS的写法就是为了修这个坑把printx和print的区分彻底交给标识符的完整匹配。5.3x -3直接报语法错误factor 没有处理一元负号现象a 0 - 3;能正常编译执行a -3;却在解析阶段报错。错误信息指向-号说明解析器在factor层看到负号时不知道该怎么处理。原因parse_factor只接受数字、标识符和括号负号没有被纳入表达式语法。负号在表达式中是“一元运算符”与被减数缺失的二元减号不同。很多人在设计表达式语法时只考虑了常见的二元运算符忽略了一元负号这个看起来很小但无处不在的语法元素。解决在parse_factor开头增加一个分支如果当前 token 是-就跳过它、解析后面的因子然后构造一个等价的BinOp(-, Number(0), factor)让代码生成阶段完全复用现有的减法指令。也可以新增一条NEG指令但小项目用零减因子更省事不需要动指令集和虚拟机。5.4 除零让整个 VM 直接崩溃执行期错误要有明确出口现象运行a 1 / 0;时 Python 解释器爆出ZeroDivisionError报错堆栈指向虚拟机的DIV分支。更麻烦的是此时操作数栈里残留着两个未消费的操作数后续的PRINT会打出一个完全不可预期的数。原因栈式虚拟机把算术运算暴露给了执行期所有运行期错误都发生在DIV执行的那一瞬间。没有检查除数是否为零也没有人定义“除零后虚拟机应该做什么”系统默认的异常就这样直接透传上来了。解决至少要处理两层。第一层在DIV分支中先检查除数是否为零为零时抛出一个带明确语义的RuntimeError(除零错误)同时保证不会向栈写入半成品。第二层如果希望编译期就拦截可以在gen_expr中检查除号右子树是否为Number(0)常量并直接扔出编译错误。后者只能查出常量除零但覆盖面已经不小。执行器的健壮性和编译器的报错质量往往就是在这种细节上拉开差距。5.5 变量未声明也能通过语义检查不能只依赖代码生成现象源代码里写了x 1;但前面根本没有int x;程序居然通过了编译虚拟机能跑到某一步才报 KeyError。还有另一种现象更隐蔽int a; int a;没有报重复声明两个声明各自分配了不同的槽位。原因代码生成阶段的SymbolTable.register确实会做查重但如果语义检查没有在代码生成前完整跑一遍 AST某些路径就会漏检。尤其是当语言开始加入if、while后未被执行的语句块同样需要检查漏检的场景会迅速变多。解决把“检查变量是否声明、是否重复声明”从代码生成中抽成一个独立函数在gen_program之前对 AST 显式遍历一遍。这个函数只检查名字相关的规则不生成任何指令。它的存在让编译器能够在生成字节码之前就拒绝非法程序而不是把错误留到 VM 运行期。哪怕目前只是给codegen增加一个前置调用也要保证这条链路是显式可见的这一点在以后扩展控制流时尤其重要。6. 加两个功能让编译器「毕业」控制流与两趟处理6.1 用 while 循环引入跳转指令与地址回填表达式和赋值跑通后控制流是让这个编译器“毕业”的第一步。以while (i 10) { i i 1; }为例需要新增三条指令LT比较两个数并压入 0 或 1JMPZ在栈顶为 0 时跳转JMP无条件跳转。对应字节码形状是LOOP: LOAD 0 PUSH 10 LT JMPZ END LOAD 0 PUSH 1 ADD STORE 0 JMP LOOP END: HALT执行到这里LOOP和END都是逻辑标签本质就是要填入的数字。生成代码时先记下每个标签在指令列表中的位置遇到JMPZ和JMP时先写占位符等全部指令生成完再把占位符替换成真实的目标地址。这就是编译器领域常说的“跳转目标回填”也是从玩具编译器走向真实编译器的一道重要分水岭。6.2 两趟处理与调试习惯有了控制流语义检查就不该再和代码生成挤在一起。我一般会在解析和代码生成之间加一个独立的第一趟遍历 AST收集所有变量声明并构建完整符号表再跑一遍检查所有使用都合法。这一趟完成后代码生成阶段遇到任何变量都直接从符号表查槽位不需要边生成边注册。好处是“先使用后声明”这类规则可以在语言层直接支持所有语义错误也都集中在同一阶段暴露。我还有一个坚持了很久的调试习惯无论编译器做得多小都必须保留 AST 打印和字节码打印两个函数。遇到任何怪异行为先打印 AST 看树形结构对不对再打印字节码看指令流对不对最后才去看 VM 的栈变化。绝大多数问题在第一步或第二步就能暴露出来真正需要单步调试虚拟机的机会少之又少。这个习惯救过我很多次每次写完一个语法扩展我都会重新跑一遍 dump 流程确认中间产物没有变形。希望帮到你。本文还有配套的精品资源点击获取
