简介：这是一套面向中国海洋大学编译原理课程的实验源码与指导合集，覆盖2020年春季学期全部8个实验：从词法分析、语法分析、语义分析，到中间代码生成、代码优化、目标代码生成、错误处理与编译器综合，并附《实验内容和要求》文档，适合正在学习编译器构造的学生按阶段对照实践。压缩包内共有74个文件，以C源码和Lex/Yacc源文件为核心，配合头文件、makefile构建脚本、可执行程序与测试用例，整体仅774KB，目录按实验一至八分模块展示，便于定位。已有4411人学习下载。借助其中完整的编译前端实现、语法树打印与错误诊断代码，以及测试程序和输出样例，读者可运行调试、观察二义性文法与无二义文法的处理差异，并将各阶段组件串成完整编译器，真正理解编译原理从源码到目标代码的完整脉络。

1. OUC编译原理全部实验：一门课里最值得自己动手重写的代码

OUC编译原理全部实验，是这类课程里最值得自己一行行重写的代码：词法分析、语法分析、语义分析、符号表管理，串起来就是一条完整的编译器前端链路。很多人上课时听懂了正则、LL(1)、LR(1)，一打开实验模板却对着几百行骨架发懵，最后从网上找一份代码改个文件名交差，答辩时连变量都解释不清。这篇文章按课程实验的常见顺序，把每个实验的输入、输出、边界和踩坑讲清楚，写给两类人：正在被实验报告追着跑的在校生，以及工作后想回炉把编译原理前端补扎实的工程师。你能照着这个思路重写一套自己的实现，而不是复制一份连注释都是别人的代码。

2. 词法分析实验：从正则到 token 流，手写一个扫描器

2.1 词法分析到底在考什么：把正则文法变成状态机

词法分析实验是整个编译原理实验的入口，它的任务是把源程序字符串拆成 token 序列。很多人觉得这是在考正则表达式，实际上实验模板给你的往往不是正则库，而是要求你手工构造一个有限自动机。比如识别一个标识符，正则写起来是[a-zA-Z_][a-zA-Z0-9_]*，但手写扫描器时你要维护的状态是：当前字符是不是字母或下划线、后续字符是否允许出现在标识符中间、什么时候该把累积的字符切出来。

这里的核心概念是“最长匹配”。比如输入intx，如果关键字表里只有int，扫描器不能读进i、n、t就立刻判定为关键字，而要继续读x，发现intx整体是一个标识符。最容易出错的地方也在这里：把关键字判定放在最长匹配之前，导致intx被拆成int和x两个 token。实验报告的得分点通常就藏在这种边界用例里。

我见过不少同学直接用 JDK 的String.split加一堆正则硬拆，面对运算优先级不敏感的简单语法也能跑通，但一旦加上字符串常量、浮点数、多行注释，规模就失控了。常见做法仍然是手写逐字符扫描，因为词法分析器的逻辑是线性的：读一个字符、判断状态、决定是否切分。这个线性逻辑在后续语法分析报错时需要精确到行号和列号，正则批量替换很难做到。

2.2 最小可跑的 Java 词法分析器：识别标识符、数字、运算符

下面这个实现是我常用的一种最小结构，适合 OUC 编译原理第一个实验的常见要求：识别标识符、整型/浮点数字、加减乘除运算符、括号、赋值号，并记录行号。语言用 Java，因为很多学校模板就是 Java，但它换成 C++ 或 Python 只是语法差异，状态迁移逻辑完全一样。

import java.util.ArrayList; import java.util.List; import java.util.Set; public class Lexer { private final String src; private int pos = 0; private int line = 1; private static final Set<String> KEYWORDS = Set.of("int", "float", "if", "else", "while", "return"); public Lexer(String src) { this.src = src; } public List<Token> tokenize() { List<Token> tokens = new ArrayList<>(); while (pos < src.length()) { char c = src.charAt(pos); if (Character.isWhitespace(c)) { if (c == '\n') line++; pos++; } else if (Character.isLetter(c) || c == '_') { tokens.add(readIdentifierOrKeyword()); } else if (Character.isDigit(c)) { tokens.add(readNumber()); } else if (c == '+' || c == '-' || c == '*' || c == '/') { tokens.add(new Token("OP", String.valueOf(c), line)); pos++; } else if (c == '(' || c == ')' || c == '{' || c == '}') { tokens.add(new Token("DELIM", String.valueOf(c), line)); pos++; } else if (c == '=') { if (pos + 1 < src.length() && src.charAt(pos + 1) == '=') { tokens.add(new Token("OP", "==", line)); pos += 2; } else { tokens.add(new Token("ASSIGN", "=", line)); pos++; } } else { throw new LexException("无法识别的字符 '" + c + "' 在第 " + line + " 行"); } } tokens.add(new Token("EOF", "", line)); return tokens; } private Token readIdentifierOrKeyword() { int start = pos; while (pos < src.length() && (Character.isLetterOrDigit(src.charAt(pos)) || src.charAt(pos) == '_')) { pos++; } String word = src.substring(start, pos); String type = KEYWORDS.contains(word) ? "KEYWORD" : "IDENT"; return new Token(type, word, line); } private Token readNumber() { int start = pos; while (pos < src.length() && Character.isDigit(src.charAt(pos))) { pos++; } if (pos < src.length() && src.charAt(pos) == '.') { pos++; while (pos < src.length() && Character.isDigit(src.charAt(pos))) { pos++; } } return new Token("NUM", src.substring(start, pos), line); } }

逻辑说明：tokenize()是主循环，每次只前进一步，遇到空白字符时单独处理换行，保证行号跟踪准确。readIdentifierOrKeyword()先按“字母/数字/下划线连续”读满整个词，再查关键字表，把intx这类输入正确处理为标识符。readNumber()使用两个连续的while循环，第一个保证整型部分读完，第二个在遇到小数点时读取小数部分，这样能识别3.14而不是拆成3、.、14。

参数说明：KEYWORDS集合决定了哪些词会被当作关键字，实际实验里要根据自定义文法增减。==这种情况是二字符运算符的典型代表，如果你的文法还有>=、<=、&&，需要在=分支里继续扩展字符匹配。行号记录实现是line++，但注释和字符串里的换行不能触发行号自增，这块在扩展实验里必须改。

注意：这种实现默认源程序是纯 ASCII。如果实验要求支持中文字符串常量，Character.isLetter会把中文也判定为标识符起始字符，需要在readIdentifierOrKeyword()里增加“仅 ASCII 字母”的判断。

2.3 必调细节：关键字表、行号记录、错误恢复

词法分析器看起来代码量不大，但几个细节决定了实验能不能拿到高分。第一是关键字表放在哪里。有的人把关键字写在switch里，每读一个词做字符串比较，效率低且难维护；用Set的contains判断，复杂度是 O(1)，而且扩展关键字只改一处。

第二是行号记录。很多同学只在 token 里存了词法和值，没存行号，等到语法分析实验做报错定位时才发现要回头改结构。我建议从第一个实验就把Token类设计成包含type、value、line三个字段，后面所有实验都能直接复用。

第三是错误恢复。词法分析遇到非法字符时，最简单的做法是抛异常结束。但课程实验有时候要求“跳过非法字符继续分析”，这时候需要把异常换成recordError()并在累加错误数后pos++跳过。如果目标不是课程分数而是做一个真正能用的前端，我建议保留“报错即停”的模式，因为早期编译阶段频繁出错时，一次性给你 50 个错误里可能只有 5 个是真的，其余全是连锁误报。

3. 语法分析实验：用递归下降吃掉表达式与语句

3.1 为什么实验选递归下降而不是 LALR

语法分析实验是 OUC 编译原理里卡住人最多的一关，因为它有两种典型路线：自顶向下的递归下降和自底向上的 LALR 分析表。学校实验室里要求手写代码的，绝大多数用递归下降，原因很实际：代码可读性强、报错位置准确、和后续语义动作能直接挂钩。

LALR 分析器生成工具（比如 yacc）虽然功能强大，但生成的表是个黑匣子，实验答辩时老师问“这个状态转移为什么是 3 个动作”，你很难答上来。更关键的是，LALR 的文法冲突报错极其抽象，对初学者极不友好。递归下降则是一手文法一手代码，每个非终结符对应一个方法，文法长什么样代码就是什么样。缺点是必须手动消除左递归，比如E -> E + T这种文法直接写会无限递归，常见做法是把左递归改成右递归，或者用循环代替递归。

我一般会建议把实验文法限制在 LL(1) 子集内。如果实验给的文法里有公共左因子，比如两个产生式都以同一个终结符开头，需要先提取公共左因子，不然递归下降里无法决定走哪个分支。这一步做好了，后面表达式、语句、作用域的代码都能按部就班地写下去。

3.2 表达式优先级：从文法消除二义性到代码实现

表达式是语法分析里最有代表性的部分，因为加减乘除和括号的优先级是人人都懂、但代码实现最容易乱的地方。文法上要先消除二义性，经典做法是把优先级分层：

expr -> term | expr + term | expr - term term -> factor | term * factor | term / factor factor -> NUMBER | IDENT | ( expr )

这个文法仍然有左递归，直接写成递归下降会死循环。常见做法是改成基于优先级爬升（Pratt Parsing）的循环实现，代码比纯递归下降更简洁。下面是一个最小实现，处理加减乘除和括号：

public class ExprParser { private final Lexer lexer; private Token cur; public ExprParser(Lexer lexer) throws LexException { this.lexer = lexer; this.cur = lexer.tokenize().get(0); } public ASTNode parseExpr() { return parseExprWithMinPrec(1); } private ASTNode parseExprWithMinPrec(int minPrec) { ASTNode left = parseFactor(); while (cur.type.equals("OP") && prec(cur.value) >= minPrec) { String op = cur.value; advance(); ASTNode right = parseExprWithMinPrec(prec(op) + 1); left = new BinaryOpNode(op, left, right); } return left; } private ASTNode parseFactor() { if (cur.type.equals("NUM") || cur.type.equals("IDENT")) { ASTNode node = new AtomNode(cur); advance(); return node; } if (cur.value.equals("(")) { advance(); ASTNode inner = parseExpr(); if (!cur.value.equals(")")) { throw new ParseException("缺少右括号", cur.line); } advance(); return inner; } throw new ParseException("无法识别的表达式起始符号 " + cur.value, cur.line); } private int prec(String op) { if (op.equals("+") || op.equals("-")) return 10; if (op.equals("*") || op.equals("/")) return 20; return 0; } private void advance() { List<Token> tokens = lexer.tokenize(); int nextIndex = tokenIndex + 1; // 实际工程里应通过索引游标取下一个 token，这里省略游标细节 cur = tokens.get(nextIndex); } }

逻辑说明：parseExprWithMinPrec(1)是最小优先级入口，minPrec参数决定当前层接受哪些运算符。parseFactor()只负责数字、标识符和括号，它永远是最底层的原子节点。循环内部读取运算符后，递归调用parseExprWithMinPrec(prec(op) + 1)，+1是关键，它保证左结合性：1 - 2 + 3会先算(1 - 2)再算+ 3，而不是把2 + 3先结合。

参数说明：prec(op)返回 10 和 20 两个等级，乘法优先级高于加法。如果实验文法里有取负号这种单目运算符，需要单独设一个更高的优先级并放到parseFactor的前缀分支里。代码里advance()简化了 token 游标的细节，实际实现时应该让词法分析器返回一个List<Token>，语法分析器内部维护一个index字段，每次调用advance()只做index++。

3.3 语句与作用域：从语法树到语义动作

表达式层做完后，语法分析实验的下一层是语句。常见装备是给文法加上赋值、if、while、return，树节点从表达式节点扩展成语句节点。这一层真正的难点不是识别语法，而是理解“语法分析不关心变量有没有声明过”。比如x = y + 1，递归下降只负责确认这是一个合法的赋值语句，至于x和y有没有定义、类型对不对，那是语义分析的活。

这里容易踩一个坑：在语法分析阶段就试图查符号表。比如写parseStatement()时遇到IDENT就去符号表里查一下，如果没找到就直接报错。这在简单实验里仿佛可行，但遇到“先使用后声明”的语言特性就翻车。正确做法是语法分析只建树或直接输出语法动作，符号表绑定放到专门的语义分析遍历。如果你的课程实验没有明确划分阶段，我建议至少保留一个“语法分析完后再遍历一次 AST 做检查”的步骤，这比边解析边查表要容易调试得多。

语句的递归下降实现核心是：每种语句对应一个方法，方法开头根据当前 token 决定走哪个分支。比如if开头就走parseIfStatement()，while开头走parseWhileStatement()，IDENT开头尝试读=，读到了就是赋值语句，读不到就回溯。回溯在递归下降里很费劲，因此文法设计时要避免歧义。

4. 符号表与语义分析实验：作用域、绑定与类型检查

4.1 符号表设计：栈式作用域还是哈希表

词法分析和语法分析做完，编译原理实验进入一个分水岭——符号表与语义分析。这也是热词里“编译原理符号表”对应的核心考点。符号表的第一问题不是用什么数据结构存，而是作用域怎么表达。最简单的是单张哈希表，适合没有块级作用域的实验语言；但大多数 OUC 实验要求支持函数作用域和块作用域，单张哈希表会在退出作用域时无法恢复上一层的同名变量。

常见做法是栈式作用域：每个作用域一张哈希表，作用域压栈进入，出栈销毁。查符号时从栈顶向下找，每个表查不到就查下一层。这种设计代码量小、语义直观，且对嵌套作用域天然支持。另一种做法是给每个符号一个 ID，哈希表里存(名字, 作用域ID, 类型)，副作用是查询时必须携带当前作用域 ID 做过滤，稍微复杂，但便于实现“同一作用域内不允许重复声明”的检查。

我一般会选择栈式作用域做课程实验，因为它和递归下降天然匹配：进一个{}块就pushScope()，出块就popScope()。而且后续实验做中间代码生成时，需要为每个变量生成偏移量，栈式结构方便在符号条目里保存偏移信息。

4.2 变量声明、引用与类型检查的最小实现

语义分析实验的常见要求是：变量使用前必须声明、类型必须匹配、函数调用参数个数和类型必须一致。下面是一个简化但结构完整的符号表实现，支持作用域嵌套和基本类型检查：

import java.util.*; public class SymbolTable { private final Deque<Map<String, Symbol>> scopes = new ArrayDeque<>(); public void pushScope() { scopes.push(new HashMap<>()); } public void popScope() { scopes.pop(); } public void declare(String name, String type, int line) { Map<String, Symbol> top = scopes.peek(); if (top.containsKey(name)) { throw new SemanticException("重复声明 " + name, line); } top.put(name, new Symbol(name, type, line)); } public Symbol lookup(String name, int line) { for (Map<String, Symbol> scope : scopes) { Symbol sym = scope.get(name); if (sym != null) return sym; } throw new SemanticException("未声明变量 " + name, line); } public String checkType(String name, int line) { Symbol sym = lookup(name, line); return sym.type; } static class Symbol { String name; String type; int definedLine; Symbol(String name, String type, int definedLine) { this.name = name; this.type = type; this.definedLine = definedLine; } } }

逻辑说明：pushScope和popScope维护当前作用域链，declare只往栈顶写，如果栈顶已经有同名符号就报重复声明错误。lookup从栈顶向下遍历，每一层查不到继续往下一层查，直到栈底。这样内层作用域可以遮蔽外层同名变量，退出内层后外层变量恢复可见。

参数说明：Symbol里的type字段按实验要求可以是int、float、bool或自定义类型。definedLine字段用于错误报告，语义分析报错时能定位声明位置，这在课程报告里是加分项。类型检查的实现通常是在遍历 AST 时，对每个表达式节点调用checkType，然后比较左右操作数的类型，遇到int + float是否允许取决于实验文法；如果不允许，就在这个位置报类型不匹配。

注意：函数声明需要单独处理参数列表和返回类型。常见做法是符号条目里增加List<Param>字段，函数调用时逐个比对数类型而不是直接比较一个整体类型字符串。

4.3 语义错误的处理策略：如何做到一次报告多个错误

语义分析实验的另一个大坑是错误恢复。常见的报错方式是throw new SemanticException，遇到第一个错误就终止。这在测试简单程序时没问题，但课程实验的测试用例往往故意包含多个错误，比如同时又重复声明和类型不匹配，你的编译器只报第一个错误，成绩单上就被扣分。

我建议增加一个errorCount和一个reportError方法，遇到错误先记录、不抛出、继续分析当前节点，只有错误数超过阈值时才强制终止。比如：

private int errorCount = 0; private void reportError(String msg, int line) { System.err.println("第 " + line + " 行: " + msg); errorCount++; if (errorCount >= 50) { throw new TooManyErrorsException("错误超过 50 个，终止编译"); } }

这个策略的思想是：单个错误往往不影响分析器继续向下走，比如int x = "abc";虽然类型不匹配，但赋值语句的 AST 结构是完整的，可以继续分析后续代码。只有错误导致 AST 结构无法构建时（比如缺少右括号），才必须立即终止。这也是真实编译器如 GCC 的做法：能恢复就恢复，不能恢复才放弃。

5. 实验避坑：编译原理实验的五个常见翻车点

5.1 翻车点一：一上来就想写一个完整的 C 语言编译器

现象：拿到实验说明书后，第一反应是参照 GCC 的功能清单，给自己的编译器加上数组、结构体、指针、函数重载，结果写了两个星期，连词法分析器都还在处理字符串转义。原因：实验的评分标准是按阶段划分的，词法分析实验只考 token 拆分，语法分析实验只考 AST 结构，过度设计反倒是给自己挖坑。解决：严格按实验公告的阶段目标控制范围，先把当前阶段跑通、提交、拿分，再回头扩展。扩展功能时先加测试用例，后加实现代码，不要凭感觉加特性。

5.2 翻车点二：报错信息定位不准，调试全靠 print

现象：程序输入一个错误表达式，报错只写“语法错误”，不写行号、不写当前 token，你对着自己的代码找半天也没找到是在哪个函数抛的异常。原因：我在 Java 课程设计里见过很多同学用System.out.println("error")代替真正的错误报告，这类调试输出到了提交阶段又删不干净，而且没有上下文信息。解决：从词法分析实验开始就统一错误信息格式，至少包含行号、期望值、实际值三个字段，比如第 3 行: 期望 ')'，实际 '}'。这样错误报告不是给人看的摆设，而是能直接指导调试的线索。

5.3 翻车点三：没有标准测试集，改一处挂一片

现象：词法分析跑通了int a = 3;，加到语法分析后改成支持数组下标，发现原来能通过的测试样例全挂了，还不知道什么时候改坏的。原因：没有回归测试，每次改代码只测刚加的功能，不跑历史样例。解决：花半天时间建一个testcases/目录，按实验阶段放 10 到 20 个输入文件，每个文件对应一个输出期望文件，再写一个简单的 Shell 脚本批量跑。做实验时每次改动代码后跑一遍全量测试，用时不到一分钟，能省下大量调试时间。这个习惯在实验结束写报告时也很有说服力，测试数据可以直接作为附件。

5.4 翻车点四：中间代码生成和符号表不同步

现象：语义分析阶段生成了符号表，到中间代码实验时又自己建了一套变量名和临时变量的表格，两边信息对不上，生成的三地址码里频繁出现未定义寄存器。原因：把符号表设计成了面向语义分析的结构，没有预留中间代码生成需要的字段。解决：在设计符号表条目时就把后续要用的字段都预留出来：变量名、类型、作用域深度、如果需要生成三地址码，再加一个临时位置或偏移量字段。即便当前实验用不到，也先在Symbol类里写着，避免之后重构。这个设计上的远视比其他补救措施都省时间。

5.5 翻车点五：不懂得利用已有工具链对拍

现象：自己的编译器输出结果不知道对不对，老师给的测试用例太少，心里没底。原因：没有使用成熟的参考实现来验证自己的输出。解决：用一个简单的 Python 脚本或javac来跑相同的源码，对比自己的编译器和参考实现的行为差异。注意，不能直接把参考实现当模板抄代码，而是用它来检查行为：比如自己把1 < 2的布尔值生成反了，跑一遍javac就知道正确输出是什么。这个对拍手段尤其适用于代码生成实验，能独立验证每个运算符的语义，而不是靠肉眼猜。

6. 把全部实验串成一条龙：最小编译管线的验证方法与边界

6.1 建立最小测试集：从一行程序到嵌套函数

所有实验都完成后，我建议搭建一条“源码文件 → 词法 token → 语法 AST → 符号表绑定 → 输出”的最小管线，用脚本一键跑完。测试集按难度递增分三档：第一档是只有一个表达式的最小程序，用于快速验证前端链路通不通；第二档加入变量声明、赋值和 if、while 语句，覆盖语法分析和符号表最常用的路径；第三档加入函数调用和嵌套作用域，专门验证符号表的生命周期和类型检查边界。

每档测试都要有一个对应的期望输出文件，格式可以是 token 序列、AST 缩进打印或中间代码文本。期望文件的生成办法是：先用参考编译器跑一遍人工确认正确的样例，把输出存下来，以后每次都和它做 diff。这个测试集就是你的“后悔药”，在后续做扩展实验时，能立刻发现哪个改动破坏了几百行之前的功能。

6.2 验证实验成果的实用技巧：一个 Shell 脚本加三个检查点

我习惯在每个实现阶段留一个检查脚本，核心只有三行命令：编译、运行、对比 diff。检查点按顺序来：第一，词法分析输出中所有 token 都带正确行号；第二，语法分析对错误输入能报出包含行号和预期的错误，而不是抛异常崩溃；第三，语义分析不能出现“查不到符号”的内部空指针，所有错误必须通过统一错误入口报告。

一个常被忽略的边界是 EOF 处理：源文件末尾没有换行时，词法分析器要能正常结束而不是越界。这看起来是小问题，但在测试脚本里用printf "int a=3;" | 你的编译器这种输入时就会暴露。另一个边界是空文件，很多实现遇到空文件时 token 列表是空的，语法分析入口若无判断会直接抛IndexOutOfBoundsException。

我对编译原理实验最大的教训是：不要迷信一次写对的谬误，再简单的实验也要留回归测试，再快的修复也要跑一遍全量用例。课程实验的评分不是看你写了多少行代码，而是看你处理了多少边界、报错是否友好、结构是否清晰。照这个流程走下来，你会发现编译原理实验的每一阶段都在给下一个阶段铺路，而不是交完作业就断掉。

希望这份从词法到语义分析的拆解，能帮你少走几段弯路，把 OUC 编译原理全部实验做成一份自己讲得清楚、老师挑不出毛病的工程实践。

本文还有配套的精品资源，点击获取