简介本资源是编译原理课程实验的完整配套资料面向计算机专业学生及需要动手实现编译前端的学习者围绕词法分析器设计、LL(1)分析法、逆波兰式生成与计算、LR(1)分析法四个核心实验展开帮助读者把课堂理论落到可运行的代码上。压缩包共35个文件约789KB以cpp源码、docx实验报告、txt与md说明文档为主另含xls数据表、png截图及工程配置按实验模块分目录组织便于逐项对照学习。目前已有150人学习下载。读者可获取四类分析器的C实现、配套实验报告与使用说明理解FIRST/FOLLOW集构造、预测分析表、后缀表达式栈式计算及LR(1)状态栈规约等关键过程并借助文档完成编译、调试与代码修改适合作为课程实验参考与期末复习材料。1. 编译原理实验四件套从词法分析到 LR(1)一套代码怎么串起来很多人学编译原理课本翻到第三章就卡住了什么 FIRST 集、FOLLOW 集、项目集闭包概念全认识合上书一个字写不出来。这门课真正的分水岭不在期末考试而在你第一次动手写词法分析器的时候——正则表达式怎么变成代码、Token 流怎么喂给语法分析器、逆波兰式到底在哪个环节生成这些问题不亲手跑一遍永远停留在“好像懂了”的状态。这篇文章围绕一套编译原理实验代码展开覆盖四个核心模块词法分析器、LL(1) 分析法、逆波兰式的生成及计算、LR(1) 分析法。适合正在做编译原理实验的本科生也适合想用 Java 或 Python 把编译前端流程串一遍的开发者。我不会只讲理论每个模块都会落到可运行的代码结构、关键参数和调试方法上。读完你至少能做到拿到一套源码知道从哪个文件开始看自己写的时候知道哪里容易翻车以及四个模块之间怎么衔接成一条完整的编译流水线。2. 词法分析器正则到 Token 流的最小实现路径2.1 为什么先写词法分析器而不是直接上语法分析编译前端的第一道工序永远是词法分析。原因很直接语法分析器不管 LL(1) 还是 LR(1)的输入必须是结构化的 Token 序列而不是原始字符流。如果你跳过词法分析直接让语法分析器去读字符代码会变得极其臃肿每一条产生式里都要处理空格、换行、注释维护成本直接爆炸。词法分析器的本质是一个有限状态自动机DFA。你写的正则表达式比如标识符[a-zA-Z_][a-zA-Z0-9_]*、整数[0-9]、运算符|-|*|/最终都会被转换成状态转移表。手工写代码的时候常见做法是用一个while循环逐字符扫描根据当前字符类别切换状态遇到终止状态就吐出一个 Token。Token 的数据结构一般包含三个字段类型type、值value、行号line。行号这个字段新手经常忽略但后面做错误报告的时候没有它你会非常痛苦。我一般会定义一个TokenType枚举把关键字、标识符、常量、运算符、界符全列进去这样语法分析器拿到 Token 之后直接做switch判断就行。2.2 用 Java 实现词法分析器的核心代码结构下面是一个简化但可运行的词法分析器骨架用 Java 写的Python 版本逻辑一样只是语法不同。public class Lexer { private String input; // 待分析的源代码字符串 private int pos; // 当前扫描位置 private int line; // 当前行号 private ListToken tokens;// 输出的 Token 列表 public Lexer(String input) { this.input input; this.pos 0; this.line 1; this.tokens new ArrayList(); } public ListToken tokenize() { while (pos input.length()) { char ch input.charAt(pos); if (ch \n) { line; pos; } else if (Character.isWhitespace(ch)) { pos; // 跳过空白字符 } else if (Character.isLetter(ch) || ch _) { readIdentifierOrKeyword(); } else if (Character.isDigit(ch)) { readNumber(); } else { readOperatorOrDelimiter(); } } tokens.add(new Token(TokenType.EOF, EOF, line)); return tokens; } private void readIdentifierOrKeyword() { int start pos; while (pos input.length() (Character.isLetterOrDigit(input.charAt(pos)) || input.charAt(pos) _)) { pos; } String word input.substring(start, pos); // 关键字表用 HashSet 存O(1) 判断 TokenType type Keywords.isKeyword(word) ? TokenType.KEYWORD : TokenType.IDENTIFIER; tokens.add(new Token(type, word, line)); } private void readNumber() { int start pos; while (pos input.length() Character.isDigit(input.charAt(pos))) { pos; } tokens.add(new Token(TokenType.NUMBER, input.substring(start, pos), line)); } private void readOperatorOrDelimiter() { char ch input.charAt(pos); // 处理双字符运算符如 、、 if (pos 1 input.length()) { String two input.substring(pos, pos 2); if (Operators.isDoubleOperator(two)) { tokens.add(new Token(TokenType.OPERATOR, two, line)); pos 2; return; } } tokens.add(new Token(TokenType.OPERATOR, String.valueOf(ch), line)); pos; } }这段代码的逻辑很直白主循环根据当前字符决定进入哪个读取分支每个分支负责消费一类 Token 并推进pos。readIdentifierOrKeyword里用了一个关键字表来判断是标识符还是关键字这个表通常用HashSetString存查找效率是 O(1)。readOperatorOrDelimiter里先尝试匹配双字符运算符匹配失败再按单字符处理这是处理和这类歧义的标准做法。参数方面input是完整的源代码字符串pos是全局扫描指针line用于记录行号。如果你要做更复杂的词法分析比如支持浮点数、字符串字面量、注释只需要在tokenize的主循环里加分支就行。浮点数在readNumber里多判断一个小数点字符串字面量遇到就进入专门的读取循环直到遇到闭合引号。注意行号更新一定要放在跳过换行符的分支里不要在每个读取函数里各自维护否则行号会错乱。2.3 词法分析器的测试与验证方法写完词法分析器之后不要急着接语法分析器先单独测。测试用例至少覆盖以下几类第一类正常输入。比如int a 10 20;期望输出是KEYWORD(int) IDENTIFIER(a) OPERATOR() NUMBER(10) OPERATOR() NUMBER(20) DELIMITER(;)。第二类边界输入。比如空字符串、只有空白字符、只有注释。第三类异常输入。比如#$这种非法字符你的词法分析器应该能报错并指出行号而不是直接崩溃或者死循环。我一般会写一个简单的测试主函数把 Token 列表打印出来逐个人工核对。如果 Token 数量对不上大概率是某个分支没有正确推进pos导致死循环或者跳字符。死循环是词法分析器最常见的 bug排查方法是在主循环里加一个pos变化检测如果一轮循环下来pos没变直接抛异常。3. LL(1) 分析法FIRST 集、FOLLOW 集与预测分析表3.1 LL(1) 的适用边界与选型理由LL(1) 是自顶向下语法分析里最经典的方法核心思想是从左到右扫描输入每次只看一个 Token 就能决定用哪条产生式展开。它的优点是实现简单、易于手工构造缺点是能处理的文法有限——左递归文法必须先消除左递归提取左公因子否则预测分析表里会出现多重入口。很多学校的编译原理实验要求同时实现 LL(1) 和 LR(1)目的就是让你对比两种方法的差异。LL(1) 适合文法结构清晰、层次分明的语言子集比如表达式文法、简单的语句文法。如果你要处理更复杂的语法比如带有优先级和结合性的完整表达式LR(1) 会更合适。选 LL(1) 做实验的好处是整个流程非常透明从文法到 FIRST 集、FOLLOW 集、预测分析表每一步都可以手工验证。你写完之后能清楚地看到每个 Token 是怎么被“预测”着匹配掉的。3.2 从文法到预测分析表的完整计算流程假设你有这样一组文法产生式已消除左递归E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id第一步计算 FIRST 集。规则是对于产生式A - α如果 α 的第一个符号是终结符直接加入 FIRST(A)如果是非终结符把 FIRST(那个非终结符) 加进来如果 α 能推导出 εε 也加入 FIRST(A)。第二步计算 FOLLOW 集。规则是起始符号的 FOLLOW 集包含$对于产生式A - αBβ把 FIRST(β) 中除 ε 外的符号加入 FOLLOW(B)如果 β 能推导出 ε把 FOLLOW(A) 加入 FOLLOW(B)。第三步构造预测分析表。对于每条产生式A - α对 FIRST(α) 中的每个终结符 a把A - α填入M[A, a]如果 α 能推导出 ε对 FOLLOW(A) 中的每个符号 b把A - ε填入M[A, b]。下面是用 Python 计算 FIRST 集的核心代码def compute_first(grammar, non_terminals, terminals): first {nt: set() for nt in non_terminals} changed True while changed: changed False for head, productions in grammar.items(): for prod in productions: if prod [ε]: if ε not in first[head]: first[head].add(ε) changed True continue for symbol in prod: if symbol in terminals: if symbol not in first[head]: first[head].add(symbol) changed True break else: before_len len(first[head]) first[head] | (first[symbol] - {ε}) if len(first[head]) ! before_len: changed True if ε not in first[symbol]: break else: if ε not in first[head]: first[head].add(ε) changed True return first这段代码用了一个while changed循环反复迭代直到所有 FIRST 集不再变化。这是处理递归文法的标准做法因为一个非终结符的 FIRST 集可能依赖另一个非终结符而后者又反过来依赖前者。grammar是一个字典键是非终结符值是产生式列表每个产生式用符号列表表示。terminals是终结符集合。FOLLOW 集的计算逻辑类似也是迭代到不动点。预测分析表的构造就是把 FIRST 和 FOLLOW 的结果填进一个二维表。3.3 预测分析表的驱动代码与调试技巧有了预测分析表之后驱动代码就是一个栈加一个输入指针def ll1_parse(tokens, parse_table, start_symbol): stack [$, start_symbol] index 0 while stack: top stack.pop() current tokens[index] if top $ and current $: return True # 分析成功 if top current: index 1 # 匹配终结符消费输入 elif top in parse_table and current in parse_table[top]: production parse_table[top][current] if production ! [ε]: # 逆序压栈保证最左符号在栈顶 for symbol in reversed(production): stack.append(symbol) else: print(f语法错误行 {index}意外符号 {current}) return False return False调试 LL(1) 分析器的时候最常见的翻车点是预测分析表里有冲突——同一个格子填了两条产生式。这说明你的文法不是 LL(1) 文法需要回头做左递归消除或左公因子提取。另一个常见问题是栈的压入顺序搞反了导致匹配顺序错乱。记住产生式右部要逆序压栈这样最左边的符号才会在栈顶。4. 逆波兰式的生成及计算从表达式树到后缀序列4.1 逆波兰式在编译流程中的位置逆波兰式后缀表达式是表达式求值的经典中间表示。在编译原理实验里它通常出现在语法分析之后、代码生成之前。你可以在语法分析的过程中顺便生成逆波兰式也可以先建表达式树再后序遍历得到。为什么用逆波兰式而不是直接建树因为逆波兰式可以用一个栈在 O(n) 时间内完成求值不需要递归也不需要存储树结构。对于简单的表达式计算器来说这是最轻量的方案。生成逆波兰式的经典算法是调度场算法Shunting Yard由 Dijkstra 提出。核心逻辑是遇到操作数直接输出遇到运算符则与栈顶运算符比较优先级如果栈顶优先级不低于当前运算符就弹出栈顶输出直到条件不满足再把当前运算符压栈。遇到左括号直接压栈遇到右括号则弹出栈顶直到遇到左括号。4.2 调度场算法的代码实现与优先级表def infix_to_rpn(expression): precedence {: 1, -: 1, *: 2, /: 2} output [] operator_stack [] i 0 while i len(expression): ch expression[i] if ch.isdigit(): # 读取完整数字支持多位数 num while i len(expression) and expression[i].isdigit(): num expression[i] i 1 output.append(num) continue elif ch (: operator_stack.append(ch) elif ch ): while operator_stack and operator_stack[-1] ! (: output.append(operator_stack.pop()) operator_stack.pop() # 弹出左括号 elif ch in precedence: while (operator_stack and operator_stack[-1] ! ( and precedence.get(operator_stack[-1], 0) precedence[ch]): output.append(operator_stack.pop()) operator_stack.append(ch) i 1 while operator_stack: output.append(operator_stack.pop()) return outputprecedence字典定义了运算符优先级乘除高于加减。operator_stack是运算符栈output是输出的逆波兰式列表。注意数字读取部分用了内层while循环来处理多位数如果只读单个字符10 20会被拆成1 0 2 0结果完全错误。计算逆波兰式就更简单了def evaluate_rpn(rpn): stack [] for token in rpn: if token.isdigit(): stack.append(int(token)) else: b stack.pop() a stack.pop() if token : stack.append(a b) elif token -: stack.append(a - b) elif token *: stack.append(a * b) elif token /: stack.append(a // b) return stack[0]注意减法、除法不满足交换律弹出栈顶的两个操作数时先弹出的是右操作数后弹出的是左操作数顺序不能反。4.3 逆波兰式与语法分析的衔接方式在实际的编译原理实验代码里逆波兰式的生成通常不是独立模块而是嵌入在语法分析过程中。比如你在做 LR(1) 分析的时候每次归约一个产生式就可以顺便输出对应的逆波兰式片段。这样一遍扫描下来语法分析完成的同时逆波兰式也生成好了。如果你先建了语法树那就对语法树做后序遍历左子树、右子树、根节点。后序遍历的输出顺序天然就是逆波兰式。这种方法更直观但需要额外的树结构存储开销。两种方式各有适用场景。表达式简单、追求效率就用调度场算法语法结构复杂、需要多次遍历就用语法树后序遍历。我一般做实验的时候先用调度场算法快速验证表达式求值逻辑再在 LR(1) 分析器里嵌入逆波兰式生成这样两个模块可以独立调试。5. LR(1) 分析法项目集闭包、分析表与冲突排查5.1 LR(1) 比 LL(1) 强在哪里LR(1) 是自底向上语法分析里能力最强的实用方法之一。它从左到右扫描输入构造最右推导的逆过程。相比 LL(1)LR(1) 能处理的文法范围大得多左递归文法不需要消除表达式的优先级和结合性也能自然处理。LR(1) 的核心概念是项目Item形如A - α·β, a其中a是向前看符号。项目集闭包Closure和状态转移GOTO是构造分析表的两个基本操作。相比 SLR(1) 和 LALR(1)LR(1) 的向前看符号更精确冲突更少代价是状态数更多。做编译原理实验的时候LR(1) 通常是难度最高的一个模块。状态机手工构造几乎不可能必须写代码自动生成。但一旦跑通你会对自底向上分析有完全不同的理解。5.2 项目集闭包与 GOTO 函数的代码实现def closure(items, grammar, first_sets): result set(items) changed True while changed: changed False for item in list(result): head, body, dot, lookahead item if dot len(body) and body[dot] in grammar: B body[dot] beta body[dot1:] # 计算 FIRST(beta lookahead) first_beta compute_first_of_sequence(beta [lookahead], first_sets) for prod in grammar[B]: for a in first_beta: new_item (B, tuple(prod), 0, a) if new_item not in result: result.add(new_item) changed True return frozenset(result)items是初始项目集每个项目用四元组表示产生式头部、产生式体、点的位置、向前看符号。closure函数反复扫描项目集如果点后面是非终结符就把该非终结符的所有产生式加进来向前看符号用 FIRST(beta lookahead) 计算。changed标志控制迭代直到不动点。GOTO 函数更简单对项目集中的每个项目如果点后面是符号 X就把点右移一位然后对新项目集求闭包。def goto(items, symbol, grammar, first_sets): moved set() for head, body, dot, lookahead in items: if dot len(body) and body[dot] symbol: moved.add((head, body, dot 1, lookahead)) if not moved: return frozenset() return closure(moved, grammar, first_sets)5.3 LR(1) 分析表的构造与冲突处理构造出所有项目集之后给每个项目集编号然后填 ACTION 表和 GOTO 表。ACTION 表的规则是如果项目形如A - α·aβ, b且 a 是终结符则ACTION[state, a] shift next_state如果项目形如A - α·, a则ACTION[state, a] reduce A - α如果项目是S - S·, $则ACTION[state, $] accept。冲突主要有两种移进-归约冲突和归约-归约冲突。移进-归约冲突通常是因为优先级没处理好归约-归约冲突说明文法有歧义。LR(1) 的向前看符号能消除大部分冲突但如果你用的是 SLR(1) 或 LALR(1)冲突会更多。排查冲突的时候先把冲突的状态号和涉及的项打印出来看看是哪个向前看符号导致了多重入口。如果是移进-归约冲突检查运算符优先级表是否正确如果是归约-归约冲突检查文法是否有二义性。6. 避坑与排查四个模块联调时最容易翻车的地方6.1 Token 类型不匹配导致语法分析器静默失败现象词法分析器输出的 Token 流看起来没问题但语法分析器一直报错或者直接返回失败没有任何有用信息。原因词法分析器的 TokenType 枚举和语法分析器期望的类型不一致。比如词法分析器把int标记为KEYWORD但语法分析器的预测分析表里用的是INT两边对不上分析器找不到匹配的产生式。解决在项目里定义一个共享的 TokenType 枚举词法分析器和语法分析器都引用同一个文件。如果语言不同比如词法用 Java、语法用 Python至少保证字符串表示一致并且在联调前先打印 Token 流人工核对一遍。6.2 逆波兰式计算时操作数顺序颠倒现象10 - 3算出来是-7而不是720 / 4算出来是0.2而不是5。原因逆波兰式求值时遇到运算符弹出两个操作数先弹出的是右操作数后弹出的是左操作数。如果代码里直接用a - b而a是先弹出的那个结果就反了。解决严格按b stack.pop(); a stack.pop();的顺序取值然后执行a op b。这个坑几乎每个人都会踩一次建议在代码里加注释标明。6.3 LL(1) 预测分析表出现多重入口现象构造预测分析表的时候同一个格子被填入了两条不同的产生式程序报冲突或者随机选一条导致分析结果不稳定。原因文法不是 LL(1) 文法。常见情况是存在左递归没有完全消除或者两个产生式的 FIRST 集有交集且没有提取左公因子。解决回头检查文法用标准算法消除左递归、提取左公因子。如果消除之后仍然有冲突说明该文法本身就不是 LL(1) 的需要换用 LR(1) 方法。不要试图在代码层面“绕过”冲突那只会把问题推迟到运行时。6.4 LR(1) 项目集数量爆炸导致内存不足现象构造 LR(1) 项目集的时候状态数急剧增长程序跑了几分钟还没结束或者直接内存溢出。原因LR(1) 的状态数本来就比 LALR(1) 多很多如果文法产生式多、向前看符号组合多状态数可能达到几千甚至上万。代码里如果用了低效的数据结构比如用列表做成员检查性能会进一步恶化。解决用frozenset存储项目集用字典做状态编号映射成员检查用哈希而不是线性扫描。如果状态数仍然太大考虑合并同心项目集退化成 LALR(1)。实验环境下一般文法规模不会太大优化数据结构就够了。6.5 四个模块的输入输出格式不统一现象单独测每个模块都能跑串起来就报错。词法分析器输出的是 Java 对象列表语法分析器期望的是字符串列表逆波兰式模块又期望另一种格式。原因模块之间没有约定统一的数据交换格式。每个人写自己的模块时用了自己顺手的数据结构联调的时候就对不上。解决在项目开始之前先定义好接口。Token 用统一的类或字典表示至少包含 type 和 value 两个字段。语法分析器的输出产生式序列或语法树也用统一格式。逆波兰式就是一个字符串列表。接口定好了每个模块可以独立开发和测试最后拼装的时候只需要做格式转换。7. 把四个模块串成一条流水线我的调试习惯与进阶建议四个模块单独跑通只是第一步真正的挑战在于把它们串成一条完整的编译流水线。我自己的习惯是先写一个Main类或者main函数把输入源代码字符串依次传给词法分析器、语法分析器、逆波兰式生成器和计算器每一步的输出都打印出来。这样任何一步出问题我都能立刻定位到是哪个模块的锅。具体来说我会在流水线的每个阶段加一个“检查点”。词法分析之后打印 Token 列表语法分析之后打印归约序列或语法树逆波兰式生成之后打印后缀表达式计算之后打印最终结果。这四个检查点的输出格式固定下来以后换测试用例只需要看输出对不对不需要改代码。进阶用法方面如果你已经跑通了基本流程可以尝试以下几个方向。第一把词法分析器的正则表达式改成从配置文件读取这样不用改代码就能支持新的 Token 类型。第二在 LL(1) 和 LR(1) 之间加一个自动切换逻辑先尝试 LL(1)如果预测分析表有冲突就自动切换到 LR(1)。第三给逆波兰式计算器加上变量支持用一个符号表存储变量值这样就能处理带变量的表达式。验证方法上我一般会准备三组测试用例。第一组是教科书上的经典例子比如id id * id用来验证基本逻辑。第二组是边界用例比如空输入、只有括号、嵌套括号用来验证异常处理。第三组是综合用例比如一个完整的if-else语句块用来验证模块之间的衔接。三组都过了这套代码才算真正可用。最后说一个我踩过的坑不要等到四个模块全写完才联调。每写完一个模块就立刻和上一个模块对接哪怕上一个模块还是个简化版。这样问题暴露得早修起来也快。等到四个模块都写完再联调你会发现错误信息互相纠缠根本分不清是谁的问题。希望帮到你。本文还有配套的精品资源点击获取