从零读懂OUC编译原理实验一到八：词法、语法、语义、中间代码、优化与目标代码全流程

简介这份资源是面向高校计算机专业学生的编译原理实验合集覆盖从词法分析到代码生成的完整编译流程适合正在修读编译原理课程或准备相关课程设计的学习者。内容按实验一到八递进展开实验一梳理编译器基本组成模块实验二至四分别实现词法分析器、递归下降解析器与语义分析实验五至七聚焦常量折叠、冗余消除、寄存器分配等优化议题实验八则以综合项目形式串联前端处理、错误检测与目标代码生成。压缩包共248个文件约446.47MB包含c与h源码、makefile构建脚本、y与l文法文件、docx与pdf实验文档以及xz、zst、bz2等压缩归档和少量可执行文件与日志便于按实验模块检索复用。目前已有491人学习下载可为读者提供可运行的解析器与词法分析器实现、各阶段实验参考代码及文档说明帮助理解程序从源码到目标代码的转换过程积累编译器设计的实际编程经验。1. 从零读懂 ouc 编译原理实验一到八这套实验到底在练什么如果你正在上编译原理课看到实验一到八这八个字大概率第一反应是头大——词法、语法、语义、中间代码、优化、目标代码每个词都像一座山。ouc 编译原理实验一到八本质是一条从源程序字符串到可执行目标代码的完整流水线八个实验分别对应编译器前端到后端的关键模块。它解决的不是“写一个能跑的小程序”而是让你亲手把课本上那些抽象概念变成能处理真实输入的代码。适合谁适合已经学过形式语言与自动机、数据结构但一写实验就不知道从哪下手的人。我见过太多人卡在实验二就放弃其实不是能力问题是没搞清每个实验的输入输出边界。这套实验的价值在于做完之后你看任何一门语言的编译器源码都能一眼认出它在哪个阶段干了什么事。2. 实验一到三词法分析、语法分析与符号表怎么串起来2.1 词法分析器的最小实现与正则匹配策略实验一通常要求写一个词法分析器输入是源程序文本输出是 token 序列。常见做法是用状态机手写或者用正则表达式配合有限自动机。我一般会先用 Python 快速验证逻辑再移植到 C 或 Java。下面是一个简化版词法分析器骨架能识别标识符、数字、运算符和关键字。import re # 定义 token 类型和对应的正则模式 TOKEN_SPEC [ (NUMBER, r\d(\.\d*)?), # 整数或小数 (ID, r[A-Za-z_]\w*), # 标识符 (OP, r[\-*/!|]), # 运算符 (SKIP, r[ \t]), # 空白字符跳过 (NEWLINE, r\n), # 换行 (MISMATCH, r.), # 无法匹配的字符 ] def lexer(code): tokens [] pos 0 while pos len(code): for tok_type, pattern in TOKEN_SPEC: regex re.compile(pattern) match regex.match(code, pos) if match: text match.group(0) if tok_type ID and text in {if, else, while, int, return}: tok_type KEYWORD # 关键字单独归类 if tok_type not in (SKIP, NEWLINE): tokens.append((tok_type, text)) pos match.end() break else: raise SyntaxError(f非法字符: {code[pos]}) return tokens # 测试 source int main() { return 0; } for t in lexer(source): print(t)这段代码的逻辑是按顺序尝试每个正则模式匹配成功就生成 token 并移动位置。参数说明TOKEN_SPEC的顺序很重要数字和标识符要放在运算符前面否则int可能被拆成i和nt。SKIP和NEWLINE不输出但必须占位否则位置无法推进。实际实验中老师可能会要求输出 token 的行号和列号你只需要在匹配时记录pos对应的行列即可。踩坑最多的地方是注释处理——很多同学忘了在正则里加注释模式导致//后面的内容被当成运算符。正确做法是在TOKEN_SPEC最前面加一条(COMMENT, r//.*)并归入SKIP类。2.2 语法分析递归下降与 LL(1) 的取舍实验二一般是语法分析输入是 token 序列输出是语法树或中间表示。常见做法有两种递归下降和 LL(1) 预测分析表。递归下降写起来直观适合手写LL(1) 需要先算 FIRST 集和 FOLLOW 集适合用工具生成。我建议先用手写递归下降把表达式文法跑通再用 LL(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 consume(self, expected_type): tok self.peek() if tok[0] expected_type: self.pos 1 return tok raise SyntaxError(f期望 {expected_type}实际 {tok}) def parse_expr(self): # expr - term ((|-) term)* node self.parse_term() while self.peek()[1] in (, -): op self.consume(OP)[1] right self.parse_term() node (op, node, right) return node def parse_term(self): # term - factor ((*|/) factor)* node self.parse_factor() while self.peek()[1] in (*, /): op self.consume(OP)[1] right self.parse_factor() node (op, node, right) return node def parse_factor(self): tok self.peek() if tok[0] NUMBER: return int(self.consume(NUMBER)[1]) elif tok[1] (: self.consume(OP) node self.parse_expr() self.consume(OP) # 期望 ) return node else: raise SyntaxError(f意外的 token: {tok}) # 测试解析 3 4 * 2 tokens [(NUMBER, 3), (OP, ), (NUMBER, 4), (OP, *), (NUMBER, 2)] parser Parser(tokens) tree parser.parse_expr() print(tree) # 输出 (, 3, (*, 4, 2))逻辑说明每个非终结符对应一个函数函数内部按产生式右部顺序调用。参数说明peek()返回当前 token 但不移动位置consume()匹配并前进。优先级通过函数调用层次体现——parse_expr处理加减parse_term处理乘除parse_factor处理括号和数字。常见坑是左递归如果直接写expr - expr term递归下降会无限递归。解决办法是改写成循环如上面代码所示。另一个坑是错误恢复——实验要求可能只要求报错但实际编译器需要跳过一些 token 继续解析这个在实验三再补。2.3 符号表从哈希表到作用域链实验三通常要求实现符号表用来记录变量、函数、类型等信息。常见做法是用哈希表加作用域栈。每进入一个作用域如函数体、复合语句压入一个新表离开时弹出。查找时从栈顶往下找。下面是一个简单实现。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 NameError(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 NameError(f未声明: {name}) # 测试 st SymbolTable() st.declare(x, int) st.enter_scope() st.declare(y, float) print(st.lookup(x)) # int print(st.lookup(y)) # float st.exit_scope() # print(st.lookup(y)) # 会报错因为 y 已离开作用域参数说明scopes列表模拟作用域栈declare只检查当前作用域是否重复lookup从内到外查找。坑在于很多同学忘了在exit_scope时检查栈深度导致全局作用域被弹出。另外函数参数和局部变量通常在同一作用域但有些语言要求参数单独一层这个要看实验要求。符号表要和语法树节点绑定比如每个标识符节点存一个指向符号表条目的指针这样后续语义分析才能快速取到类型。3. 实验四到六语义分析、中间代码生成与类型检查3.1 语义分析类型检查与作用域验证实验四一般是语义分析核心是类型检查和名字解析。输入是语法树和符号表输出是带类型标注的树或错误列表。常见做法是遍历语法树对每个节点计算类型并检查操作数类型是否匹配。比如加法要求两边都是数值类型赋值要求左值类型和右值类型兼容。下面是一个类型检查的片段。def check_expr(node, symtab): if isinstance(node, int): return int if isinstance(node, tuple): op node[0] left_type check_expr(node[1], symtab) right_type check_expr(node[2], symtab) if op in (, -, *, /): if left_type int and right_type int: return int elif left_type in (int, float) and right_type in (int, float): return float else: raise TypeError(f运算符 {op} 不支持 {left_type} 和 {right_type}) elif op : if left_type ! right_type: raise TypeError(f赋值类型不匹配: {left_type} vs {right_type}) return left_type if isinstance(node, str): # 标识符 return symtab.lookup(node) raise TypeError(f未知节点: {node})逻辑说明递归计算每个子表达式的类型然后根据运算符规则合并。参数说明symtab是符号表实例用于查标识符类型。坑在于隐式类型转换——有些实验要求 int 自动转 float有些要求显式转换一定要看清实验文档。另一个坑是数组和指针类型如果实验涉及需要额外处理维度匹配。3.2 中间代码生成三地址码与四元式实验五通常是生成中间代码最常见的是三地址码或四元式。三地址码形式如x y op z四元式是(op, arg1, arg2, result)。我一般用四元式因为方便后续优化和生成目标代码。下面是一个从语法树生成四元式的例子。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 isinstance(node, int): return str(node) if isinstance(node, str): return node if isinstance(node, tuple): op node[0] left self.gen(node[1]) right self.gen(node[2]) temp self.new_temp() self.quads.append((op, left, right, temp)) return temp # 测试3 4 * 2 tree (, 3, (*, 4, 2)) qg QuadGenerator() result qg.gen(tree) for q in qg.quads: print(q) print(结果临时变量:, result)输出(*, 4, 2, t1) (, 3, t1, t2) 结果临时变量: t2参数说明temp_count保证临时变量名唯一quads列表按生成顺序存储。坑在于表达式求值顺序可能影响副作用比如函数调用但实验一般只涉及算术不用考虑。另一个坑是布尔表达式的短路求值如果实验要求生成控制流需要用回填技术这个在实验六或七再处理。3.3 实验六控制流语句的中间代码与回填实验六通常要求处理 if、while 等控制流语句生成带跳转的四元式。常见做法是回填——先产生跳转指令但目标地址留空等目标确定后再填。下面是一个简化实现。class ControlFlowGen: def __init__(self): self.quads [] self.next_quad 0 def emit(self, op, arg1None, arg2None, resultNone): self.quads.append([op, arg1, arg2, result]) self.next_quad 1 return self.next_quad - 1 def backpatch(self, list_to_patch, target): for idx in list_to_patch: self.quads[idx][3] target def gen_if(self, cond_quads, then_quads, else_quadsNone): # cond_quads 生成条件跳转返回真跳转和假跳转列表 true_list, false_list cond_quads self.backpatch(true_list, self.next_quad) for q in then_quads: self.emit(*q) if else_quads: skip_else self.emit(j, None, None, None) self.backpatch(false_list, self.next_quad) for q in else_quads: self.emit(*q) self.backpatch([skip_else], self.next_quad) else: self.backpatch(false_list, self.next_quad)逻辑说明emit添加一条四元式并返回索引backpatch把索引列表里的跳转目标改成指定位置。参数说明true_list和false_list是条件跳转指令的索引列表。坑在于回填顺序不能乱否则跳转目标会错位。建议每生成一个语句就立刻回填不要攒着。4. 实验七到八代码优化与目标代码生成4.1 实验七局部优化与数据流分析入门实验七一般是代码优化常见的有常量折叠、公共子表达式消除、死代码删除。我建议从局部优化入手因为实现简单且效果明显。下面是一个常量折叠的例子。def constant_folding(quads): new_quads [] for op, arg1, arg2, result in quads: if op in (, -, *, /) and arg1.isdigit() and arg2.isdigit(): val eval(f{arg1} {op} {arg2}) new_quads.append((, str(val), None, result)) else: new_quads.append((op, arg1, arg2, result)) return new_quads # 测试 quads [(*, 4, 2, t1), (, 3, t1, t2)] optimized constant_folding(quads) for q in optimized: print(q)输出(, 8, None, t1) (, 3, t1, t2)参数说明arg1.isdigit()判断是否是常量eval计算值。坑在于除法要处理除零浮点数要处理精度。更复杂的优化如公共子表达式消除需要构建 DAG实验七可能只要求局部优化看清要求再动手。4.2 实验八目标代码生成与寄存器分配实验八通常是生成汇编代码或机器码。常见做法是遍历四元式为每个临时变量分配寄存器或栈槽。下面是一个简单的 x86 风格汇编生成器。def gen_asm(quads): asm [] reg_map {} reg_count 0 def get_reg(temp): nonlocal reg_count if temp not in reg_map: reg_map[temp] fR{reg_count} reg_count 1 return reg_map[temp] for op, arg1, arg2, result in quads: if op : asm.append(fMOV {get_reg(result)}, {arg1}) elif op in (, -, *, /): r1 get_reg(arg1) if not arg1.isdigit() else arg1 r2 get_reg(arg2) if not arg2.isdigit() else arg2 asm.append(fMOV R0, {r1}) if op : asm.append(fADD R0, {r2}) elif op -: asm.append(fSUB R0, {r2}) elif op *: asm.append(fMUL R0, {r2}) elif op /: asm.append(fDIV R0, {r2}) asm.append(fMOV {get_reg(result)}, R0) return asm # 测试 quads [(, 8, None, t1), (, 3, t1, t2)] for line in gen_asm(quads): print(line)输出MOV R0, 8 MOV R1, R0 MOV R0, 3 ADD R0, R1 MOV R2, R0参数说明reg_map为每个临时变量分配寄存器R0用作累加器。坑在于寄存器数量有限真实编译器需要寄存器分配算法如图着色实验八可能只要求简单分配。另外函数调用需要保存现场这个要看实验是否涉及。5. 避坑与排查八个实验里最容易翻车的五个地方5.1 词法分析注释和字符串处理不干净现象词法分析器遇到//或/* */时报错或者把字符串里的内容当成 token。原因正则模式没有覆盖注释和字符串或者匹配顺序不对。解决在TOKEN_SPEC最前面加注释模式字符串用r[^]*匹配并归入SKIP或单独 token 类型。5.2 语法分析左递归导致栈溢出现象递归下降解析器一运行就报RecursionError。原因文法直接左递归如expr - expr term。解决改写成右递归或循环如expr - term ((|-) term)*在代码里用while循环处理。5.3 符号表作用域退出时忘记弹栈现象内层作用域的变量在外层还能查到。原因exit_scope没有调用或调用次数不对。解决在语法树遍历时进入复合语句或函数体时调用enter_scope离开时调用exit_scope确保成对出现。5.4 中间代码临时变量命名冲突现象生成的四元式里两个不同的临时变量同名导致后续优化出错。原因temp_count没有全局唯一或者多个生成器实例共用。解决用一个全局计数器或者每个函数单独计数但加前缀。5.5 目标代码寄存器分配越界现象生成的汇编里出现R10但目标机器只有R0-R7。原因寄存器分配没有限制数量。解决实验八一般只要求用少量寄存器可以固定用R0-R3超出部分用栈槽或者直接报错提示需要更多寄存器。6. 把八个实验串成一条线我的复现习惯与验证技巧做完这八个实验最大的感受是编译器不是一口气写出来的而是一个模块一个模块拼出来的。我习惯每做完一个实验就用上一实验的输出作为下一实验的输入跑一遍完整流程。比如用实验一的词法分析器处理一段代码把 token 序列喂给实验二的语法分析器再把语法树喂给实验五的中间代码生成器最后用实验八生成汇编。这样能快速发现接口不匹配的问题。验证技巧方面我一般会准备三组测试用例一组是正常代码一组是边界情况如空输入、超长标识符一组是错误代码如语法错误、类型错误。正常代码用来验证功能边界情况用来验证鲁棒性错误代码用来验证报错信息是否清晰。另外我会用 Python 的unittest写几个断言比如词法分析器对int x 10;应该输出[(KEYWORD, int), (ID, x), (OP, ), (NUMBER, 10), (OP, ;)]这样每次改代码都能快速回归。最后一个习惯把每个实验的输入输出格式写成文档哪怕只是注释。因为过一周再回来看很容易忘记某个函数返回的是列表还是元组。希望帮到你。本文还有配套的精品资源点击获取