尧图网站建设 
简介这是一份面向编译原理课程学习者的完整实验资料内容来自中国海洋大学2020年春季学期编译原理课程涵盖词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、错误处理与编译器综合共8个实验及实验要求文档。资源包共74个文件以C源码为主同时包含lex/flex与yacc/bison的工程文件.l、.y、可执行程序、测试文件及makefile等整体仅774KB便于快速下载和本地复现。已有4408人浏览学习适合高校学生对照课程要求动手实践也适合自学编译器的开发者借鉴完整实验思路。通过逐项实验与要求文档读者可以了解编译器各阶段的主要任务、常见工具链的使用方法并在已有代码基础上进行改造与验证从而系统掌握编译器构造的核心流程。 如果你正在海大读计算机大概率躲不开“OUC编译原理全部实验”这道坎。我印象特别深第一次听说这门课要自己从零写一个能识别词法、分析语法、生成中间代码的小编译器时整个人是懵的——前面的数据库实验、操作系统实验好歹还有框架代码编译原理直接要求我“造轮子”。但等期末把工程交付再回头复盘这一路我反而觉得这是本科阶段含金量最高的一次代码马拉松。这篇文章不打算给你抄完整答案那没有意义。我会按照当年做这套实验的实际流程把每个实验的核心思路、最容易踩的坑、以及我调试到半夜才想明白的原理讲清楚。内容主要基于用 Java 实现、教材采用清华大学出版社编译原理王生原等第三版、并配合哈工大陈鄞老师视频课这种最常见配置你可以对照自己的实验要求灵活调整。1. OUC编译原理实验的整体画像一学期做出一台“会算数”的编译器1.1 实验到底有几次从词法到综合的横向拆解海大的编译原理实验通常不是一次性让你交一个巨无霸工程而是拆成若干阶段每个阶段对应一个课堂知识模块。我当年碰到的是五次实验大致如下实验阶段核心任务课堂理论对应实验一词法分析器正规式、DFA、NFA实验二语法分析器LL(1)、递归下降、FIRST/FOLLOW实验三语义分析与符号表属性文法、类型检查实验四中间代码生成三地址码、四元式、回填实验五综合实验组装完整编译器前后端整合、解释执行这套顺序的聪明之处在于每一次实验都是在上一次产物上做加法。你不需要一步到位做完整编译器但每一步都不能糊弄否则后面跑不起来。比如语法分析如果直接返回一堆“这里报错那里报错”那么语义分析阶段就得回头改 parser中间代码生成又依赖语法树的正确性。说白了这就是一套“欠债迟早要还”的流水线。1.2 每个实验的评分点与卡人之处多数同学以为实验成绩只看最后能不能跑通其实老师更看重三件事功能是否覆盖要求、关键代码是否体现原理、实验报告是否讲得清楚问题与解决过程。功能测试只占一部分真正卡人的往往是“你写的东西能不能经受答辩提问”。另一个容易被忽视的点是老师不要求你用多高级的框架反而会警惕你用正则库和解析器生成器一带而过。因为编译原理实验的核心就是让你手动实现一次 DFA 状态转移、手动写递归下降函数、手动生成四元式。如果全用现成工具等于把最有价值的训练过程外包了。所以我在整个学期都在不断提醒自己宁可代码写得“土”一点也要让每一步都讲得出原理。2. 实验一手写词法分析器时最容易后悔没想明白的三件事2.1 用状态机还是正则匹配库这个决定要早做一开始我确实动过用 Java 正则表达式一把梭的念头Pattern.compile([a-zA-Z_][a-zA-Z0-9_]*)就能匹配标识符多省事。但真写起来才发现问题很多正则库一次匹配一个 Token边界处理和错误定位很难做更重要的是老师一问你“这个正则对应的 DFA 长什么样”你根本讲不清楚。老老实实手写状态机的思路其实并不复杂维护一个当前状态读一个字符更新状态。比如标识符识别的核心逻辑可以简化成下面这样// 伪代码示意 private Token nextToken() { skipWhitespaceAndComments(); int startLine line, startCol col; char c peek(); if (isLetter(c)) { StringBuilder sb new StringBuilder(); while (isLetterOrDigit(peek())) { sb.append(peek()); advance(); } String word sb.toString(); // 先按关键字查表查不到就是标识符 TokenType type keywords.getOrDefault(word, TokenType.IDENT); return new Token(type, word, startLine, startCol); } if (isDigit(c)) { // 数字识别注意要支持多位数以及数字后面的非法字符检查 } // 运算符、分隔符单字符和双字符分开处理 }这段代码看起来简单但里面藏着第一个大坑关键字和标识符的区分不能只靠“第一个字符是不是字母”而是必须走最长匹配。如果你在读到第一个字符i时就先判断它是if那么遇到intValue这种变量名就会识别成关键字直接整段崩掉。正确做法是先读完整段字母数字序列再查关键字表。2.2 忽略行号和列号后面调试会哭很多同学实验一犯的“调式拖延症”是没有在 Token 里存行号和列号。等到实验二、实验三一报错满屏只有一串null或者空指针你根本不知道是哪一行哪一列出了问题。我的建议很简单从一开始就给 Token 加上line和col字段。这样做的好处是语法分析报错时你能输出这种可读信息Parse error at line 3, column 12: unexpected token ) , expected ;实验报告里贴上这种日志截图比贴十页代码更让老师认可。提示注释的处理也要在词法阶段完成。行注释//和块注释/* */都要跳过并且块注释里不能忽略换行计数否则后续报错的行号全错位。2.3 Token 的类别设计要预留扩展空间我第一版写的 Token 只有type和value两个字段结果到了实验三做类型检查时我不得不在语法树上重新去找每个标识符对应的字符串值非常别扭。比较合理的做法是enum TokenType { INT, VOID, IF, ELSE, WHILE, FOR, RETURN, IDENT, NUMBER, PLUS, MINUS, STAR, SLASH, ASSIGN, EQ, NE, LT, LE, GT, GE, SEMI, COMMA, LPAREN, RPAREN, LBRACE, RBRACE, LBRACKET, RBRACKET, EOF } class Token { TokenType type; String lexeme; int line; int col; }lexeme保存原始单词type保存类别这样后面做符号表查重、类型比较时都非常顺手。别小看这个设计后期能帮你省掉大量“类型转型”的脏代码。3. 实验二语法分析我为什么拼命劝你用递归下降3.1 先改写文法再写代码顺序千万别反实验二是很多人的分水岭。我看到不少同学拿到文法就开始写 parse 函数结果写完才发现左递归导致无限循环expr - expr term左边递归代码里parseExpr()第一句话又调用parseExpr()栈直接爆掉。正确流程是先做文法等价改写。常见的操作有两个一是消除左递归二是提取左因子。比如算术表达式可以改写成适合递归下降的文法expr - term expr_rest expr_rest - term expr_rest | - term expr_rest | ε term - factor term_rest term_rest - * factor term_rest | / factor term_rest | ε factor - NUMBER | IDENT | ( expr )改写完再手算一遍 FIRST 和 FOLLOW 集合心里有数后再动手写代码。这一步看起来很“理论”实际价值非常大——它能帮你确认某个 token 应该由哪个非终结符处理也能少踩很多分支逻辑混乱的坑。3.2 每个非终结符对应一个方法代码骨架越规整越省心我见过有些同学把整个语法分析写成一个五百行的巨型函数里面 switch-case 满天飞。调试的时候想单步跟进某个分支头皮都发麻。递归下降的核心思想是“一符一函数”结构清晰程度和文法几乎一一对应class Parser { private Lexer lexer; private Token lookahead; // E - T E public ASTExpr parseExpr() { ASTExpr left parseTerm(); while (lookahead.type TokenType.PLUS || lookahead.type TokenType.MINUS) { Token op lookahead; nextToken(); ASTExpr right parseTerm(); left new ASTBinaryExpr(left, op, right); // 构建语法树节点 } return left; } }注意这里我在递归下降的同时就直接构建了 AST 节点。这样实验三做语义分析和实验四做中间代码生成时就不需要再把 token 流从头推一遍语法了。虽然一开始写 AST 类会多一点代码但从整条实验链路看是完全值得的。3.3 错误恢复不追求完美但要能“跌倒后爬起来”语法分析器最容易出现的崩溃场景是用户输入少了一个分号你的 parser 抛个异常直接退出。如果是作业引擎测试可能意味着后面的测试用例全部得不到结果。课程实验里最常用的技巧叫“恐慌模式”错误恢复当解析到非法 token 时不直接终止整个程序而是跳过一些 token直到找到一个“同步标记”比如分号、右大括号。这个同步标记通常是当前语句的结束位置。实现起来也很简单private void synchronize() { while (lookahead.type ! TokenType.EOF) { if (lookahead.type TokenType.SEMI || lookahead.type TokenType.RBRACE) { nextToken(); return; } nextToken(); } }这样即使 token 流里有错误语法分析也能尽量多分析出几处问题最后一次性汇总报错。这个设计在实验报告里写出来明显比“遇错就死”高一个档次。4. 实验三和四语义分析与中间代码生成最容易翻车的地带4.1 符号表设计作用域栈加 HashMap 没那么简单到了实验三很多同学才明白什么叫“编译前端的另一半”。语法分析只管结构对不对不管语义对不对。a b 1里如果b根本没声明语法分析是发现不了的这就要靠符号表。我推荐的符号表结构是“作用域栈“全局一个哈希表进入局部复合语句时再压入一个新的哈希表。查找变量时从栈顶一路往下找定义变量时只往当前栈顶写入。这样天然支持了“内层变量遮蔽外层变量”的规则。class ScopeStack { private DequeHashMapString, Symbol stack new ArrayDeque(); public void enterScope() { stack.push(new HashMap()); } public void leaveScope() { stack.pop(); } public void define(String name, Type type) { ... } public Symbol lookup(String name) { ... } }这个阶段最经典的三个“老师常考错误”是重复声明、未声明标识符引用、作用域结束后的错误引用。每一个都需要你在遍历 AST 时对应一个专门的检查分支。4.2 把 if-else 翻译成四元式亲手写一遍才懂控制流实验四要求中间代码生成常见形式是四元式也就是(op, arg1, arg2, result)。算术表达式相对好处理难点在控制流语句。以if (a b) x 1; else x 2;为例四元式可以写成#if_start: (, a, b, T0) // 计算 a b 结果存入临时变量 T0 (jz, T0, _, L_false) // 如果为假跳转到 else (, 1, _, x) // then 分支x 1 (jmp, _, _, L_end) // 跳过 else L_false: (, 2, _, x) // else 分支x 2 L_end:这里有个很关键的机制叫“回填”一开始jz指令的跳转目标是不知道的因为 else 标签还没生成出来。你可以先给指令一个“待回填”标记等后面生成了L_false之后再回填真正的行号。我当年第一次看课本里的回填概念时觉得抽象直到自己动手实现才发现它无非就是“先占坑后填地址”。4.3 布尔表达式别偷懒真出口和假出口要分开维护布尔表达式的翻译在课本上专门讲了 true list 和 false list实验里非常容易被忽略。不少同学直接把它翻译成“计算结果 0 或 1再用 jz 处理”这样做测试分支逻辑不一定错但生成的中间代码指令冗余严重而且不好支持短路运算。更规范的做法是为每个布尔表达式维护两个列表一个记录“为真时跳转的未回填指令”一个记录“为假时跳转的未回填指令”。在处理a b时a为假则可以跳过对b的计算这正是短路的本质。能把这一步写对实验四基本就稳了。注意四元式里的临时变量要以T0、T1递增生成否则两个表达式复用同一个临时变量最终结果会互相覆盖。我在调试时踩过一次排查了很久才发现是指令序列里的临时变量编号冲突。5. 综合实验把 Tokenizer、Parser、CodeGen 整合成完整命令行工具5.1 从单测到集成先保证每条流水线都有日志综合实验最怕的不是单个模块难写而是模块之间接不上。比如你说 Token 的类别是INTparser 里判断IDENT的条件少了一层运行时直接抛异常。我当时的策略是给每个阶段各加一个“转储”入口能够单独打印 token 流、AST、符号表、四元式序列。命令行大概长这样java Compiler demo.c0 -print-tokens java Compiler demo.c0 -print-ast java Compiler demo.c0 -print-ir java Compiler demo.c0 -run这样做的好处极其明显任何时刻出了 bug我都能用“二分定位法”快速判断是哪一层的输出不对。如果没有这些 dump 接口我只能从头到尾黑盒调试那真是灾难。5.2 用一组黄金测试用例验证“全套编译器”我建议从实验一开始就积累测试用例不要等综合实验再临时想。整个编译器最少要有这样几组输入空程序和只含声明语句的程序算术优先级嵌套表达式比如1 2 * 3 - (4 / 2)嵌套 if-else、while 循环、以及循环内有 break 的场景变量遮蔽全局变量和局部变量同名错误输入少分号、未声明变量、类型不匹配。每次都跑同样的用例只要这次结果和上次不一致就说明最近一次改动引入了回归问题。综合实验的最后阶段我基本就是在反复跑这些用例清单比随便敲几个 demo 输入靠谱得多。5.3 Java 代码如何组织包名即架构到了综合实验代码量已经不小了我强烈建议按职责分包。我的工程目录非常直白compiler/ lexer/ // Token、Lexer、TokenType parser/ // Parser、AST节点类 semantic/ // Symbol、ScopeStack、TypeChecker ir/ // Quad、IRGem、Interpreter Compiler.java // 入口这样组织的好处是答辩时很容易讲清楚模块边界词法只负责字符流变 token 流语法只负责 token 流变 AST语义分析只处理类型和作用域IR 只负责代码生成。任何模块替换或修改都不会影响其他部分。我记得答辩时老师就顺着包结构问了一遍我只要按照依赖关系讲下来整个流程非常顺畅。6. 回头再看OUC 编译实验在高年级课程里的特殊位置6.1 实验做完了期末笔试依然要背的概念映射很多同学以为实验过了笔试就稳了其实不然。实验训练的是“会做”笔试考的是“会讲原理”。比如你能手写递归下降不代表你能解释清楚 LR 分析表的构造过程你能生成四元式不代表你能分析属性文法的继承属性与综合属性。但反过来实验确实让理论知识变得容易理解多了。比如课本里讲 DFA 最小化我一开始完全看不懂状态合并的意义做完词法分析器后再回头咀嚼“等价状态”这个概念就能自然联想到标识符和关键字其实在同一状态集合里处理边界。所以我的建议是实验要认真做但不要以为做实验可以替代看书理论和实验是互补关系不是二选一。6.2 给下一届的几个实在建议时间线、工作量、组队策略如果你现在刚开始这门课我给你三个核心建议时间线要提前。词法分析一周解决语法分析至少留两周语义分析和中间代码生成不要压缩到一周综合实验再留两周。拖到最后一周通宵大概率会和我当年一样修改一个 bug 又带出三个新 bug。多读教材里的经典伪代码但不建议直接抄网上的完整工程。那些工程往往用了不少高级封装和课程要求脱节答辩时一问三不知反而减分。合作可以但要先自己跑通一遍。找同学 debug 讨论完全没问题但绝不能分工到“我写词法、你写语法”这种程度因为编译器的各个阶段本质上是一条紧密耦合的流水线谁缺一块整体就转不起来。最后再分享一个小技巧中间代码生成器的调试阶段不要一开始就拿复杂程序测。先测1 2;再测if再测while每加一个特性就回归一遍前面的用例。这个习惯陪着我走完了整个 OUC 编译实验也让我真正体会到编译原理并没有想象中那么遥不可及它只是把一个“读懂源代码”的大问题分解成一层层可以验证、可以测试的小问题。等你亲手把第一个可执行的中间代码跑出结果时那种感觉挺值的。本文还有配套的精品资源点击获取 OUC编译原理实验全解析：手写词法、语法分析与中间代码生成通关指南
简介这是一份面向编译原理课程学习者的完整实验资料内容来自中国海洋大学2020年春季学期编译原理课程涵盖词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、错误处理与编译器综合共8个实验及实验要求文档。资源包共74个文件以C源码为主同时包含lex/flex与yacc/bison的工程文件.l、.y、可执行程序、测试文件及makefile等整体仅774KB便于快速下载和本地复现。已有4408人浏览学习适合高校学生对照课程要求动手实践也适合自学编译器的开发者借鉴完整实验思路。通过逐项实验与要求文档读者可以了解编译器各阶段的主要任务、常见工具链的使用方法并在已有代码基础上进行改造与验证从而系统掌握编译器构造的核心流程。 如果你正在海大读计算机大概率躲不开“OUC编译原理全部实验”这道坎。我印象特别深第一次听说这门课要自己从零写一个能识别词法、分析语法、生成中间代码的小编译器时整个人是懵的——前面的数据库实验、操作系统实验好歹还有框架代码编译原理直接要求我“造轮子”。但等期末把工程交付再回头复盘这一路我反而觉得这是本科阶段含金量最高的一次代码马拉松。这篇文章不打算给你抄完整答案那没有意义。我会按照当年做这套实验的实际流程把每个实验的核心思路、最容易踩的坑、以及我调试到半夜才想明白的原理讲清楚。内容主要基于用 Java 实现、教材采用清华大学出版社编译原理王生原等第三版、并配合哈工大陈鄞老师视频课这种最常见配置你可以对照自己的实验要求灵活调整。1. OUC编译原理实验的整体画像一学期做出一台“会算数”的编译器1.1 实验到底有几次从词法到综合的横向拆解海大的编译原理实验通常不是一次性让你交一个巨无霸工程而是拆成若干阶段每个阶段对应一个课堂知识模块。我当年碰到的是五次实验大致如下实验阶段核心任务课堂理论对应实验一词法分析器正规式、DFA、NFA实验二语法分析器LL(1)、递归下降、FIRST/FOLLOW实验三语义分析与符号表属性文法、类型检查实验四中间代码生成三地址码、四元式、回填实验五综合实验组装完整编译器前后端整合、解释执行这套顺序的聪明之处在于每一次实验都是在上一次产物上做加法。你不需要一步到位做完整编译器但每一步都不能糊弄否则后面跑不起来。比如语法分析如果直接返回一堆“这里报错那里报错”那么语义分析阶段就得回头改 parser中间代码生成又依赖语法树的正确性。说白了这就是一套“欠债迟早要还”的流水线。1.2 每个实验的评分点与卡人之处多数同学以为实验成绩只看最后能不能跑通其实老师更看重三件事功能是否覆盖要求、关键代码是否体现原理、实验报告是否讲得清楚问题与解决过程。功能测试只占一部分真正卡人的往往是“你写的东西能不能经受答辩提问”。另一个容易被忽视的点是老师不要求你用多高级的框架反而会警惕你用正则库和解析器生成器一带而过。因为编译原理实验的核心就是让你手动实现一次 DFA 状态转移、手动写递归下降函数、手动生成四元式。如果全用现成工具等于把最有价值的训练过程外包了。所以我在整个学期都在不断提醒自己宁可代码写得“土”一点也要让每一步都讲得出原理。2. 实验一手写词法分析器时最容易后悔没想明白的三件事2.1 用状态机还是正则匹配库这个决定要早做一开始我确实动过用 Java 正则表达式一把梭的念头Pattern.compile([a-zA-Z_][a-zA-Z0-9_]*)就能匹配标识符多省事。但真写起来才发现问题很多正则库一次匹配一个 Token边界处理和错误定位很难做更重要的是老师一问你“这个正则对应的 DFA 长什么样”你根本讲不清楚。老老实实手写状态机的思路其实并不复杂维护一个当前状态读一个字符更新状态。比如标识符识别的核心逻辑可以简化成下面这样// 伪代码示意 private Token nextToken() { skipWhitespaceAndComments(); int startLine line, startCol col; char c peek(); if (isLetter(c)) { StringBuilder sb new StringBuilder(); while (isLetterOrDigit(peek())) { sb.append(peek()); advance(); } String word sb.toString(); // 先按关键字查表查不到就是标识符 TokenType type keywords.getOrDefault(word, TokenType.IDENT); return new Token(type, word, startLine, startCol); } if (isDigit(c)) { // 数字识别注意要支持多位数以及数字后面的非法字符检查 } // 运算符、分隔符单字符和双字符分开处理 }这段代码看起来简单但里面藏着第一个大坑关键字和标识符的区分不能只靠“第一个字符是不是字母”而是必须走最长匹配。如果你在读到第一个字符i时就先判断它是if那么遇到intValue这种变量名就会识别成关键字直接整段崩掉。正确做法是先读完整段字母数字序列再查关键字表。2.2 忽略行号和列号后面调试会哭很多同学实验一犯的“调式拖延症”是没有在 Token 里存行号和列号。等到实验二、实验三一报错满屏只有一串null或者空指针你根本不知道是哪一行哪一列出了问题。我的建议很简单从一开始就给 Token 加上line和col字段。这样做的好处是语法分析报错时你能输出这种可读信息Parse error at line 3, column 12: unexpected token ) , expected ;实验报告里贴上这种日志截图比贴十页代码更让老师认可。提示注释的处理也要在词法阶段完成。行注释//和块注释/* */都要跳过并且块注释里不能忽略换行计数否则后续报错的行号全错位。2.3 Token 的类别设计要预留扩展空间我第一版写的 Token 只有type和value两个字段结果到了实验三做类型检查时我不得不在语法树上重新去找每个标识符对应的字符串值非常别扭。比较合理的做法是enum TokenType { INT, VOID, IF, ELSE, WHILE, FOR, RETURN, IDENT, NUMBER, PLUS, MINUS, STAR, SLASH, ASSIGN, EQ, NE, LT, LE, GT, GE, SEMI, COMMA, LPAREN, RPAREN, LBRACE, RBRACE, LBRACKET, RBRACKET, EOF } class Token { TokenType type; String lexeme; int line; int col; }lexeme保存原始单词type保存类别这样后面做符号表查重、类型比较时都非常顺手。别小看这个设计后期能帮你省掉大量“类型转型”的脏代码。3. 实验二语法分析我为什么拼命劝你用递归下降3.1 先改写文法再写代码顺序千万别反实验二是很多人的分水岭。我看到不少同学拿到文法就开始写 parse 函数结果写完才发现左递归导致无限循环expr - expr term左边递归代码里parseExpr()第一句话又调用parseExpr()栈直接爆掉。正确流程是先做文法等价改写。常见的操作有两个一是消除左递归二是提取左因子。比如算术表达式可以改写成适合递归下降的文法expr - term expr_rest expr_rest - term expr_rest | - term expr_rest | ε term - factor term_rest term_rest - * factor term_rest | / factor term_rest | ε factor - NUMBER | IDENT | ( expr )改写完再手算一遍 FIRST 和 FOLLOW 集合心里有数后再动手写代码。这一步看起来很“理论”实际价值非常大——它能帮你确认某个 token 应该由哪个非终结符处理也能少踩很多分支逻辑混乱的坑。3.2 每个非终结符对应一个方法代码骨架越规整越省心我见过有些同学把整个语法分析写成一个五百行的巨型函数里面 switch-case 满天飞。调试的时候想单步跟进某个分支头皮都发麻。递归下降的核心思想是“一符一函数”结构清晰程度和文法几乎一一对应class Parser { private Lexer lexer; private Token lookahead; // E - T E public ASTExpr parseExpr() { ASTExpr left parseTerm(); while (lookahead.type TokenType.PLUS || lookahead.type TokenType.MINUS) { Token op lookahead; nextToken(); ASTExpr right parseTerm(); left new ASTBinaryExpr(left, op, right); // 构建语法树节点 } return left; } }注意这里我在递归下降的同时就直接构建了 AST 节点。这样实验三做语义分析和实验四做中间代码生成时就不需要再把 token 流从头推一遍语法了。虽然一开始写 AST 类会多一点代码但从整条实验链路看是完全值得的。3.3 错误恢复不追求完美但要能“跌倒后爬起来”语法分析器最容易出现的崩溃场景是用户输入少了一个分号你的 parser 抛个异常直接退出。如果是作业引擎测试可能意味着后面的测试用例全部得不到结果。课程实验里最常用的技巧叫“恐慌模式”错误恢复当解析到非法 token 时不直接终止整个程序而是跳过一些 token直到找到一个“同步标记”比如分号、右大括号。这个同步标记通常是当前语句的结束位置。实现起来也很简单private void synchronize() { while (lookahead.type ! TokenType.EOF) { if (lookahead.type TokenType.SEMI || lookahead.type TokenType.RBRACE) { nextToken(); return; } nextToken(); } }这样即使 token 流里有错误语法分析也能尽量多分析出几处问题最后一次性汇总报错。这个设计在实验报告里写出来明显比“遇错就死”高一个档次。4. 实验三和四语义分析与中间代码生成最容易翻车的地带4.1 符号表设计作用域栈加 HashMap 没那么简单到了实验三很多同学才明白什么叫“编译前端的另一半”。语法分析只管结构对不对不管语义对不对。a b 1里如果b根本没声明语法分析是发现不了的这就要靠符号表。我推荐的符号表结构是“作用域栈“全局一个哈希表进入局部复合语句时再压入一个新的哈希表。查找变量时从栈顶一路往下找定义变量时只往当前栈顶写入。这样天然支持了“内层变量遮蔽外层变量”的规则。class ScopeStack { private DequeHashMapString, Symbol stack new ArrayDeque(); public void enterScope() { stack.push(new HashMap()); } public void leaveScope() { stack.pop(); } public void define(String name, Type type) { ... } public Symbol lookup(String name) { ... } }这个阶段最经典的三个“老师常考错误”是重复声明、未声明标识符引用、作用域结束后的错误引用。每一个都需要你在遍历 AST 时对应一个专门的检查分支。4.2 把 if-else 翻译成四元式亲手写一遍才懂控制流实验四要求中间代码生成常见形式是四元式也就是(op, arg1, arg2, result)。算术表达式相对好处理难点在控制流语句。以if (a b) x 1; else x 2;为例四元式可以写成#if_start: (, a, b, T0) // 计算 a b 结果存入临时变量 T0 (jz, T0, _, L_false) // 如果为假跳转到 else (, 1, _, x) // then 分支x 1 (jmp, _, _, L_end) // 跳过 else L_false: (, 2, _, x) // else 分支x 2 L_end:这里有个很关键的机制叫“回填”一开始jz指令的跳转目标是不知道的因为 else 标签还没生成出来。你可以先给指令一个“待回填”标记等后面生成了L_false之后再回填真正的行号。我当年第一次看课本里的回填概念时觉得抽象直到自己动手实现才发现它无非就是“先占坑后填地址”。4.3 布尔表达式别偷懒真出口和假出口要分开维护布尔表达式的翻译在课本上专门讲了 true list 和 false list实验里非常容易被忽略。不少同学直接把它翻译成“计算结果 0 或 1再用 jz 处理”这样做测试分支逻辑不一定错但生成的中间代码指令冗余严重而且不好支持短路运算。更规范的做法是为每个布尔表达式维护两个列表一个记录“为真时跳转的未回填指令”一个记录“为假时跳转的未回填指令”。在处理a b时a为假则可以跳过对b的计算这正是短路的本质。能把这一步写对实验四基本就稳了。注意四元式里的临时变量要以T0、T1递增生成否则两个表达式复用同一个临时变量最终结果会互相覆盖。我在调试时踩过一次排查了很久才发现是指令序列里的临时变量编号冲突。5. 综合实验把 Tokenizer、Parser、CodeGen 整合成完整命令行工具5.1 从单测到集成先保证每条流水线都有日志综合实验最怕的不是单个模块难写而是模块之间接不上。比如你说 Token 的类别是INTparser 里判断IDENT的条件少了一层运行时直接抛异常。我当时的策略是给每个阶段各加一个“转储”入口能够单独打印 token 流、AST、符号表、四元式序列。命令行大概长这样java Compiler demo.c0 -print-tokens java Compiler demo.c0 -print-ast java Compiler demo.c0 -print-ir java Compiler demo.c0 -run这样做的好处极其明显任何时刻出了 bug我都能用“二分定位法”快速判断是哪一层的输出不对。如果没有这些 dump 接口我只能从头到尾黑盒调试那真是灾难。5.2 用一组黄金测试用例验证“全套编译器”我建议从实验一开始就积累测试用例不要等综合实验再临时想。整个编译器最少要有这样几组输入空程序和只含声明语句的程序算术优先级嵌套表达式比如1 2 * 3 - (4 / 2)嵌套 if-else、while 循环、以及循环内有 break 的场景变量遮蔽全局变量和局部变量同名错误输入少分号、未声明变量、类型不匹配。每次都跑同样的用例只要这次结果和上次不一致就说明最近一次改动引入了回归问题。综合实验的最后阶段我基本就是在反复跑这些用例清单比随便敲几个 demo 输入靠谱得多。5.3 Java 代码如何组织包名即架构到了综合实验代码量已经不小了我强烈建议按职责分包。我的工程目录非常直白compiler/ lexer/ // Token、Lexer、TokenType parser/ // Parser、AST节点类 semantic/ // Symbol、ScopeStack、TypeChecker ir/ // Quad、IRGem、Interpreter Compiler.java // 入口这样组织的好处是答辩时很容易讲清楚模块边界词法只负责字符流变 token 流语法只负责 token 流变 AST语义分析只处理类型和作用域IR 只负责代码生成。任何模块替换或修改都不会影响其他部分。我记得答辩时老师就顺着包结构问了一遍我只要按照依赖关系讲下来整个流程非常顺畅。6. 回头再看OUC 编译实验在高年级课程里的特殊位置6.1 实验做完了期末笔试依然要背的概念映射很多同学以为实验过了笔试就稳了其实不然。实验训练的是“会做”笔试考的是“会讲原理”。比如你能手写递归下降不代表你能解释清楚 LR 分析表的构造过程你能生成四元式不代表你能分析属性文法的继承属性与综合属性。但反过来实验确实让理论知识变得容易理解多了。比如课本里讲 DFA 最小化我一开始完全看不懂状态合并的意义做完词法分析器后再回头咀嚼“等价状态”这个概念就能自然联想到标识符和关键字其实在同一状态集合里处理边界。所以我的建议是实验要认真做但不要以为做实验可以替代看书理论和实验是互补关系不是二选一。6.2 给下一届的几个实在建议时间线、工作量、组队策略如果你现在刚开始这门课我给你三个核心建议时间线要提前。词法分析一周解决语法分析至少留两周语义分析和中间代码生成不要压缩到一周综合实验再留两周。拖到最后一周通宵大概率会和我当年一样修改一个 bug 又带出三个新 bug。多读教材里的经典伪代码但不建议直接抄网上的完整工程。那些工程往往用了不少高级封装和课程要求脱节答辩时一问三不知反而减分。合作可以但要先自己跑通一遍。找同学 debug 讨论完全没问题但绝不能分工到“我写词法、你写语法”这种程度因为编译器的各个阶段本质上是一条紧密耦合的流水线谁缺一块整体就转不起来。最后再分享一个小技巧中间代码生成器的调试阶段不要一开始就拿复杂程序测。先测1 2;再测if再测while每加一个特性就回归一遍前面的用例。这个习惯陪着我走完了整个 OUC 编译实验也让我真正体会到编译原理并没有想象中那么遥不可及它只是把一个“读懂源代码”的大问题分解成一层层可以验证、可以测试的小问题。等你亲手把第一个可执行的中间代码跑出结果时那种感觉挺值的。本文还有配套的精品资源点击获取