实验报告：子集构造法.doc

实验报告课程名称编译原理题 目子集构造法院 （系）信息与控制工程学院专业班级姓 名学 号指导教师叶娜 2017年 4 月 30 日 第 5 页目 录一、实验目的2二、实验要求、内容2三、实验设备2四、实验原理及步骤2五、程序源代码3六、存在的问题及体会4一、实验目的掌握将非确定有限自动机确定化的方法和过程二、实验要求、内容实验要求：1. 输入一个NFA，输出一个接受同一正规集的DFA2. 采用C+语言，实现该算法3. 编制测试程序4. 调试程序实验步骤：1.NFA关系图2.通过一个转换算法将NFA转换为DFA3.显示DFA关系图三、实验设备开发系统：Windows 10开发工具：Visual Studio 2013四、实验原理及步骤1、NFA与DFA之间的联系 将NFA转换成等价的DFA的基本思想是让DFA的每一个状态对应NFA的一组状态，也就是说让DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态，在读入输入符号之后，DFA处在a1a2.an那样一个状态，该状态表示这个NFA的状态的一个子集T，T是从NFA的开始状态沿着某个标记为a1a2.an可以达到的那些状态构成的。2、 DFA的化简得到新的DFA之后，并没有完成任务，因为通过NFA转化成DFA不一定是最简单的，即有多余的状态可以删除，即NFA转换成DFA之后，还需要化简，确定化。化简DFA的基本思想是将它的状态分成一些互不相交的子集，每一个子集中的状态都不是等价的，不同子集中的状态可以由某个输入串来区别，最后将不能区别的每个子集用一个状态来做代表，具体方法如下：（1） 将M的所有状态分成两个子集，即终态集和非终态集；（2） 考察每一个子集，若发现某子集中的状态不等价，将其划分为两个集合；（3） 重复第（2）步，继续考察一得到的每一个子集，直到没有任何一个子集需要继续划分为止。此时DFA的状态被分为若干个互不相交的子集；（4） 从每个子集中选出一个状态做代表即可得到最简的DFA。3、 流程图图3-1程序总框图开始输入NFA，初始化NFA初步转化为DFA重命名化简结束图4-2 功能图5、 程序源代码部分代码：void child_method()int m,n;for(m=0;m100;m+) for(n=0;n100;n+) Dtranmn=#; for(m=0;m100;m+)DFAm.flag=-1; State S0,U;S0.flag=0;S0.count=1;S0.H0=first;State T;T=closure(S0);T.mark=0;T.flag=0;DFAnumof_Dtran+=T;memset(useof_DFA,0,sizeof(useof_DFA);int j=check_inDFA(); int k; while(j!=-1) useof_DFAj=1;for(k=0;knumof_char;k+) U=closure(move(DFAj,alphak); /if U不在DFA中 if(!check_whetherin_DFA(U) U.mark=numof_Dtran;DFAnumof_Dtran+=U; DtranDFAj.markU.mark=alphak;j=check_inDFA();6、 存在的问题及体会 虽然在此之前学习了很多的编程语言，但是对于编程还不是那么熟练。对于此次的编译原理实验，要求用子集构造法来求NFA转换为DFA的算法实现，由于在课上对于本节的知识点掌握的也只是表面，因而要用算法来实现对于我来说还是有些困难。对于此次的程序首先需要实现NFA转换为DFA，其次就是NFA的确定化。这两方面的实现都是有些难度，起初对于程序的实现毫无头绪，之后在同学与老师的讲解下有了相应的了解，然后再在网上查阅相关资料以及相关程序算法的博客，向同学请教，解读别人的算法，加深自己的理解。经过长时间的调试之后，该程序终于得以成功实现。 经过此次的实