NFA转化为DFA编译原理实验报告

编译原理实验报告实验名称正则表达式与有限自动机院系信息工程学院班级计算机科学与技术1班学号2013550336姓名朱义一、实验目的通过本次实验，加深对正则表达式，NFA，DFA及其识别的语言的理解二、实验题目编程实现NFA确定化为NFA的过程三、算法思想1.一个自动机是一个五元组，分别是状态集，符号集，f函数，起始状态，终止状态2.使用子集法的步骤是：1)将起始状态求闭包，得到S0。2)从0开始直到totss对每个子集求各个字符所能到达的新子集将其加入tot+1子集中。3)检查tot+1子集是否与之前的子集重合或者为空,如果重合或为空则子集不增加。4)记录新的状态转换函数。3.根据NFA转化为DFA的过程一步步模拟进行操作。四、数据结构介绍程序里将NFA五元组分别储存在以下数据结构里初态集储存在int数组sta_statu[maxs]里maxs为元素的最大数终态集储存在int数组end_statu[maxs]里字符集储存在char数组cha[maxs]里状态储存为0~n-1（n个状态情况）状态转换函数储存于结构stuctstatu里structEdge{//转化边charcost;//消耗intdest;//指向的终点};structstatu{Edgenode[50];//终点intcnt;//边的数量statu(){cnt=0;for(inti=0;i50;i++){node[i].cost='#';node[i].dest=0;}}}sta[50];//起点五、具体实现使用子集法实现：函数接口解释：voidcreat_subset(void);构造子集函数Ins(inta,intss)用深搜（dfs）求状态ss的闭包，并将闭包里的所有元素加入到子集closure[a]里。voidins_subset(inta,intss,chartarget)求状态ss通过字符target所能到达的所有状态，并将这些状态加入到子集closure[a]里。intcheck(inttt)检查子集closure[tt]是否与之前的子集重合，为空则返回-2，不重合返回-1，重合则返回重合的子集下标。voidprint(void)输出DFA的五元组信息。1.将起始状态求闭包，得到S0。将初状态里所有的元素及其能通过e空路所到的状态加入closure[0]作为初始子集for(inti=0;ict_sta_statu;i++)//求起始状态求闭包，得到S0{closure[0].members.insert(sta_statu[i]);ins(0,sta_statu[i]);}//e_closure(s0)2.从0开始直到totss对每个子集求各个字符所能到达的新子集将其加入tot+1子集中。for(tempss=0;tempss=totss;tempss++)//tempss表示当前运算的状态下表totss表示总共的状态数新生产的状态子集加入到closur[tot+1]中{for(intj=0;jct_cha;j++)for(it=closure[tempss].members.begin();it!=closure[tempss].members.end();it++){ins_subset(totss+1,*it,cha[j]);}}voidins_subset(inta,intbeg,chartarget)//求状态ss通过字符target所能到达的所有状态，并将这些状态加入到子集closure[a]里。{for(inti=0;ista[beg].cnt;i++){if(sta[beg].node[i].cost==target){closure[a].members.insert(sta[beg].node[i].dest);ins(a,sta[beg].node[i].dest);//求出这些状态后用dfs求其能经过ε空路所到达的状态也加入closure[a]}}return;}voidins(inta,intbeg)//求集合的ε闭包{for(inti=0;ista[beg].cnt;i++){if(sta[beg].node[i].cost=='#'){closure[a].members.insert(sta[beg].node[i].dest);ins(a,sta[beg].node[i].dest);}}}3.检查tot+1子集是否与之前的子集重合或者为空,如果重合或为空则子集不增加intcheck(inttt){if(closure[tt].members.empty())return-2;//为空则返回-2setint::iteratorisa,isb;for(inti=0;itt;i++){isb=closure[tt].members.begin();if(closure[tt].members.size()==closure[i].members.size())for(isa=closure[i].members.begin();isa!=closure[i].members.end();isa++){if(*isa!=*isb)break;else{isb++;}}if(isb==closure[tt].members.end())returni;//重合则返回之前相同的子集的下标}return-1;//不重合返回-1}4.记录新的状态转换函数if(ok==-2)//新子集为空;elseif(ok==-1)//与之前的子集不重合，记录新状态转换函数{totss++;newsta[tempss].node[newsta[tempss].cnt].cost=cha[j];newsta[tempss].node[newsta[tempss].cnt++].dest=totss;}else//与之前的子集重合，记录新状态转换函数{closure[totss+1].members.clear();newsta[tempss].node[newsta[tempss].cnt].cost=cha[j];newsta[tempss].node[newsta[tempss].cnt++].dest=ok;}5.输出DFA信息六、设计过程中的问题与对策NFA转化为DFA的过程中最难解决的是如何储存状态转换函数以及记录新的状态转换函数的问题，我开始设计为一个二维数组，实际应用时发现当NFA中一个字符对应两个目标时前一个目标会被覆盖。于是再仔细观察NFA的特点，多个初态，多个终态，一个状态经一个字符可对应多个状态。设计了一种新的储存结构，因为每个NFA相当于一个有向图。用一个结构体储存每个状态的边数，每个边的消耗及重点。然后即可顺利进行了。七、测试与运行情况样例1输出样例2输出样例3输出八、实验总结这次实验让我加深了对NFA,DFA的理解，实现编写NFA到DFA的转化过程中遇到了许多困难，让我不断地去查阅资料，增长了自己的知识，丰富了自己的实践经验。