OUC编译原理实验全流程：从词法分析到目标代码生成的避坑指南

简介这份资源是中国海洋大学2020年春季学期编译原理课程的完整实验代码合集面向正在学习编译原理的高校学生与自学者帮助读者把词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、错误处理与编译器综合这八个阶段逐一落地实践。压缩包共74个文件约774KB以C语言源码、Flex词法规则文件、Bison语法规则文件、头文件、Makefile及可执行程序为主另附实验要求文档与测试用例覆盖从源程序到可执行文件的完整编译流程。资源已有4411人学习下载读者可参照各实验的规则文件与构建脚本理解递归下降、LL(1)、LALR(1)等解析方法掌握符号表构建、类型检查、三地址码生成与常量折叠等优化策略并借助错误诊断模块学习如何让编译器输出更友好的提示信息适合作为课程实验对照与编译器构造入门的实践参考。1. 从 OUC 编译原理全部实验说起一套能跑通的编译器前端流水线长什么样如果你正在搜 OUC 编译原理全部实验大概率不是想听“编译原理是计算机核心课程”这种场面话而是想知道这套实验到底要做几个、每个卡在哪、怎么把词法分析到目标代码生成这条链路真正跑通。我当年做这套实验时最大的感受是编译原理实验不是“写几个独立程序”而是一条流水线前一阶段的输出格式直接决定后一阶段能不能开工。OUC 这套实验通常覆盖词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成几个环节每个环节单独验收但真正折磨人的是接口对齐。这篇文章面向正在做或准备做这套实验的人把每个阶段的实现路径、参数设置和常见翻车点讲清楚让你少走我当年走过的弯路。2. 词法分析与语法分析从正则到语法树的落地路径2.1 词法分析器的最小实现与 token 设计词法分析是整个流水线的入口它的输出质量直接决定后续阶段是否顺畅。常见做法是用有限自动机DFA手工构造或者用 flex 这类工具生成。我一般建议先手工写一遍理解状态转移再用工具对照验证。先定义 token 类型。以 C 语言子集为例需要覆盖关键字、标识符、常量、运算符和界符# token 类型定义 TOKEN_TYPES { KEYWORD: [int, float, if, else, while, return], OPERATOR: [, -, *, /, , , !, , , , ], DELIMITER: [(, ), {, }, ;, ,], ID: None, # 标识符正则匹配 NUMBER: None, # 数字常量 EOF: None # 结束标记 }逻辑说明关键字和运算符用查表法匹配标识符和数字用正则表达式识别。参数上标识符的正则建议用[a-zA-Z_][a-zA-Z0-9_]*数字常量区分整数和浮点\d\.\d|\d。注意最长匹配原则——遇到不能先匹配成两个这是词法分析最经典的坑。import re def tokenize(source): tokens [] pos 0 while pos len(source): # 跳过空白和注释 if source[pos].isspace(): pos 1 continue if source[pos:pos2] //: while pos len(source) and source[pos] ! \n: pos 1 continue # 匹配标识符或关键字 m re.match(r[a-zA-Z_][a-zA-Z0-9_]*, source[pos:]) if m: word m.group() ttype KEYWORD if word in TOKEN_TYPES[KEYWORD] else ID tokens.append((ttype, word)) pos len(word) continue # 匹配数字 m re.match(r\d\.\d|\d, source[pos:]) if m: tokens.append((NUMBER, m.group())) pos len(m.group()) continue # 匹配双字符运算符 if source[pos:pos2] in (, !, , ): tokens.append((OPERATOR, source[pos:pos2])) pos 2 continue # 匹配单字符运算符和界符 if source[pos] in -*/: tokens.append((OPERATOR, source[pos])) pos 1 continue if source[pos] in (){};,: tokens.append((DELIMITER, source[pos])) pos 1 continue raise SyntaxError(f非法字符: {source[pos]} 位置: {pos}) tokens.append((EOF, )) return tokens参数说明pos是当前扫描位置每次匹配后必须正确推进否则会死循环。双字符运算符的匹配必须放在单字符之前这是优先级问题。如果实验要求输出 token 序列到文件格式一般是每行(类型, 值)注意和后续语法分析器的输入格式对齐。2.2 递归下降语法分析器的构造与 AST 输出语法分析阶段OUC 实验通常要求实现 LL(1) 或 LR(1) 分析器。递归下降法最直观适合手写LR 法更通用但需要构造分析表。我建议先写递归下降因为调试成本低能快速验证文法是否正确。假设文法如下program - stmt_list stmt_list - stmt stmt_list | ε stmt - assign_stmt | if_stmt | while_stmt | block assign_stmt- ID expr ; if_stmt - if ( expr ) stmt else stmt while_stmt - while ( expr ) stmt block - { stmt_list } expr - term expr_tail expr_tail - term expr_tail | - term expr_tail | ε term - factor term_tail term_tail - * factor term_tail | / factor term_tail | ε factor - ID | NUMBER | ( expr )对应的递归下降代码框架class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 self.ast [] def peek(self): return self.tokens[self.pos] if self.pos len(self.tokens) else (EOF, ) def match(self, ttype, valueNone): tok self.peek() if tok[0] ttype and (value is None or tok[1] value): self.pos 1 return tok raise SyntaxError(f期望 {ttype} {value}实际 {tok}) def parse_program(self): while self.peek()[0] ! EOF: self.ast.append(self.parse_stmt()) return self.ast def parse_stmt(self): tok self.peek() if tok[0] KEYWORD and tok[1] if: return self.parse_if() elif tok[0] KEYWORD and tok[1] while: return self.parse_while() elif tok[0] DELIMITER and tok[1] {: return self.parse_block() elif tok[0] ID: return self.parse_assign() else: raise SyntaxError(f无法识别的语句: {tok}) def parse_assign(self): name self.match(ID)[1] self.match(OPERATOR, ) expr self.parse_expr() self.match(DELIMITER, ;) return (assign, name, expr) def parse_expr(self): left self.parse_term() while self.peek()[1] in (, -): op self.match(OPERATOR)[1] right self.parse_term() left (op, left, right) return left def parse_term(self): left self.parse_factor() while self.peek()[1] in (*, /): op self.match(OPERATOR)[1] right self.parse_factor() left (op, left, right) return left def parse_factor(self): tok self.peek() if tok[0] NUMBER: self.pos 1 return (num, tok[1]) elif tok[0] ID: self.pos 1 return (id, tok[1]) elif tok[1] (: self.pos 1 expr self.parse_expr() self.match(DELIMITER, )) return expr raise SyntaxError(f因子解析失败: {tok})逻辑说明每个非终结符对应一个函数函数内部按产生式顺序匹配 token。peek()用于前瞻match()用于消费并校验。参数上self.pos是 token 流指针必须保证每个分支最终都推进指针否则会死循环。AST 用嵌套元组表示方便后续遍历。提示递归下降的陷阱在于左递归。如果文法有expr - expr term这种形式必须改写为右递归或消除左递归否则会无限递归。2.3 语法错误恢复的三种策略实验验收时老师往往会给几个错误用例看你的分析器能不能报错并继续。常见策略有三种恐慌模式、短语级恢复和错误产生式。恐慌模式最简单——发现错误后丢弃 token 直到遇到分号或右花括号然后继续分析。短语级恢复是在特定位置插入缺失 token比如缺少分号时自动补上。错误产生式则是在文法里显式加入错误规则。我一般用恐慌模式实现成本低且效果够用def parse_stmt_with_recovery(self): try: return self.parse_stmt() except SyntaxError as e: print(f语法错误: {e}) # 丢弃直到分号或右花括号 while self.peek()[0] ! EOF: if self.peek()[1] in (;, }): self.pos 1 break self.pos 1 return (error, str(e))参数说明恢复粒度的选择很关键。以分号为界适合语句级恢复以右花括号为界适合块级恢复。如果错误嵌套太深可能需要多级恢复。注意恢复后要保证 token 指针正确推进否则会陷入死循环。3. 语义分析与中间代码生成让 AST 变成四元式3.1 符号表的组织与作用域处理语义分析的核心是符号表。每个标识符需要记录类型、作用域层级、存储位置等信息。常见做法是用栈式符号表进入作用域时压栈退出时弹栈。class SymbolTable: def __init__(self): self.scopes [{}] # 栈底是全局作用域 def enter_scope(self): self.scopes.append({}) def exit_scope(self): if len(self.scopes) 1: self.scopes.pop() def declare(self, name, type_info): if name in self.scopes[-1]: raise SemanticError(f重复声明: {name}) self.scopes[-1][name] type_info def lookup(self, name): for scope in reversed(self.scopes): if name in scope: return scope[name] raise SemanticError(f未声明: {name})逻辑说明scopes列表模拟作用域栈declare只在当前作用域检查重复lookup从内到外查找。参数上type_info可以是int、float或更复杂的结构体描述。注意 C 语言的作用域规则——内层可以遮蔽外层同名变量但同一层不能重复声明。3.2 四元式生成的遍历框架与参数约定中间代码常用四元式(op, arg1, arg2, result)。遍历 AST 时每个节点返回一个临时变量名父节点用这些临时变量构造四元式。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 node[1] if node[0] id: return node[1] if node[0] in (, -, *, /): left self.gen(node[1]) right self.gen(node[2]) temp self.new_temp() self.quads.append((node[0], left, right, temp)) return temp if node[0] assign: value self.gen(node[2]) self.quads.append((, value, _, node[1])) return node[1] raise SemanticError(f未知节点: {node[0]})参数说明temp_count保证临时变量名唯一。四元式的result字段对于赋值语句是变量名对于运算表达式是临时变量。注意_表示空参数后续优化阶段会用到这个约定。3.3 类型检查与隐式转换的插入时机类型检查在生成四元式之前做。如果int和float混合运算需要插入转换指令。常见做法是在 AST 节点上标注类型遍历时检查并插入int2float四元式。def check_and_convert(self, left, right, op): lt self.get_type(left) rt self.get_type(right) if lt rt: return left, right if lt int and rt float: temp self.new_temp() self.quads.append((int2float, left, _, temp)) return temp, right if lt float and rt int: temp self.new_temp() self.quads.append((int2float, right, _, temp)) return left, temp raise SemanticError(f类型不匹配: {lt} {op} {rt})逻辑说明转换只向精度更高的方向做避免精度丢失。参数上get_type需要查符号表或从 AST 节点推断。注意赋值语句也要检查——把float赋给int变量需要报错或显式转换具体看实验要求。4. 代码优化与目标代码生成从四元式到可执行指令4.1 局部优化的三个实用 Pass代码优化实验通常要求实现至少两种优化。我推荐从常量折叠、公共子表达式消除和死代码消除入手实现简单且效果明显。常量折叠遍历四元式如果两个操作数都是常量直接计算结果并替换。def constant_folding(quads): result [] for op, a1, a2, res in quads: if op in (, -, *, /) and a1.isdigit() and a2.isdigit(): val eval(f{a1}{op}{a2}) result.append((, str(val), _, res)) else: result.append((op, a1, a2, res)) return result公共子表达式消除用哈希表记录已计算过的表达式遇到相同表达式直接复用结果。def cse(quads): expr_map {} result [] for op, a1, a2, res in quads: key (op, a1, a2) if key in expr_map: result.append((, expr_map[key], _, res)) else: expr_map[key] res result.append((op, a1, a2, res)) return result死代码消除标记所有被使用的变量删除定义但未被使用的四元式。注意副作用——函数调用不能随便删。4.2 目标代码生成的寄存器分配策略目标代码生成阶段如果实验要求生成汇编寄存器分配是难点。简单做法是用栈式分配——所有变量放栈上运算时加载到寄存器算完写回。虽然效率低但正确性容易保证。def gen_asm(quads): asm [] for op, a1, a2, res in quads: if op : asm.append(fMOV R0, {a1}) asm.append(fMOV {res}, R0) elif op in (, -, *, /): asm.append(fMOV R0, {a1}) asm.append(fMOV R1, {a2}) opcode {: ADD, -: SUB, *: MUL, /: DIV}[op] asm.append(f{opcode} R0, R1) asm.append(fMOV {res}, R0) return asm参数说明R0、R1是通用寄存器。如果寄存器不够用需要引入溢出处理——把暂时不用的变量写回栈。注意除法要处理除零实验里可以简化处理但生产环境必须检查。4.3 从四元式到汇编的映射表设计映射表决定每种四元式对应哪些汇编指令。建议用字典组织方便扩展四元式操作汇编模板备注MOV R0, arg1; MOV result, R0赋值MOV R0, arg1; ADD R0, arg2; MOV result, R0加法-MOV R0, arg1; SUB R0, arg2; MOV result, R0减法*MOV R0, arg1; MUL R0, arg2; MOV result, R0乘法/MOV R0, arg1; DIV R0, arg2; MOV result, R0除法需检查除零int2floatCVTIF R0, arg1; MOV result, R0类型转换注意不同实验环境的目标架构可能不同映射表要根据实际指令集调整。如果实验只要求生成三地址码可以跳过汇编映射。5. 避坑与排查OUC 编译原理实验里最容易翻车的五个点5.1 词法分析最长匹配失效导致 token 切分错误现象输入ab被切分成a、、、b语法分析报错。 原因单字符运算符的匹配优先级高于双字符或者正则没有按最长匹配原则组织。 解决把双字符运算符的匹配放在单字符之前或者用正则的贪婪模式|!|||[-*/]统一匹配。5.2 递归下降遇到左递归导致栈溢出现象分析器运行后无限递归最终RecursionError。 原因文法中存在直接左递归如expr - expr term。 解决消除左递归改写为expr - term expr_tailexpr_tail - term expr_tail | ε。或者改用 LR 分析器。5.3 符号表作用域未正确弹栈导致变量泄漏现象内层块声明的变量在外层可见或者退出块后变量仍然存在。 原因enter_scope和exit_scope没有配对调用或者异常路径下跳过了exit_scope。 解决用try...finally保证exit_scope一定执行或者在 AST 遍历的块节点入口和出口严格配对。5.4 四元式临时变量命名冲突现象优化后变量被错误覆盖运行结果不对。 原因临时变量计数器在多个阶段之间没有重置或共享导致重名。 解决每个阶段用独立的计数器或者用全局唯一 ID 生成器。优化阶段引入的新临时变量要避开已有名字。5.5 目标代码生成时寄存器分配不当导致数据覆盖现象汇编执行结果和预期不符某个中间值被后续指令覆盖。 原因多个四元式共用同一个寄存器但没有及时保存。 解决每个四元式执行完后把结果写回内存或者用活跃变量分析做更精细的分配。实验阶段建议保守处理——所有变量放栈上寄存器只做临时中转。6. 验收前的自测清单与一个提效技巧验收前我一般会跑一套自测用例覆盖正常和异常路径。下面这张表是我当年整理的你可以直接拿去用测试类型输入示例预期输出检查点正常赋值int a; a 1 2;四元式含常量折叠符号表、类型检查混合运算int a; float b; b a 1.5;插入 int2float类型转换嵌套作用域{ int a; { int a; } }内层遮蔽外层符号表弹栈语法错误int a ;报错并恢复错误恢复除零检查a 1 / 0;报错或警告语义检查未声明变量a b 1;报错符号表查找一个提效技巧把每个阶段的输入输出都落盘成文件阶段之间用文件传递。这样调试时不用每次从头跑直接改中间文件就能验证后续阶段。我当年在语法分析卡了很久后来把词法分析的 token 序列存成文件手动改几个 token 就能测试各种语法分支省了大量时间。另外如果你用的是 Java 或 Python建议把每个阶段的入口写成独立函数用命令行参数控制跑哪个阶段。比如python compiler.py --stage lexer --input test.c这样验收时老师让你单独演示某个阶段你不用改代码。最后说个血泪经验别等到全部写完再联调。每写完一个阶段立刻用上一阶段的输出做输入跑一遍确保接口对齐。我见过太多人词法分析输出格式和语法分析输入格式不一致联调时才发现返工成本极高。希望帮到你。本文还有配套的精品资源点击获取