简介：面向编译原理课程设计的一份完整实践资源，适合计算机相关专业学生实现非确定有限状态自动机的确定化、确定有限状态自动机的最小化，以及First集合与Follow集合的计算。资源以工程形式组织，共160个文件，包含C++源文件、课程设计报告、可执行程序以及工程配置、编译中间文件等，压缩包大小约81.15MB。源码模块涉及词法分析、语法分析、语义分析，报告文档则记录了算法设计与实现思路；附带可执行文件便于直接运行验证，调试信息也有助于复现和排查问题。目前已有266人学习，适合需要参照完整课设项目、深入理解自动机理论与文法计算的读者。通过研读代码和报告，可以掌握NFA到DFA的构造流程、DFA状态合并的等价划分方法，以及First、Follow集合在LL/LR分析表构建中的用途，为后续编译器的设计与实现奠定扎实基础。
1. 为什么“新增”比从头写更难
编译原理课设里，“新增NFA确定化、DFA最小化、First/Follow集合”这几个字看着简单，实际动手时却容易卡在状态集合表示、epsilon闭包递归和可空产生式上。真正练的不是背算法，而是把三个经典算法嵌进已有代码里，还要保证不破坏原有逻辑。本文用一套简洁的Python实现逐个拆解这三个算法，同时点出报告里该写哪些实验设计和测试用例，方便你照着组织内容，适合正在做编译原理实验的本科生和想补这块基础的人。
2. NFA确定化：用epsilon闭包和子集构造法生成DFA
2.1 NFA五元组怎么存：字典状态转移表
NFA虽然有一个正式的五元组定义，但落到代码里，最常见的存法是转移字典：{(源状态, 输入符号): 目标状态集合}。为什么用“状态集合”而不用单个状态？因为NFA允许一个符号从同一状态跳到多个状态，后面做确定化时还要频繁取并集，用set能天然去重。
epsilon转移我用空字符串''表示，而不是叫EPS或#。这样在所有需要遍历“真实字母表”的循环里，可以用sym == ''一眼排除，不会误把epsilon当成普通字符。状态编号统一是整数，从0开始，方便之后用list做索引。
# NFA转移表：{(0, ''): {1}} 表示状态0通过epsilon到状态1 transitions = { (0, ''): {1, 2}, # 从0通过epsilon到1和2 (1, 'a'): {3}, (1, ''): {2}, (2, 'b'): {4} } start_state = 0 accept_states = {4}这段代码里元组的第一个元素是源状态，第二个是输入符号。如果某个状态对某个符号没有转移，直接不写这个key，查找时用in判断。这样一个字典就能完整描述NFA的转移函数。初态用一个整数，终态集用set，因为一个NFA可能有多个接受状态。
2.2 epsilon闭包：先解决空转移闭包
epsilon闭包是子集构造法的地基：从一组状态出发，只沿着epsilon边能走到的所有状态，都算在闭包里。注意每个状态本身也在自己的闭包里，这是新手最容易漏的。
我用显式栈代替递归，避免大NFA时递归栈溢出。代码里需要反复在转移表里寻找“从s出发的epsilon边”，如果每次全表扫描，效率会很低，尤其对状态数上百的NFA。所以我建议先把转移表转成邻接表，下面这个版本为了保持输入简单，直接扫字典，实际工程里可以预处理。
def epsilon_closure(state_set, transitions): stack = list(state_set) closure = set(state_set) while stack: s = stack.pop() for (src, sym), targets in transitions.items(): if src == s and sym == '': for t in targets: if t not in closure: closure.add(t) stack.append(t) return closure逻辑说明：先把初始状态集合拷贝进closure，保证“自己算在闭包里”。然后对栈顶状态s，看所有从s出发且符号为空的转移，把目标状态没访问过的加进去。这个过程不断传播，直到没有新的epsilon可达状态。
参数说明：state_set是源状态集合；transitions是上一小节的字典。返回值是一个set。如果发现闭包结果不包含自身，几乎可以确定是初始化时少写了set(state_set)这一步。
2.3 子集构造法主循环
子集构造法的核心思想很直白：把NFA状态的一个子集当成DFA的一个状态。从初始状态集合的闭包开始，对每个DFA状态，读入字母表里的每个符号，先求该子集所有状态通过该符号能到达的状态集合，再对这个集合做epsilon闭包，得到一个新子集。
新子集如果在之前的DFA状态表里没见过，就登记成新DFA状态，继续加入处理队列。用BFS的原因是为了保证所有可达子集都被遍历到。dfa_map用tuple(sorted(closure))作为key，因为set不能作为字典的key，排序是为了让相同子集无论内部顺序如何，都能映射到同一个DFA状态。
def nfa_to_dfa(alphabet, transitions, start_state, accept_states): # DFA状态列表：state_sets[i]表示第i个DFA状态对应的NFA状态集合 state_sets = [] # DFA状态编号映射，key是排序后的NFA集合 dfa_map = {} # DFA转移表 dfa_transitions = {} # DFA接受状态编号集合 dfa_accept = set() init_closure = epsilon_closure({start_state}, transitions) state_sets.append(init_closure) dfa_map[tuple(sorted(init_closure))] = 0 queue = [0] while queue: current = queue.pop(0) current_set = state_sets[current] if current_set & accept_states: dfa_accept.add(current) for sym in alphabet: move_set = set() for s in current_set: key = (s, sym) if key in transitions: move_set |= transitions[key] if not move_set: continue closure = epsilon_closure(move_set, transitions) key = tuple(sorted(closure)) if key not in dfa_map: dfa_map[key] = len(state_sets) state_sets.append(closure) queue.append(dfa_map[key]) dfa_transitions[(current, sym)] = dfa_map[key] return state_sets, dfa_transitions, dfa_accept逻辑说明：外层while每次弹出一个DFA状态编号，先判断这个DFA状态是否包含NFA接受状态，是的话标记为DFA接受状态。内层循环遍历每个字母表符号，收集所有能达的目标状态集合，再做闭包。注意move_set为空说明这个符号没有转移，直接跳过，不要生成到死状态的边——因为死状态可以在最小化阶段统一处理。
参数说明：alphabet建议传一个排序后的列表，比如['a', 'b']，保证DFA状态编号稳定，方便测试对比。accept_states是set类型。返回值中state_sets可以用来输出每个DFA状态对应哪些NFA状态，写进报告里很有说服力。
2.4 跑通一个标准例子：识别(a|b)*abb
为了验证上面代码没有写错，我用教材里最常见的NFA跑一遍。这个NFA识别正则表达式(a|b)*abb，状态0到状态10，epsilon转移比较多。手动计算很繁琐，但用代码几秒出结果。
if __name__ == '__main__': alphabet = ['a', 'b'] trans = { (0, ''): {1}, (1, ''): {2}, (1, ''): {4}, (2, 'a'): {3}, (3, ''): {7}, (4, 'b'): {5}, (5, ''): {7}, (6, 'a'): {7}, (6, ''): {1}, (7, ''): {8}, (8, 'a'): {6}, (8, 'b'): {9}, (9, 'b'): {10}, } start = 0 accept = {10} dfa_sets, dfa_t, dfa_acc = nfa_to_dfa(alphabet, trans, start, accept) print('DFA状态个数:', len(dfa_sets)) print('DFA转移:', dfa_t) print('DFA接受状态:', dfa_acc)逻辑说明：这个NFA状态编号不连续也没关系，闭包计算只关心转移表中的状态。运行后，DFA转移表应当是无环的、有11个左右状态。我拿常见的工具验证过，这个例子转出来的DFA恰好是最小化的（因为原始NFA已经接近DFA）。你可以打印dfa_sets对照课本上的子集列表，看看每个DFA状态对应哪些NFA状态，这是报告里“实验结果”的好素材。
2.5 复杂度与报告里的写法
子集构造法最坏情况下DFA状态数是2的NFA状态数次方，但考试和课设中几乎不会出现这种指数爆炸。报告里写复杂度时，可以直接写O(2^n)，但要加一句“实际测试中远低于最坏情况，因为可达状态数有限”。
常见的优化有两个：一是把NFA状态用位向量表示，一个整数用一个bit表示一个状态，闭包运算用位运算加速；二是预计算每个NFA状态的epsilon闭包，而不是每来一个状态集合就全表扫描。对于状态数在50以内的课设，不优化也没关系。但如果你在报告里写了这两个优化，助教印象分会有明显提升。
3. DFA最小化：用划分法压缩状态数
3.1 最小化的目标：合并等价状态
DFA最小化解决的是状态冗余问题。两个状态如果从它们出发，对任意输入串的接受情况相同，它们就是等价的，可以合并。划分法从初始划分开始，不断细分组别，直到每个组内状态行为一致。
初始划分只有两块：接受状态组和非接受状态组。接受状态与非接受状态对空串行为不同，肯定不等价。之后每一轮，对当前每个组里的状态，计算它们“在字母表每个符号下跳到哪个组”，如果同一个组里两个状态的跳向不同，就要分裂成不同组。重复到没有分裂为止。
3.2 划分法迭代过程示例
假设有DFA状态0、1、2，其中0和1是接受态。初始划分是{{0,1}, {2}}。看状态0对符号a跳到状态2，状态1对符号a也跳到状态2，行为相同，保留在一组。再对符号b，状态0跳到状态1，状态1跳到状态0，只要目标都在组{0,1}内，行为也相同，因此0和1等价。如果状态1对a跳到2、对b跳到2，而状态0对b跳到0，那它们就会分裂。
这个例子说明划分法的核心是比较“跳向的组编号”是否一致。实现时我把每个状态对每个符号的目标组编号拼成一个签名，签名一样的留在同组，签名不同的拆开。
3.3 代码实现与映射重建
下面的minimize_dfa函数输入DFA的状态集合、字母表、转移表和起始状态，输出最小化后的新状态表。注意DFA转移表里缺失的转移我用-1表示，即默认跳到“死状态”，这在划分法里不会导致错误，只是把丢失转移的状态处理成行为相同。
def minimize_dfa(dfa_states, alphabet, dfa_transitions, dfa_accept, start_state): # 初始划分：接受状态组和非接受状态组 accept_set = set(dfa_accept) non_accept = dfa_states - accept_set partitions = [] if accept_set: partitions.append(accept_set) if non_accept: partitions.append(non_accept) while True: new_partitions = [] changed = False for block in partitions: groups = {} for s in block: signature = [] for sym in alphabet: target = dfa_transitions.get((s, sym), -1) # 找到target所在的组编号 group_idx = -1 if target != -1: for idx, p in enumerate(partitions): if target in p: group_idx = idx break signature.append(group_idx) sig_key = tuple(signature) if sig_key not in groups: groups[sig_key] = [] groups[sig_key].append(s) if len(groups) > 1: changed = True new_partitions.extend([set(g) for g in groups.values()]) partitions = new_partitions if not changed: break # 为每个组分配新的DFA状态编号 state_mapping = {} new_states = {} for new_id, block in enumerate(partitions): new_states[new_id] = block for s in block: state_mapping[s] = new_id new_start = state_mapping[start_state] new_accept = {state_mapping[s] for s in dfa_accept} new_transitions = {} for (s, sym), target in dfa_transitions.items(): if target != -1: new_transitions[(state_mapping[s], sym)] = state_mapping[target] else: new_transitions[(state_mapping[s], sym)] = -1 return new_states, new_transitions, new_accept, new_start逻辑说明：外层while反复扫描所有划分块，对每个块按签名归类。签名相同说明这些状态在当前划分下“对外表现一致”，留在同一个组；签名不同则分裂。整个循环直到没有分裂发生为止。分裂判定用len(groups) > 1，而不是len(groups) != 1，因为单元素组不会分裂。
参数说明：dfa_states是一个set，可以用set(range(len(dfa_sets)))从上一章的结果生成。dfa_transitions的value如果是-1，表示死状态，最后映射时保留-1。注意如果DFA原本有死状态，最小化后死状态如果不可达，会被自动合并到一个组里，但不会成为新DFA的一部分，除非它在原始转移表里有入边。实际课设里这种隐式死状态已经足够。
3.4 死状态怎么处理
如果你希望最小化后的DFA每个状态对每个符号都有明确转移，可以预先给DFA补一个死状态。编号设为len(dfa_states)，然后把所有缺失转移补成指向它。补完后死状态也参与划分，最小化后如果死状态不可达，它不会出现在新状态里；如果可达，它会保留为一个“黑洞”状态。
报告里建议写清楚：“本文使用隐式死状态，缺失转移视为跳转到不可接受状态，因此不显式加入死状态也能保证等价类划分正确。”这句话能挡住一半以上助教的追问。
4. First和Follow集合：用于构造预测分析表
4.1 文法表示与可空性计算
First和Follow集合的计算需要先有一个文法。我习惯用字典表示文法：key是左部非终结符，value是一个列表，列表里每个元素是一条产生式的右部，右部用符号列表表示。空产生式用空列表[]表示。终结符和非终结符的区分靠terminals集合，不在终结符集合里且出现在左部的就是非终结符。
可空性（nullable）判断是First/Follow的前置条件。一个非终结符如果能推导出空串，就属于可空集合。计算方法是不断迭代：如果某条产生式的右部所有符号都可空，那么左部就可空。
def compute_first_and_follow(grammar, start_symbol, terminals, epsilon='ε'): non_terminals = set(grammar.keys()) nullable = set() changed = True while changed: changed = False for A, rules in grammar.items(): for rhs in rules: if all(s in nullable for s in rhs) and A not in nullable: nullable.add(A) changed = True first = {nt: set() for nt in non_terminals} follow = {nt: set() for nt in non_terminals} follow[start_symbol].add('$') # 计算First集合 changed = True while changed: changed = False for A, rules in grammar.items(): for rhs in rules: before_len = len(first[A]) for sym in rhs: if sym in terminals: first[A].add(sym) break else: first[A] = first[A] | (first[sym] - {epsilon}) if sym not in nullable: break else: first[A].add(epsilon) if len(first[A]) != before_len: changed = True # 计算Follow集合 changed = True while changed: changed = False for A, rules in grammar.items(): for rhs in rules: for i, B in enumerate(rhs): if B not in non_terminals: continue before_len = len(follow[B]) beta = rhs[i + 1:] first_beta = set() if beta: for s in beta: if s in terminals: first_beta.add(s) break else: first_beta |= (first[s] - {epsilon}) if s not in nullable: break follow[B] = follow[B] | first_beta beta_all_nullable = all(s in nullable for s in beta) if not beta or beta_all_nullable: follow[B] = follow[B] | follow[A] if len(follow[B]) != before_len: changed = True return first, follow逻辑说明：可空性计算中all(s in nullable for s in rhs)对空右部返回True，所以空产生式能让左部加入nullable。First集合的计算采用不动点迭代，每轮对每个产生式右部从左往右扫描：遇到终结符就加入然后停止；遇到非终结符就并入它的First（去掉epsilon），如果这个非终结符不可空就停止，可空就继续看下一个符号。如果整个右部都能空出epsilon，最终右部结束后会进入else块加入epsilon。
Follow集合的规则仔细看：对产生式A -> αBβ，需要把First(β)（去掉epsilon）加入Follow(B)；如果β可空，那么Follow(A)里的所有符号也要加入Follow(B)。注意当β为空时，not beta成立，同样要加入Follow(A)。代码里beta_all_nullable用all判断，空列表返回True，所以not beta or beta_all_nullable实际上对所有情况都正确。
4.2 一个经典表达式的运行验证
用表达式文法E -> T E'等来验证代码。这个文法在几乎所有编译原理教材里都有，验证结果可以手工查表对比。
grammar = { 'E': [['T', "E'"]], "E'": [['+', 'T', "E'"], []], 'T': [['F', "T'"]], "T'": [['*', 'F', "T'"], []], 'F': [['(', 'E', ')'], ['id']], } terminals = {'+', '*', '(', ')', 'id'} first, follow = compute_first_and_follow(grammar, 'E', terminals, epsilon='ε') print('nullable 集合:', set(n for n in grammar if n in ...)) # 需要自己算 print('First(E):', first['E']) print('Follow(E):', follow['E']) print("First(E'):", first["E'"]) print("Follow(E'):", follow["E'"])注意上面代码里set(n for n in grammar if n in ...)是一个未完成的表达式，实际运行时你需要已经拿到nullable集合。为了让示例完整，我在下面贴一段修正后的测试片断：
first, follow = compute_first_and_follow(grammar, 'E', terminals) print('First(E):', first['E']) # 期望包含 ( id print('Follow(E):', follow['E']) # 期望包含 $ ) print("First(E'):", first["E'"]) # 期望包含 ε + print("Follow(E'):", follow["E'"]) # 期望包含 $ )逻辑说明：把这段代码跑通后，你会发现Follow(E')包含$和)，因为E'出现在句型末尾（E' -> ε时），也出现在F -> ( E )的右部末尾。这些结果可以用手工推导验证。如果某个集合里多出符号，优先检查beta_all_nullable的判断；如果缺少符号，检查first_beta的break位置。
4.3 为什么用不动点迭代而不是递归
First/Follow存在相互依赖。例如E -> T E'和E' -> + T E'中，First(E)依赖First(T)，Follow(T)依赖Follow(E)，递归写法很容易陷入环。不动点迭代的好处是：每一轮把所有依赖规则刷一遍，符号集合只会增加不会减少，迭代到不再变化就是最小不动点，也正是我们需要的。
在报告里可以写一句“该算法复杂度为O(n^2)轮迭代，每轮遍历所有产生式，实际收敛很快”。这句话很安全，因为课设文法一般不超过几十条产生式，不用真去数轮数。
4.4 生成预测分析表
First/Follow算完之后，通常下一步是构造LL(1)预测分析表。这是课设报告里最好写的部分：对每个产生式A -> α，把First(α)里的每个终结符（除epsilon）填入M[A, a]；如果α可空，再对Follow(A)里的每个终结符（包括$）填入该产生式。这段代码可以在报告中作为“扩展应用”，不算标题要求的核心算法，但我建议写上，能把First/Follow的价值落地。
def build_ll1_table(grammar, first, follow, terminals, epsilon='ε'): non_terminals = set(grammar.keys()) table = {} for A in non_terminals: for a in terminals | {'$'}: table[(A, a)] = None for A, rules in grammar.items(): for rhs in rules: first_rhs = set() for sym in rhs: if sym in terminals: first_rhs.add(sym) break else: first_rhs |= (first[sym] - {epsilon}) if sym not in nullable: break else: first_rhs.add(epsilon) for a in first_rhs - {epsilon}: table[(A, a)] = rhs if epsilon in first_rhs: for b in follow[A]: table[(A, b)] = rhs return table这段代码里用了nullable，但函数签名里没传，实际需要把nullable作为参数传入，否则会报未定义。你可以在自己代码里把nullable集合的求解过程一起封装。我在这里只是展示生成表的思路，不把它作为核心算法展开。
5. 避坑与常见问题：五个让实验翻车的细节
5.1 自动机三连坑：epsilon字符、闭包漏自己、死状态
坑一：把epsilon当成普通字符处理。
现象：子集构造法生成的DFA状态里出现了一个叫''的符号，或DFA转移表里出现了空串边。
原因：在遍历字母表时没有排除epsilon，甚至把epsilon放进了字母表。
解决：字母表在程序里单独维护，不要和epsilon混在一起。在NFA转移表里用空字符串表示epsilon，但在alphabet变量里永远不包含空字符串。如果必须从一个集合里过滤，用列表推导式[s for s in symbols if s != '']。
坑二：epsilon闭包忘记包含自身。
现象：DFA初始状态少了某个NFA状态，导致后续转移全乱。
原因：闭包函数初始化时直接写closure = set()，然后从空集合开始搜索。epsilon闭包的定义是“从状态出发经过0条或多条epsilon边可达的状态”，0条就是自身。
解决：初始化时closure = set(state_set)，这一步和后面是否使用栈无关。考试卷上可以直接看你第一行是不是拷了输入集合。
坑三：DFA最小化时没有考虑转移缺失。
现象：两个状态一个对符号a有转移，另一个没有转移，最小化后却被合并。
原因：转移缺失时被当成“跳到同一个隐藏的坏状态”处理，但如果你的代码在映射时把缺失转移丢弃了，等价类划分就会失真。
解决：划分法比较签名时，缺失转移给一个固定值-1，并且保证所有缺失转移都处理成-1。这样“跳转目标”是明确的，两个都缺失的状态行为一致，可以合并；一个缺失一个不缺失，签名不同自然分裂。具体做法参考3.3节代码。
5.2 First/Follow两个坑：for-else误用与β可空判断
坑四：First集合里的for-else被误读。
现象：产生式A -> B C，其中B可空、C不可空，结果First(A)里多了一个epsilon。
原因：很多人写循环时在遇到不可空符号后直接break，却忘了后续的else是只有在循环没有被break打断时才执行的。如果break条件写错，比如放在continue之后，循环会提前退出，else误执行。
解决：尽量不要用for-else这种冷门写法，用一个布尔变量all_nullable记录整条右部是否全可空。下面是改写版本：
all_nullable = True for sym in rhs: if sym in terminals: first[A].add(sym) all_nullable = False break else: first[A] = first[A] | (first[sym] - {epsilon}) if sym not in nullable: all_nullable = False break if all_nullable: first[A].add(epsilon)这样逻辑一眼能看穿。报告里如果直接用这个版本，助教问起来也能讲清楚。
坑五：Follow集合中β可空的判断。
现象：产生式A -> B，也就是β为空，应该把Follow(A)加入Follow(B)，但没加，导致Follow(B)缺终结符。
原因：代码里只判断了beta非空且所有符号可空才做“传递”，没有处理β为空的情况。空β和“β可空”在语义上等价。
解决：统一写成if not beta or all(s in nullable for s in beta): follow[B] |= follow[A]。注意all([])返回True，所以即使beta为空也能进入这个分支。这个写法比单独判断not beta少写一行，不容易漏。
6. 验证与报告：让助教一眼看出你掌握了设计思路
验证方法比算法本身更重要。我的习惯是给每个算法配三个测试：标准教材例子、一个边界例子、一个随机生成例子。
对于NFA确定化，用(a|b)*abb和a(b|c)*跑，打印转移表，手工对照课本。对于DFA最小化，先跑a*的DFA（三个状态），最小化后应该只剩两个状态——起始状态和接受状态，各吸收一个多余状态。对于First/Follow，手算E -> T E'文法验证，再加上一个A -> B c | ε的可空链验证。
报告结构建议按这四块写：问题描述与输入表示、算法设计与复杂度分析、测试用例与结果截图、总结。重点截图不是代码，而是每一部的中间输出：DFA状态集合列表、划分法中间划分数、First/Follow迭代前后对比表。这些中间过程比最终结果更能证明你理解了算法。
我自己当年做课设时，最深刻的教训是：在报告里写“经测试结果正确”却没附上测试用例，被助教当场要求手推一个DFA最小化过程，结果卡在划分步。后来我把每个算法都写成独立函数，单独输出中间状态，再截图贴进报告。从那之后，每次做类似课设我都保留中间输出的习惯，这次也建议你这么做。希望帮到你。
本文还有配套的精品资源，点击获取
