★ FEATURED ARTICLE 简介适用于《编译原理》课程中NFA转DFA并最小化实验面向郑州大学ZZU计算机相关专业学生及需要完成类似实验的学习者。压缩包共2个文件一个C源程序一个Word实验报告。C代码以子集构造法为核心完成NFA状态集到DFA状态集的转换并通过对等价状态的合并实现最小化代码逻辑清晰便于对照算法流程逐步理解还能直观体会DFA简化对词法分析效率的影响。实验报告涵盖实验目的、设计思路、核心代码说明、运行结果以及问题排查过程可帮助读者快速掌握实验要点同时可作为课程报告的撰写参考。通过阅读代码和报告可以系统梳理NFA、DFA、子集构造与最小化的关系为后续词法分析设计打下基础。资源包整体约722KB下载和查阅都很方便。目前已有415人学习/下载适合正在完成同题实验或复习编译原理自动机知识的学生使用。1. NFA转DFA为什么一个非确定的模型反而要先写出来编译原理实验里NFA转DFA并最小化几乎是一道必修的硬骨头而C又恰好是这个实验最常见的实现语言。我第一次做这个实验时心里有个巨大的问号既然NFA已经能描述正则语言为什么还要多此一举转成DFA甚至还要再最小化反直觉的结论是NFA是写给人看的描述模型CPU根本没法直接执行它——NFA在一个状态读一个输入符号可能同时进入多个分支而物理上的CPU只有一个程序计数器没有同时进入多个分支的能力。真要硬跑NFA只能回溯或穷举所有路径最坏是指数级的。所以词法分析器的标准路线永远是正则表达式到NFA再经子集构造法得到DFA最后最小化。这篇要拆的就是子集构造法和最小化背后的集合机制以及怎么用C把状态集合老老实实落成一张张由数组下标组成的转移表。搞懂这段词法分析器从正则到状态机的那条路就彻底通了。2. 当NFA遇上DFA子集构造法到底在构造什么先给一个最朴素的理解NFA的转移关系是一个多值关系同一状态、同一输入符号可能指向零个或多个状态而DFA的转移是一个单值函数。子集构造法的全部思想就是用一个NFA状态集合来扮演DFA的一个状态——把我当前同时可能处于这些状态这件事本身编码进一个DFA状态里。这样DFA虽然状态数变多了但每个状态都是确定的给出当前输入就能算出一个唯一的下一步编号。这个思路看起来简单落地却有两个容易含糊的算子ε-闭包和move。它们一管不消费字符的路径一管消费一个字符的路径两者合成一步完整转移。这一章把这两个运算符的语义和顺序讲透它们才是子集构造法能成立的根基。2.1 ε-闭包先回答不读任何字符能走到哪标准构造法从正则表达式建NFA时会大量使用ε边。ε边不消费任何输入它只是把一个子表达式的出口胶水到另一个子表达式的入口像流水线上的传送带。正因如此NFA里会出现我明明没读字符但状态已经悄悄变了好几个的情况。ε-闭包要回答的就是给定一个NFA状态集合T在不读取任何输入符号的前提下从T中的状态出发沿ε边能到达的所有状态包含T自身共有哪些。形式化定义是一个最小不动点closure(T) T ∪ closure(move(T, ε))意思是先取T本身再看T通过ε边一步能到的状态循环往复直到不再增长。这个最小很关键不是随便找一个满足条件的集合而是要所有ε可达状态的并集。实现时建议用队列做BFS而不是写一个不做标记的递归——一旦NFA里有ε环标记不清的递归会直接栈溢出。// 求状态集合 T 的 ε-闭包nfa.eps[s] 是状态 s 的 ε 转移目标列表 StateSet epsClosure(const NFA nfa, const StateSet T) { StateSet closure(T); // 先把 T 自身放进去 queueint q; vectorbool in(nfa.n, false); // 判重标记防止 ε 环死循环 for (int s : T) { q.push(s); in[s] true; } while (!q.empty()) { int u q.front(); q.pop(); for (int v : nfa.eps[u]) { if (!in[v]) { in[v] true; closure.insert(v); // 发现新的 ε 可达状态 q.push(v); } } } return closure; }这段代码的核心是in数组。没有它遇到自环或环状ε边时同一个状态会被反复入队轻则重复计算重则永不停机。closure.insert(v)保证集合的有序性也为后面用mapStateSet,int做状态编号埋下伏笔——有序集合才能作为稳定的键。2.2 move 与闭包的顺序一步转移的完整语义move 的定义很直白从集合T中任一状态出发读一个输入符号 ch走一步得到的所有目标状态的集合。move(T, ch) { q | 存在 p∈Tp 通过 ch 一步到达 q }但它不包含走完这一步之后再沿ε边滑动的部分。NFA的语义是读完一个字符后可以连续走任意多条ε边所以读一个符号后的完整状态集合必须是next(T, ch) epsClosure(move(T, ch))这里有一个非常容易踩的顺序坑是先对T求闭包再move还是先move再闭包我见过不少代码写的是先闭包再move理由是当然得先看看闭包里有没有更多能走这条边的状态。这两种写法在一般情况下结果不同。考虑一个极简NFA状态0经ε到达状态1状态1读a到达状态2取T{0}。先闭包再move得到{2}先move再闭包得到空集。正确语义是{2}因为NFA允许先滑过ε边再读a。为什么按照先move再闭包的公式算结果却是空集呢关键在于子集构造法有一个隐含约定存进DFA状态表里的每一个NFA状态集合都已经是ε-闭包之后的规格化形态。初始状态是初态的闭包之后每生成一个新状态也立刻求闭包再入库。所以代码里实际执行的是epsClosure(move(已闭包的集合, ch))其中move的源集合本身就含了闭包中的状态1结果自然正确。这个约定是整个算法不跑偏的前提DFA状态集合永远是闭包形态不允许把一个未闭包的集合放进去当状态。2.3 从NFA到DFA队列式生成状态表有了两个算子子集构造法的主流程就非常简单了计算初态集合的ε-闭包作为DFA的初态入队并编号。从队列取出一个DFA状态对字母表中每个符号ch计算epsClosure(move(S, ch))。结果若已存在直接复用编号否则分配新编号入队并记录其接受性。循环直到队列为空。接受性的判定规则是只要这个NFA状态集合中至少包含一个NFA接受状态对应的DFA状态就是接受状态。注意由于集合都是闭包形态NFA接受状态经ε边能到达的其他状态也已经在这个集合里不需要额外处理。StateSet start epsClosure(nfa, {nfa.start}); dfaStates.push_back(start); idOf[start] 0; dfaAccept.push_back(containsAccept(start, nfa.accept)); for (int i 0; i (int)dfaStates.size(); i) { dfaTable.push_back({}); for (char ch : nfa.alphabet) { StateSet go epsClosure(nfa, move(nfa, dfaStates[i], ch)); if (go.empty()) { dfaTable[i].push_back(-1); // 无转移留空 continue; } auto it idOf.find(go); int id; if (it idOf.end()) { id (int)dfaStates.size(); // 新状态编号 idOf[go] id; dfaStates.push_back(go); dfaAccept.push_back(containsAccept(go, nfa.accept)); } else { id it-second; } dfaTable[i].push_back(id); } }这段代码有两个值得注意的参数。idOf是mapStateSet,int键是NFA状态集合值是DFA编号。用map而不是unordered_map是因为StateSet是setint本身就支持比较而哈希容器还得为集合写哈希函数实验环境里没必要。dfaTable的每一行对应一个DFA状态列数等于字母表大小-1表示该字符上没有转移。用教材里经典的(a|b)*abb正则来做例子按标准构造法先生成含ε边的NFA再跑子集构造得到5个DFA状态转移表如下。其中 S0 是初态D 是唯一的接受状态因为它对应的NFA状态集合里含NFA的接受状态10。DFA状态对应的NFA状态集合ab是否接受S0{0,1,2,4,7}AB否A{1,2,3,4,6,7,8}AC否B{1,2,4,5,6,7}AB否C{1,2,4,5,6,7,9}AD否D{1,2,4,5,6,7,10}AB是注意A和B在读a后都进入AD读b后回到B。这5个状态看起来已经挺规整但它果真是最少的吗这正是下一章最小化要回答的问题。3. 最小化把DFA状态当成等价类来分家子集构造法做完得到的DFA是从NFA状态集合原样映射来的它保留了NFA里的冗余多个DFA状态可能在未来所有输入下表现完全一致留着它们只是浪费内存和查表时间。最小化的本质是找出这些不可区分的状态并把它们合并成一个。很多人把最小化当成一个可选的优化步骤其实在词法分析器里状态表每多一个状态驱动循环的switch就多一个分支缓存友好度和代码体积都受影响。3.1 不可区分性什么情况下两个状态可以合并两个DFA状态p、q是等价的当且仅当对任意一个剩余输入串w从p出发读w最终进入接受状态当且仅当从q出发读w也最终进入接受状态。换句话说它们在剩余语言上是完全一样的合并任何一个都不会改变自动机接受的语言。这个等价关系有很好的代数性质自动机理论里有结论说按这个关系划分出的等价类数量就是能接受该语言的最小DFA状态数。最小化算法不需要关心这个定理怎么证明但要知道两个推论第一接受状态和非接受状态永远不等价因为空串w就能把它们区分开。所以初始划分一定是两组接受组和非接受组。第二如果两个状态在当前划分下属于同一组但对某个输入符号ch它们的转移目标却落入了不同的组那么它们必须分家——存在一个串ch接上能区分那两个目标组的剩余串能把它们区分开。3.2 划分迭代每一轮都是在扩展测试串的长度算法的主体是一个不断分裂分组的循环。对每个状态构造一个签名自己的组号加上对字母表每个符号转移目标各自所在的组号。签名相同的状态可以暂时留在同一组签名不同的必须拆开。vectorint minimizeDFA(const vectorvectorint table, const vectorbool accept) { int n (int)table.size(); vectorint g(n, 0); // 初始分组0 非接受 for (int s 0; s n; s) if (accept[s]) g[s] 1; // 1 接受 while (true) { setint oldGroups(g.begin(), g.end()); int oldCnt (int)oldGroups.size(); mapvectorint, int newId; vectorint ng(n); for (int s 0; s n; s) { vectorint sig; sig.push_back(g[s]); // 签名第一项自己的组号 for (int v : table[s]) // 之后每一项转移目标的组号 sig.push_back(v -1 ? -1 : g[v]); newId.emplace(sig, (int)newId.size()); // 不存在则分配新组号 ng[s] newId[sig]; } int newCnt (int)newId.size(); g ng; if (newCnt oldCnt) break; // 组数不再增加收敛 } return g; // g[s] 就是状态 s 的新编号 }这里解释三个关键点。第一-1的处理无转移的目标统一记为 -1在语义上等价于所有掉进死路的状态都聚到同一个虚拟目标这样两个读到某个符号都无路可走的状态不会因为一个记 -1 一个记别的编号而被误拆。第二收敛条件是比较新旧分组数量因为算法只分裂、不合并分组数单调不减数量稳定就说明没有任何组再被分裂。第三输出的g[s]就是最小化后新DFA的状态编号同一组的状态共享一个编号。这个迭代过程本质上是在逐步加长测试串的长度第一轮能区分空串接受性第二轮能区分长度为1的串第k轮能区分长度为k的串。因为DFA状态数有限区分到某一步必然收敛不会无限进行下去。3.3 手算实例拿上面的5状态DFA验一遍对2.3得到的5状态DFA做划分。初始分组非接受组 N{S0,A,B,C}接受组 A{D}。逐个算签名格式为自己的组读a去的组读b去的组状态第一轮签名分组结果S0(N, N, N)G1A(N, N, N)G1B(N, N, N)G1C(N, N, A)G2D(A, N, N)G3第一轮结束分成三组{S0,A,B}、{C}、{D}。注意C和S0、A、B的区别在于它读b会直接落到接受组D而S0、A、B读b落在非接受组。这个差异来自剩余串abb。第二轮继续现在组号是 G1{S0,A,B}、G2{C}、G3{D}状态第二轮签名分组结果S0(G1, G1, G1)H1B(G1, G1, G1)H1A(G1, G1, G2)H2C(G2, G1, G3)H3D(G3, G1, G1)H4第二轮后分成四组{S0,B}、{A}、{C}、{D}。S0和B终于暴露了差异S0读b进入B还在本组而A读b进入C已经独立成组。第三轮签名里S0和B的完全一致分组数不再增加收敛。最终最小化结果{S0,B}合并为一个状态其余A、C、D各自独立。这个手算过程验证了一个重要事实只看会不会到达接受状态是不够的必须追踪每一步转移落在哪个组。S0和B在第一轮看起来都一样都是读到a进A、读到b进B但A在第二轮独立出去之后S0和B的行为才显出差异。最小化的玄学就在这里——不到最后一轮你永远不知道哪个状态会在更长的测试串下露馅。4. 用C落地的关键从集合到数组下标的映射算法层面讲清楚了实际写代码时还有一层表示的艺术。编译原理实验的本质是让你亲手把自动机这种数学对象翻译成C的数据结构而这一层翻译的质量直接决定你调试时是半小时收工还是熬夜翻车。4.1 NFA与DFA的数据结构选型比代码更关键NFA的核心成员就这么几样状态数、字母表、ε转移表、按字符索引的转移表、初态集合、接受状态集合。C里最直接的就是vector嵌套结构struct NFA { int n; // 状态数编号 0..n-1 vectorchar alphabet; // 字母表不含 ε vectorvectorint eps; // eps[s]s 经 ε 可达的目标列表 vectormapchar, vectorint trans; // trans[s][ch]s 读 ch 的所有目标 int start; // 初态 vectorbool accept; // accept[s] 标记 };DFA的数据结构更简单因为转移是单值的可以直接用二维数组或vector套vector每个单元格存一个int编号struct DFA { int n; // 状态数 vectorchar alphabet; // 字母表 vectorvectorint table; // table[s][i]状态 s 读 alphabet[i] 的目标 int start; // 初态 vectorbool accept; // 接受标记 };两个结构的设计动机值得多说一句NFA的eps和trans都是列表型的因为允许一个状态对同一符号有多个转移目标DFA的table是单值型的每一格只放一个编号。数据结构直接映照了模型的数学性质这也是为什么编译原理实验特别适合用来练数据抽象——你没法用一套结构同时表示好两种自动机。4.2 子集构造的实现mapStateSet,int是核心枢纽子集构造法的完整实现已经在2.3给出。这里补充一个之前没细讲的点StateSet用setint的意义。子集构造过程中NFA状态集合可能以不同的顺序被生成比如从状态2、3出发和从状态3、2出发得到的目标集合在逻辑上是同一个集合。setint自动排序去重保证{2,3}和{3,2}是同一个键map才能正确复用DFA状态编号。如果图省事用vectorint直接当键必须先排序再去重否则同一个逻辑状态会被分配多个编号DFA状态数会爆炸最小化结果也对不上。子集构造的循环里还有一个细节for (int i 0; i dfaStates.size(); i)在循环体内可能push_back新状态而dfaStates.size()每次循环都会重新求值所以这个写法是队列式的——新增的状态会在后续轮次被处理。这是STL容器允许在遍历中追加元素时的惯用法但前提是你用的是下标循环而不是范围for。4.3 最小化的实现-1与死态的边界4.2节产出的dfaTable里有不少-1表示某些状态在某个字符上没有转移。最小化代码中-1在签名里作为一个固定的组号参与比较。这里有个隐蔽的等价性所有-1都代表掉进同一个死胡同所以两个状态如果都在某个字符上无转移它们在签名里对应位置都是-1不会被误拆。这比给每个无转移格子塞一个独立的死状态编号更省事但代价是转移表里始终存在空项。如果你希望最终DFA是一张完整的转移表——词法分析器驱动时不判空直接查表——那么可以显式加一个死状态把所有的-1都替换成死状态的编号。死状态本身的转移指向自己。两种方案在最小化结果上等价死状态会被划分成一个单独的分组如果它不可达还可以从最终结果中删掉。但实测中删掉不可达死状态这一步经常被漏掉导致最小化后保留一个多余状态。这就是下一章要讲的坑。5. 常见问题与避坑NFA转DFA最容易翻车的五个细节这一章的每一条都是真实调过的血泪经验。现象、原因、解决分开写方便你对着自己的代码排查。5.1 状态编号混乱集合没有规格化DFA状态凭空多出几倍现象子集构造跑完DFA状态数比手算多了好几倍而且最小化之后仍然很多怎么都合不拢。原因StateSet用的是vectorint没排序也没去重。同一个NFA状态集合因为遍历顺序不同被记录成{2,3}和{3,2}在map里成了两个键于是生成了两个DFA状态。它们行为完全等价但算法认不出。解决统一用setint作为状态集合的底层容器或者手动对vector排序去重后再序列化成字符串或转为有序tuple当键。核心是规格化三个字——集合的表示形式必须唯一。5.2 ε-闭包写成递归遇上ε环直接栈溢出现象程序在构造初态闭包时崩溃报栈溢出或者小数据没事NFA状态一多就卡死。原因闭包函数用了递归但没有visited标记。NFA的ε边经常成环表示可重复任意次递归在环上反复调用自己栈被压爆。解决2.1的BFS写法用队列加in数组判重。如果坚持递归也必须带一个全局visited数组。最简单的自检办法构造一个状态0经ε到状态1状态1经ε再回到状态0的微型NFA跑一下闭包函数能正常结束才算过。5.3 最小化前忘了删不可达状态结果和教材对不上现象最小化后的状态数比答案多一个且多出来的状态从初态出发永远走不到。原因划分法只保证等价状态合并不可达状态虽然不影响语言但只要它存在就会占据一个分组编号最终结果里就多一个孤儿状态。解决在最小化之前先从初态对转移表做一次BFS或DFS收集所有可达状态把转移表映射到只含可达状态的新编号上再做划分。这一步在很多实验报告里叫删除无用状态它和最小化是两个独立阶段顺序不能颠倒。5.4 接受状态的判定写错漏掉集合包含关系现象某些字符串理论上该接受但生成的DFA里对应状态标成了非接受或者反过来把普通状态标成了接受。原因判定接受性时用了集合相等或包含所有NFA接受状态的逻辑。正确规则是包含至少一个NFA接受状态。因为子集构造的DFA状态是一个NFA状态集合只要其中任何一个成员是NFA接受状态这个DFA状态就应该接受——它代表NFA当前确实停在某个可接受的分支上。解决用一个containsAccept函数遍历集合成员遇到nfa.accept[s] true就返回真。另外注意DFA状态的接受性在第一次创建时就该定好不要等最小化阶段再补否则第二轮迭代用的初始分组就错了。5.5 最小化时拿NFA集合内容当等价依据现象最小化结果比预期少合并了行为不同的状态导致某些输入串的接受结果变化。原因这是最危险的一个错。手算时觉得两个DFA状态对应的NFA状态集合长得很像就手动把它们归到一组。但等价性只由接受性 每个符号转移目标所在的组号决定与NFA集合内容没有直接关系。两个NFA集合可能完全不同对应的DFA状态却等价也可能只差一个状态行为却南辕北辙。解决严格只用签名机制做划分不要掺任何人工判断。划分迭代是全自动的你唯一能干预的地方是初始分组和字母表顺序。如果怀疑实现有bug拿3.3的手算表验一遍每个状态的签名都列出来看分组是否和程序输出一致。6. 设计取舍从状态编码看自动机工程的边界把整个实验做完你会发现闪光点不在算法本身——子集构造法和划分法都是几十年前的经典结果——而在于你选择了哪一层表示。C实现里每一个设计取舍都在影响代码的复杂度边界。第一个取舍是状态集合的编码。用setint做map的键换来的是写起来省心代价是每次查表和插入都要做对数次比较NFA状态一多性能就难看。真要压性能可以把NFA状态集合按固定顺序序列化成一个64位整数或字符串配unordered_map把查找摊到O(1)。但实验规模下前者明显更值得——先保证正确再谈优化。第二个取舍是-1与显式死态。我在4.3说过两种方案结果等价但它们对下游代码的影响不同。词法分析器读字符时-1意味着当前词法状态失效需要回退并重新匹配这是个独立控制流显式死态则意味着继续查表停在死态即可。选择-1会让驱动逻辑多一个分支判断但保留了死态不存在这个不变式最小化分组时不需要为死态多留一个组。我倾向于用-1原因很朴素它让转移表里的每个未定义项一眼能看出来调试时不用猜这个状态到底往哪走。第三个取舍是划分法实现时的一个细节签名里的-1要不要单独编码。我见过有实现把无转移的格子填成-2结果两个都无转移的状态被当成不同签名拆开最小化结果多出冗余。把无转移统一视为同一个虚拟目标是这次实现里最不显眼却最关键的一个决定。做完这个实验我养成了一个习惯每次写状态机相关的代码都强制先做一步——把所有状态集合定义为有序、去重、闭包形态的规格化对象再开始写转移逻辑。这一个小小的约定省掉的调试时间远比写它的时间多。从那以后我的编译原理实验报告里不再有跑出的状态数和手算不符这类bug因为所有对不上的情况最后都回溯到了同一句话状态的表示不唯一。希望这篇拆解能帮你在写这份代码时少走几步我当时走过的弯路。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
