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

编译原理实验报告实验名称 正则表达式与有限自动机院 系 信息工程学院 班 级 计算机科学与技术1班 学 号 姓 名 朱义 1、 实验目的通过本次实验，加深对正则表达式，NFA，DFA及其识别的语言的理解二、实验题目编程实现NFA确定化为NFA的过程3、 算法思想1. 一个自动机是一个五元组，分别是2. 使用子集法的步骤是：1) 将起始状态求闭包，得到S0。2) 从0开始直到totss对每个子集求各个字符所能到达的新子集将其加入tot+1子集中。3) 检查tot+1子集是否与之前的子集重合或者为空,如果重合或为空则子集不增加。4) 记录新的状态转换函数。3. 根据NFA转化为DFA的过程一步步模拟进行操作。4、 数据结构介绍程序里将NFA五元组分别储存在以下数据结构里初态集储存在 int数组 sta_statumaxs里 maxs为元素的最大数终态集储存在 int数组 end_statumaxs里字符集储存在 char数组 chamaxs里状态储存为0n-1（n个状态情况）状态转换函数储存于结构 stuct statu里struct Edge /转化边 char cost; /消耗 int dest; /指向的终点;struct statu Edge node50; / 终点 int cnt;/边的数量 statu() cnt=0; for(int i=0;i50;i+) nodei.cost=#; nodei.dest=0; sta50;/起点5、 具体实现使用子集法实现：函数接口解释： 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) 检查子集closurett是否与之前的子集重合，为空则返回-2，不重合返回-1，重合则返回重合的子集下标。void print(void) 输出DFA的五元组信息。 1.将起始状态求闭包，得到S0。 将初状态里所有的元素及其能通过e空路所到的状态加入closure0作为初始子集 for(int i=0;ict_sta_statu;i+) / 求起始状态求闭包，得到S0 closure0.members.insert(sta_statui); ins(0,sta_statui); / e_closure(s0)2.从0开始直到totss对每个子集求各个字符所能到达的新子集将其加入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所能到达的所有状态，并将这些状态加入到子集closurea里。 for(int i=0;t;i+) if(stabeg.nodei.cost = target) closurea.members.insert(stabeg.nodei.dest); ins(a,stabeg.nodei.dest);/求出这些状态后用dfs求其能经过空路所到达的状态也加入closurea return ; 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; /为空则返回-2 set:iterator isa,isb; for(int i=0;itt;i+) isb=closurett.members.begin(); if(closurett.members.size()=closurei.members.size() for(isa=closurei.members.begin();isa!=closurei.members.end();isa+) if(*isa!=*isb) break; else isb+; if(isb=closurett.members.end() return i; /重合则返回之前相同的子集的下标 return -1;/不重合返回-14.记录新的状态转换函数 if(ok=-2)/新子集为空 ; else if(ok=-1) /与之前的子集不重合，记录新状态转换函数 totss+; t.cost=chaj; t+.dest=totss; else/与之前的子集重合，记录新状态转换函数 closuretotss+1.members.clear(); t.cost=chaj; t+.dest=ok; 5.输出DFA信息六、设计过程中的问题与对策NFA转化为DFA的过程中最难解决的是如何储存状态转换函数以及记录新的状态转换函数的问题，我开始设计为一个二维数组，实际应用时发现当NFA中一个字符对应两个目标时前一个目标会被覆盖。于是再仔细观察NFA的特点，多个初态，多个终态，一个状态经一个字符可对应多个状态。设计了一种新的储存结构，因为每个NFA相当于一个有向图。用一个结