东南大学编译原理实验：从词法分析到目标代码生成的完整编译器模拟系统实现

简介这份资源是东南大学软件学院编译原理课程的实验项目压缩包面向正在学习编译原理、需要动手实现完整编译器流程的高校学生与自学者。它围绕词法分析、语法分析、语义分析、中间代码生成、目标代码生成与代码优化等环节构建了一个从源代码到可执行代码的模拟系统适合课程实验复现、编译流程梳理与工程能力训练。包内共28个文件以12个java源文件和12个class编译产物为主体另含2个txt说明、1个iml工程配置与1个md文档整体约20KB体量轻便便于直接导入IDE阅读与调试。目录中可见词法分析器、语法分析器等模块划分配合说明文件可快速理解各阶段职责与调用关系。目前已有63人学习适合作为编译原理课程设计、实验报告撰写与编译器入门实践的参考素材帮助读者把抽象理论落到可运行的代码结构上。1. 从东南大学软件学院编译原理实验项目说起一个完整编译器模拟系统到底长什么样很多同学第一次拿到东南大学软件学院编译原理课程实验项目的任务书时第一反应是“这不就是写个能跑的四则运算解释器吗”。真正动手才发现从源代码到可执行代码的完整编译流程涉及词法分析、语法分析、语义分析、中间代码生成、目标代码优化五大阶段每个阶段都有独立的输入输出约定和错误处理要求。这个综合性实践平台的目标是构建一个从源代码到可执行代码的完整编译器模拟系统而不是只做其中某一个环节。适合已经学过编译原理理论课、需要把龙书里的自动机、文法、语法制导翻译真正落地成代码的本科生和研究生。如果你正在搜“编译原理实验怎么做”“词法分析语法分析怎么串起来”这篇笔记会按我实际带学生做这个项目的顺序把每个阶段的实现路径、参数设置和踩坑点讲清楚。2. 词法分析与语法分析从正则表达式到语法树的落地路径2.1 词法分析器为什么建议手写而不是直接上 Lex东南大学软件学院编译原理实验项目通常要求提交完整的编译器模拟系统词法分析是第一个要跑通的模块。很多同学第一反应是用 Flex/Lex 自动生成但课程实验的评分点往往在于你是否理解有限自动机DFA的构造过程。我一般会建议手写一个基于状态转移的词法分析器核心逻辑用 Python 或 Java 实现都行关键是能把标识符、关键字、运算符、界符、常量这几类 token 区分清楚。下面是一个最小可用的词法分析器骨架用 Python 写方便调试import re # token 类型定义 TOKEN_TYPES [ (KEYWORD, r\b(int|float|if|else|while|return)\b), (ID, r\b[a-zA-Z_][a-zA-Z0-9_]*\b), (NUMBER, r\b\d(\.\d)?\b), (OP, r[\-*/!]), (DELIM, r[;,(){}]), (SKIP, r[ \t\n]), ] def lex(source): tokens [] pos 0 while pos len(source): match None for ttype, pattern in TOKEN_TYPES: regex re.compile(pattern) match regex.match(source, pos) if match: text match.group(0) if ttype ! SKIP: tokens.append((ttype, text)) pos match.end() break if not match: raise SyntaxError(f非法字符 {source[pos]} 在位置 {pos}) return tokens # 测试 src int a 10; if (a 5) return a; for t in lex(src): print(t)这段代码的逻辑说明TOKEN_TYPES列表按优先级排列关键字必须放在标识符前面否则int会被识别成普通 ID。lex函数用re.match从当前位置尝试匹配匹配成功就推进pos失败就报词法错误。参数方面SKIP类型用来过滤空白字符但要注意换行符的处理——如果后续语法分析需要行号信息就不能简单跳过而应该记录行号。提示词法分析阶段最常见的翻车点是关键字和标识符的优先级顺序。把ID写在KEYWORD前面if和while就永远匹配不到关键字类型后面语法分析会直接崩掉。2.2 递归下降语法分析把文法直接翻译成函数语法分析阶段东南大学软件学院编译原理实验项目一般要求实现 LL(1) 或 LR(1) 分析器。如果文法已经消除了左递归和回溯递归下降是最直观的选择——每个非终结符对应一个函数函数体就是产生式的右部。以表达式文法为例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 match(self, ttype): tok self.peek() if tok[0] ttype: self.pos 1 return tok raise SyntaxError(f期望 {ttype}实际 {tok}) def parse_expr(self): # Expr - Term ((|-) Term)* node self.parse_term() while self.peek()[1] in (, -): op self.match(OP)[1] right self.parse_term() node (binop, op, node, right) return node def parse_term(self): # Term - Factor ((*|/) Factor)* node self.parse_factor() while self.peek()[1] in (*, /): op self.match(OP)[1] right self.parse_factor() node (binop, op, node, right) return node def parse_factor(self): tok self.peek() if tok[0] NUMBER: self.match(NUMBER) return (num, float(tok[1])) elif tok[0] ID: self.match(ID) return (id, tok[1]) elif tok[1] (: self.match(DELIM) node self.parse_expr() self.match(DELIM) # ) return node raise SyntaxError(f意外的 token: {tok})逻辑说明parse_expr处理加减parse_term处理乘除parse_factor处理数字、变量和括号。这种分层写法天然处理了运算符优先级不需要额外维护优先级表。参数方面self.pos是当前 token 索引peek()不消耗 tokenmatch()消耗并返回。如果文法里有左递归比如Expr - Expr Term递归下降会无限递归必须改写成Expr - Term ( Term)*的形式。注意语法分析阶段最容易踩的坑是错误恢复。一旦某个 token 匹配失败不要直接抛异常退出而应该跳到下一个分号或右括号再继续否则一个错误会导致后面所有正确代码都被误报。3. 语义分析与中间代码生成符号表、类型检查和四元式3.1 符号表的设计作用域链怎么建才不乱语义分析的核心是符号表。东南大学软件学院编译原理实验项目通常要求支持嵌套作用域比如函数内定义的变量不能在外面访问。我一般用栈式符号表进入一个作用域就压入一个新表离开就弹出。每个表用字典存变量名 - (类型, 值/地址)。class SymbolTable: def __init__(self): self.scopes [{}] # 全局作用域 def enter_scope(self): self.scopes.append({}) def exit_scope(self): self.scopes.pop() def declare(self, name, typ): if name in self.scopes[-1]: raise SemanticError(f重复定义: {name}) self.scopes[-1][name] typ def lookup(self, name): for scope in reversed(self.scopes): if name in scope: return scope[name] raise SemanticError(f未定义: {name})逻辑说明scopes列表的最后一个元素是当前作用域lookup从内到外查找实现了作用域链。参数方面declare只检查当前作用域是否重复允许内层遮蔽外层同名变量。如果实验要求支持函数重载符号表的值就不能只存类型还要存参数列表。3.2 四元式生成中间代码为什么选它中间代码生成阶段四元式是最常见的格式(op, arg1, arg2, result)。比如a b c * d会生成(*, c, d, t1) (, b, t1, t2) (, t2, _, a)生成四元式的关键是遍历语法树遇到二元运算就生成临时变量。下面是一个简化版的生成器class QuadGenerator: def __init__(self): self.quads [] self.temp_count 0 def new_temp(self): self.temp_count 1 return ft{self.temp_count} def gen(self, node): if node[0] num: return str(node[1]) elif node[0] id: return node[1] elif node[0] binop: left self.gen(node[2]) right self.gen(node[3]) temp self.new_temp() self.quads.append((node[1], left, right, temp)) return temp逻辑说明gen递归处理语法树返回操作数变量名或临时变量。binop节点先递归生成左右操作数再生成一条四元式。参数方面temp_count保证临时变量名不重复。如果实验要求做常量折叠优化可以在binop节点判断左右是否都是num是就直接计算结果不生成四元式。提示语义分析阶段最容易被忽略的是类型检查。比如int和float相加四元式里应该插入一条int2float转换指令否则目标代码生成时寄存器类型对不上运行结果会变成玄学。4. 目标代码优化与代码生成从四元式到可执行指令4.1 基本块划分与局部优化目标代码优化通常从基本块开始。基本块是连续执行的指令序列入口是第一条指令或跳转目标出口是跳转指令或最后一条。划分基本块后可以在块内做常量传播、公共子表达式消除、死代码删除。以公共子表达式消除为例遍历基本块内的四元式如果两条四元式的(op, arg1, arg2)完全相同第二条的结果可以直接替换为第一条的结果def eliminate_common_subexpr(quads): expr_map {} result [] for op, a1, a2, res in quads: key (op, a1, a2) if key in expr_map: # 替换后续所有对 res 的引用 result.append((, expr_map[key], _, res)) else: expr_map[key] res result.append((op, a1, a2, res)) return result逻辑说明expr_map记录已经计算过的表达式到结果的映射。如果当前四元式的表达式已经存在就生成一条赋值指令把之前的结果赋给当前变量。参数方面这个算法只在一个基本块内有效跨基本块需要数据流分析。4.2 目标代码生成寄存器分配的最小实现目标代码生成阶段最简单的策略是“每次运算都从内存加载到寄存器算完写回内存”。虽然效率低但能跑通完整流程。以 x86 风格汇编为例def gen_asm(quads): asm [] for op, a1, a2, res in quads: if op : asm.append(fMOV R0, {a1}) asm.append(fADD R0, {a2}) asm.append(fMOV {res}, R0) elif op *: asm.append(fMOV R0, {a1}) asm.append(fMUL R0, {a2}) asm.append(fMOV {res}, R0) elif op : asm.append(fMOV R0, {a1}) asm.append(fMOV {res}, R0) return asm逻辑说明每条四元式翻译成 2-3 条汇编指令。R0是临时寄存器所有运算都通过它中转。参数方面如果实验要求做寄存器分配优化可以把频繁使用的变量固定分配到R1、R2减少内存访问。但要注意寄存器数量有限变量多了还是要溢出到内存。注意目标代码生成阶段最常见的翻车是寄存器冲突。比如a b c和d a * b连续执行如果a还在R0里没写回内存第二条指令又覆盖了R0结果就错了。血泪经验是每条四元式结束后如果结果变量后续还会被用到必须确保它已经写回内存或分配了固定寄存器。5. 避坑与排查编译原理实验里最容易翻车的 5 个地方5.1 词法分析报“非法字符”但源文件里根本找不到现象词法分析器在某个位置报非法字符但用编辑器打开源文件那个位置看起来是空的。原因源文件里混入了不可见字符比如 UTF-8 BOM 头、全角空格、制表符和空格的混合。解决在读取源文件时统一做source.replace(\ufeff, ).replace(\u3000, )并且用repr()打印出错位置的字符确认它的 Unicode 码点。5.2 语法分析递归下降时栈溢出现象解析一个稍微复杂的表达式程序直接RecursionError。原因文法里有左递归比如Expr - Expr Term递归下降会无限调用parse_expr。解决改写文法消除左递归变成Expr - Term ( Term)*用循环代替递归。如果实验要求必须用原始文法就改用 LR 分析器用栈模拟而不是函数递归。5.3 语义分析阶段符号表查不到变量现象变量明明在上一行定义了下一行却报“未定义”。原因进入新作用域时压入了新表但退出时忘记弹出或者lookup只查了当前作用域。解决检查enter_scope和exit_scope是否成对出现lookup必须从scopes[-1]倒序遍历到scopes[0]。另外函数参数要在进入函数体作用域之前就声明。5.4 四元式生成时临时变量名冲突现象两个不同的表达式生成了同名的临时变量t1导致目标代码计算结果错乱。原因temp_count是全局的但多个函数或多次调用之间没有重置或隔离。解决把temp_count绑定到每个函数或每个基本块或者用函数名_序号的格式生成临时变量名。更稳妥的做法是每次生成四元式前检查当前作用域内是否已有同名临时变量。5.5 目标代码优化后程序行为改变现象开启常量折叠和公共子表达式消除后程序输出和未优化时不一致。原因优化时没有考虑副作用比如a f() f()公共子表达式消除会把两次函数调用合并成一次但f()可能有副作用。解决只对纯运算做优化函数调用、数组访问、指针解引用这些有副作用的节点不能参与公共子表达式消除。常量折叠时也要注意浮点数的精度问题0.1 0.2折叠成0.3可能和运行时结果有微小差异。6. 进阶技巧用差分测试验证编译器正确性完整编译器模拟系统跑通之后怎么确认它生成的代码是对的我一般用差分测试同一段源代码分别用你的编译器和 Python 的eval或exec执行比较输出结果。如果结果不一致就缩小输入范围定位到具体是哪个阶段出了问题。具体做法是写一个测试脚本随机生成算术表达式和变量赋值语句分别走两条路径import random def random_expr(depth0): if depth 3 or random.random() 0.3: return str(random.randint(1, 10)) op random.choice([, -, *, /]) left random_expr(depth 1) right random_expr(depth 1) return f({left} {op} {right}) def differential_test(n100): for i in range(n): expr random_expr() # 路径1你的编译器 tokens lex(expr) parser Parser(tokens) ast parser.parse_expr() quads QuadGenerator().gen(ast) # 这里需要你实现一个四元式解释器来求值 my_result interpret_quads(quads) # 路径2Python 原生求值 py_result eval(expr) if abs(my_result - py_result) 1e-6: print(f不一致: {expr}, 编译器{my_result}, Python{py_result}) return print(f{n} 个随机表达式全部通过) differential_test()逻辑说明random_expr递归生成随机表达式differential_test分别用编译器和 Python 求值比较结果。参数方面depth控制表达式嵌套深度避免生成过长的表达式导致递归过深。n是测试轮数一般跑 1000 轮以上才能覆盖边界情况。这个方法的优势在于你不需要手动构造测试用例随机生成的表达式会自然覆盖各种运算符组合和优先级情况。如果发现不一致把出错的表达式单独拿出来逐步打印词法分析、语法分析、四元式生成的结果就能定位到具体是哪个阶段的问题。提示差分测试时要注意除零错误和浮点数精度。eval遇到除零会抛异常你的编译器也应该在语义分析阶段就检查除零而不是等到运行时。浮点数比较用abs(a - b) 1e-6不要用。我自己的习惯是每完成一个阶段就先跑一遍差分测试不要等五个阶段全写完再联调。词法分析写完就测 token 序列语法分析写完就测语法树结构四元式写完就测中间代码解释器的输出。这样出问题时你永远知道是刚改的那部分代码的锅不用在几千行代码里大海捞针。希望帮到你。本文还有配套的精品资源点击获取