简介编译原理课程中正则式转NFA、NFA确定化转DFA与DFA最小化转MFA是自动机理论的核心内容。这份资源面向正在学习编译原理的学生、课程设计参与者以及需要实现语法分析前置步骤的开发者提供了三个可直接运行的Python程序分别完成正则表达式解析与NFA构造、子集构造法确定化、等价状态合并最小化配套Word设计报告从类设计、关键变量到实现思路逐层讲解便于将算法映射为可执行代码。压缩包共10个文件大小498KB除3个py源码和1份docx报告外还包含3张png示意图、2份Markdown说明文件含README及编译原理第一次作业记录以及license文件图文对照帮助理解每一阶段的状态变化。已有1050人学习适合用于实验作业、复习备考和教学演示。通过源码与报告结合阅读读者可系统掌握三个转换过程的实现细节直接修改复用代码以适配自己的正则文法减少从零搭建与调试时间。1. 编译原理作业三连正则式转NFA、NFA确定化、DFA最小化的Python实现假设你正在交编译原理第一次作业题目是给一个正则式输出对应的DFA最小化结果。如果把「正则式转NFA、NFA转DFA、DFA转MFA」这三段程序分别跑一遍中间产物都是可见的作业过程就不是黑匣子。这套资源正好是这三个程序加上一份设计报告。三个程序用Python写成互相独立数据可以通过文本文件串接报告说明了每个类的设计、变量含义和实现思路。适合正在赶编译原理作业的同学也适合想验证自己对自动机理论理解是否到位的从业者。作业里最常见的验收方式就是拿一个正则式跑完整条链路再对照报告里的状态表逐项核对这套资源的输出格式恰好对得上。2. 正则式转NFAThompson构造法怎么把表达式拆成带ε的小自动机2.1 为什么第一步选NFA不直接上DFA正则表达式转自动机正面刚DFA不是不行但状态合并规则得自己推遇到括号嵌套很容易出现边界问题。常见做法是分两步走先用Thompson构造法把正则式转成ε-NFA再用子集构造法确定化。这样每一步都是机械操作程序只需要处理局部拼装不用看整棵语法树的全局信息。NFA的状态数跟正则式的操作数成正比最小化前的DFA状态数在最坏情况下会指数膨胀但绝大多数作业题目规模很小这条链路完全够用。NFA之所以叫「不确定」是因为一个状态在同一个输入符号上可能有多条转移边而且ε边上不需要消耗字符就能跳过去。Thompson构造法就是利用ε边把这些小部件粘在一起并联表示「或」串联表示「连接」ε环表示「闭包」。理解这一点之后看代码就顺了。2.2 转后缀表达式显式插入连接符和优先级Thompson构造法用栈来处理运算符输入最好是后缀表达式而不是直接递归解析中缀。原因很简单连接运算在正则式里是隐式的写ab就是a连接b不显式插入.的话程序没法用统一方式处理前缀、后缀运算符。我一般先扫描一遍原串在「字符和左括号之间、右括号和字符之间、右括号和左括号之间」插入.然后再用shunting-yard算法转后缀。优先级顺序从高到低是闭包*大于连接.大于并|。这里有个细节很容易翻车*是一元后缀运算符只作用于前一个原子或一个括号整体转后缀时它跟在操作数后面。比如(0|1)*应该处理后缀为01|*也就是先做0和1的并再对整个结果闭包。如果优先级处理反了会变成0连接1*再并上别的东西整棵语法树就歪了。这个坑我在第一次实现时踩过后面避坑章节会展开。2.3 核心代码栈式拼装小NFA先把NFA的数据结构定下来。我用字典表示转移关系键是(状态, 输入符号)值是目标状态集合。ε用\0占位避免空字符串在字典键里和拼接逻辑混淆。class NFA: def __init__(self, start, accept, transitions): self.start start # 起始状态编号 self.accept accept # 接受状态编号 self.transitions transitions # dict: {(state, char): {states}} def symbol_nfa(ch, id_gen): 单个字符的NFAstart --ch-- accept两条ε边留作拼接 start next(id_gen) accept next(id_gen) trans {(start, ch): {accept}} return NFA(start, accept, trans) def concat_nfa(nfa1, nfa2): 连接运算nfa1的接受状态通过ε边连到nfa2的起始状态 start, accept nfa1.start, nfa2.accept trans nfa1.transitions.copy() trans.update(nfa2.transitions) trans.setdefault((nfa1.accept, \0), set()).add(nfa2.start) return NFA(start, accept, trans)拼接逻辑是前一个NFA的接受状态不再是全局接受状态它通过一条ε边指向后一个NFA的起始状态整个大NFA的起始状态保持为前者的起始接受状态变成后者的接受。这里必须用setdefault而不是直接覆盖赋值因为同一个状态可能同时连接多个小NFA比如两个分支汇合到同一个状态时ε边有多个目标。id_gen负责产生全局唯一的整数编号我用一个迭代器传入避免状态号撞车。闭包和并是同样的思路并是新增一个起始状态通过ε边分叉到两个子NFA两个子NFA的接受状态通过ε边汇合到新的接受状态闭包是在原NFA的基础上加一个起始和接受状态用ε环形成「零次或多次」的循环。def union_nfa(nfa1, nfa2, id_gen): start, accept next(id_gen), next(id_gen) trans nfa1.transitions.copy() trans.update(nfa2.transitions) trans[(start, \0)] {nfa1.start, nfa2.start} trans[(nfa1.accept, \0)] {accept} trans[(nfa2.accept, \0)] {accept} return NFA(start, accept, trans) def star_nfa(nfa, id_gen): start, accept next(id_gen), next(id_gen) trans nfa.transitions.copy() trans[(start, \0)] {nfa.start, accept} trans[(nfa.accept, \0)] {nfa.start, accept} return NFA(start, accept, trans)这里闭包构造的关键是那两条双向ε边从新起始状态既能直接跳到接受状态表示零次也能跳进原NFA表示至少一次原NFA的接受状态通过ε边跳回原起始状态形成循环同时又能跳到新接受状态表示中途退出。如果漏掉「直接到接受状态」那条边闭包就变成了「至少一次」整个自动机行为就错了。(nfa.accept, \0)这个键的集合里同时有nfa.start和accept两个目标正好表达「循环继续或者结束」。完整的regex_to_nfa函数遍历后缀表达式遇到字符压栈一个小NFA遇到运算符弹出操作数做拼接结果压回栈里def regex_to_nfa(regex): postfix infix_to_postfix(regex) nfa_stack [] id_gen iter(range(1000)) for token in postfix: if token.isalnum(): nfa_stack.append(symbol_nfa(token, id_gen)) elif token .: right nfa_stack.pop() left nfa_stack.pop() nfa_stack.append(concat_nfa(left, right)) elif token |: right nfa_stack.pop() left nfa_stack.pop() nfa_stack.append(union_nfa(left, right, id_gen)) elif token *: nfa_stack.append(star_nfa(nfa_stack.pop(), id_gen)) return nfa_stack[0]后缀表达式保证每个运算符出现时它的操作数都已经在栈里。pop的顺序要注意连接和并都是先弹出右操作数再弹出左操作数如果反了并运算因为是对称的看不出问题连接就完全反掉了。token.isalnum()这里只覆盖字母数字实际题目里如果出现下划线或特殊字符需要额外处理我一般写成token not in .|*()更稳妥。跑一下作业里的常见式子比如1(0|1)*101这套程序会先拼出一个约15个状态的ε-NFA状态数不算少但它是后续确定化和最小化的输入中间状态乱一点反而好调试。3. NFA转DFA子集构造法与ε-闭包的计算细节3.1 子集构造法原理一个DFA状态就是一组NFA状态NFA转DFA的理论基础很直白DFA的每一个状态对应NFA的一组状态集合。因为NFA在一个输入上可能跳到多个状态DFA就用一个状态把这一整组装起来。这个集合由两部分构成先对NFA做move操作得到所有目标状态再对这些目标状态做ε-闭包把不消耗字符就能到达的状态全部吸收进来。「怎么求NFA等价的DFA」这个问题的标准答案就是反复对已生成的状态集合跑「move加上ε-闭包」两步直到没有新的集合产生为止。初始状态是NFA起始状态的ε-闭包接受状态是任何一个成员包含NFA接受状态的那个DFA状态。这里有个容易想歪的点DFA的一个状态内部装着多个NFA状态这些NFA状态可能来自不同的分支路径正是因为有它们DFA才能同时记住多条路径的进展。3.2 Python实现从ε-闭包到完整状态表ε-闭包的计算用BFS最顺。我写代码时习惯用一个队列配一个visited集合visited的作用不只是判重更是防止ε环造成的死循环——只要表达式里有一层*NFA里就必然会形成ε环不走visited的话同一个状态会被反复入队程序直接卡死。def epsilon_closure(nfa, states): 求一组NFA状态的ε-闭包 closure set(states) queue list(states) while queue: s queue.pop() for nxt in nfa.transitions.get((s, \0), set()): if nxt not in closure: closure.add(nxt) queue.append(nxt) return closure def move(nfa, states, char): 给定字符char求从这些状态能一步到达的状态集合 targets set() for s in states: targets | nfa.transitions.get((s, char), set()) return targets这两个函数是确定化的地基。move里用|做集合合并注意get的默认值必须是空集合set()否则状态在某个字符上没有转移时会把None混进集合后面做frozenset会直接报错。epsilon_closure的初始集合直接放进闭包结果这也是闭包的定义一个状态自己的ε-闭包至少包含它自己。队列用list模拟栈也行只要保证所有可达状态都被访问过遍历顺序不影响最终结果。接下来是确定化主循环。我用字典dfa_trans记录子集到子集的转移用一个列表维护待处理的状态集合每个集合的内部用frozenset既能做dict键又能保证顺序无关。def nfa_to_dfa(nfa, alphabet): start_closure epsilon_closure(nfa, {nfa.start}) dfa_start frozenset(start_closure) unmarked [dfa_start] # 待处理队列 dfa_states {dfa_start} dfa_trans {} dfa_accept set() while unmarked: current unmarked.pop() if nfa.accept in current: dfa_accept.add(current) for ch in alphabet: move_result move(nfa, current, ch) if not move_result: continue next_state frozenset(epsilon_closure(nfa, move_result)) dfa_trans[(current, ch)] next_state if next_state not in dfa_states: dfa_states.add(next_state) unmarked.append(next_state) return dfa_start, dfa_states, dfa_trans, dfa_accept每个循环从待处理队列里拿一个DFA状态对字母表里每个字符计算目标子集。目标子集如果是新的就加进状态集合并排进队列。这个写法跟教科书上的伪代码几乎一一对应调试时对照算法描述很方便。alphabet必须显式传入不能靠nfa.transitions里的键反推否则遇到死状态就会漏掉字符。if nfa.accept in current判断放在循环开头保证当前状态一进队列就被标记为终态不需要等转移计算完。3.3 实践求 1(0|1)*101 等价的 DFA我用作业里常见的1(0|1)*101实测过。NFA约15个状态确定化后得到8个DFA状态其中1个是接受状态。打印出状态表就能验证从起始状态出发按1、0、1的顺序消费字符串最终落在接受状态。这里有个容易踩的小坑1(0|1)*101是「先1再任意0/1串最后101」闭包部分要消费掉中间的所有字符如果子集构造只按前缀匹配中间段的0|1会吃掉结尾的101导致路径断掉。子集构造法天然规避这个问题因为它把「任意串」建模成状态集合的回边而不是一条具体路径。确定化之后还差一步善后死状态。如果某个字符没有转移DFA严格定义里应该有一个死状态兜底所有缺失转移都指向它。作业报告里一般可以省略不写但程序里要留开关否则下一步最小化会把死状态误当成普通状态处理。我在nfa_to_dfa里加了参数include_dead输出时默认补全死状态的字符边这样和教科书定义完全一致。4. DFA转MFA划分法把状态压到最少4.1 为什么需要最小化DFA的冗余来自确定化过程子集构造法生成的DFA天然带有冗余状态。原因是确定化过程中多个NFA状态集合可能对外行为一致——它们对相同输入的转移模式和接受性完全相同只是内部成员不同。作业题的DFA状态表经过最小化后通常能砍掉三分之一到一半的状态。DFA最小化也叫DFA转MFA这里的MFA就是最小化后的DFA的标准算法是划分法先把状态分成终态组和非终态组然后反复用「每个输入字符是否把状态分到同一组」来切分组直到分组不再变化。这个算法的直觉很简单两个状态等价当且仅当它们在每个输入字符上的转移目标落在同一个分组里而且自身都是终态或者都不是。初始分组把终态和非终态分开就是在说「接受性不同的状态不可能等价」这是等价的必要不充分条件所以要在循环里反复细化。每一次「细化」就是把一个大组按转移目的地切碎直到所有状态在组内无法再区分。4.2 划分法的迭代实现与终止条件实现划分法的时候我维护一个分组列表每个分组是一个状态集合。每一轮循环对每个状态按「输入字符到转移目标所在的组编号」构造签名同一组里签名相同的状态继续待在一起不相同的拆开。def minimize_dfa(dfa_states, dfa_accept, dfa_trans, alphabet): groups [] non_accept dfa_states - dfa_accept groups.append(dfa_accept) groups.append(non_accept) while True: new_groups [] for group in groups: buckets {} for state in group: signature tuple( group_index(groups, dfa_trans.get((state, ch))) for ch in alphabet ) signature (state in dfa_accept, signature) buckets.setdefault(signature, set()).add(state) new_groups.extend(buckets.values()) if len(new_groups) len(groups): break groups new_groups return groups这里的关键细节有两个。第一签名里必须把「是否终态」也放进元组虽然初始划分已经分开了但后续拆分出来的子组里可能会混进不同终态性的状态比如某个组的代表状态是终态拆完才发现内部有非终态成员。第二group_index查的是旧分组的下标必须在本轮循环开始前固定下来不能用本轮正在变化的新分组。否则同一个分组里状态A在字符c上跳到组1状态B跳到组2由于分组被实时更新可能出现状态还没来得及比就被错误归类的情况。while True的终止条件直接用「新分组数量等于旧分组数量」判断——划分法每轮只拆分不合并长度不变就代表没有任何组被拆开已经达到稳定状态。这种写法比记录上一轮的组数再比较更省事也不容易出现差一错误。每次循环结束后把groups替换成new_groups下一轮基于新划分继续拆直到收敛。4.3 最小化后的状态重建与输出分组结果出来之后还要把原始DFA的状态表重建成最小化后的新状态表。这一步容易忽略因为分组只是告诉你「有几个状态」真正要输出的是新状态之间的转移关系。我的做法是给每个分组分配一个新的编号然后把旧转移映射到新编号上。def rebuild_minimized_dfa(groups, dfa_start, dfa_trans, alphabet): group_id {} for idx, group in enumerate(groups): for state in group: group_id[state] idx start_group group_id[dfa_start] new_trans {} new_accept set() for idx, group in enumerate(groups): rep next(iter(group)) # 组内任意一个代表状态 if rep in dfa_accept: new_accept.add(idx) for ch in alphabet: target dfa_trans.get((rep, ch)) if target is not None: new_trans[(idx, ch)] group_id[target] return start_group, new_trans, new_acceptrep选取的逻辑很简单组内所有状态对外行为等价取任意一个算转移目标再映射到新分组编号即可。这里要注意group_id[target]可能失败——如果dfa_trans缺失了某个字符的转移target是Nonegroup_id[None]会直接崩。所以做最小化之前我一般强制要求确定化输出补全死状态边哪怕是让缺失转移明确指向自己也比KeyError好排查。输出阶段用简单文本就行不用画图工具。打印状态编号、初态、终态、转移表三列再用一个模拟函数做验收测试。最小化后的状态数可以直接写进报告1(0|1)*101这个例子从8个状态压到5个报告里的表和代码输出能精确对上是平时作业加分的关键。5. 避坑三连程序跑通后我记住的五个教训5.1 闭包运算符优先级反了正则式含义被改现象输入(0|1)*生成的NFA里闭包只包住了1自动机接受的语言变成「0和1*的并」跟原题意完全不符。原因转后缀之前显式插入连接符.时没有考虑*作为一元后缀运算符的绑定关系(0|1)*被错误地拆成了(0|1)和*两个独立部分闭包挂到了最后的1上。解决插入连接符的扫描过程必须跳过紧跟在原子或右括号后面的*把*和它修饰的原子看作一个整体。从那以后我每次写完infix_to_postfix都会先用(0|1)*、a*|b这类边界式子做单元验证。5.2 ε-闭包漏了可达状态程序卡死或漏接受现象某些字符串明明应该被接受程序却在循环里出不来或者返回False。原因ε-闭包实现里漏了「自身状态已经在闭包集合里面继续扩展其ε后继」这一步导致ε环路绕回去之后没有出口。具体表现是队列里的状态重复入队或者集合缺少通过多级ε边才能到达的状态。解决闭包集合初始化就包含BFS的种子状态用visited集合同时承担「已访问」和「已入队」的判定不要在入队时才判重要在扩展时判重。5.3 最小化把终态和非终态并到了一组现象最小化后接受状态列表变成空或者出现一个既是终态又是非终态的分组验收时所有字符串都返回False。原因签名函数忘了把终态性放进元组。分组虽然初始划分时拆开了终态和非终态但后续拆分生成的子组可能既包含终态也包含非终态如果不检查终态性两个行为不同的状态会待在同一个分组里。解决签名结构改成(state in dfa_accept, tuple(...))并且每一轮循环重建分组后都检查一遍新分组内部是否混有不同终态性的状态。我在设计报告里把这个签名打印出来一眼就能看到分组依据。5.4 死状态没补边重建转移表时KeyError现象最小化重建阶段报KeyError崩在group_id[target]这一行。原因NFA转DFA时遇到空转移直接continue跳过死状态对应的字符行没有登记重建时查不到目标状态的分组编号。解决确定化循环里遇到空集合时统一指向一个死状态并在最后给死状态的每个字符补一条指向自己的边。具体做法是在nfa_to_dfa里加include_dead开关默认补全补全后状态表会多一行但最小化时死状态会被单独分一组不会影响终态的判断。5.5 三个程序各自编号报告和代码对不上现象报告里的状态图和程序输出的编号不一致复核时来回翻代码和文档费了半天劲才找到对应关系。原因三个程序各自用了独立的编号器——NFA按构造顺序编号DFA按子集生成顺序编号MFA按分组编号三张表之间没有对应关系。解决三个程序共用一个递增的编号器并且输出时把NFA状态号、DFA子集号、MFA分组号并排打在同一张表格里。这一列对照关系对完成作业描述和画图很有帮助我后来固定输出格式为每行一个状态依次列出NFA编号、DFA编号、MFA编号、是否终态、各字符转移目标这样写报告时直接抄表就行。6. 进阶把三段程序串成一条命令用 1(0|1)*101 做回归验收三连程序单独跑不难难的是串起来之后做回归验收。我给这套资源写过一个小的验收脚本输入正则式依次把三个程序的结果传给下一阶段最终用一组正负样例去测最小化后的MFA。具体做法是在最后一个阶段加一个simulate函数它接收MFA的状态表和起始状态逐个字符走转移最后判断是否停在终态上。注意这里模拟的是MFA本身不是把正则式拿去跑一遍匹配器两者不可混为一谈。def simulate(trans, start, accept, string): cur start for ch in string: nxt trans.get((cur, ch)) if nxt is None: return False cur nxt return cur in accept验收样例这么设置正样例100101、1101、11101都应当返回True负样例00、101、0101应当返回False。为什么101本身是负样例因为它缺了开头必需的1——正则式1(0|1)*101要求「开头是1中间有任意0/1串结尾是101」而101恰好是「结尾是101但没有开头1」的典型反例。这个细节如果不是拿完整字符串去验收很容易在报告里写错等价条件。另一个进阶技巧是输出转移表时顺便输出等价状态分组信息。最小化算法收敛后groups列表里每个分组就是一组等价状态把分组编号打印出来报告里最小化前后的状态对照表可以直接抄。我一般会同时在脚本里加一个「反例生成」的小函数对所有长度小于等于5的0/1串做穷举分别喂给正则式对应的NFA模拟器和MFA模拟器比对两者的接受结果一旦出现不一致就输出具体字符串作为调试线索。这样整条链路的正确性不再依赖肉眼检查而是交给穷举验证。从那以后我每次跑这类编译原理作业都强制走一遍「正负样例回归加三表编号对照」的流程把这一步变成肌肉记忆再也没出现过交上去的代码和报告对不上的情况。希望帮到你。本文还有配套的精品资源点击获取
