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

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

2、函数。3. 根据 NFA 转化为 DFA 的过程一步步模拟进行操作。四、数据结构介绍程序里将 NFA 五元组分别储存在以下数据结构里初态集储存在 int 数组 sta_statumaxs 里 maxs 为元素的最大数终态集储存在 int 数组 end_statumaxs 里字符集储存在 char 数组 chamaxs 里状态储存为 0n-1 ( n 个状态情况)状态转换函数储存于结构 stuct statu 里struct Edge /转化边char cost;/ 消耗int dest;/ 指向的终点;struct statuEdge node50; / 终点int cnt;/ 边的数量sta

3、tu()cnt=0;for(int i=0;i50;i+)nodei.cost=#;nodei.dest=0;sta50;/ 起点五、具体实现使用子集法实现：函数接口解释：void creat_subset(void); 构造子集函数Ins(int a,int ss) 用深搜( dfs )求状态 ss 的闭包，并将闭包里的所有元素加入到子集 closurea 里。void ins_subset(int a,int ss,char target)求状态 ss 通过字符 target 所能到达的所有状态，并将这些状态加入到子集 closurea 里。int check(int tt) 检查子集 c

4、losurett 是否与之前的子集重合， 为空则返回 -2 ，不重合返 回-1，重合则返回重合的子集下标。void print(void) 输出 DFA 的五元组信息。1. 将起始状态求闭包，得到 S0 。将初状态里所有的元素及其能通过 e 空路所到的状态加入 closure0 作为初始子 集for(int i=0;ict_sta_statu;i+)/ 求起始状态求闭包，得到 S0closure0.members.insert(sta_statui);ins(0,sta_statui); / e_closure(s0)2. 从 0 开始直到 totss 对每个子集求各个字符所能到达的新子集将其

5、加入tot+1 子集中。表示当前运算的状态下表for(tempss=0;tempss=totss;tempss+)/tempss totss 表示总共的状态数 新生产的状态子集加入到 closurtot+1 中for(int j=0;jct_cha;j+)for(it=closuretempss.members.begin();it!=closuretempss.members.end();it+)ins_subset(totss+1,*it,chaj);void ins_subset(int a,int beg,char target)/ 求状态 ss 通过字符 target 所能到达的所有

6、 状态，并将这些状态加入到子集 closurea 里。for(int i=0;t;i+)if(stabeg.nodei.cost = target)closurea.members.insert(stabeg.nodei.dest);ins(a,stabeg.nodei.dest);求出这些状态后用 dfs求其能经过&空路所到达的状态也加入 closureareturn ;void ins(int a,int beg)/ 求集合的& 闭包for(int i=0;t;i+)if(stabeg.nodei.cost=#)closurea.members.insert(stabeg.nodei.dest); ins(a,stabeg.nodei.dest);3. 检查 tot+1 子集是否与之前的子集重合或者为空,如果重合或为空则子集不增加int check(int tt)if(closurett.members.empty()return -2;/为空则返回 -2set:iterator isa,isb;for(int i=0;i execution time : 3H.181 s ress any ke to cantinue八、实验总结这次实验