企业官网建设流程全解析

简介：这是一份面向编译原理课程设计或形式语言理论学习者的Python完整实现资源，围绕正则式转NFA、NFA确定化及DFA最小化三个核心流程展开，覆盖从状态定义、转移表构建到幂集构造与等价类合并的完整编码与报告说明，适合高校学生对照课程要求完成作业或深入理解自动机原理。资源包共9个文件，以3个Python源码文件为核心，分别对应正则式转NFA、NFA确定化、DFA最小化的分模块实现；另含3张PNG图片用于示意图或运行结果展示，2个Markdown文档提供实现思路与课程设计说明，并附带许可证文件，压缩包大小仅243KB，整体结构清晰、便于查阅。已有355人浏览学习，适合正在做编译原理作业、需要可运行示例或参考资料的学生使用。通过该资源可掌握NFA与DFA的构建细节、最小化算法的实际编码思路，并能直接复用代码进行扩展调试，对提升算法设计能力与编译原理实践水平有直接帮助。

1. 正则式转NFA、NFA确定化、DFA最小化：完整链路为什么值得手写一遍

正则表达式本身没有执行语义。它描述的是语言，而不是匹配算法；只有 NFA、DFA 这类自动机，才真正知道怎么逐字符消耗输入并判定受理状态。把a(b|c)*这样的模式拿去匹配字符串时，编译原理里那条「正则式转NFA → NFA确定化为DFA → DFA最小化」的链路，正是很多生产级正则引擎在编译期真正走的路线。这篇文章用纯 Python 完整实现整条链路：先构建带 ε 边的 NFA，再用子集构造法做确定化，最后用划分细化合并冗余状态。读完你可以拿到三个可验证的产物：NFA 状态图、DFA 转移表、最小化后的 DFA。熟悉 Python 但没手写过编译器的读者，也可以把这套实现当作词法分析器的最小样例来读。

2. 正则式转NFA：State类、调车场算法与Thompson构造的落地组合

正则式转 NFA 的常见做法有两条：对语法树做递归下降，或者先把中缀正则转成后缀表达式再统一拼装。我一般用后者。输入a(b|c)*，调车场算法会先补出显式连接符·，得到后缀形式a b c | · *。后缀的好处是每个运算符都对应一个明确的时机——从栈里弹一个或两个片段，再按 Thompson 构造的模板拼出新的 NFA 片段，全程不需要维护递归调用栈。

2.1 先把NFA数据结构定义清楚：一个状态一张转移表

NFA 本质是一张有向图，状态只做两件事：记唯一编号，记出边。出边要么带一个普通字符，要么带None表示 ε 边。使用邻接表而不是稠密二维表，是因为 ε 边和字符边在实际构建中都比较稀疏，遍历时只访问存在的边更高效。

class NFAState: """NFA状态：id用于调试输出，transitions保存全部出边。""" def __init__(self, sid): self.id = sid self.transitions = [] def add_edge(self, symbol, target): # symbol为None时表示ε边，否则是普通字符边 self.transitions.append((symbol, target)) class NFAFragment: """自动机片段：对外只暴露start与accept两个状态。""" def __init__(self, start, accept): self.start = start self.accept = accept class StateFactory: """全局状态编号生成器，保证打印自动机图时状态不重名。""" def __init__(self): self.counter = 0 def new_state(self): s = NFAState(self.counter) self.counter += 1 return s

NFAFragment是 Thompson 构造的核心抽象。拼接运算时只需要知道片段的入口和出口，内部结构全部封装起来，这样连接、选择、闭包都可以用统一的栈操作完成。NFAState没有自定义__eq__，所以默认按对象身份哈希，放进set或作为字典键都不会出错。

2.2 中缀转后缀：调车场算法让“|”和连接不再纠缠

手写递归下降解析器当然可行，但优先级关系会散落在多个parse_x()函数里，调试时反而难定位。调车场算法把优先级集中在一张表里，碰到运算符就按优先级弹栈，对后续 Thompson 拼接更直接。

def insert_concat_ops(pattern): """在相邻因子之间插入显式连接符·，让连接变成可见的二元运算。""" result = [] for i, ch in enumerate(pattern): result.append(ch) if i + 1 < len(pattern): nxt = pattern[i + 1] # 当前字符能结束一个因子，且后一个字符能开始一个因子时补连接符 if ch not in '(|' and nxt not in '|*+?)': result.append('·') return ''.join(result) def shunting_yard(pattern): """正则中缀转后缀，返回token列表。""" pattern = insert_concat_ops(pattern) prec = {'|': 1, '·': 2} out, ops = [], [] for ch in pattern: if ch in ('|', '·'): while ops and ops[-1] != '(' and prec[ops[-1]] >= prec[ch]: out.append(ops.pop()) ops.append(ch) elif ch == '(': ops.append(ch) elif ch == ')': while ops and ops[-1] != '(': out.append(ops.pop()) ops.pop() # 弹出左括号本身 elif ch in ('*', '+', '?'): out.append(ch) # 一元后缀运算符不参与中缀优先级比较 else: out.append(ch) # 普通字符直接输出 while ops: out.append(ops.pop()) return out

代码里的优先级只用在中缀二元运算符之间：

insert_concat_ops的边界条件要注意：(a|b)内部不能插入·，ab之间要插，a*不能插。上面ch not in '(|'和nxt not in '|*+?)'两个条件同时满足才插，覆盖了所有常见组合。

2.3 Thompson构造的四种运算符怎么拼NFA片段

拿到后缀表达式后，构建过程变成纯粹的栈运算。遇到字符就新建两个状态和一条字符边；遇到运算符就弹出对应数量的片段，按固定的 ε 边模板拼装。

def thompson_build(postfix, factory): """按后缀表达式逐个运算，栈里存的始终是NFAFragment。""" stack = [] for ch in postfix: if ch == '·': right, left = stack.pop(), stack.pop() # 连接：left出口接right入口，只需要一条ε边 left.accept.add_edge(None, right.start) stack.append(NFAFragment(left.start, right.accept)) elif ch == '|': right, left = stack.pop(), stack.pop() # 选择：新建公共入口和公共出口，两条ε边分别引入 s = factory.new_state() a = factory.new_state() s.add_edge(None, left.start) s.add_edge(None, right.start) left.accept.add_edge(None, a) right.accept.add_edge(None, a) stack.append(NFAFragment(s, a)) elif ch == '*': frag = stack.pop() # 闭包：允许跳过frag，也允许从内部回到入口重复执行 s = factory.new_state() a = factory.new_state() s.add_edge(None, frag.start) s.add_edge(None, a) frag.accept.add_edge(None, frag.start) frag.accept.add_edge(None, a) stack.append(NFAFragment(s, a)) elif ch == '+': frag = stack.pop() # e+等价于至少出现一次：不能跳过frag，但可以循环 s = factory.new_state() a = factory.new_state() s.add_edge(None, frag.start) frag.accept.add_edge(None, frag.start) frag.accept.add_edge(None, a) stack.append(NFAFragment(s, a)) elif ch == '?': frag = stack.pop() # e?等价于出现0次或1次：提供一条直接到公共出口的旁路 s = factory.new_state() a = factory.new_state() s.add_edge(None, frag.start) s.add_edge(None, a) frag.accept.add_edge(None, a) stack.append(NFAFragment(s, a)) else: # 普通字符：新建起止状态，连一条字符边 s = factory.new_state() a = factory.new_state() s.add_edge(ch, a) stack.append(NFAFragment(s, a)) return stack[0]

这段代码里，right, left = stack.pop(), stack.pop()的顺序不能反：后弹出的是左操作数。对于|和·而言顺序影响很大，尤其是连接运算，一但左右颠倒，整个自动机读到字符的顺序就反了。*、+、?都是单目操作，只弹一个片段，内部修改的是frag.accept这个状态的出边，所以能实现“回到起点”或“跳到出口”的回路。

2.4 为什么用后缀表达式而不是递归下降解析

递归下降更接近人的阅读直觉，但需要为每个优先级层次写一个函数，还要处理“连接”这种隐式运算。后缀表达式把两层问题分离：调车场算法负责解析，Thompson 构造只关心拼接。另一个实际原因是，后缀求值天然是左到右的线性扫描，方便在函数里加入状态计数或断点日志，排错时可以一行一行看栈里发生了什么。

这里有个容易踩的坑：同一个NFAFragment对象不能在同一时刻被复用两次。拼接运算会修改片段的accept出边，如果拿同一个片段去构建两个不同的父运算，后续调试会出现共享状态。常见写法是保证每个语法单位都新建独立片段。(a*)*这类嵌套不会出问题，因为内层*已经返回了新片段，外层*是在新片段上再包一层。

3. NFA确定化：子集构造法实现DFA转移表，别漏算ε-闭包

NFA 确定化的术语叫“子集构造法”，核心思想是：NFA 在某个时刻可能同时处于多个状态，DFA 的一个状态就代表一组 NFA 状态的集合。读入一个字符后，所有可能到达的状态合并成一个新集合，这个集合就是下一个 DFA 状态。关键点在于，任何一次跳转后都要补算 ε-闭包，因为 ε 边不消耗字符，但能改变当前活跃状态集合。

3.1 ε-闭包的计算：用栈实现，避免递归深度翻车

ε-闭包的定义是从一组状态出发，只沿着 ε 边就能到达的所有状态集合。实现时不建议写递归，因为自动机的 ε 环路很常见，比如a*的内部就有回边，递归容易栈溢出或无限循环。用显式栈做 BFS/DFS 更稳妥。

def epsilon_closure(nfa_states): """求一组NFA状态的ε-闭包：沿ε边能到达的所有状态都算进去。""" result = set(nfa_states) stack = list(nfa_states) while stack: state = stack.pop() for symbol, target in state.transitions: if symbol is None and target not in result: result.add(target) stack.append(target) return result def move(nfa_states, symbol): """返回从状态集合中经过一条symbol边到达的状态集合，不展开ε闭包。""" result = set() for state in nfa_states: for edge_symbol, target in state.transitions: if edge_symbol == symbol: result.add(target) return result

参数symbol必须是具体字符，而None表示 ε，所以move里用==比较不会误伤 ε 边。move不负责展开 ε 边，调用方必须手动补epsilon_closure。这个分工能让两个函数的职责单一，也便于单独测试。

3.2 转移表构建：frozenset当DFA状态键，天然去重

确定化的核心就是把“NFA状态集合”映射为“DFA状态编号”。Python 里最干净的做法是用frozenset作为字典键，因为集合是无序的，frozenset又是可哈希的，相同的状态集合只会对应同一个 DFA 状态。

def subset_construction(nfa, alphabet): """子集构造法：把NFA转换为DFA转移表。 返回： dfa_states list[frozenset[NFAState]] dfa_transitions list[dict[str, int]] dfa_start int dfa_accept set[int] """ start_set = frozenset(epsilon_closure([nfa.start])) dfa_states = [start_set] dfa_transitions = [{}] state_index = {start_set: 0} unprocessed = [start_set] dfa_accept = set() while unprocessed: current = unprocessed.pop() current_id = state_index[current] # 当前集合里只要包含原NFA的接受状态，这个DFA状态就是接受态 if nfa.accept in current: dfa_accept.add(current_id) for symbol in alphabet: nxt = frozenset(epsilon_closure(move(current, symbol))) if not nxt: continue if nxt not in state_index: state_index[nxt] = len(dfa_states) dfa_states.append(nxt) dfa_transitions.append({}) unprocessed.append(nxt) dfa_transitions[current_id][symbol] = state_index[nxt] return dfa_states, dfa_transitions, 0, dfa_accept

state_index就是从 NFA 状态集合到 DFA 编号的映射。出现新集合时分配一个新编号并加入工作列表，已存在的集合直接复用编号。nfa.accept in current这个判断用的是对象身份比较，前提是NFAState没有重写__eq__。如果自定义了相等比较，这里要改成any(st is nfa.accept for st in current)。

alphabet必须由调用方显式传入，而且要保证顺序稳定。我一般从正则表达式里提取所有非运算符字符，再排个序，这样多次运行生成的转移表列顺序一致。

3.3 缺失边与死状态：确定化之后需要明确的约定

自动机理论里 DFA 要求转移函数完全定义，但工程实现通常偷懒：没有可到达状态就不写这条边。两种做法各有取舍，本文代码采用“省略转移”策略，这样转移表更小，最小化时也把缺失边统一看作指向同一个虚拟死状态。

省略转移对匹配引擎没有影响：模拟 DFA 时遇到不存在的键直接返回False即可。但要注意，如果你要输出“完整”的 DFA 状态图给别人看，最好还是补一个死状态，否则图上每个非接受态都缺了若干出边，阅读者容易误解为缺陷。

4. DFA最小化：Moore划分细化算法及等价状态合并

DFA 最小化的目标是把行为完全一致的状态合并成一个。两个状态等价，必须满足两个条件：接受属性相同，并且对任意输入符号，它们转移到的目标状态也等价。这件事用“划分细化”做最直观：先假定所有状态归为一个大分区，再逐轮按签名拆分，直到没有状态被拆开。

4.1 等价状态的定义与初始划分：接受态与非接受态必须分开

初始划分必须至少区分接受态和非接受态，因为这两个集合的行为在“最终是否受理”上已经不同，不可能等价。以(a|b)*abb为例，确定化后得到 4 个 DFA 状态，编号为 0、1、2、3，其中 3 是接受态。初始划分是{0,1,2}与{3}。

后续每一轮迭代，都要检查同一分区内部每个状态在所有符号下的目标分区。目标分区不同，状态就要拆到新分区。整个过程如下：

迭代终止后，0 和 1 被合并成同一状态，整个自动机从 4 个状态缩到 3 个。

4.2 划分迭代：用转移签名判定状态是否继续拆散

实现划分细化时，我用“签名”来给状态分组：对某个状态，计算它分别在每个字符下到达的目标分区编号，组成一个元组。同一分区里签名相同的状态归入同一新分区，签名不同的必然拆开。

def minimize_dfa(dfa_transitions, alphabet, dfa_accept): """Moore划分细化：返回最终分区列表和state->分区映射。""" n = len(dfa_transitions) accept_set = set(dfa_accept) # 初始分区：非接受态在前，接受态在后 partitions = [] non_accept = [s for s in range(n) if s not in accept_set] accept_list = [s for s in range(n) if s in accept_set] if non_accept: partitions.append(frozenset(non_accept)) if accept_list: partitions.append(frozenset(accept_list)) state_to_part = {} for idx, part in enumerate(partitions): for s in part: state_to_part[s] = idx while True: new_partitions = [] new_state_to_part = {} for part in partitions: groups = {} for state in sorted(part): # 排序保证分区编号稳定 sig = tuple( state_to_part.get(dfa_transitions[state].get(sym), -1) for sym in alphabet ) groups.setdefault(sig, []).append(state) for group in groups.values(): g = frozenset(group) new_partitions.append(g) for s in g: new_state_to_part[s] = len(new_partitions) - 1 # 分区数量不再增加，说明没有任何状态被继续拆散 if len(new_partitions) == len(partitions): return partitions, state_to_part partitions = new_partitions state_to_part = new_state_to_part

签名里的-1对应缺失边。dfa_transitions[state].get(sym)返回None时，state_to_part.get(None, -1)得到-1，所有缺失边因此被视为转向同一个虚拟死状态。这个约定让省略转移的 DFA 也能正确参与最小化。

终止条件用“分区数量不变”已经足够：每一轮只会拆分区、不会合并分区，因此只要数量不变，就说明没有任何分区发生拆分，结果收敛。如果想控制迭代次数，可以在循环里加计数器，最多跑n轮。

4.3 从划分结果重建最小DFA转移表

得到分区后再重建最小 DFA 的转移表。每个分区对应一个新状态，转移表的目标指向目标状态所在的分区编号。

def rebuild_minimized_dfa(dfa_transitions, alphabet, start_index, dfa_accept): """用最小化分区结果重建DFA转移表。""" partitions, state_to_part = minimize_dfa(dfa_transitions, alphabet, dfa_accept) min_table = [] min_accept = set() for part in partitions: rep = min(part) # 取分区内最小编号做代表，输出稳定 table = {} for symbol in alphabet: target = dfa_transitions[rep].get(symbol) if target is not None: table[symbol] = state_to_part[target] min_table.append(table) if rep in dfa_accept: min_accept.add(len(min_table) - 1) return min_table, min_accept, state_to_part[start_index]

min(part)只是为了输出稳定，换成任意一个分区内状态都可以，因为同一分区内的状态已经被判定为等价，它们对每个符号的目标分区完全一致。起始状态的处理直接映射state_to_part[start_index]，新起始状态永远是包含起始状态的那个分区。

4.4 状态数大到什么程度才考虑Hopcroft优化

本文的划分细化实现复杂度大约是O(n^2 * |Σ|)，对几百个状态的 DFA 完全够用。课程设计和大部分编译原理作业里，NFA 状态数通常只有几十个，确定化后的 DFA 也很少超过几百，直接跑这个版本最快。只有当 DFA 状态数上万、重复迭代轮数过高时，才值得换成 Hopcroft 算法。Hopcroft 的精髓是维护一个待处理分区队列，每轮只处理涉及某个符号的分区，而不是扫描全部分区，能把平均复杂度降到接近O(n log n)。但它的实现容易出边界问题，我一般先用 Moore 版本验证正确性，再按需替换。

5. 用测试代码验证最小DFA与原始正则式的匹配一致性

整条链路做完后，验证逻辑其实很简单：同一段字符串分别喂给 NFA、确定化后的 DFA、最小化后的 DFA，三个结果必须完全一致。这个验证同时检验了确定化和最小化两个阶段有没有改变自动机接受的语言。

5.1 三个阶段的匹配结果对照

先写 NFA 和 DFA 的模拟函数，再写一个汇总测试入口。NFA 模拟每次读入字符后都要做一次 ε-闭包，DFA 模拟则是纯粹的查表。

def run_nfa(nfa, text): """在NFA上跑一段字符串，返回是否接受。""" states = epsilon_closure([nfa.start]) for ch in text: states = epsilon_closure(move(states, ch)) if not states: return False return nfa.accept in states def run_dfa(trans_table, start, accept_set, text): """在DFA转移表上跑字符串，缺失边直接返回False。""" state = start for ch in text: if ch not in trans_table[state]: return False state = trans_table[state][ch] return state in accept_set def test_chain(pattern, alphabet, samples): factory = StateFactory() postfix = shunting_yard(pattern) nfa = thompson_build(postfix, factory) dfa_states, dfa_table, dfa_start, dfa_accept = subset_construction(nfa, alphabet) min_table, min_accept, min_start = rebuild_minimized_dfa( dfa_table, alphabet, dfa_start, dfa_accept ) print(f"pattern={pattern} postfix={' '.join(postfix)}") print(f"NFA={factory.counter} states, DFA={len(dfa_states)} states, MIN={len(min_table)} states") for text in samples: r1 = run_nfa(nfa, text) r2 = run_dfa(dfa_table, dfa_start, dfa_accept, text) r3 = run_dfa(min_table, min_start, min_accept, text) ok = (r1 == r2 == r3) print(f" {text:>8} NFA={r1} DFA={r2} MIN={r3} 一致={ok}")

用两个典型模式做回归，一组是含闭包和选择的a(b|c)*，一组是经典练手题(a|b)*abb：

第二个模式的状态数变化很直观：NFA 8 个状态，确定化为 4 个 DFA 状态，最小化后剩 3 个。如果这三处模拟结果出现不一致，优先检查确定化阶段的 ε-闭包是否漏算，其次检查最小化的初始分区是否误把接受态和非接受态放在了一起。

5.2 典型踩坑：把转移表打印出来对状态名

排错时不要只在布尔结果里打转，直接把三张转移表结构化打印出来。给每个 NFA 状态的出边按编号排序，输出的行会更容易比对。我常用的一行调试是print(nfa.accept.id, [(st.id, [(s, t.id) for s, t in st.transitions]) for st in all_states])。习惯上我会给状态编号留出间隔，方便中间插入新状态，但这段实现里StateFactory自增计数器已经保证唯一性，不需要预留。

5.3 最小结果如何落盘复用

最小 DFA 已经是一张纯粹的表：状态编号、字符到目标编号的字典、接受状态集合。它可以直接序列化为 JSON，在编译型项目的构建阶段生成一次，运行时加载，避免每次启动都重复做正则式转 NFA、确定化、最小化三件事。比如把min_table和接受集合写成{"trans": [[{"a": 1}], [{"b": 2}]], "accept": [2], "start": 0}，加载时逐行还原成原来的字典结构即可。这个缓存策略对词汇表数量很大的词法分析器收益明显，一次最小化省掉的是整个编译前端的重复工作。

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