从零手写小型编译程序：词法分析、语法分析与代码生成实战

简介这份资源面向学习编译原理、需要完成课程设计的高校学生围绕SLR(1)分析法实现一个小型编译程序解决从高级语言源程序到四元式程序翻译的实践问题。资源包共14个文件约22KB以c源码、dat测试数据、asm汇编输出、med中间结果和txt说明文档为主分别对应编译主程序、输入用例、目标代码与运行结果记录结构紧凑便于对照调试。目前已有2775人学习下载说明其在同类课设中具有较高参考价值。读者可据此完成必做的第一阶段翻译任务理解词法、语法与SLR(1)分析表的构造流程并借助测试文件验证表达式分析过程选做部分还涉及四元式到汇编的二次翻译为进阶改进留出空间。整体适合作为编译原理课设的起步模板与排错参照。1. 从零手写一个小型编译程序为什么它是打通计算机基础的最短路径很多人第一次听到“实现一个小型编译程序”时第一反应是“这玩意儿离我太远”。毕竟日常工作里写业务代码、调接口、改配置才是常态编译器像是另一个世界的东西。但真实情况恰恰相反一个只支持整数四则运算、变量赋值和打印语句的迷你编译器核心代码量通常在 800 到 1500 行之间用 Python 或 C 都能在两三天内跑通。它之所以值得动手是因为它把词法分析、语法分析、语义分析、中间代码生成这条链路完整地串了一遍而这套链路正是你排查“为什么这行代码不生效”“为什么类型转换会崩”这类问题的底层依据。这篇文章面向的是有基本编程能力、但没系统写过编译器的工程师。我会按“先跑通最小闭环再逐步加功能”的思路把一个小型编译程序的实现路径拆成可复现的步骤。你不需要先学完龙书也不需要啃完形式语言与自动机只要会写递归函数、理解栈和树就能跟着做下来。最终你会得到一个能把源码文本变成可执行结果的完整程序而不是一堆零散的知识点。2. 小型编译程序的四层架构从字符流到可执行结果2.1 为什么先定架构再写代码四层职责划分一个最小可用的编译程序通常拆成四层词法分析器Lexer、语法分析器Parser、语义分析器Semantic Analyzer、代码生成器Code Generator。这四层不是学术上的强制划分而是工程上最省心的切法。词法分析负责把字符流切成 token语法分析负责把 token 流组织成抽象语法树AST语义分析负责检查变量是否声明、类型是否匹配代码生成负责把 AST 翻译成目标形式——可以是直接求值的解释器也可以是栈式虚拟机的指令序列。我一般建议初学者先做“解释器式编译器”不生成机器码而是遍历 AST 直接算出结果。这样做的好处是省掉了目标平台指令集、寄存器分配、链接器这一大坨东西能把注意力集中在编译前端。等前端跑通了再换成生成三地址码或栈式指令难度曲线会平滑很多。四层之间的数据流是单向的源码字符串 → token 列表 → AST → 带注解的 AST → 执行结果。每一层的输出都是下一层的输入层与层之间通过明确的数据结构解耦。这种解耦带来的直接好处是排错时能快速定位如果结果不对先看 token 切得对不对再看 AST 建得对不对最后才怀疑语义检查和代码生成。2.2 用 Python 搭出 Lexer 的最小骨架词法分析器的任务很单纯从左到右扫描字符遇到数字就攒成整数 token遇到字母就攒成标识符 token遇到运算符就单独成 token遇到空白就跳过。下面是一个能处理整数、标识符、四则运算符和括号的 Lexer 骨架。import re TOKEN_TYPES [ (NUMBER, r\d), (ID, r[a-zA-Z_]\w*), (PLUS, r\), (MINUS, r-), (MUL, r\*), (DIV, r/), (LPAREN, r\(), (RPAREN, r\)), (ASSIGN, r), (SEMI, r;), (SKIP, r[ \t\n]), (MISMATCH, r.), ] class Lexer: def __init__(self, text): self.text text self.pos 0 self.tokens [] def tokenize(self): while self.pos len(self.text): for ttype, pattern in TOKEN_TYPES: regex re.compile(pattern) match regex.match(self.text, self.pos) if match: text match.group(0) if ttype ! SKIP: self.tokens.append((ttype, text)) self.pos match.end() break else: raise SyntaxError(f非法字符: {self.text[self.pos]}) return self.tokens这段代码的关键点有三个。第一TOKEN_TYPES的顺序决定了匹配优先级NUMBER必须排在ID前面否则123会被当成标识符的一部分。第二SKIP类型用来吞掉空白字符不产生 token但必须保留在列表里否则空白会触发MISMATCH。第三MISMATCH放在最后作为兜底任何没被前面规则匹配的字符都会落到这里方便报错时给出具体位置。参数方面self.pos是当前扫描位置每次匹配成功后推进到match.end()。如果你要支持浮点数把NUMBER的正则改成\d(\.\d)?即可但要注意1.和.1这两种边界情况通常需要额外处理。如果要支持注释加一条(COMMENT, r//[^\n]*)并归入SKIP类即可。2.3 递归下降 Parser把 token 流变成 AST语法分析器我推荐用递归下降原因是它写起来直观、调试方便每个非终结符对应一个函数函数体就是该非终结符的产生式。对于表达式语法需要处理运算符优先级常见做法是分层expr → term ((|-) term)*term → factor ((*|/) factor)*factor → NUMBER | ID | ( 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 consume(self, expectedNone): ttype, text self.peek() if expected and ttype ! expected: raise SyntaxError(f期望 {expected}实际 {ttype}) self.pos 1 return (ttype, text) def parse_expr(self): node self.parse_term() while self.peek()[0] in (PLUS, MINUS): op self.consume()[0] right self.parse_term() node (BinOp, op, node, right) return node def parse_term(self): node self.parse_factor() while self.peek()[0] in (MUL, DIV): op self.consume()[0] right self.parse_factor() node (BinOp, op, node, right) return node def parse_factor(self): ttype, text self.peek() if ttype NUMBER: self.consume() return (Num, int(text)) elif ttype ID: self.consume() return (Var, text) elif ttype LPAREN: self.consume(LPAREN) node self.parse_expr() self.consume(RPAREN) return node else: raise SyntaxError(f意外的 token: {ttype})AST 节点用元组表示(BinOp, op, left, right)表示二元运算(Num, value)表示数字字面量(Var, name)表示变量引用。这种表示法虽然不如类定义优雅但胜在轻量打印出来一眼就能看懂结构。parse_expr和parse_term的循环结构保证了左结合性比如1-2-3会被解析成((1-2)-3)而不是(1-(2-3))。如果你要加赋值语句和语句序列需要在 Parser 顶层加parse_statement和parse_program语句之间用分号分隔。赋值语句的产生式是ID expr ;解析时先看peek()是不是ID且下一个 token 是ASSIGN如果是就按赋值处理否则按表达式语句处理。3. 语义检查与代码生成让 AST 真正跑起来3.1 符号表与类型检查三个必须拦住的错误语义分析阶段的核心任务是维护符号表并检查变量使用是否合法。对于只支持整数的小型编译程序符号表可以用一个字典实现键是变量名值是变量类型这里只有int一种。必须拦住的错误有三类使用未声明的变量、重复声明同名变量、除数为零的字面量。class SemanticAnalyzer: def __init__(self): self.symbols {} def visit(self, node): if node[0] Num: return int elif node[0] Var: name node[1] if name not in self.symbols: raise NameError(f未声明的变量: {name}) return self.symbols[name] elif node[0] BinOp: left_type self.visit(node[2]) right_type self.visit(node[3]) if left_type ! int or right_type ! int: raise TypeError(运算符两侧必须是整数) if node[1] DIV and node[3][0] Num and node[3][1] 0: raise ZeroDivisionError(除数字面量为零) return int elif node[0] Assign: name node[1] expr_type self.visit(node[2]) self.symbols[name] expr_type return expr_type这段代码里visit函数根据节点类型分派处理逻辑。Assign节点在检查完右值类型后把变量名和类型写入符号表。注意符号表是在语义分析阶段填充的代码生成阶段直接复用不需要重新推导类型。如果你要支持块级作用域符号表需要改成栈式结构进入块时压入新字典离开块时弹出。一个容易被忽略的点是语义分析应该在代码生成之前完整跑一遍而不是边生成边检查。这样做的好处是错误能在执行前全部暴露出来不会出现“跑了一半才崩”的情况。对于小型编译程序这个顺序差异不大但养成习惯后扩展到更大规模时能省很多事。3.2 树遍历解释器二十行代码让 AST 出结果代码生成阶段我选择直接写树遍历解释器因为它最直观也最容易验证前端是否正确。解释器的eval函数递归下降遇到Num返回数值遇到Var查环境遇到BinOp递归求左右再运算。class Interpreter: def __init__(self): self.env {} def eval(self, node): if node[0] Num: return node[1] elif node[0] Var: return self.env[node[1]] elif node[0] BinOp: left self.eval(node[2]) right self.eval(node[3]) op node[1] if op PLUS: return left right if op MINUS: return left - right if op MUL: return left * right if op DIV: return left // right elif node[0] Assign: value self.eval(node[2]) self.env[node[1]] value return valueself.env是运行时的变量环境和语义分析阶段的符号表分开维护。这样做的好处是语义分析只负责检查不产生副作用解释器只负责执行不重复检查。如果你要做常量折叠优化可以在语义分析阶段把(BinOp, op, (Num, a), (Num, b))直接替换成(Num, 计算结果)这样解释器执行时少递归一层。除法这里用了//而不是/是为了保持整数语义。如果你要支持浮点数把//改成/同时把词法分析里的NUMBER正则改成支持小数点即可。注意整数除法在负数情况下的行为在不同语言里不一致Python 的//是向下取整C 的/是向零取整做跨语言对比时要留意这个差异。3.3 把四层串起来一个完整的编译执行入口把 Lexer、Parser、SemanticAnalyzer、Interpreter 串起来就是一个完整的小型编译程序。入口函数接收源码字符串依次调用四层返回执行结果。def run(source): lexer Lexer(source) tokens lexer.tokenize() parser Parser(tokens) ast parser.parse_program() analyzer SemanticAnalyzer() analyzer.visit(ast) interpreter Interpreter() return interpreter.eval(ast) if __name__ __main__: src x 3 4 * 2; y (x - 1) / 2; y; print(run(src)) # 输出 5这段代码里parse_program需要你自行实现逻辑是循环调用parse_statement直到 token 耗尽。每个语句解析完后AST 是一个语句列表语义分析和解释器需要能处理列表节点。如果你只做单表达式求值可以跳过parse_program直接调parse_expr。参数方面source是完整的源码字符串分号是语句分隔符最后一个表达式的结果作为整个程序的返回值。这种设计借鉴了 REPL 的求值习惯方便快速验证。如果你要做成命令行工具可以用sys.argv接收文件路径读文件内容后传给run函数。4. 避坑与排查小型编译程序最容易翻车的五个地方4.1 词法分析把关键字当成标识符现象输入if x 0时if被识别成ID而不是关键字导致语法分析报“意外的 token”。原因是词法规则里ID的正则[a-zA-Z_]\w*会优先匹配if而关键字规则排在后面永远轮不到。解决在ID匹配成功后额外查一张关键字表如果文本在表里就改判为对应关键字类型。关键字表用字典或集合都行查表是 O(1)对性能没影响。注意关键字表要覆盖你语法里用到的所有保留字漏一个就会在语法分析阶段炸出来。4.2 递归下降解析器遇到左递归直接栈溢出现象写产生式expr → expr term | term时parse_expr第一件事就是递归调用自己程序瞬间栈溢出。原因是左递归在递归下降里会无限展开。解决把左递归改写成右递归加循环即expr → term ( term)*对应代码里先用parse_term拿到第一个操作数再用while循环处理后续的。这个改写是机械的任何形如A → A α | β的产生式都能改成A → β (α)*。改写后结合性从右结合变成左结合正好符合加减乘除的语义。4.3 符号表在循环里被反复覆盖现象解析x 1; x 2; x;时最终输出是 2但如果你在语义分析里每遇到一次赋值就清空符号表第二次赋值会报“未声明变量”。原因是符号表的生命周期搞错了应该在整个程序范围内持续存在而不是每条语句重置。解决符号表在SemanticAnalyzer初始化时创建一次整个分析过程共用同一个实例。如果你要支持块级作用域用栈式符号表进入块压栈、离开块弹栈但全局符号表始终在栈底。判断变量是否声明时从栈顶往下查查到就用查不到才报错。4.4 整数除法在负数上结果和预期不一致现象计算-7 / 2时Python 的//返回-4而 C 的/返回-3。如果你的测试用例里混了负数除法结果会对不上。解决先明确你的编译程序采用哪种除法语义。如果对齐 C 语言用int(left / right)代替left // right因为 Python 的/是浮点除法int()截断 toward zero。如果对齐 Python保留//。这个选择没有对错但要在文档里写清楚否则用户会当成 bug 报上来。4.5 错误信息只报行号不报列号现象源码里有个拼写错误报错信息只写“第 3 行语法错误”但第 3 行有二十个 token你不知道是哪个出的问题。解决在 Lexer 里记录每个 token 的行号和列号Parser 报错时把当前 token 的位置一起打出来。列号可以从self.pos反推或者维护一个line_start变量记录每行起始位置。错误信息格式建议写成第 3 行第 12 列: 期望 RPAREN实际 SEMI这样用户能直接定位到字符。别小看这个改进调试效率能差好几倍。5. 从解释器到字节码给小型编译程序加一层栈式虚拟机当你把树遍历解释器跑通之后下一步值得做的是把 AST 编译成栈式虚拟机的字节码。这一步的收益不是性能而是让你真正理解“编译”和“解释”的分界线解释器直接遍历 AST字节码编译器先把 AST 翻译成线性指令序列再由虚拟机执行。多出来的这层翻译就是很多真实编译器如 CPython、JVM的核心结构。栈式虚拟机的指令集很小通常只需要PUSH、LOAD、STORE、ADD、SUB、MUL、DIV、PRINT、HALT这几条。编译规则也简单Num节点生成PUSH valueVar节点生成LOAD nameBinOp节点先递归编译左右子树再生成对应运算指令。赋值语句生成右值指令后跟STORE name。class BytecodeCompiler: def __init__(self): self.instructions [] def compile(self, node): if node[0] Num: self.instructions.append((PUSH, node[1])) elif node[0] Var: self.instructions.append((LOAD, node[1])) elif node[0] BinOp: self.compile(node[2]) self.compile(node[3]) op_map {PLUS: ADD, MINUS: SUB, MUL: MUL, DIV: DIV} self.instructions.append((op_map[node[1]],)) elif node[0] Assign: self.compile(node[2]) self.instructions.append((STORE, node[1])) return self.instructions生成的指令序列是线性的执行时用一个栈保存中间值。PUSH把常量压栈LOAD把变量值压栈ADD弹出两个值相加后压回结果STORE弹出栈顶存入变量。这种“后进先出”的求值顺序天然匹配表达式树的后序遍历不需要额外处理优先级。虚拟机本身用一个循环加一个栈就能实现大约三十行代码。执行时维护pc程序计数器指向当前指令stack保存操作数env保存变量。遇到HALT就停止栈顶就是最终结果。如果你想验证字节码编译器是否正确可以写一个对比测试同一段源码分别用树遍历解释器和字节码虚拟机执行结果必须一致。这个对比测试能帮你抓出绝大多数编译错误。我自己的习惯是先把字节码打印出来人工检查一遍确认指令顺序符合后序遍历再跑虚拟机。这一步多花五分钟能省掉后面半小时的调试。另外字节码的好处是可序列化你可以把编译结果存成文件下次直接加载执行省掉词法和语法分析的开销。对于小型编译程序这个优化意义不大但理解这个思路对以后做 DSL 或规则引擎很有帮助。最后说一个我踩过的坑栈式虚拟机在遇到DIV时弹出顺序是右操作数先出栈左操作数后出栈所以计算时要写成left stack.pop(); right stack.pop(); stack.append(left // right)顺序反了结果就变成right // left。这个错误在测试用例只包含加法和乘法时不会暴露一旦加上减法和除法就会翻车。希望帮到你。本文还有配套的精品资源点击获取