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

《NFA转化为DFA编译原理实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、编译原理实验报告实验名称正则表达式与有限自动机院系信息工程学院班级计算机科学与技术1班学号2013550336姓名朱义一、实验目的通过本次实验，加深对正则表达式，NFA，DFA及其识别的语言的理解二、实验题目编程实现NFA确定化为NFA的过程三、算法思想1.一个自动机是一个五元组，分别是<状态集，符号集，f函数，起始状态，终止状态>2.使用子集法的步骤是：1)将起始状态求闭包，得到S0。2)从0开始直到totss对每个子集求各个字符所能到达的新子集将其加入tot+1子集中。3)检查tot+1子集是否与之前的子集重合或者为空,如果重合或为空则

2、子集不增加。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];

3、//终点intcnt;//边的数量statu(){cnt=0;for(inti=0;i<50;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所能到达的所有状态，并将这

4、些状态加入到子集closure[a]里。intcheck(inttt)检查子集closure[tt]是否与之前的子集重合，为空则返回-2，不重合返回-1，重合则返回重合的子集下标。voidprint(void)输出DFA的五元组信息。1.将起始状态求闭包，得到S0。将初状态里所有的元素及其能通过e空路所到的状态加入closure[0]作为初始子集for(inti=0;i

5、tu[i]);}//e_closure(s0)2.从0开始直到totss对每个子集求各个字符所能到达的新子集将其加入tot+1子集中。for(tempss=0;tempss<=totss;tempss++)//tempss表示当前运算的状态下表totss表示总共的状态数新生产的状态子集加入到closur[tot+1]中{for(intj=0;j

6、t(totss+1,*it,cha[j]);}}voidins_subset(inta,intbeg,chartarget)//求状态ss通过字符target所能到达的所有状态，并将这些状态加入到子集closure[a]里。{for(inti=0;i

7、过ε空路所到达的状态也加入closure[a]}}return;}voidins(inta,intbeg)//求集合的ε闭包{for(inti=0;i

8、t].members.empty())return-2;//为空则返回-2set::iteratorisa,isb;for(inti=0;i