简介面向编译原理课程中 NFA 转 DFA 并最小化实验的代码与报告资源由 ZZU 学生整理适合计算机相关专业本科生对照实现与复习备考。压缩包共 2 个文件其中 C 源文件实现了子集构造法将 NFA 转为 DFA并通过合并等价状态完成 DFA 最小化Word 实验报告详细记录了实验目的、步骤、遇到的问题及解决方案便于理解自动机理论在词法分析中的应用。资源包仅 722KB轻量易用已有 413 人学习浏览。代码注重算法流程清晰报告结构完整既可作为课设提交模板也能用于巩固子集构造、状态等价划分等重点难点对正在完成编译原理实验的学生具有直接参考价值。 编译原理课在ZZU有一个很经典的实验NFA转DFA并最小化。我把这个实验拆开看其实就是两件事——先用子集构造法把不确定的自动机变成确定的再用划分法把确定自动机里行为完全一样的等价状态合并掉。代码量说实话不大核心逻辑加起来两百行左右但每年都有不少人栽在ε-closure和划分法的细节上。这篇文章把我整理过的完整实现思路、实验报告写法、以及我踩过的坑都写出来适合正在做这个实验、或者想彻底搞懂NFA和DFA之间转换关系的人。1. 这实验到底考什么一条线串起三个算法1.1 题面拆解ZZU的编译原理实验指导书通常会给出这样的要求输入一个正则表达式经过一系列转换输出一个等价的最小化DFA。这个流程在教材上被分成三个算法——从正则表达式构造NFAThompson构造法、NFA转DFA子集构造法、DFA最小化划分法。我在做的时候发现很多人把时间耗在第一步的正则解析上反而忽略了后面两个核心算法。这里先说明白本文重点讲后两段也就是如何写出NFA转DFA的代码和如何写出最小化DFA的代码。如果你实验指导书要求从正则表达式开始那只需要把Thompson构造法的NFA输出对接上即可我下面定义的数据结构完全兼容。1.2 为什么需要这三步NFA对人友好因为从正则表达式构造NFA的过程完全机械几乎不需要思考。但NFA对机器不友好比如字符串abb在NFA里可能同时存在多条匹配路径词法分析器如果直接照着NFA跑每一步都需要回溯性能完全不可控。DFA就不一样了它每个状态在某个输入符号下有且只有一个转移目标匹配字符串就是一次线性扫描。所以编译器后端宁可要一个状态更多但确定性的自动机也不要一个状态更少但充满不确定性的自动机。而最小化DFA就更有工程味道了。子集构造法生成的DFA状态数往往是原来的好几倍但这些状态里有很多是行为一致的它们可以合并。状态少了查表空间就小了词法分析器的运行效率也会提升。说白了这个实验不只是让你背算法而是在演示一个典型的编译优化过程。1.3 一个通用的NFA数据结构在写代码之前先把NFA的存储方式定下来。我选择用字典表示转移函数原因很简单(状态, 符号) - 目标状态集合天然就是字典的key-value结构查起来又快又直观。nfa { states: {0, 1, 2, 3}, alphabet: {a, b}, transitions: { (0, a): {1}, (1, ε): {2}, (2, b): {3}, }, start: 0, accepting: {3}, }这里的ε我用一个普通字符串表示你放心它不会和输入字母表里的真实符号冲突因为正规的字母表里不会允许 ε 作为输入字符。转移函数里查不到某个(state, symbol)的key时就说明该状态在当前符号下没有转移目标集合为空集代码里直接当空处理就行。2. 子集构造法实现核心是两个基本函数2.1 ε-closure和move这两个操作先搞明白子集构造法的理论很绕但落到代码上真正的核心就两个操作。第一个是eps_closure(states)从当前状态集合出发沿着所有的 ε 边能够到达的所有状态的集合。这个操作本质是一个图上遍历问题用BFS或者DFS都能实现。注意它必须把传入的状态本身也包含在结果里因为一个状态通过零条ε边到达的还是它自己。第二个是move(states, symbol)从当前状态集合出发沿着某条具体的输入符号边能到达的所有状态的集合。这个操作很简单就是把这组状态每一个都在转移表里查一遍把目标合并。这两个操作的关系是这样NFA转DFA时对某个DFA状态它本身是一个NFA状态集合读取符号a后的目标状态不是直接等于move(current, a)而是eps_closure(move(current, a))。因为到达目标后还能继续沿ε边往下走必须把ε闭包也包进来才是完整的后继状态。当时我就是漏了这层包裹导致结果差一截。2.2 子集构造主循环一个队列清空为止有了上面两个函数主循环的思路就清晰了先把NFA的起始状态的ε闭包算出来它作为DFA的起始状态。把这个状态标记为未处理进入待处理队列。每次从队列里取出一个状态对字母表里的每个符号计算eps_closure(move(current, symbol))得到一个新的NFA状态集合。如果这个集合之前没见过就分配一个新DFA状态名放进待处理队列。记录(当前DFA状态, 符号) - 目标DFA状态的转移关系。重复直到队列为空。这本质上是对所有可达的NFA状态子集做一次全图遍历。这里有个容易剩的细节DFA状态必须用不可变的frozenset作为字典key因为普通set在Python里不可哈希没法作为key。2.3 核心代码从NFA到DFA我直接用Python写一套可运行的版本你如果实验要求用C/C逻辑完全一样把set换成std::set或bitset即可。def eps_closure(nfa, states): stack list(states) closure set(states) while stack: s stack.pop() nxt nfa[transitions].get((s, ε), set()) for t in nxt: if t not in closure: closure.add(t) stack.append(t) return closure def move(nfa, states, symbol): result set() for s in states: nxt nfa[transitions].get((s, symbol), set()) result.update(nxt) return result def nfa_to_dfa(nfa): start_set frozenset(eps_closure(nfa, {nfa[start]})) state_map {start_set: A} unmarked [start_set] dfa_transitions {} while unmarked: current unmarked.pop(0) cur_name state_map[current] for sym in nfa[alphabet]: if sym ε: continue nxt_set frozenset(eps_closure(nfa, move(nfa, current, sym))) if len(nxt_set) 0: continue if nxt_set not in state_map: state_map[nxt_set] chr(ord(A) len(state_map)) unmarked.append(nxt_set) dfa_transitions[(cur_name, sym)] state_map[nxt_set] dfa_accepting set() for st_set, name in state_map.items(): if any(s in nfa[accepting] for s in st_set): dfa_accepting.add(name) return state_map, dfa_transitions, dfa_accepting2.4 状态命名与接受状态判断状态命名我用A、B、C这样递增的字符。这里的顺序有一个事实上的规律先分配的状态往往就是距离起始状态较近的状态输出起来比较自然。接受状态判断要特别注意一个原则只要DFA状态对应的NFA状态集合里包含任意一个NFA接受状态这个DFA状态就是接受状态。反过来不对——不是说所有NFA状态都必须是接受状态。这个细节理解错了最小化后会得到完全错误的划分结果。3. DFA最小化划分法的代码落地3.1 先做一次可达性清洗最小化之前强烈建议先做一步预处理删除不可达状态。子集构造法理论上不会产生不可达状态但如果你是自己手工构造的DFA或者从前一步接的数据有问题这一步能帮你节省大量排查时间。做法本身很简单从起始状态出发沿所有符号跑一遍BFS能遍历到的状态就是可达的。然后把可达状态之外的转移和状态列表全部删掉。我遇到过同学拿着一个有不可达状态的DFA做最小化初始划分把不可达状态也放进去了结果新DFA里凭空多出几个没人能到达的状态整个最小化结果看起来非常奇怪。3.2 初始划分接受和非接受先分开最小化的理论依据是等价状态如果两个状态在任意输入下最终的接受/拒绝行为完全一致那它们就可以合并。Hopcroft算法虽然是更优的划分方式但工程和实验层面划分细化法反而更好写、更好验证。第一步永远是把DFA状态集划分成两个组接受状态组和非接受状态组。为什么要这么分因为等价状态有个最底层的约束接受状态和非接受状态在空串下行为就不同不可能等价。3.3 迭代细化用行为指纹分裂组划分法的核心是反复检查每个组里的状态看它们在某个符号下是否跳出了本组。具体做法是对组内每个状态计算它分别在每个输入符号下到达的目标状态记录这些目标状态各自属于当前划分的第几组形成一个行为指纹。如果组内某两个状态的行为指纹不同说明它们在某个符号输入后走到了不同性质的组必须分裂开。举个最直观的例子某组里有状态X和Y在输入a时X跳到组0Y跳到组1那X和Y绝对不可等价因为后面发生的事完全不同。3.4 最小化完整代码def minimize_dfa(state_map, dfa_transitions, dfa_accepting, alphabet): states set(state_map.values()) symbols [s for s in alphabet if s ! ε] partition [set(dfa_accepting), set(states) - set(dfa_accepting)] partition [g for g in partition if g] while True: new_partition [] for group in partition: fingerprint {} for st in group: behavior [] for sym in symbols: target dfa_transitions.get((st, sym)) group_index None for idx, g in enumerate(partition): if target in g: group_index idx break behavior.append(group_index) key tuple(behavior) fingerprint.setdefault(key, set()).add(st) new_partition.extend(fingerprint.values()) if len(new_partition) len(partition): partition new_partition break partition new_partition return partition这个写法里有个小trick对每个状态生成行为指纹后用字典的setdefault把指纹相同的状态塞进同一集合一句话就完成了按指纹分组。你如果写C可以用mapvectorint, vectorint达到同样效果。3.5 重命名状态并输出新DFA划分完成后需要把每个组映射成一个新状态重新生成转移表。我的做法是给组按顺序编号S0, S1, S2...然后遍历原DFA的每一条转移把源状态和目标状态都替换成组编号。这里还有一个容易忽略的细节最小化后的DFA的起始状态就是原起始状态所在的组接受状态是那些整个组都属于原来接受集合的组。由于初始划分已经保证了接受态和非接受态不会在同一个组里所以这一步判断非常简单。4. 怎么验证程序对不对这类实验的测试玄学4.1 手工可算的经典用例写完了代码怎么确信它是对的我的习惯是找一个能手工推演的用例把程序输出和手算结果逐行对照。推荐使用正则表达式(a|b)*abb对应的NFA。这个例子在龙书里出现过也是我实验时拿来做验证的标准用例。手工推导的结果是转换后的DFA有5个状态记为A到E其中E是接受状态最小化之后变成4个状态因为有两个状态在行为上等价的。如果你跑出来的结果和这个对不上那一定哪里出了问题。为什么这个用例好因为它既包含了ε转移又有多个不同的可达子集还真的存在可合并的等价状态。一个用例能同时检验NFA转DFA和最小化两个阶段的正确性。4.2 逐步打印调试法调试这类算法我强烈建议写一个调试输出函数每一步都打印当前队列内容、当前状态集合、计算出的ε闭包。比如在子集构造的主循环里把每个当前状态和它产生的所有后继集合都打出来。很多bug本质上是状态集合算错了但如果你只盯着最终DFA看根本看不出是哪个中间步骤出了问题。把每一步的eps_closure(move(...))结果都打印出来对照教材上手工推导的每一步几秒钟就能定位到问题。4.3 边界情况清单我整理了一份经常被忽视的边界情况做实验前先自查NFA只有一个状态且没有转移空串可接受。这时DFA应当只有一个状态而且它是接受状态。某个DFA状态在某符号下没有任何转移。代码里要允许target不存在行为指纹里记为None。全体状态都是接受状态。初始划分里非接受组是空集合代码要先过滤空组。存在不可达状态。这个前面提过先删再最小化。这些边界情况看着不起眼但往往是验收老师最喜欢问的你这个程序能处理吗的问题。5. 实验报告怎么写老师才会给高分5.1 报告不是代码粘贴板我见过很多人把实验报告写成代码打印版一个类图都没有DFS讲解也没有全是代码。这种报告在ZZU的编译原理实验里一般只能拿个及格分。老师的评分逻辑其实很简单实验核心算法你是否真的理解了。这种理解没法通过代码体积证明只能通过文字、图表、步骤推演来传递。所以报告里一定要有算法流程图手画或截图都行、关键数据结构说明、以及至少一个用例的完整推导过程。5.2 一份高分报告的结构我在最终提交时用的是这个结构你可以直接参考实验目的两句话点明掌握子集构造法和划分法。算法设计分别说明NFA转DFA和最小化的核心思想最好有一个状态集合转换的例子。数据结构设计解释为什么用字典存转移、为什么用frozenset作为状态key。核心代码只贴关键函数不要贴完整文件代码里要有充分注释。测试与分析给出(a|b)*abb的完整推演结果包含每一步的状态集合。遇到的问题我在报告里写的是ε-closure计算时遗漏了起始状态本身和最小化时初始划分忘记过滤空组这些真实的踩坑记录反而很加分说明你真的调过、想过。5.3 让测试与分析部分更有说服力写测试部分时不要只贴一张控制台截图。更好的做法是给一个三列表格输入字符串、手动推导结果、程序输出结果。比如abb - 接受、abba - 不接受、babb - 接受等等。字符串覆盖要讲究最短接受串、最长拒绝串、包含死循环的回退串、空串。把这些结果整理成表格老师一眼就看出你程序的行为是对的比你在报告里夸自己十句都管用。6. 我踩过的坑和编写心得6.1 三个隐蔽bug每一个都能让你调试到怀疑人生第一个是move和eps_closure的顺序问题。有人写成move(eps_closure(...), sym)有人写成eps_closure(move(...))。这两种语义完全不同。正确顺序一定是先move再closure因为ε边可能在符号边之后继续延伸但绝不会在符号边之前帮你读入一个符号。这个顺序我当时混淆过一次输出的DFA状态弧全乱套了。第二个是frozenset使用问题。Python的字典key必须是可哈希的普通set不可哈希要是一不小心用set当key程序一运行就报TypeError: unhashable type: set。解决办法是统一转成frozenset。第三个是死状态的处理。DFA最小化时如果一个状态在某个符号下没有转移它的行为指纹里该符号对应的组编号就会是None。两个状态同样没有转移它们在这个符号下的指纹应当一致都是None这样它们才可能等价。一开始我在处理这种行为时用了不同的默认值导致两个等价状态没合并成功状态数多了一个。6.2 对性能的一点点扩展思考实验本身对性能要求不高但如果后续往下做词法分析器状态表的存储方式就要重新考虑了。我当时实验用的是矩阵式转移表也就是用二维数组存状态和符号的交叉表查起来复杂度O(1)。而子集构造法里用字典存稀疏转移在实验规模下更方便调试。还有一个扩展方向是Hopcroft算法。划分法在实验层面足够用但Hopcroft算法把待处理组用栈或队列管理能在O(n log n)时间内完成最小化。有兴趣的话可以在实验报告的改进方向里提两笔老师对这个比较有兴趣但代码主体不要换否则出了问题反而得不偿失。这个实验做完之后我最大的感受是编译原理里最抽象的自动机概念其实是可以用几百行代码、几十个状态集合、一张转移表来摸得着的东西。如果你现在正被 ε-closure 绕晕或者最小化结果总差一个状态别急着怀疑自己把每一步集合都打印出来手推一遍基本都能找到原因。本文还有配套的精品资源点击获取