简介一份覆盖中国海洋大学2020年春季学期编译原理课程全部8个实验的完整源码与实验要求文档包面向正在学习编译器构造的计算机专业学生。实验由浅入深依次涉及词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、错误处理与编译器综合并配有实验要求文档说明各实验目标、预期输出与考核标准可帮助读者系统掌握从源码到可执行程序的编译全流程。压缩包共74个文件包含C源码、flex/bison语法文件.l/.y、头文件、makefile、可执行程序及实验说明文档等包体仅774KB便于下载后快速在本地环境编译运行。资源已有4411人学习适合作为课程实验的参考模板或自学编译器设计的入门实践材料。通过对照实验要求与示例代码读者能模仿经典语法分析器实现思路掌握符号表管理、中间表示生成、错误恢复等核心难点。1. OUC编译原理全部实验从词法到中间代码的一条龙实现OUC编译原理全部实验是中国海洋大学OUC编译原理课程上机实验的完整源码集合覆盖从词法分析、语法分析、符号表管理到中间代码生成这条完整前端链路。这份资源不是半成品拼盘每个实验的输入输出边界都对齐到可验收状态词法分析输出带行列号的 token 流语法分析构建 AST 并支持 panic mode 错误恢复语义阶段做符号表管理和类型检查最后落成带临时变量的三地址码。适合两类人一类是正在赶编译原理实验、想找结构清晰的参考代码的同学另一类是实验做完但没搞懂几个阶段怎么拼起来的人——对照这份代码的调用链看比翻教材快得多。你可以不照抄但拿它换文法、改参数、对拍验活至少能省一整个通宵。2. 词法分析状态机实现、关键字识别与错误定位2.1 一套编译前端实验的完整模块划分拆开这份资源你会发现它并不是孤立的几个 Main 类而是按编译阶段组织的模块化工程。常见课程设计会把编译前端拆成四到六个实验词法单独一个语法选 LL(1) 或 LR(1) 一个符号表有时独立成一个实验语义检查和中间代码生成各占一个。OUC 的编译原理上机题也遵循这条主线这套源码把每个阶段都落成了可独立运行的 Java 类入口统一放在 Main 类里按命令行参数切换。阶段验收产出输入 → 输出词法分析token 流含行列号、种别码源程序 → ListToken语法分析抽象语法树 / 分析过程token 流 → AST符号表管理作用域符号表AST 遍历期间实时维护语义检查类型错误与未定义变量报告AST → 报错列表中间代码生成三地址码AST → ListQuad工程目录按这个链路组织源码包里的布局大致是这样compiler-src/ ├── src/cn/edu/ouc/ │ ├── lexer/ # Token、TokenType、Lexer │ ├── parser/ # Parser、ASTNode、递归下降与表驱动入口 │ ├── symbol/ # Symbol、SymbolTable、作用域管理 │ ├── semantic/ # TypeChecker、语义错误列表 │ └── codegen/ # Quad、ThreeAddrEmitter ├── testcase/ # *.cmm 源程序和对应的期望输出 └── README.mdtestcase 目录里每个.cmm源文件旁配一个.exp期望输出这是整个工程能自动对拍的前提。验收回归靠的是diff而不是肉眼看输出这条思路从第一个实验就要建立起来。至于选 Java 而不是 C原因很实际词法阶段要频繁查关键字表、语法阶段要算集合、语义阶段要维护嵌套符号表Java 的 HashMap、HashSet 和泛型集合写起来手顺另外javac、java命令天然适合脚本对拍不用像 C 那样处理头文件和链接。网上一搜 java编译原理 的实验源码也不少但在代码结构清晰度上这套算得上规整。2.2 手工状态机的核心代码逐字符处理与关键字查表词法分析器的本质是一个有限状态自动机从起始状态出发每读一个字符转移一次状态读到终结状态就确定一个 token。写实验代码时不需要真的建模状态图用几个分支方法就能覆盖全部状态转移。public class Lexer { private final String src; private int pos 0; private int line 1, col 0; private static final MapString, TokenType KEYWORDS new HashMap(); static { KEYWORDS.put(if, TokenType.IF); KEYWORDS.put(else, TokenType.ELSE); KEYWORDS.put(while, TokenType.WHILE); KEYWORDS.put(int, TokenType.INT); KEYWORDS.put(float, TokenType.FLOAT); KEYWORDS.put(return, TokenType.RETURN); } public Token nextToken() { skipWhitespace(); if (pos src.length()) { return new Token(TokenType.EOF, $, line, col); } int startLine line, startCol col; char ch src.charAt(pos); if (Character.isLetter(ch)) { return readWord(startLine, startCol); } if (Character.isDigit(ch)) { return readNumber(startLine, startCol); } return readOperator(startLine, startCol); } private void skipWhitespace() { while (pos src.length()) { char ch src.charAt(pos); if (ch \n) { line; col 0; pos; } else if (ch || ch \t || ch \r) { col; pos; } else break; } } private Token readWord(int startLine, int startCol) { StringBuilder sb new StringBuilder(); while (pos src.length()) { char ch src.charAt(pos); if (Character.isLetterOrDigit(ch)) { sb.append(ch); pos; col; } else break; } String word sb.toString(); return new Token( KEYWORDS.getOrDefault(word, TokenType.IDENTIFIER), word, startLine, startCol); } }关键字识别用了一个看似取巧的方案先把词按标识符读出来再去查 KEYWORDS 表。这样“while”不会读成“whil”加“e”也不需要为每个关键字单独建一个状态。给每个关键字单独建状态的做法是纯自虐状态多了之后维护成本暴涨完全没必要。注意两个细节一是isLetterOrDigit连续读变量名abc123才能被完整切出来二是col在每个字符消费时自增而不是在 token 结束时统一计算。这样多字符运算符如的列号取的是起点位置报错时定位才准。2.3 错误定位行号列号的维护与报错格式词法阶段最容易翻车的不在识别而对报错格式。验收脚本通常按“行号,类型,值”或“行号 种别码 属性值”这种固定格式比对 token 流你多打一个空格、少打一个逗号整份输出就废了。我一般统一输出为[line:col] 词法错误: 无法识别的字符 ?错误信息混入 token 流会让对拍很难看所以建议所有报错走标准输出但加统一前缀后面第 5 章会再展开。下面这段readOperator处理双字符运算符是词法分析里必须小心的部分private Token readOperator(int startLine, int startCol) { char ch src.charAt(pos); col; switch (ch) { case : if (pos src.length() src.charAt(pos) ) { pos; col; return new Token(TokenType.LE, , startLine, startCol); } return new Token(TokenType.LT, , startLine, startCol); case : if (pos src.length() src.charAt(pos) ) { pos; col; return new Token(TokenType.EQ, , startLine, startCol); } return new Token(TokenType.ASSIGN, , startLine, startCol); default: if (-*/;,()[]{}.indexOf(ch) 0) { return new Token(TokenType.SYMBOL, String.valueOf(ch), startLine, startCol); } throw new LexException(line, col, 无法识别的字符 ch ); } }这里用的是“超前查看一个字符”的策略先取当前字符再看下一个字符是否等于由此区分和、和。实验代码里建议最多超前查看一个字符就够处理 这类前缀重叠的运算符时两个字符的状态转移逻辑已经足够清晰。3. 语法分析LL(1) 递归下降与 SLR(1) 表驱动的选型实战3.1 递归下降与表驱动的适用边界语法分析是编译原理实验里最耗时间的一环。选递归下降还是 SLR(1) 表驱动我的判断标准是先看实验题怎么要求如果题目说“用预测分析法分析表达式”递归下降配合预测分析表最顺手如果题目点名“构造自动分析器”或“实现 SLR(1) 分析”那就必须做表驱动。两个方案没有绝对优劣但自己手写时递归下降的错误定位天然贴近源码调试体验好很多。递归下降的本质是每个非终结符对应一个方法。下面这段解析 C-- 表达式是典型写法// expr → term { (|-) term } private ASTNode expr() { ASTNode node term(); // 先解析 term while (peek().type TokenType.PLUS || peek().type TokenType.MINUS) { Token op advance(); ASTNode right term(); // 注意是 term 不是 expr node new BinOpNode(op, node, right); } return node; }这里的 while 循环不是递归调用 expr 本身所以不需要额外消除左递归。如果写成expr - term | expr term教科书文法递归下降会直接死循环。每个方法必须保证至少消费一个 token 再返回这是递归下降的第一纪律。3.2 FIRST/FOLLOW 集合与预测分析表的构造表驱动方案绕不开 FIRST 和 FOLLOW 集合。以经典表达式文法为例E - T E1 E1 - T E1 | ε T - F T1 T1 - * F T1 | ε F - ( E ) | id | num计算出的 FIRST 集合如下非终结符FIRSTE{ id, num, ( }E1{ , ε }T{ id, num, ( }T1{ *, ε }F{ id, num, ( }FOLLOW 集合在构造预测分析表时才会用到重点看 E 和 E1非终结符FOLLOWE{ $, ) }E1{ $, ) }T{ , $, ) }T1{ , $, ) }F{ , *, $, ) }集合的计算是迭代过程直到所有集合不再变化为止。手算几次之后我一般直接用代码算def compute_first(g): first defaultdict(set) changed True while changed: changed False for lhs, rhs in g.productions: for sym in rhs: before len(first[lhs]) first[lhs] | (first[sym] - {ε}) after len(first[lhs]) if before ! after: changed True if ε not in first[sym]: break return first规则不复杂产生式右边第一个终结符加入左边如果某个非终结符有 ε就继续往后看下一个符号。真正影响正确性的是迭代只加不减所以外层 while 用集合长度变化做终止条件。3.3 冲突消解与 panic mode 错误恢复表驱动方案在构造 ACTION/GOTO 表时必然遇到两类冲突实验报告里也常被问到冲突类型典型来源解决办法shift/reduce悬空 else、运算符优先级未定义引入优先级声明或改写文法reduce/reduce同一状态存在两个可归约项检查文法是否有等价产生式悬空 else 是 shift/reduce 冲突的教科书案例if (expr) if (expr) stmt else stmt这个 else 既可以归约外层 if也可以移进内层 if。常见处理是声明 else 优先级高于其他也就是“就近匹配”或者在文法上强行拆开。手动构造分析表时检测到冲突后在状态里保留优先级更高的动作即可。分析器跑起来后还会遇到语法错误实验里通常用 panic mode 恢复遇到错误就把 token 不断丢弃直到碰到同步符号集合。我常用的同步符号集是分号、右花括号和文件结束符private static final SetTokenType SYNC_SET EnumSet.of(TokenType.SEMI, TokenType.RBRACE, TokenType.EOF); private void synchronize() { while (!SYNC_SET.contains(peek().type)) { advance(); } }这个方法的妙处在于它永远不会无限循环——EOF 一定在同步集合里最坏情况是丢完所有输入然后报一次最终的“意外文件结束”。错误恢复不是让你不报错而是让解析器从错误里活过来继续检查后面的代码一次编译多报几个错总比重启十次强。4. 语义分析与中间代码符号表、类型检查与三地址码生成4.1 符号表作用域嵌套、重复定义与查找时机编译原理实验里的符号表核心就两个问题作用域怎么嵌套、定义和查找的规则怎么定。很多同学的实现是“一个 HashMap 走天下”这种方案在嵌套块里必然翻车——函数体内定义一个i另一个块再定义i时要么误报重复定义要么查不到外层同名变量。我常用的方案是链式作用域每个作用域一个 Map压入栈里查找时从当前层逐层往外找。public class SymbolTable { private final DequeMapString, Symbol scopes new ArrayDeque(); public void enterScope() { scopes.push(new HashMap()); } public void exitScope() { scopes.pop(); } public void define(String name, Symbol s) { MapString, Symbol cur scopes.peek(); if (cur.containsKey(name)) { throw new SemanticException(重复定义: name); } cur.put(name, s); } public Symbol lookup(String name) { for (MapString, Symbol scope : scopes) { if (scope.containsKey(name)) { return scope.get(name); } } return null; } }define只检查当前作用域lookup逐层遍历这两个方法的语义必须分开。有一个容易漏的细节函数参数应该先define进函数体作用域再解析函数体否则函数内部引用参数时会报“未定义变量”这个错误在实验里极其常见。4.2 类型检查规则表与隐式转换类型检查基于 AST 遍历不同节点的检查规则先列出来表达式类型规则结果类型int int无需转换intint floatint 隐式提升为 floatfloatfloat float无需转换floatarr[i]arr 必须为数组i 必须为 int数组元素类型函数调用实参个数与类型匹配形参函数返回类型隐式转换的处理建议在类型检查阶段直接修改 AST 节点给 BinOpNode 加一个targetType字段标记两端要不要提升。后面生成中间代码时看到targetType FLOAT就把另一个操作数的类型改成 float不需要重新遍历。把转换动作藏在语义阶段中间代码生成器会简单很多。4.3 三地址码生成临时变量分配与布尔表达式回填三地址码生成器的核心是临时变量分配。每条指令至多一个运算符结果放进一个新的临时变量。用一个自增计数器是标准做法public class ThreeAddrEmitter { private int tempCount 0; private final ListQuad code new ArrayList(); private String newTemp() { return t tempCount; } public String genBinary(String op, String left, String right) { String result newTemp(); code.add(new Quad(op, left, right, result)); return result; } public String visitBinOp(BinOpNode node) { String left visit(node.left); String right visit(node.right); if (node.op.type TokenType.PLUS) { return genBinary(, left, right); } if (node.op.type TokenType.EQ) { return genBinary(, left, right); } return genBinary(node.op.lexeme, left, right); } }每个节点返回的是“这个子表达式的存储位置”父节点拿它当参数。这里的调用顺序和最终打印顺序可能不一致所以中间代码不要边生成边打印先把 Quad 都收进 List最后统一输出。布尔表达式的短路计算要稍微绕一点。a || b要生成的不是一条简单运算而是条件跳转先算 a如果为真直接跳到真出口为假才继续算 b。实验里常用回填backpatch技术生成跳转指令时目标地址先填占位值等真出口、假出口确定后再回头补上。5. 避坑实验验收中的五个经典翻车点与排查5.1 token 输出格式错位导致验收获判零分现象自己终端里看 token 流完全正常单词也对但交上去就是零分或者大面积扣分。原因验收脚本按固定分隔符比对。你的输出是“类型 值 行号”脚本要的是“行号,类型,值”一个顺序不对整行全错。还有的把 token 流和错误信息混打脚本本应读到 20 行 token结果前两行是报错文本。解决先找实验说明里的输出格式样例严格照抄。拿 testcase 里给的期望输出文件做diff而不是肉眼看。我一般在所有报错前加统一前缀ERROR:验收脚本匹配到ERROR:就认为该用例失败token 流部分交给另一个脚本检查两边不互相污染。5.2 递归下降死循环没消费 token 就递归现象程序跑起来不报错也不结束CPU 占用拉满多半是栈溢出或 while 死循环。原因某个非终结符方法在解析失败时没有抛异常而是返回 null外层循环看到 null 后继续调下一轮或者advance()没有真正让 pos 前进token 流卡在同一个位置。解决每个方法入口断言当前 token 的类型。advance()里必须pos然后返回旧 token同时方法的返回值不要用 null 表示失败直接抛ParseException。我在实现 expr 和 term 时被这种死循环坑过两次从那以后所有解析方法都强制先写 token 消费再写逻辑再也没有空转问题。5.3 SLR(1) 冲突shift/reduce 与 reduce/reduce现象构造分析表时打印出一堆“shift/reduce conflict in state 12”或者在运行 analyze 时走进错误分支。原因文法本身有二义性最常见的是悬空 else。reduce/reduce 冲突则通常是文法里有两条产生式右部完全一样比如A - B和C - B同时可以把同一个符号归约成不同非终结符。解决shift/reduce 冲突先改文法把悬空 else 拆成两条 stmt 产生式如果文法不允许大改就声明优先级。reduce/reduce 冲突基本只能改文法两条右部一样的产生式必然说明文法层次设计有问题。实验报告里把冲突前后的 ACTION 表各贴一份老师一眼就看明白你做过调试。5.4 符号表作用域清理时机不对现象函数体里的局部变量在函数结束后还能查到或者同一个函数里两个嵌套块各自定义同名变量被误判成重复定义。原因enterScope()和exitScope()没配对。解析函数体时中途抛了异常异常一路向上穿exitScope()根本没执行到栈里残留了没弹出的作用域。解决解析每个 block 时用try/finally包住finally里强制exitScope()。这样即使语法错误导致线程中断作用域也会被正确弹出。注意函数参数要先define再进入函数体作用域否则 lookup 参数时找的是全局同名变量类型对不上还不好查。5.5 三地址码临时变量编号错乱现象输出的三地址码从 t0 到 t9 编号连续但引用关系对不上比如t3 t2 t1可 t1 在这之前根本不是那个值。原因生成三地址码时边遍历 AST 边打印而 visit 的调用顺序是深度优先右结合的打印顺序和结果的赋值顺序不一致。比如先访问了右子树算出 t2随后左子树又启动计数器生成了 t3等回到根节点时引用的临时变量编号全乱。解决先递归生成完所有 Quad统一存进 List最后再一起输出。临时变量的分配只发生在newTemp()这一个入口确保生成顺序和遍历顺序完全一致。对拍时如果发现编号错乱先在 Quad 列表的打印循环里断点看的是“生成后的完整列表”而不是“边生成边输出的行”问题立刻暴露。6. 进阶用法把整套实验改造成一次可对拍的编译流水线6.1 一条命令跑完全链路实验做到后期别总用 IDE 点按钮把编译和测试合成一条命令效率高很多。我习惯在工程根目录写一个简单脚本javac -d out $(find src -name *.java) java -cp out cn.edu.ouc.compiler.Main testcase/test01.cmm test01.out diff test01.out testcase/test01.exp-d out指定字节码输出目录-cp out是 classpathfind src -name *.java把源码全部收集起来编译。换成更自动化的循环写法一次跑完所有用例并把结果显示在终端for f in testcase/*.cmm; do base$(basename $f .cmm) java -cp out cn.edu.ouc.compiler.Main $f /tmp/$base.out if diff -q /tmp/$base.out testcase/$base.exp /dev/null; then echo PASS: $base else echo FAIL: $base fi donediff -q只输出是否不同适合快速过一遍。失败的时候再用不带-q的 diff 看具体差异。6.2 用 AST 可视化辅助调试语法分析器的调试比起词法要难一个量级token 流错了能看到行号AST 结构错了却很难从报错里看出来。我给 AST 节点加了一个toDot()方法输出 Graphviz 格式用dot -Tsvg直接生成节点图java -cp out cn.edu.ouc.compiler.Main -ast testcase/test02.cmm | dot -Tsvg ast.svg-ast参数让 Main 在语法分析完成后输出 AST 的 dot 描述而不是继续做语义分析。看图形化的树比盯着一堆嵌套括号值直观得多尤其检查左结合性、优先级这类问题时一张图就能定位是哪层节点挂错了。从那以后我每次改完语法或语义代码第一件事就是跑一遍上面的对拍循环再顺手生成一张 AST 图扫一眼结构。diff 一红就先修问题绝不在红灯状态下继续写新功能这套习惯帮我拦住了至少三次最低级的拼写错误。希望帮到你。本文还有配套的精品资源点击获取
