简介面向编译原理课程设计的学习者这套资源围绕非确定有限自动机的确定化、确定有限自动机的最小化以及First集合与Follow集合的计算展开覆盖词法分析、语法分析、语义分析等编译器核心模块适合需要完整代码参考与报告范式的高校学生。压缩包共160个文件约81.15MB以C源码、Word报告、可执行程序为主另含工程文件、调试信息、说明文档等tlog、obj、ipch等编译生成文件也一并保留便于直接加载工程查看与运行。已有266人学习下载。内容包含可运行的自动机构造与集合计算代码也提供课程设计报告和实验总结能够帮助读者理解非确定有限自动机的确定化流程、确定有限自动机的状态最小化原理以及LL(1)/LR(1)分析表所需的First集合与Follow集合计算过程适合作为完成课设、复习备考或二次开发的基础材料。 编译原理课设做到NFA确定化、DFA最小化、First/Follow集合这几块基本就是把自己按在地上摩擦一遍。如果你是第一次接触这几个算法别慌这篇文章就是给你准备的。我会把整个课设拆开揉碎讲清楚每个算法在干什么、代码怎么写、报告怎么凑不是凑是组织最后再把我当时踩过的一些坑原封不动告诉你。整个课设的任务一句话概括给一个正规式把它变成NFA再确定化成DFA再最小化给一个文法算出每个非终结符的First集合和Follow集合。听起来好像就是几个算法拼一起但真正动手就发现每一步都在跟集合、状态、映射这些东西较劲。这篇文章会从整体设计讲到每个算法的实操细节再讲测试用例怎么设计、报告怎么提交帮你把这条路走顺。1. 课设的整体设计与实现思路1.1 先搞清楚输入输出是什么这个课设的核心输入有两类。一类是正规式比如(a|b)*abb你要把它转成等价的NFA再确定化为DFA最后最小化另一类是文法比如常见的表达式文法E - ET | T这种你要为每个非终结符求First和Follow。说得直白一点前面的NFA/DFA是在解决“正则表达式怎么被机器高效识别”的问题后面的First/Follow是在为自顶向下语法分析做铺垫。很多同学写代码时喜欢直接上手撸算法结果数据结构设计得一塌糊涂后悔都来不及。我先劝你一句花一天时间把输入输出定义清楚比什么都值。我当时的做法是正规式输入纯文本转成NFA然后输出NFA的状态数、边集合、初态和终态。NFA确定化后输出DFA状态表每个状态对应一个状态集。DFA最小化后输出最小状态数和状态转移表。文法输入产生式列表输出每个非终结符的First集合和Follow集合。这些输出在调试时就是你的“照妖镜”哪里有问题一目了然。1.2 模块划分与语言选型整个课设我建议分成四个模块模块职责正规式解析与NFA构造把正规式转成ε-NFA一般用Thompson构造法NFA确定化子集构造法把ε-NFA转成DFADFA最小化划分法合并等价状态First/Follow计算文法处理迭代求解两个集合语言选型上C、Java、Python都行。如果你不是对C特别熟我推荐Python因为set、dict这些数据结构写集合运算不要太爽调试起来也快。但如果你学校要求必须C也完全没问题就是代码量会大一些后面习惯就好了。我自己用的是C因为当时课设要求控制台程序而且我对STL还算熟。2. NFA确定化子集构造法的完整拆解2.1 ε-闭包的计算逻辑NFA确定化第一步就是算ε-闭包。所谓ε-闭包就是从某个状态集合出发沿着所有ε边能到达的状态的全体包括自己。这个算法本质上就是个图的遍历。我用的方式是栈setsetint epsilonClosure(const setint states, const vectorNFATransition transitions) { setint closure states; stackint stk; for (int s : states) stk.push(s); while (!stk.empty()) { int cur stk.top(); stk.pop(); for (const auto t : transitions) { if (t.from cur t.symbol EPSILON closure.find(t.to) closure.end()) { closure.insert(t.to); stk.push(t.to); } } } return closure; }有一个细节特别容易漏初始状态集合本身的每个状态都要在闭包里。我当时就因为这个第一次跑出来的DFA状态数怎么都不对折腾了快一个晚上才发现是闭包初始化没包含初始集合。2.2 子集构造法的主流程确定化的核心思路是把NFA状态的一个子集当作DFA的“一个状态”然后看这个子集经过某个字符能走到哪些状态。这里的关键点是要区分“经字符转移”和“经ε转移”两者要配合使用。我当时的主流程大致是这样的把NFA的初态集合求ε-闭包作为DFA的初态。用一个队列保存还没处理过的DFA状态每个状态就是一个子集。对每个输入符号a计算当前子集经a能到达的所有状态的ε-闭包。如果这个新子集没出现过就创建一个新的DFA状态加入队列。如果原NFA的终态出现在某个子集里这个DFA状态就是终态。这里有个判断终态的小技巧只要子集里包含至少一个原NFA终态这个DFA状态就是终态不管子集里还有没有别的状态。这个点不难但很多教材写得含糊容易让新手犹豫。2.3 确定化过程的常见坑我总结了一下NFA确定化时大家最容易出问题的地方有三个重复计算ε-闭包。如果你每次都重新遍历所有边性能会很难看。我后来用了一个缓存表记录每个子集计算过的闭包结果速度明显快很多。状态编号和子集映射对不上。建议维护一个mapsetint, int每个子集唯一对应一个DFA状态编号别自己想着编。忘记处理空转移目标。有时候move(I, a)的结果是空集这个情况要直接跳过不要为它分配DFA状态否则最后状态表里会多出一堆死状态。NFA确定化这一块建议用比较简单的正规式先跑通比如ab然后逐步加|、*最后再上(a|b)*abb。每步都用纸笔推一遍再对比程序输出。3. DFA最小化划分法的实现与细节3.1 划分法的核心思想DFA最小化就是把等价的状态合并成一个。教材上一般用划分法先把状态分成两个大组——终态组和非终态组然后反复检查每个组里的状态是否在同一个输入符号下转移到同一个组如果行为不一致就继续拆分。我第一次看这个算法觉得还挺绕的。后来想明白了一个类比就好比班上一群学生先按“是不是课代表”分两组然后不断根据“交作业给谁”这种行为再把每个组拆细直到每个组里所有人都一样。实现上我当时用一个数组group[state]表示每个状态属于哪个组然后迭代执行拆分逻辑。每轮遍历所有状态、所有输入符号判断是否要拆分。直到某一轮没有任何组被拆分算法就结束了。3.2 最小化后的状态映射最小化结束之后每个组就是一个新的DFA状态。这一步要注意新DFA的初态是包含原DFA初态的那个组终态是包含原终态的组可能有多个。我在这里踩过一次坑最小化后的终态判断不能沿用原来的状态编号必须通过组号重新映射。因为我习惯直接复用原来的状态表结果后面对应关系全乱了。后来我改成先建立“旧状态-新编号”的映射表再生成新的状态转移表这个问题就彻底解决了。3.3 最小化过程中的经典问题不可达状态。最小化之前最好先用可达性分析把从初态不可达的状态删掉。很多实现里不删也不影响正确性但会让输出状态数偏多看起来不专业。老师检查的时候很容易被问一句“为什么不删”非常尴尬。拆分条件判断。判断一个组是否需要拆分不能光看“转移到是否同一个组”还必须保证拆出来的新组没有被重复创建。我当时用mappairint, char, int来判断当前状态应该分到哪个新组避免了重复。死循环风险。如果状态数量较大迭代轮数可能很多记得在循环里加一个“本轮是否有变动”的标记否则有可能死循环。DFA最小化写完以后强烈建议打印出每一轮的划分结果这样调试时能直观看到每个组是怎么一步步被拆开的。我当时就是把每组的成员打出来对着纸笔演算非常方便。4. First与Follow集合的完整实现4.1 First集合的计算递归与迭代之间的取舍First集合的教材定义很简单非终结符A能推出的所有终结符的集合。但编程实现的时候有两条路递归法深度优先和不动点迭代法。递归法写起来很直观对每个产生式A - X1 X2 ... Xn逐个扫描右部符号如果是终结符加入First(A)然后break。如果是非终结符把它的First除ε外加进来如果它不能推出ε就break。如果能一直推出ε到最后一个符号就把ε加入First(A)。我用C写的时候是这个样子void computeFirst(char nt, mapchar, vectorstring productions, mapchar, setchar first) { if (!first[nt].empty()) return; // 防止重复计算 for (const string rhs : productions[nt]) { for (size_t i 0; i rhs.size(); i) { char ch rhs[i]; if (isTerminal(ch)) { first[nt].insert(ch); break; } else { computeFirst(ch, productions, first); bool hasEpsilon false; for (char c : first[ch]) { if (c EPSILON) hasEpsilon true; else first[nt].insert(c); } if (!hasEpsilon) break; if (i rhs.size() - 1) first[nt].insert(EPSILON); } } } }递归法有个大坑左递归文法会死循环。比如E - E T计算First(E)时会先递归计算First(E)直接栈溢出。所以如果你要处理的文法里有左递归不要用递归法直接上迭代法不动点迭代虽然写起来啰嗦一点但绝对稳定。4.2 Follow集合的依赖关系与计算顺序Follow集合的计算规则里有两条核心对产生式A - αBβ把First(β)中除ε以外的所有符号加入Follow(B)。如果A - αB或者β能推出ε那么把Follow(A)的所有符号加入Follow(B)。这个逻辑最搞人的地方是Follow集合之间会互相依赖。比如E - T要算Follow(T)得先知道Follow(E)而Follow(E)可能又要靠别的产生式才能求出来。所以Follow一般建议用不动点迭代反复遍历所有产生式直到所有集合都不再变化。我当时把Follow的计算拆成了两层循环外层循环不断标记“是否发生变化”内层遍历所有产生式应用规则。这样实现最简单也不太容易出错。至于效率课设文法规模都不大几轮就能收敛不用操心性能问题。4.3 几个容易漏掉的边界情况开始符号的Follow要加结束标记。一般用#或者$千万别漏。漏了的话后面做预测分析表会出问题。产生式右部结尾的非终结符Follow继承左部的Follow。这条规则是A - αB的情况很多人只记得A - αBβ一路查First忘了最直接的尾巴继承。ε传递。当β能推出ε时A - αBβ退化成A - αB必须继续继承Follow(A)。这个坑我当时是在测试E - E T | T这种文法时发现的Follow(E)算出来空荡荡排查半天才反应过来。First和Follow的代码写完后验证方式也很简单拿课本上的经典文法手算一遍再对照程序输出完全一致基本就稳了。我当年用了表达式文法验证结果First和Follow都能跟教材对上线那感觉确实踏实。5. 测试用例设计与调试实录5.1 用(a|b)*abb验证整个NFA/DFA流程正规式(a|b)*abb是编译原理教材里的经典案例几乎所有NFA确定化和DFA最小化章节都会拿它当例子。用这个例子你可以验证NFA是否包含正确的状态数和边数。确定化后的DFA状态数是否为教材上的个数一般是5个。最小化后的DFA状态数是否为4个。我当时写完后跑这个用例第一次结果DFA是6个状态最小化后5个跟教材对不上。排查下来发现是ε-闭包计算里漏了初始状态的自环修完之后就完全一致了。这个过程其实很锻炼人因为你必须真的理解每一步在做什么才能定位到代码里的问题。5.2 文法取表达式文法验证First/Follow验证First和Follow我建议用这个文法带左递归、带括号、带优先级E - E T | T T - T * F | F F - ( E ) | id这个文法的First和Follow是编译原理课上的标配手算结果到处都能查到。用它可以验证的细节包括左递归情况下First是否能正确计算如果用了迭代法就没问题。F - ( E )这种右部以终结符开头的产生式终结符是否加入First(F)。Follow(E)是否正确包含)和#。出现E T时First(T)是否被加入Follow(E)前面的。如果这个文法跑出来和教材一致那你的First/Follow实现基本就合格了。5.3 调试中遇到的高频问题记录我整理了一下当时调试过程中遇到的最典型的几个问题给大家参考现象可能原因解决方案DFA状态数比预期多ε-闭包计算错误初始集合没算全检查闭包初始化确认包含初始状态本身最小化后终态丢失终态判断沿用了旧状态编号建立旧状态到新组号的映射表First集合递归死循环文法存在左递归且使用了递归法改用不动点迭代法Follow集合越算越空开始符号没加#或尾部继承规则漏写补上结束标记和尾部继承逻辑输出乱码用了中文符号做终结符统一用ASCII字符除此之外还有一个建议所有程序输出都做成一行一个集合的形式比如First(E) { , *, (, ), id }这样就算老师不跑你的程序看输出文件也能一眼看懂。6. 课程设计报告的撰写技巧6.1 报告的结构与逻辑课设要“包含报告”很多同学把报告写成代码注释合集这其实是最大的误区。老师想看到的报告是一个完整的工程思路展示而不是代码抄写。我的报告结构是这样的需求分析——课设要解决什么问题输入输出是什么。总体设计——模块划分、数据结构设计、每个模块的职责。算法详细设计——NFA确定化、DFA最小化、First/Follow分别用什么算法为什么选这个算法。测试与运行——测试用例、运行截图或输出、结果分析。总结与心得——遇到的问题、怎么解决的、学到的经验。6.2 老师最看重报告的哪几块根据我带过几年课设的经验以及我自己当年被老师点评的经历老师通常重点看这几块算法流程图或伪代码重点说明子集构造法、划分法、First/Follow迭代法三个算法。测试用例的覆盖度有没有测空串、多字符正规式、单字符正规式、左递归文法、含ε产生式的文法。问题和解决方案报告里写清楚“我遇到了什么问题、怎么排查的”特别加分。代码结构清晰度关键函数注释到位不要大段大段贴代码。我当时报告里把每种算法都画了流程图再把关键代码配上去后面再附上完整运行输出。老师说这份报告至少在结构上比大多数同学清晰我觉得主要是因为我没有堆代码而是讲清楚了“为什么”。6.3 报告写作的排版建议排版上的建议就三条代码只保留核心算法部分比如epsilonClosure()、splitGroups()、computeFirst()别把整个文件贴上去。所有截图统一尺寸输出窗口用同样的字体和颜色看起来专业。图表用统一的配色风格不要Word里一个配色、Visio里又一个配色非常散乱。还有一个小技巧报告里的运行结果先用小用例验证比如ab | ba再上大例子(a|b)*abb。小用例截图放前面大用例放后面展示从简到繁的调试过程。最后再分享一个我个人的体会这个课设真正难的不是算法本身而是把数据结构设计得干净、调试起来顺手。如果你做完之后能感觉自己对“集合”“映射”“状态转移”这些概念的理解上了一个台阶那这个课设就没白做。哪怕中间改了好几版代码回头看都是值得的。祝你们都能顺利跑通少掉几根头发。本文还有配套的精品资源点击获取