简介OUC编译原理实验一到八全套资料覆盖编译原理课程从词法分析、语法分析、语义分析到代码生成与优化的完整实验链适合高校本科生、考研复试者及自学编译器的读者。资源共248个文件压缩包整体约446MB主要包含c/h源程序、lex/yacc语法文件、docx/doc实验报告、pdf说明文档以及xz、zst、bz2等格式的辅助工具包文件类型多样支持在不同环境下复现实验。已有491人浏览学习。借助完整源码、实验文档及中间文件读者可对照理解正则表达式与有限自动机在词法分析中的应用、递归下降解析器与CFG的构建并参考中间代码优化、寄存器分配等扩展内容既能巩固编译原理理论也能提升实际调试与代码实现能力。 大二下学期最让人头秃的课编译原理绝对排得上号。理论课上听得云里雾里以为编译器就是把源程序从头到尾扫一遍等自己动手做实验才发现一个能跑起来的微型编译器背后是词法、语法、语义、中间代码、优化、目标代码整整六个阶段的接力。很多学校把这套内容拆成八个递进实验一周一个关卡做完第八个再回头看当初踩过的坑全部变成了理解。这篇博客把我做实验一到实验八的完整脉络和踩坑经验整理了出来覆盖词法分析、语法分析、符号表、中间代码生成、优化和目标代码生成也会顺带聊聊用 Java 实现整个编译器工程时的典型问题。不管你是正在赶编译原理课设的学生还是想自己动手写个解释器或编译器的爱好者里面这些思路和注意事项都能帮你省下不少试错时间。1. 八个实验的整体脉络从词法到代码生成1.1 课程实验为什么要拆成八关很多人第一反应都是直接写一个完整编译器不就完了干嘛拆八个实验我一开始也这么想结果写完词法分析器就明白了。编译器不是一个大算法而是一条流水线每个阶段都有独立的输入输出——词法分析吃源码吐 Token语法分析吃 Token吐语法树语义分析吃语法树再吐带类型信息的中间表示。这种天然分层的架构决定了它特别适合分成几个小关卡逐个击破。拆成八关之后每周只需要专注解决一个核心问题实验一的输出是实验二的输入代码逐步复用。更关键的是每一关验收时错误范围被限定得很小定位问题非常快速不会出现一个 bug 查了三小时还找不到藏在哪个模块里的情况。所以与其觉得拆开太麻烦不如把这当成工程实践的第一课先把边界切清楚再把每一段做扎实。1.2 用一张表把八个实验串起来不同学校的实验编号会有细微差别但整体框架基本一致。我们学校的八次实验对应关系大致如下表。拿到这张表之后我强烈建议先别急着写代码花半小时把整条链路在脑子里过一遍每个阶段的输出是什么下一个阶段拿到这些数据要做什么哪些数据需要额外保留。想清楚再动手后面七周会顺畅很多。实验编号核心主题关键产出涉及的核心理论实验一词法分析Token 序列正则表达式、状态机、最长匹配实验二语法分析自顶向下递归下降程序 / 预测分析表FIRST 集合、FOLLOW 集合、LL(1) 文法实验三语法分析自底向上项目集规范族、LR 分析表LR(0)/SLR(1)、移进归约实验四符号表管理支持嵌套作用域的符号表哈希表、作用域链、类型记录实验五语义分析与中间代码生成四元式 / 三地址码属性文法、语法制导翻译实验六中间代码优化优化后的中间代码常量折叠、死代码消除、公共子表达式删除实验七目标代码生成MIPS 汇编代码指令选择、寄存器分配实验八综合实验一个可运行的编译器 / 解释器前七个实验的串联这张表里最能看出问题的是 Token 设计。实验一如果只做当前任务Token 类里存个类型和字符串值就收工了但等到实验二要输出语法错误报错信息里需要行号和列号你才发现 Token 里没存就只能回头改词法分析器所有构造点。所以哪怕当前实验用不到Token 类最好一开始就预留 line 和 column 字段这个习惯会帮你避免一次大范围返工。2. 前四关实战词法、语法与符号表2.1 实验一词法分析先画状态图再写代码词法分析是整个编译器的入口任务是把源代码拆成 Token 序列。很多初学者栽在实现方式上包括我自己。第一版我完全靠 if-else 堆逻辑每读一个字符就判断它可能是标识符、数字还是运算符结果代码越写越长状态互相纠缠加一个关键字匹配就要动三四个地方。后来换了个套路先把所有 Token 类型枚举出来再给每类 Token 画状态转移图最后照着状态图用 switch 实现流转整个代码立刻清爽了。public enum TokenType { IDENT, NUMBER, KEYWORD_IF, KEYWORD_ELSE, KEYWORD_WHILE, OP_PLUS, OP_MINUS, OP_ASSIGN, OP_EQ } public class Lexer { private String src; private int pos 0; public Token nextToken() { skipWhitespace(); char c src.charAt(pos); if (isLetter(c)) { StringBuilder sb new StringBuilder(); while (isLetterOrDigit(peekNext())) { sb.append(advance()); } // 关键字优先完整读入后先查表 if (isKeyword(sb.toString())) { return new Token(TokenType.valueOf(KEYWORD_ sb.toString().toUpperCase()), sb.toString(), line, col); } return new Token(TokenType.IDENT, sb.toString(), line, col); } if (c ) { if (peekNext() ) { advance(); return new Token(TokenType.OP_EQ, , line, col); } return new Token(TokenType.OP_ASSIGN, , line, col); } // 数字、运算符、字符串等分支略 return null; } }写词法分析器最容易翻车的是运算符最长匹配。比如判断如果一读到就返回赋值号后续的就变成游离字符a b会被拆成a、、、b四个 Token后面语法分析直接懵。正确做法是读到一个字符后不急着结束多往后看一眼只有当下一个字符也是时才归为相等比较。这个向后看一个字符的小技巧在词法分析里很常用注释结束判断、字符串转义处理都会遇到。另一个高频问题是关键字和标识符的区分。很多语言的if、while不是标识符而是关键字正确顺序是完整读入一个单词后先查关键字表命中就设成对应关键字类型没命中再归为标识符。顺序反了语法分析阶段会看到一大堆标识符永远等不到想要的 if 符号报错也会非常离谱。2.2 实验二和三自顶向下与自底向上怎么选实验二通常做自顶向下的语法分析主流实现是递归下降子程序法。这个方法非常直观每个非终结符对应一个函数函数体就是一个产生式右侧符号序列的处理过程。例如表达式文法E - T { (|-) T }可以写成如下代码一看就懂。public class Parser { private Lexer lexer; private Token lookahead; // E - T { (|-) T } public double parseE() { double left parseT(); while (lookahead.is(TokenType.OP_PLUS) || lookahead.is(TokenType.OP_MINUS)) { char op lookahead.value().charAt(0); consume(); double right parseT(); left op ? left right : left - right; } return left; } // T - F { (*|/) F } public double parseT() { // 实现类似 parseE省略 return 0; } }递归下降法最大的坑是左递归。如果文法里有E - E TparseE() 第一行就调用 parseE()无限递归直到栈溢出。解决办法是文法等价变换把左递归改成右递归或者更直白的改成循环迭代形式先解析一个 T然后循环判断下一个 Token 是不是加号或减号是就继续解析下一个 T。这种写法完全避免了递归调用自己。实验三的自底向上分析LR 类要抽象得多SLR(1) 需要构造项目集规范族涉及 CLOSURE 闭包运算和 GOTO 函数然后生成 LR 分析表。手工推导项目集非常容易出错项目一多就眼花。我当时的做法是写一个自动计算 CLOSURE 和 GOTO 的工具函数文法产生式输进去分析表自动出来省下的时间全部用来排查别的问题了。那自顶向下和自底向上到底选哪个如果老师两个都要求那就老老实实都做。如果自己写一个真实语言的小型解释器我更推荐递归下降法调试方便、报错位置精确、代码量少。LR 类分析器更庞大也更难调试它真正的价值体现在用工具生成分析器的场景。课程实验里把这个知识点掌握好比手撸一个工业级 LR 分析器更实际。2.3 实验四符号表要往贯穿全程方向设计符号表实验很容易被当成一个简单的哈希表练习插入、查找就完事了。但你要知道符号表不是实验四用完就扔的实验五语义分析要查类型实验七目标代码生成要查存储位置它几乎是贯穿整个编译器的公共数据结构。如果一开始设计得太简陋后面三周每隔几天就要回来改一次非常折磨。public class SymbolTable { private final ListMapString, Symbol scopes new ArrayList(); public void enterScope() { scopes.add(new HashMap()); } public void exitScope() { scopes.remove(scopes.size() - 1); } public void insert(String name, Symbol symbol) { scopes.get(scopes.size() - 1).put(name, symbol); } public Symbol lookup(String name) { for (int i scopes.size() - 1; i 0; i--) { Symbol s scopes.get(i).get(name); if (s ! null) return s; } return null; } }这段代码展示的是基于栈的嵌套作用域实现进入一个代码块就 push 一个 HashMap退出就 pop查找时从栈顶往下逐层找。Symbol 类不要只存名字和类型要预留类型信息、作用域深度、声明位置、存储位置等字段。尤其存储位置极其重要到实验七生成汇编时每个变量在栈上的偏移量都来自这里。符号表最容易出错的是作用域遮蔽。外层有变量 a内层又声明了 a内层代码访问 a 要命中内层跳出内层后再命中外层。上面这种实现天然满足本文还有配套的精品资源点击获取 编译原理实验全通关：从词法分析到目标代码生成的完整实战指南
简介OUC编译原理实验一到八全套资料覆盖编译原理课程从词法分析、语法分析、语义分析到代码生成与优化的完整实验链适合高校本科生、考研复试者及自学编译器的读者。资源共248个文件压缩包整体约446MB主要包含c/h源程序、lex/yacc语法文件、docx/doc实验报告、pdf说明文档以及xz、zst、bz2等格式的辅助工具包文件类型多样支持在不同环境下复现实验。已有491人浏览学习。借助完整源码、实验文档及中间文件读者可对照理解正则表达式与有限自动机在词法分析中的应用、递归下降解析器与CFG的构建并参考中间代码优化、寄存器分配等扩展内容既能巩固编译原理理论也能提升实际调试与代码实现能力。 大二下学期最让人头秃的课编译原理绝对排得上号。理论课上听得云里雾里以为编译器就是把源程序从头到尾扫一遍等自己动手做实验才发现一个能跑起来的微型编译器背后是词法、语法、语义、中间代码、优化、目标代码整整六个阶段的接力。很多学校把这套内容拆成八个递进实验一周一个关卡做完第八个再回头看当初踩过的坑全部变成了理解。这篇博客把我做实验一到实验八的完整脉络和踩坑经验整理了出来覆盖词法分析、语法分析、符号表、中间代码生成、优化和目标代码生成也会顺带聊聊用 Java 实现整个编译器工程时的典型问题。不管你是正在赶编译原理课设的学生还是想自己动手写个解释器或编译器的爱好者里面这些思路和注意事项都能帮你省下不少试错时间。1. 八个实验的整体脉络从词法到代码生成1.1 课程实验为什么要拆成八关很多人第一反应都是直接写一个完整编译器不就完了干嘛拆八个实验我一开始也这么想结果写完词法分析器就明白了。编译器不是一个大算法而是一条流水线每个阶段都有独立的输入输出——词法分析吃源码吐 Token语法分析吃 Token吐语法树语义分析吃语法树再吐带类型信息的中间表示。这种天然分层的架构决定了它特别适合分成几个小关卡逐个击破。拆成八关之后每周只需要专注解决一个核心问题实验一的输出是实验二的输入代码逐步复用。更关键的是每一关验收时错误范围被限定得很小定位问题非常快速不会出现一个 bug 查了三小时还找不到藏在哪个模块里的情况。所以与其觉得拆开太麻烦不如把这当成工程实践的第一课先把边界切清楚再把每一段做扎实。1.2 用一张表把八个实验串起来不同学校的实验编号会有细微差别但整体框架基本一致。我们学校的八次实验对应关系大致如下表。拿到这张表之后我强烈建议先别急着写代码花半小时把整条链路在脑子里过一遍每个阶段的输出是什么下一个阶段拿到这些数据要做什么哪些数据需要额外保留。想清楚再动手后面七周会顺畅很多。实验编号核心主题关键产出涉及的核心理论实验一词法分析Token 序列正则表达式、状态机、最长匹配实验二语法分析自顶向下递归下降程序 / 预测分析表FIRST 集合、FOLLOW 集合、LL(1) 文法实验三语法分析自底向上项目集规范族、LR 分析表LR(0)/SLR(1)、移进归约实验四符号表管理支持嵌套作用域的符号表哈希表、作用域链、类型记录实验五语义分析与中间代码生成四元式 / 三地址码属性文法、语法制导翻译实验六中间代码优化优化后的中间代码常量折叠、死代码消除、公共子表达式删除实验七目标代码生成MIPS 汇编代码指令选择、寄存器分配实验八综合实验一个可运行的编译器 / 解释器前七个实验的串联这张表里最能看出问题的是 Token 设计。实验一如果只做当前任务Token 类里存个类型和字符串值就收工了但等到实验二要输出语法错误报错信息里需要行号和列号你才发现 Token 里没存就只能回头改词法分析器所有构造点。所以哪怕当前实验用不到Token 类最好一开始就预留 line 和 column 字段这个习惯会帮你避免一次大范围返工。2. 前四关实战词法、语法与符号表2.1 实验一词法分析先画状态图再写代码词法分析是整个编译器的入口任务是把源代码拆成 Token 序列。很多初学者栽在实现方式上包括我自己。第一版我完全靠 if-else 堆逻辑每读一个字符就判断它可能是标识符、数字还是运算符结果代码越写越长状态互相纠缠加一个关键字匹配就要动三四个地方。后来换了个套路先把所有 Token 类型枚举出来再给每类 Token 画状态转移图最后照着状态图用 switch 实现流转整个代码立刻清爽了。public enum TokenType { IDENT, NUMBER, KEYWORD_IF, KEYWORD_ELSE, KEYWORD_WHILE, OP_PLUS, OP_MINUS, OP_ASSIGN, OP_EQ } public class Lexer { private String src; private int pos 0; public Token nextToken() { skipWhitespace(); char c src.charAt(pos); if (isLetter(c)) { StringBuilder sb new StringBuilder(); while (isLetterOrDigit(peekNext())) { sb.append(advance()); } // 关键字优先完整读入后先查表 if (isKeyword(sb.toString())) { return new Token(TokenType.valueOf(KEYWORD_ sb.toString().toUpperCase()), sb.toString(), line, col); } return new Token(TokenType.IDENT, sb.toString(), line, col); } if (c ) { if (peekNext() ) { advance(); return new Token(TokenType.OP_EQ, , line, col); } return new Token(TokenType.OP_ASSIGN, , line, col); } // 数字、运算符、字符串等分支略 return null; } }写词法分析器最容易翻车的是运算符最长匹配。比如判断如果一读到就返回赋值号后续的就变成游离字符a b会被拆成a、、、b四个 Token后面语法分析直接懵。正确做法是读到一个字符后不急着结束多往后看一眼只有当下一个字符也是时才归为相等比较。这个向后看一个字符的小技巧在词法分析里很常用注释结束判断、字符串转义处理都会遇到。另一个高频问题是关键字和标识符的区分。很多语言的if、while不是标识符而是关键字正确顺序是完整读入一个单词后先查关键字表命中就设成对应关键字类型没命中再归为标识符。顺序反了语法分析阶段会看到一大堆标识符永远等不到想要的 if 符号报错也会非常离谱。2.2 实验二和三自顶向下与自底向上怎么选实验二通常做自顶向下的语法分析主流实现是递归下降子程序法。这个方法非常直观每个非终结符对应一个函数函数体就是一个产生式右侧符号序列的处理过程。例如表达式文法E - T { (|-) T }可以写成如下代码一看就懂。public class Parser { private Lexer lexer; private Token lookahead; // E - T { (|-) T } public double parseE() { double left parseT(); while (lookahead.is(TokenType.OP_PLUS) || lookahead.is(TokenType.OP_MINUS)) { char op lookahead.value().charAt(0); consume(); double right parseT(); left op ? left right : left - right; } return left; } // T - F { (*|/) F } public double parseT() { // 实现类似 parseE省略 return 0; } }递归下降法最大的坑是左递归。如果文法里有E - E TparseE() 第一行就调用 parseE()无限递归直到栈溢出。解决办法是文法等价变换把左递归改成右递归或者更直白的改成循环迭代形式先解析一个 T然后循环判断下一个 Token 是不是加号或减号是就继续解析下一个 T。这种写法完全避免了递归调用自己。实验三的自底向上分析LR 类要抽象得多SLR(1) 需要构造项目集规范族涉及 CLOSURE 闭包运算和 GOTO 函数然后生成 LR 分析表。手工推导项目集非常容易出错项目一多就眼花。我当时的做法是写一个自动计算 CLOSURE 和 GOTO 的工具函数文法产生式输进去分析表自动出来省下的时间全部用来排查别的问题了。那自顶向下和自底向上到底选哪个如果老师两个都要求那就老老实实都做。如果自己写一个真实语言的小型解释器我更推荐递归下降法调试方便、报错位置精确、代码量少。LR 类分析器更庞大也更难调试它真正的价值体现在用工具生成分析器的场景。课程实验里把这个知识点掌握好比手撸一个工业级 LR 分析器更实际。2.3 实验四符号表要往贯穿全程方向设计符号表实验很容易被当成一个简单的哈希表练习插入、查找就完事了。但你要知道符号表不是实验四用完就扔的实验五语义分析要查类型实验七目标代码生成要查存储位置它几乎是贯穿整个编译器的公共数据结构。如果一开始设计得太简陋后面三周每隔几天就要回来改一次非常折磨。public class SymbolTable { private final ListMapString, Symbol scopes new ArrayList(); public void enterScope() { scopes.add(new HashMap()); } public void exitScope() { scopes.remove(scopes.size() - 1); } public void insert(String name, Symbol symbol) { scopes.get(scopes.size() - 1).put(name, symbol); } public Symbol lookup(String name) { for (int i scopes.size() - 1; i 0; i--) { Symbol s scopes.get(i).get(name); if (s ! null) return s; } return null; } }这段代码展示的是基于栈的嵌套作用域实现进入一个代码块就 push 一个 HashMap退出就 pop查找时从栈顶往下逐层找。Symbol 类不要只存名字和类型要预留类型信息、作用域深度、声明位置、存储位置等字段。尤其存储位置极其重要到实验七生成汇编时每个变量在栈上的偏移量都来自这里。符号表最容易出错的是作用域遮蔽。外层有变量 a内层又声明了 a内层代码访问 a 要命中内层跳出内层后再命中外层。上面这种实现天然满足本文还有配套的精品资源点击获取