编译原理实验全链路解析：从词法分析到代码生成的完整指南

简介：这份资源是中国海洋大学2020年春季学期编译原理课程的完整实验代码合集，面向计算机专业学生及希望动手理解编译器构造的自学者，可解决从词法分析到目标代码生成各阶段缺乏可运行参考实现的问题。压缩包共74个文件、约774KB，以C源文件、Flex词法规则（.l）、Bison语法规则（.y）、头文件、Makefile及可执行程序为主，另含实验要求文档与测试用例，覆盖词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、错误处理与编译器集成八个实验，并附无二义文法与有二义文法对比等素材。已有4418人学习下载，读者可据此对照实验要求复现各阶段流程，理解符号表构建、三地址码生成、优化策略与错误诊断的实现思路，并借助Makefile与测试输入快速验证自己的编译器组件。

1. 编译原理实验全景：从词法到代码生成的一张地图

编译原理这门课，很多人学完一学期，脑子里只剩下一堆零散的名词：正则表达式、NFA、DFA、LL(1)、LR(1)、四元式、活跃变量。单独拎出来都认识，串起来就断片。真正把这条链路打通的方式，不是再刷一遍课件，而是把实验从头到尾走一遍——因为编译器是少数「每一层都能被完整实现」的系统，词法分析器的输出就是语法分析器的输入，语义分析的产物直接喂给代码生成，任何一环偷懒，后面必然翻车。

这份 OUC 编译原理全部实验源码，覆盖的正是这条完整链路：词法分析、语法分析、语义分析与中间代码、代码优化与目标代码生成。它适合两类人：一类是正在跟着课程做实验、卡在某个阶段想对照参考的；另一类是期末复习，想把「理论课上讲的算法」和「实际能跑的程序」对上号的。下面按模块把这张地图拆开，重点标出每一层的关键算法、实现取舍和最容易踩的坑。

2. 词法分析：正则、NFA 到 DFA 的三级跳

词法分析是整个编译器的入口，任务很单纯：把字符流切成 token 流，同时过滤空白和注释、记录行号。但它的理论骨架不简单——正则表达式 → NFA → DFA → 最小化 DFA，这条转换链是编译原理第一个真正的「算法密集区」，也是实验里第一个容易让人卡住的地方。

2.1 三种实现路线的取舍

做词法分析实验，通常有三条路可选，选哪条直接决定了工作量和健壮性：

课程实验一般要求走第二条，因为子集构造法和 DFA 最小化本身就是考点。但实际写的时候，很多同学会退化成「手写扫描器 + 事后补一个自动机演示」，结果两边都不彻底。比较稳的做法是：用规则表描述 token（正则形式），程序里真正跑的是构造出来的 DFA 状态转移表，手写部分只负责驱动这张表。

2.2 子集构造与最小化的关键细节

子集构造法的核心是 ε-闭包和 move 操作，伪代码逻辑不复杂，但实现时有几个点必须盯住：

# 子集构造：从 NFA 状态集合出发，构造 DFA 状态 def subset_construction(nfa_start, nfa_states, alphabet): start = epsilon_closure({nfa_start}) # 初始状态的 ε-闭包 dfa_states = [start] worklist = [start] transitions = {} while worklist: current = worklist.pop() for ch in alphabet: moved = move(current, ch) # 沿 ch 能到达的 NFA 状态 if not moved: continue closure = epsilon_closure(moved) # 再做一次 ε-闭包 if closure not in dfa_states: dfa_states.append(closure) worklist.append(closure) transitions[(tuple(sorted(current)), ch)] = closure return dfa_states, transitions

这段代码里，epsilon_closure必须用栈或队列做传递闭包，不能只展开一层，否则带*和?的正则会漏状态；move只处理单字符，不要顺手把 ε 边也算进去。另一个高频错误是状态用set存却在字典里当 key——set不可哈希，必须先frozenset或排序转元组，这是很多人第一次跑就报错的地方。

DFA 最小化用 Hopcroft 划分法，初始把状态分成「终态」和「非终态」两组，然后按每个输入字符的转移目标所在组不断细分，直到划分稳定。这里最容易忽略的是死状态和不可达状态：不可达状态要在最小化前先删掉，否则划分结果里会多出永远进不去的组，看起来没错，实际状态数对不上。

2.3 最长匹配与回退

真正的词法分析器不是「匹配到就返回」，而是「匹配到最长的那个」。比如>=和>，读入>后不能立刻返回，得再看一个字符，是=就吞掉返回 GE，不是就回退一格返回 GT。这个回退机制在文件流上实现时，要么用缓冲区加指针回退，要么用ungetc之类的接口。血泪经验是：回退只回退一个字符，但如果你在匹配标识符时用了贪婪读入，回退点要记清楚，否则行号会算错，报错位置全偏。

提示：行号统计放在「吞掉换行符」的那一步，而不是放在 token 返回时，否则注释里的换行会被漏计。

3. 语法分析：LL(1) 与 LR 的两套世界观

语法分析是实验里分量最重的一块，也是考试最容易出大题的地方。核心矛盾只有一个：怎么在只看有限前瞻符号的情况下，决定用哪条产生式。LL(1) 和 LR 系列是两种完全不同的回答方式，前者自顶向下预测，后者自底向上归约，实验里通常要求至少实现一种，很多课程会要求两种都做以便对比。

3.1 FIRST/FOLLOW 集与预测分析表

LL(1) 的整套流程是：消除左递归 → 提取左公因子 → 求 FIRST 和 FOLLOW → 填预测分析表 → 用栈驱动分析。前两步是「让文法变得可 LL(1)」，后三步才是分析本身。很多实验报告栽在第一步：左递归没消干净，或者消除后引入了新的公共前缀却没提取，导致预测表里同一个格子出现两条产生式，直接冲突。

FIRST 集的求法要处理「能推出 ε」的符号串，规则是：对产生式右部X1 X2 ... Xn，先把FIRST(X1)里除 ε 外的元素加进去，如果X1能推 ε，再加FIRST(X2)，依次往后；如果全都能推 ε，才把 ε 加进FIRST(左部)。FOLLOW 集则要看「某非终结符后面跟什么」，产生式右部里A → αBβ，FIRST(β)\{ε}进FOLLOW(B)；若β能推 ε，FOLLOW(A)也进FOLLOW(B)。这两条规则写反、漏掉「β 推 ε」的传递，是最常见的错误。

# 预测分析表填充的核心判断 for production in grammar: # A -> X1 X2 ... Xn lhs, rhs = production first_rhs = first_of_sequence(rhs) for terminal in first_rhs - {'ε'}: table[(lhs, terminal)] = production if 'ε' in first_rhs: # 右部可空，用 FOLLOW 填 for terminal in follow[lhs]: table[(lhs, terminal)] = production

first_of_sequence要按上面说的「逐个往后看、遇 ε 继续」的逻辑写，不能简单地对每个符号求 FIRST 再并起来。填表时如果table里已有值还要再写，说明文法不是 LL(1)，这时候要么改文法，要么在报告里明确说明冲突位置——后者往往比硬凑更能拿分。

3.2 LR 分析表的构造与冲突处理

LR 系列从 LR(0) 到 SLR(1) 到 LR(1) 再到 LALR(1)，是一条「项目集越精细、冲突越少、表越大」的演进线。实验里最常实现的是 SLR(1)，因为它用 FOLLOW 集解决归约冲突，工作量适中。构造流程是：增广文法 → 求项目集规范族（CLOSURE 和 GOTO）→ 填 ACTION 和 GOTO 表。

CLOSURE 的关键是：项目A → α·Bβ中圆点后是非终结符 B 时，把 B 的所有产生式B → ·γ加进来，递归直到不动。GOTO 则是「圆点右移一位后求闭包」。SLR(1) 填表时，归约项目A → α·对FOLLOW(A)里的每个终结符填r动作，移进项目对圆点后的终结符填s动作。冲突主要出现在「移进-归约」上，SLR 用 FOLLOW 集判断，但 FOLLOW 集是全局的，精度不够，这就是为什么会有 LR(1)——它给每个项目带上展望符，把归约条件收紧到「该项目自己的展望符」。

最容易忽略的是增广文法这一步：不把S' → S加进去，接受项目就没法定义，分析表里永远缺一个 acc 动作。另外 LR(1) 的项目集数量可能爆炸，实验里如果文法稍大，打印项目集时一定要做去重和编号，否则调试时根本对不上号。

3.3 用栈驱动分析的统一框架

不管 LL 还是 LR，运行时都是「栈 + 输入指针 + 分析表」三件套。LL 的栈里放的是「期望看到的符号」，LR 的栈里放的是「已识别的状态」。写驱动循环时，LL 遇到栈顶是非终结符就查表压产生式右部（逆序压），遇到终结符就匹配输入；LR 则查 ACTION 表，s就压状态，r就按产生式弹栈再查 GOTO。两者的错误处理都靠「表里查不到」触发，但 LR 的错误定位通常更准，因为它保留了更多已归约信息。

注意：LL 压栈时产生式右部要逆序入栈，这样栈顶才是第一个该匹配的符号；顺序压反了程序能跑但结果全错，是新手最典型的翻车点。

4. 语义分析与中间代码：属性文法落地成四元式

语法分析只保证「结构对」，语义分析才回答「意思对不对」。这一层的实验通常包括：符号表管理、类型检查、以及把语法树翻译成中间代码。中间代码选四元式最普遍，因为结构规整、便于后续优化。

4.1 符号表的设计取舍

符号表是语义分析的「黑匣子」，所有名字、类型、作用域信息都往里塞。实验规模下，常见做法是哈希表 + 作用域栈：进入一个块就压一层，离开就弹一层，查找时从栈顶往下找，天然实现「内层遮蔽外层」。

最容易漏的是同名不同作用域的处理：很多实现直接用name当哈希 key，结果内层变量一声明就把外层覆盖了，退出作用域后外层也找不回来。正确做法是 key 用(name, scope_level)，或者每层作用域独立一张表、查找时逐层回溯。

4.2 语法制导翻译与四元式生成

把属性文法落到代码上，核心是给每个产生式配一段语义动作。以赋值语句id = E为例，表达式E翻译完会返回一个「存放结果的临时变量名」，赋值动作就是生成一条(=, E.place, _, id.place)的四元式。算术表达式则按运算符生成(+, a, b, t1)这样的三元运算四元式。

# 表达式 E -> E1 + T 的语义动作示意 def reduce_add(e1_place, t_place): temp = new_temp() # 申请新临时变量 emit('+', e1_place, t_place, temp) # 生成四元式 return temp # 把结果位置往上传递

new_temp要保证全局唯一，通常用计数器；emit把四元式追加到一张线性表里，后续优化和代码生成都读这张表。这里的关键是属性传递方向：综合属性自下而上传（比如表达式的 place），继承属性自上而下传（比如变量声明时的类型环境）。搞混方向，生成的代码顺序就会乱。

控制流的翻译是这一层的难点。if和while需要回填：生成跳转指令时目标地址还不知道，先留空，等语句翻译完再把标号填回去。回填链表（truelist、falselist、nextlist）是标准做法，漏掉回填或者回填顺序错，生成的跳转全指向错误位置，程序一跑就死循环。

4.3 类型检查的边界

实验里的类型检查一般做到「运算双方类型兼容」「赋值左右类型匹配」「函数调用实参个数与形参一致」这三条就够。但要注意隐式转换：整型转浮点通常允许，反过来要报错或显式截断。很多实现图省事一律放行，结果后面代码生成时寄存器宽度对不上，问题被推迟到更难调的地方。

提示：类型错误尽量在语义分析阶段报出并带上行号，别留到运行期，否则调试成本翻倍。

5. 易错点清单：那些让实验反复重做的坑

这一章单独拎出来，是因为下面这几条几乎每个做编译实验的人都至少踩过一次，而且踩了之后往往要回头改前面好几个模块。

易漏点一：ε 产生式在 FIRST/FOLLOW 里的传递。为什么漏：直觉上「空串不产生任何字符」，很容易在求 FIRST 时直接跳过。怎么补：凡是右部能推出 ε 的产生式，都要把 ε 显式加入 FIRST，并在 FOLLOW 计算里触发「β 可空则 FOLLOW 左部下传」的分支，写完用一个小文法手工验算一遍。

易漏点二：词法回退与行号统计脱节。为什么漏：回退逻辑和行号更新写在两个地方，改了一个忘了另一个。怎么补：把「读字符」封装成唯一入口，行号更新只在这个入口里做，回退时同步回退行号状态，或者干脆记录每个 token 的起始行号而非实时行号。

易漏点三：LR 项目集去重不彻底。为什么漏：项目用字符串或列表表示，内容相同但顺序不同就被当成两个。怎么补：项目集统一用frozenset或排序后的元组做规范表示，CLOSURE 和 GOTO 的返回值都先规范化再比较。

易漏点四：符号表作用域弹出误删外层。为什么漏：用单一哈希表且 key 只有名字。怎么补：改成作用域栈结构，或 key 带层级，弹出时只删当前层登记的条目。

易漏点五：回填链表没合并就填。为什么漏：if-else的 truelist 和 nextlist 混在一起填，跳转目标错位。怎么补：严格区分「真出口」「假出口」「语句结束后的下一条」，用merge函数显式合并链表再统一回填，填完打印跳转表核对。

6. 复习落地：一张自检表把整条链路串起来

复习到这个阶段，最有效的动作不是再读一遍教材，而是拿一张自检表，从词法到代码生成逐项问自己「这一步的输入是什么、输出是什么、关键算法叫什么、失败时看哪里」。下面这张表可以直接抄下来当复习清单用：

配合这张表，再做一个「最小可运行验证」：自己造一个包含赋值、算术、if、while、函数调用的十几行小程序，从词法一路跑到代码生成，每一步打印中间结果。哪一步的输出和预期对不上，问题就锁定在那一步，不用全盘重来。这个习惯比反复读理论有用得多——理论告诉你「应该怎样」，只有跑通一遍才知道「实际哪里不对」。

我自己的教训是：早期做实验总想一口气写完再调，结果词法的小错被语法层放大，语法层的表冲突又被误判成语义问题，最后花的时间是分段验证的好几倍。从那以后我每次动语法分析之前，都强制先把词法输出打出来逐 token 核对一遍，确认入口干净再往下走。这份 OUC 编译原理全部实验源码的价值也在这里——它给了一条已经跑通的参照链路，你可以拿自己的中间结果和它逐段比对，把「哪一层出的问题」快速定位出来，而不是对着报错猜。希望这份梳理帮到你，复习时少走几段弯路。

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