编译原理报告：NFA转DFA(详解-附源代码)

v1.0可编辑可修改1编译原理实习报告学号：******班级：******姓名：******日期：2015目录1.题目及需求分析……………………………………………32.设计分析……………………………………………………33.调试分析……………………………………………………7v1.0可编辑可修改24.用户手册……………………………………………………75.测试结果……………………………………………………76.总结…………………………………………………………77.源代码………………………………………………………8题目：NFA转换为等价的DFA实习时间：【问题描述】以定理“设L为一个由不确定的有穷自动机接受的集合，则存在一个接受L的v1.0可编辑可修改3确定的有穷自动机”为理论基础，设计算法实现将不确定的有穷自动机(NFA)转换为与之等价的确定的有穷自动机(DFA)。【基本要求】①确定能够表示FA的合适的结构，以便FA的输入和输出②设计的算法既要成功实现题目要求的功能，又要高效、鲁棒③程序中的函数、变量等命名要规则，可读性要强(易懂)1．需求分析(1)要将以状态转换图表示的NFA转换为DFA，首先应设计一个结构来表示FA，以便图形式的FA便于输入和输出。(2)设计合适的算法来实现NFA的确定化，这里用子集法来构造等价的DFA。(3)测试数据:课本P59例转换前的NFA转换后的DFA2．设计（1）数据结构设计由于FA是一个图，可想到用图的存储结构来存储FA，但是，FA中两个结点之间的路径可以不只一条，这让想考虑用邻接矩阵来存储的FA处理起来有点复杂，我采用的是“结点-边-结点”式的三元组来表示FA。FA有多少条边就应该有多少个这样的三元组，以一个数组来存放这些三元组，那么一个FA就可以表示出来了。此外，由子集法的步骤可见，集合(set)这一结构应该使用，，set结构符合我们数学的集合要求，不含相同元素，并且两个集合间还可以进行比较是否相等，十分有利于我们的程序实现。表示FA的结构：v1.0可编辑可修改4集合与栈使用库里面的标准集合、栈。即包含头文件set、stack（2）文件结构程序不是很复杂，加之使用到的数据结构是标准库里的，文件只有一个，其中有#includeset和#includestarck。（3）程序基本框架概览（4）主要函数的实现伪代码具有简明扼要的特点，利用伪代码子来表示程序流程有利于理解和后续实现。子集法伪代码：//Triad(三元组)：S→aB即（S,a,B）structTriad{charstart;charedge;charend;};structTriad{};//FA的基本组成结构intmain(){初始化工作；determined();//确定化}e_closure(){}//求ε闭包move(){}//求集合的x弧转换determined(){}//确定化s0←NFA的开始状态集合T←e-closure(s0)把T加入到子集簇C(未标记)while(集合U←在C中找到一个未标记的集合){标记U;v1.0可编辑可修改5此外，求ε的传递闭包要利用栈这一数据结构做辅助，其伪代码如下：再在伪代码的基础上来编写这些核心函数就方便多了，具体代码如下：//求e-closure(T)的伪代码将T中的所有状态全都压入栈S、集合Uwhile(S非空){t←取栈顶元素;for(每个从t状态能通过空串转换得到的状态s)if(s不在U中){把状态s加入U;把状态s压入S;}}returnU;//集合U即为所求的ε闭包setchare_closure(setcharT,TriadG[],intN)tart==t&&G[i].edge=='*')nd);nd);//将其压栈}}}returnU;}v1.0可编辑可修改6voiddetermined(TriadG[],intN,char*input,intn){tart;setcharT0,T1;(s0);T1=e_closure(T0,G,N);mpty()&&marked[i]==false&&iMAX_NODES){marked[i]=true;for(intj=0;jn;j++){if(input[j]!='*'){setcharU=e_closure(move(C[i],input[j],G,N),G,N);if(!()){boolinC=false;intk=0;while(!C[k].empty()&&kMAX_NODES){if(U==C[k]){inC=true;break;}k++;}if(!inC){k=0;while(!C[k].empty()&&kMAX_NODES){v1.0可编辑可修改73．调试分析优点分析：NFA的输入只要求输入边的条数即可开始输入组成FA的基本结构(即三元组)，而有多少引起状态转换的输入都交给程序自己去完成，这一点就显得很简洁，对于用户来说也便捷！缺点分析：没有可视化，整个程序的输入输出是通过控制台完成的。解决办法：可合适的使用MFC可视化编程完成(这个有余力可以考虑一下)。4．用户手册该程序的使用十分简单，直接按要求输入相应数据就是。5．测试数据及测试结果课本P59例：v1.0可编辑可修改86．总结优点通过这次的实习，对编译原理NFA、DFA及之间的等价转换有了更加深刻的理解，也学会了利用伪代码来设计程序，由框架到细节的实现，这种设计相当便利高效。团队成员之间交流思想取长补短也让我学到了好多思想和方法。7.源代码#includeset#includestack#includeiostreamusingnamespacestd;tartG[i].edgeG[i].end;v1.0可编辑可修改9}setcharEdge;for(intj=0;jN;j++){(G[j].edge);}intn=();char*input=newchar[n];setchar::iteratorit;j=0;for(it=();it!=();it++){input[j]=*it;j++;}determined(G,N,input,n);return0;}setchare_closure(setcharT,TriadG[],intN){setcharU=T;stackcharS;setchar::iteratorit;v1.0可编辑可修改10for(it=();it!=();it++)(*it);chart;while(!()){t=();();for(inti=0;iN;i++){if(G[i].start==t&&G[i].edge=='*'){(G[i].end);(G[i].end);}}}returnU;}setcharmove(setcharI,chara,TriadG[],intN){setcharU;setchar::iteratorit;for(it=();it!=();it++)for(inti=0;iN;i++){if(G[i].start==*it&&G[i].edge==a)(G[i].end);v1.0可编辑可修改11}returnU;}voiddetermined(TriadG[],intN,char*input,intn){coutendl确定后的DFA:endl;boolmarked[MAX_NODES];for(inti=0;iMAX_NODES;i++)marked[i]=false;setcharC[MAX_NODES];chars0=G[0].start;setcharT0,T1;(s0);T1=e_closure(T0,G,N);C[0]=T1;i=0;while(!C[i].empty()&&marked[i]==false&&iMAX_NODES){marked[i]=true;egin();it!=C[i].end();it++)cout*it,;coutendl;*/for(intj=0;jn;j++){if(input[j]!='*'){setcharU=e_closure(move(C[i],input[j],G,N),G,N);v1.0可编辑可修改12if(!()){boolinC=false;intk=0;while(!C[k].empty()&&kMAX_NODES){if(U==C[k]){inC=true;break;}k++;}if(!inC){k=0;while(!C[k].empty()&&kMAX_NODES){k++;}C[k]=U;}couti→input[j]kendl;}}}i++;}mpty()){boolis_final_state=false;v1.0可编辑可修改13setchar::iteratorit;for(it=C[i].begin();it!=C[i].end();it++){if(*it=='#'){is_final_state=true;break;}}if(is_final_state)couti,;i++;}coutendl;}