编译原理课设最小可行实验链：NFA到LL(1)全程可调试实现

简介本资源为高校《编译原理》课程设计实践项目面向计算机专业本科生及编译技术初学者聚焦词法与语法分析核心算法的工程实现。完整覆盖NFA确定化、DFA最小化、First/Follow集合计算三大关键环节配套详细实验报告与代码工程助力理论理解与动手能力同步提升。压缩包共160个文件含7个docx格式报告与总结文档、7个cpp/h源码文件、13个可执行exe程序及大量VS编译中间产物如tlog、pdb、vcxproj等整体81.15MB结构体现完整Visual Studio项目组织方式便于调试复现与模块化学习。已有266人下载学习资源包含可直接运行的多阶段分析程序如lexical.cpp、语法分析.cpp、语义分析.cpp、工程配置文件sln/filters及原始课设报告支持从算法推导、代码实现到结果验证的全流程闭环实践。1. 这不是抄作业的课设它是一套能跑通、能调试、能讲清原理的编译原理最小可行实验链你手头那份“编译原理课设”文档里写着“新增NFA确定化、DFA最小化以及First、Follow集合的实现”但真正卡住你的往往不是算法本身而是——为什么手动画完NFA后用Python跑出来的DFA状态数比课本例题多3个为什么Follow集算出来总漏掉#输入结束符导致后续LL(1)分析表填不满为什么DFA最小化后状态合并了但状态转移图反而看不懂了这不是理论推导题而是一条可验证、可断点、可反向追踪的实验链从正则表达式 → NFAThompson构造→ 子集构造法确定化 → Hopcroft或Hopcroft-like最小化 → 文法分析 → First/Follow计算 → LL(1)可行性验证。每一步都必须输出中间结构状态集、转移表、集合列表且能用文本/ASCII图直观比对。适合两类人一是刚学完《编译原理》第二章、第三章想把“抽象自动机”变成终端里可print()的对象二是带实验课的助教需要一套不依赖GUI、不绑定特定IDE、命令行即可复现、学生能逐行调试的参考实现。它不追求图形界面炫酷但要求每个函数返回值可断点、每个集合可pprint、每个状态名可溯源——这才是课设该有的工程感而不是交一份PDF报告就结束。2. 从正则到NFA用Thompson构造法生成可序列化的NFA结构2.1 Thompson构造的核心逻辑与状态命名规则Thompson构造法的本质是递归组合把正则表达式按运算符|、·、*拆解为每个子表达式分配唯一ID的状态块再用ε-转移桥接。关键不在“画图”而在状态ID的可追溯性——不能用id()或随机数必须用(expr_id, local_state_id)元组命名例如r a|b的左支a对应状态(0,0)→(0,1)右支b对应(1,0)→(1,1)根节点起始态为(start)接受态为(accept)r (ab)*中ab子块状态为(0,0)→(0,1)→(0,2)其闭包会引入新状态(0,-1)新起始和(0,-2)新接受并用ε转移到原起始和接受态。这样命名后续确定化时才能准确还原“哪个子表达式贡献了哪些状态”。2.2 Python实现NFA类与构造函数from typing import Dict, Set, Tuple, List, Optional import re class NFA: def __init__(self, states: Set[str], alphabet: Set[str], transitions: Dict[Tuple[str, str], Set[str]], start_state: str, accept_states: Set[str]): self.states states self.alphabet alphabet self.transitions transitions # (state, symbol) - {next_states} self.start_state start_state self.accept_states accept_states def thompson(regex: str) - NFA: # 预处理括号匹配、运算符优先级* · |这里简化为支持基础操作 # 实际课设中建议用递归下降解析器而非eval或正则直接替换 stack [] state_counter 0 def new_state() - str: nonlocal state_counter s fq{state_counter} state_counter 1 return s # 处理单字符a → q0 --a-- q1 def char_nfa(c: str) - NFA: s0, s1 new_state(), new_state() trans {(s0, c): {s1}} return NFA({s0, s1}, {c}, trans, s0, {s1}) # 处理 a|b引入新起始q_start、新接受q_acceptε转到a/b的起始和接受 def union_nfa(nfa_a: NFA, nfa_b: NFA) - NFA: s_start new_state() s_accept new_state() # 合并所有状态 states nfa_a.states | nfa_b.states | {s_start, s_accept} alphabet nfa_a.alphabet | nfa_b.alphabet trans nfa_a.transitions.copy() trans.update(nfa_b.transitions) # ε转移q_start → a_start, q_start → b_start eps trans[(s_start, eps)] {nfa_a.start_state, nfa_b.start_state} # a_accept → q_accept, b_accept → q_accept for acc in nfa_a.accept_states | nfa_b.accept_states: if (acc, eps) not in trans: trans[(acc, eps)] set() trans[(acc, eps)].add(s_accept) return NFA(states, alphabet, trans, s_start, {s_accept}) # 处理 aba_accept → b_startε转移 def concat_nfa(nfa_a: NFA, nfa_b: NFA) - NFA: states nfa_a.states | nfa_b.states alphabet nfa_a.alphabet | nfa_b.alphabet trans nfa_a.transitions.copy() trans.update(nfa_b.transitions) # a的接受态ε连到b的起始态 for acc in nfa_a.accept_states: if (acc, ) not in trans: trans[(acc, )] set() trans[(acc, )].add(nfa_b.start_state) return NFA(states, alphabet, trans, nfa_a.start_state, nfa_b.accept_states) # 处理 a*新起始q_s新接受q_eq_s→q_eεq_s→a_startεa_accept→q_eεa_accept→a_startε def star_nfa(nfa_a: NFA) - NFA: s_start new_state() s_accept new_state() states nfa_a.states | {s_start, s_accept} alphabet nfa_a.alphabet trans nfa_a.transitions.copy() # ε: s_start → s_accept (空串) if (s_start, ) not in trans: trans[(s_start, )] set() trans[(s_start, )].add(s_accept) # ε: s_start → a_start trans[(s_start, )].add(nfa_a.start_state) # ε: a_accept → s_accept for acc in nfa_a.accept_states: if (acc, ) not in trans: trans[(acc, )] set() trans[(acc, )].add(s_accept) # ε: a_accept → a_start (自环) for acc in nfa_a.accept_states: trans[(acc, )].add(nfa_a.start_state) return NFA(states, alphabet, trans, s_start, {s_accept}) # 词法分析简单分割实际应构建AST tokens tokenize_regex(regex) return parse_tokens(tokens) def tokenize_regex(regex: str) - List[str]: # 简化版只处理 a, b, (ab), a|b, a*, (a|b)* 等 # 生产环境必须用lexerparser此处为课设最小可行 regex regex.replace( , ) tokens [] i 0 while i len(regex): if regex[i] (: # 找匹配右括号 j i 1 depth 1 while j len(regex) and depth 0: if regex[j] (: depth 1 elif regex[j] ): depth - 1 j 1 if depth 0: tokens.append(regex[i:j]) i j else: raise ValueError(Unmatched parenthesis) elif regex[i] in ab0123456789: tokens.append(regex[i]) i 1 elif regex[i] in |*: tokens.append(regex[i]) i 1 return tokens def parse_tokens(tokens: List[str]) - NFA: # 仅支持左结合、无优先级需加括号明确如 a|b*c 要写成 a|(b*)c if not tokens: return empty_nfa() # 构建栈操作数栈 操作符栈简化为二叉树 stack [] i 0 while i len(tokens): t tokens[i] if t | or t *: if t *: if not stack: raise ValueError(Unary * needs operand) nfa stack.pop() stack.append(star_nfa(nfa)) elif t |: if len(stack) 2: raise ValueError(Binary | needs two operands) nfa2 stack.pop() nfa1 stack.pop() stack.append(union_nfa(nfa1, nfa2)) else: if t.startswith(() and t.endswith()): inner t[1:-1] sub_nfa thompson(inner) stack.append(sub_nfa) else: stack.append(char_nfa(t)) i 1 if len(stack) ! 1: raise ValueError(Invalid regex format) return stack[0] def empty_nfa() - NFA: s0 q0 return NFA({s0}, set(), {}, s0, {s0})提示此代码不追求语法完备性但保证每个NFA对象的transitions字典键为(state, symbol)元组值为set且ε转移用空字符串表示——这是后续ε-closure计算的基础。若用字符串拼接代替元组命名如q0_q1确定化时将无法区分不同子表达式的同名状态这是课设最常翻车的第一步。3. NFA确定化子集构造法的三步落地与ε-closure精确实现3.1 ε-closure必须是迭代闭包不是单次扫描很多课设实现把ε-closure写成“找所有ε直达状态”漏掉传递性。例如q0 --ε-- q1 --ε-- q2单次扫描只得到{q0,q1}漏掉q2。正确做法是队列BFSdef epsilon_closure(nfa: NFA, states: Set[str]) - Set[str]: closure set(states) queue list(states) # 用list模拟queue避免导入deque while queue: state queue.pop(0) # 查所有从state出发的ε转移 for next_state in nfa.transitions.get((state, ), set()): if next_state not in closure: closure.add(next_state) queue.append(next_state) return closure这个函数必须被调用至少两次一次在确定化初始状态ε-closure({nfa.start_state})一次在每次状态转移后对每个输入符号先求move(T, a)再对其结果求ε-closure。3.2 子集构造主循环用frozenset作状态名避免可变集合报错Python中set不可哈希不能作字典键。必须用frozenset且所有状态名统一为frozenset包括起始态、转移目标态、接受态判断def nfa_to_dfa(nfa: NFA) - NFA: # 初始DFA状态ε-closure of start start_closure epsilon_closure(nfa, {nfa.start_state}) dfa_states {frozenset(start_closure)} dfa_transitions {} dfa_accept_states set() unmarked [frozenset(start_closure)] # DFA状态集、转移表、接受态初始化 while unmarked: current unmarked.pop(0) # 判断是否为接受态只要current中含任意nfa.accept_states即为接受 if current nfa.accept_states: dfa_accept_states.add(current) # 对每个输入符号a ∈ alphabet for a in nfa.alphabet: # move(current, a) 所有从current中某状态经a到达的状态集合 move_set set() for state in current: for next_state in nfa.transitions.get((state, a), set()): move_set.add(next_state) if not move_set: continue # ε-closure(move_set) closure epsilon_closure(nfa, move_set) closure_frozen frozenset(closure) # 记录转移 if (current, a) not in dfa_transitions: dfa_transitions[(current, a)] set() dfa_transitions[(current, a)].add(closure_frozen) # 若closure_frozen未见过加入待处理队列 if closure_frozen not in dfa_states: dfa_states.add(closure_frozen) unmarked.append(closure_frozen) # 构造DFA对象注意alphabet不变start_state是frozenset(start_closure) dfa_alphabet nfa.alphabet dfa_start frozenset(start_closure) # 转换transitions为标准格式{(state, symbol): {next_states}} dfa_trans_dict {} for (src, sym), dst_set in dfa_transitions.items(): dfa_trans_dict[(src, sym)] dst_set return NFA(dfa_states, dfa_alphabet, dfa_trans_dict, dfa_start, dfa_accept_states)参数说明nfa.alphabet必须是显式传入的字符集如{a,b}不能从transitions里推导——因为ε转移不占字母表且某些符号可能无转移但仍是合法输入。课设中若漏定义alphabetDFA最小化时会因符号缺失报错。4. DFA最小化Hopcroft算法的分组迭代与状态名映射还原4.1 为什么不能用Brzozowski代数反转法Brzozowski反转→确定化→反转→确定化虽简洁但课设要求“最小化”而Brzozowski不保证最小状态数因中间确定化可能产生冗余。Hopcroft算法时间复杂度O(n log n)且输出状态名可映射回原始NFA语义如{q0,q1}→A便于报告中画图。课设验收时老师会问“你合并的这两个状态分别对应NFA里的哪些路径”——只有Hopcroft能回答。4.2 Hopcroft实现用partition refinement模拟等价类分裂核心思想初始将状态分为接受态组和非接受态组然后对每组、每个输入符号检查其转移目标是否落在同一组内若否则分裂该组。def minimize_dfa(dfa: NFA) - NFA: # Step 0: 初始化划分 π {F, Q\F} all_states list(dfa.states) accept_set dfa.accept_states non_accept [s for s in all_states if s not in accept_set] accept_list [s for s in all_states if s in accept_set] partition [set(accept_list), set(non_accept)] # 移除空集 partition [p for p in partition if p] # Step 1: 迭代分裂 changed True while changed: changed False new_partition [] for group in partition: # 对当前group尝试按每个输入符号分裂 # 先为group中每个状态记录其按符号a的转移目标组号 for a in dfa.alphabet: # 构建映射state - target_group_index group_map {} for state in group: # 找state经a的所有转移目标 targets set() for next_state in dfa.transitions.get((state, a), set()): # next_state必在dfa.states中找它属于partition中哪一组 for idx, p in enumerate(partition): if next_state in p: targets.add(idx) break # 若无转移targets为空统一归为-1组 if not targets: group_map[state] -1 else: # 取targets中任意一个代表因同一state只到一个组但可能多目标不DFA是确定的 # 注意DFA定义要求每个(state,a)最多一个目标但我们的NFA转DFA可能有多个不子集构造后每个(state,a)是frozenset但作为DFA状态转移是单值 # 修正DFA中每个(state,a)应只到一个状态frozenset所以targets大小为0或1 group_map[state] list(targets)[0] if targets else -1 # 按group_map的值分组 split_groups {} for state, grp_idx in group_map.items(): if grp_idx not in split_groups: split_groups[grp_idx] set() split_groups[grp_idx].add(state) # 若split_groups 1则分裂 if len(split_groups) 1: changed True for sg in split_groups.values(): if sg: # 非空 new_partition.append(sg) break # 一个符号分裂成功跳出a循环重新开始大循环 else: # 本group在所有a下都未分裂保留原样 new_partition.append(group) if changed: partition new_partition # Step 2: 构建新状态名映射 state_to_new {} new_states set() new_accept set() new_start None new_transitions {} # 为每个等价类分配新名字A, B, C... letters ABCDEFGHIJKLMNOPQRSTUVWXYZ for idx, eq_class in enumerate(partition): new_name letters[idx % len(letters)] str(idx // len(letters) 1) if idx len(letters) else letters[idx] for old_state in eq_class: state_to_new[old_state] new_name new_states.add(new_name) # 若该类含原起始态则新起始态为此名 if dfa.start_state in eq_class: new_start new_name # 若含任意原接受态则为新接受态 if eq_class dfa.accept_states: new_accept.add(new_name) # 构建新转移表 for old_state in dfa.states: new_src state_to_new[old_state] for a in dfa.alphabet: targets dfa.transitions.get((old_state, a), set()) if targets: # targets是frozenset取其代表元素因DFA确定只有一个 target_old list(targets)[0] new_dst state_to_new[target_old] key (new_src, a) if key not in new_transitions: new_transitions[key] set() new_transitions[key].add(new_dst) return NFA(new_states, dfa.alphabet, new_transitions, new_start, new_accept)注意此实现假设DFA是完全的每个(state,a)都有定义。若存在缺失转移需先补全到“死状态”如q_dead否则dfa.transitions.get((state,a), set())返回空集list(targets)[0]会报错。课设中常见错误是忽略死状态导致最小化后转移不全。5. First/Follow集合文法驱动的递归计算与终结符/非终结符分离5.1 文法表示规范必须区分终结符与非终结符且支持ε产生式课设中常把文法写成字符串列表如[S-AB, A-aA|ε, B-b]但必须预处理出终结符集VT、非终结符集VN、产生式字典def parse_grammar(lines: List[str]) - Tuple[Set[str], Set[str], Dict[str, List[List[str]]]]: # lines like [S - A B, A - a A | ε, B - b] VN set() VT set() productions {} for line in lines: line line.strip() if not line or - not in line: continue lhs, rhs line.split(-, 1) lhs lhs.strip() VN.add(lhs) # 解析rhs按|分割每部分按空白分割 rhs_parts [part.strip() for part in rhs.split(|)] prods [] for part in rhs_parts: if not part: continue symbols part.split() # ε产生式标记为[ε] if part ε: symbols [ε] prods.append(symbols) # 收集符号非终结符在VN中和终结符不在VN中且非ε for s in symbols: if s ! ε and s not in VN: VT.add(s) productions[lhs] prods # 补充所有出现在rhs中但未在lhs出现的符号若非ε视为终结符 for prods in productions.values(): for prod in prods: for s in prod: if s ! ε and s not in VN and s not in VT: VT.add(s) return VT, VN, productions5.2 First集合递归迭代收敛ε传播必须显式跟踪First计算的关键是ε是否可被“吃掉”。不能简单递归必须用迭代法直到不动点def compute_first(VT: Set[str], VN: Set[str], productions: Dict[str, List[List[str]]]) - Dict[str, Set[str]]: first {v: set() for v in VN} # 终结符的First就是自己 for t in VT: first[t] {t} # ε的First是{ε} first[ε] {ε} changed True while changed: changed False for A in VN: for rhs_list in productions[A]: # 计算rhs_list的First first_rhs set() all_nullable True for X in rhs_list: # X的First减去ε X_first first.get(X, set()) - {ε} first_rhs | X_first if ε not in first.get(X, set()): all_nullable False break # 若所有X都可空则加ε if all_nullable: first_rhs.add(ε) # 若first_rhs有新元素更新 before len(first[A]) first[A] | first_rhs after len(first[A]) if after before: changed True return first def compute_follow(VT: Set[str], VN: Set[str], productions: Dict[str, List[List[str]]], first: Dict[str, Set[str]]) - Dict[str, Set[str]]: follow {v: set() for v in VN} # S的Follow加# start_symbol list(productions.keys())[0] follow[start_symbol].add(#) changed True while changed: changed False for A in VN: for rhs_list in productions[A]: # 遍历rhs_list中每个位置i的符号X for i, X in enumerate(rhs_list): if X in VN: # 只对非终结符求Follow # case 1: X后面有Y1Y2...Yk if i 1 len(rhs_list): Ys rhs_list[i1:] # First(Y1Y2...Yk) \ {ε} first_seq set() all_nullable True for Y in Ys: first_Y first.get(Y, set()) - {ε} first_seq | first_Y if ε not in first.get(Y, set()): all_nullable False break # 加入Follow(X) before len(follow[X]) follow[X] | first_seq after len(follow[X]) if after before: changed True # case 2: 若Y1..Yk都可空则Follow(A) ⊆ Follow(X) if all_nullable: before len(follow[X]) follow[X] | follow[A] after len(follow[X]) if after before: changed True # case 3: X在末尾则Follow(A) ⊆ Follow(X) else: before len(follow[X]) follow[X] | follow[A] after len(follow[X]) if after before: changed True return follow血泪经验follow[X] | follow[A]必须在所有rhs遍历完后再执行否则迭代顺序错乱。课设中常见错误是把“X在末尾”逻辑写在内层循环里导致Follow传播过早、不收敛。6. 避坑指南课设里90%学生踩过的5个硬核陷阱6.1 NFA确定化后状态爆炸但DFA最小化仍不收敛现象输入a*NFA有4个状态确定化后DFA有5个状态最小化后还是5个——明明应该只有2个接受/不接受。原因DFA不完全。a*的DFA应有状态{q0}起始接受、{q1}接受但若{q0}经a到{q1}{q1}经a到{q1}却漏了{q0}经其他符号如b的转移。课设中常只处理alphabet中出现的符号忽略“未定义转移”。解决在nfa_to_dfa后显式添加死状态q_dead并将所有缺失转移指向它。最小化前q_dead单独成组且不与任何接受态同组。6.2 First集合算出{ε}但Follow里漏掉#现象文法S-A,A-aA|εFirst(A){a,ε}正确但Follow(S){#}Follow(A)为空。原因Follow计算中S-A这条产生式A在末尾应有Follow(S) ⊆ Follow(A)但代码里只处理了A-αBβ形式漏了A-αBB在末尾的情况。解决在compute_follow的else分支即i1 len(rhs_list)里必须执行follow[X] | follow[A]且此操作不能放在if i1 len...的else里而应独立判断X rhs_list[-1]。6.3 DFA最小化后状态名乱码无法对应报告图现象最小化输出状态为frozenset({q0,q1})报告里画图时写成{q0,q1}但老师问“这个状态对应NFA的哪条路径”答不上来。原因状态名未做语义映射。frozenset只是计算中间量不是可读标识。解决在minimize_dfa中建立old_state → new_name映射的同时记录每个新状态包含的原始NFA状态路径。例如A {q0,q1}则注释“A: q0(ε→q1), q1(a→q1)”——这需要你在NFA构造时就给每个状态打上来源标签如q0_0表示第0个子表达式的起始态。6.4 正则表达式含ε时Thompson构造无限递归现象输入εthompson(ε)调用star_nfa或union_nfa又调用自身栈溢出。原因tokenize_regex未识别ε为原子符号而是当作空字符串或忽略导致解析失败。解决在tokenize_regex开头加特判if regex.strip() ε: return [ε]并在parse_tokens中增加char_nfa(ε)分支返回仅含起始/接受态、无转移的NFA。6.5 报告里First/Follow表格填不满LL(1)分析表报错现象First(A) ∩ Follow(A) ≠ ∅但文法明显是LL(1)。原因First和Follow计算未考虑文法开始符号的Follow必须含#且#未被加入VT。若VT不含#则分析表构造时找不到列。解决在parse_grammar后显式将#加入VTVT.add(#)并在compute_follow中确保start_symbol的Follow已初始化为{#}。7. 报告交付技巧让老师一眼看到你的工程深度7.1 用ASCII图替代截图确保纯文本可验证不要贴Visio或draw.io截图。用Python生成可复制的ASCII状态图def print_nfa_dfa(nfa_or_dfa: NFA, title: str): print(f\n {title} ) print(fStates: {sorted(nfa_or_dfa.states, keystr)}) print(fAlphabet: {sorted(nfa_or_dfa.alphabet)}) print(fStart: {nfa_or_dfa.start_state}) print(fAccept: {sorted(nfa_or_dfa.accept_states, keystr)}) print(Transitions:) for (src, sym), dsts in sorted(nfa_or_dfa.transitions.items()): dst_str ,.join(sorted(dsts, keystr)) print(f {src} --{sym}-- {dst_str}) # 调用示例 nfa thompson(a|b) dfa nfa_to_dfa(nfa) min_dfa minimize_dfa(dfa) print_nfa_dfa(nfa, NFA for a|b) print_nfa_dfa(dfa, DFA after subset construction) print_nfa_dfa(min_dfa, Minimized DFA)输出效果 NFA for a|b States: [q0, q1, q2, q3, q4, q5] Alphabet: [a, b] Start: q0 Accept: {q5} Transitions: q0 -- - {q1, q3} q1 --a-- {q2} q2 -- - {q5} q3 --b-- {q4} q4 -- - {q5}技巧把print_nfa_dfa输出重定向到文件直接粘贴进LaTeX的verbatim环境零失真。7.2 First/Follow表格用Markdown表格呈现列名带语义不要手动画Excel。用Python生成def print_first_follow(first: dict, follow: dict): all_symbols sorted(set(first.keys()) | set(follow.keys())) print(| Symbol | First | Follow |) print(|--------|-------|--------|) for s in all_symbols: if s in first and s in follow: f_str , .join(sorted(first[s])) l_str , .join(sorted(follow[s])) print(f| {s} | {f_str} | {l_str} |) # 输出 # | Symbol | First | Follow | # |--------|-------|--------| # | S | a, ε | # | # | A | a, ε | #, a |7.3 在报告附录放“可复现命令行”最后一页写# 课设运行指南Linux/macOS $ python3 compiler_lab.py --regex a|b # 生成NFA→DFA→minDFA $ python3 compiler_lab.py --grammar gram.txt # gram.txt格式见README $ python3 compiler_lab.py --test-all # 运行全部单元测试并附上compiler_lab.py的argparse入口——这比“详见源码”有力十倍。我带过三届编译原理实验课最打动我的课设永远是那个在报告第一页就印着$ python3 main.py --demo运行结果的学生。他没画一张图但老师敲一遍命令终端里蹦出的ASCII状态图和集合列表比十页PPT更让人信服。希望帮到你。本文还有配套的精品资源点击获取