NFA转化为DFA编译原理实验报告.docx
《NFA转化为DFA编译原理实验报告.docx》由会员分享，可在线阅读，更多相关《NFA转化为DFA编译原理实验报告.docx（9页珍藏版）》请在冰点文库上搜索。
编译原理实验报告
实验名称 正则表达式与有限自动机
院系信息工程学院
班级计算机科学与技术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;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所能到达的所有状态，并将这些状态加入到子集closure[a]里。
intcheck（inttt）检查子集closure[tt]是否与之前的子集重合，为空则返回-2，不重合返回-1，重合则返回重合的子集下标。
voidprint（void）输出DFA的五元组信息。
1.将起始状态求闭包，得到S0。
将初状态里所有的元素及其能通过e空路所到的状态加入closure[0]作为初始子集
for（inti=0;i {
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;jfor（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;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;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;//为空则返回-2
set:
:
iteratorisa,isb;
for（inti=0;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的转化过程中遇到了许多困难，让我不断地去查阅资料，增长了自己的知识，丰富了自己的实践经验。
升级会员 