编译原理报告NFA转DFA详解附源代码Word下载.docx
《编译原理报告NFA转DFA详解附源代码Word下载.docx》由会员分享,可在线阅读,更多相关《编译原理报告NFA转DFA详解附源代码Word下载.docx(15页珍藏版)》请在冰点文库上搜索。
(3)测试数据:
课本P59例4.8
转换前的NFA转换后的DFA
2.设计
(1)数据结构设计
由于FA是一个图,可想到用图的存储结构来存储FA,但是,FA中两个结点之间的路径可以不只一条,这让想考虑用邻接矩阵来存储的FA处理起来有点复杂,我采用的是“结点-边-结点”式的三元组来表示FA。
FA有多少条边就应该有多少个这样的三元组,以一个数组来存放这些三元组,那么一个FA就可以表示出来了。
此外,由子集法的步骤可见,集合(set)这一结构应该使用,,set结构符合我们数学的集合要求,不含相同元素,并且两个集合间还可以进行比较是否相等,十分有利于我们的程序实现。
表示FA的结构:
//Triad(三元组):
S→aB即(S,a,B)
structTriad{
charstart;
charedge;
charend;
};
集合与栈使用库里面的标准集合、栈。
即包含头文件set、stack
(2)文件结构
程序不是很复杂,加之使用到的数据结构是标准库里的,文件只有一个N2D.cpp,其中有#include<
set>
和#include<
starck>
。
(3)程序基本框架概览
structTriad{};
//FA的基本组成结构
intmain(){
初始化工作;
determined();
//确定化
}
e_closure(){}//求ε闭包
move(){}//求集合的x弧转换
determined(){}//确定化
(4)主要函数的实现
伪代码具有简明扼要的特点,利用伪代码子来表示程序流程有利于理解和后续实现。
子集法伪代码:
s0←NFA的开始状态
集合T←e-closure(s0)
把T加入到子集簇C(未标记)
while(集合U←在C中找到一个未标记的集合){
标记U;
for(对于每一种输入即a、b......){
U←e-closure(move(T,a))
if(U不是C的子集)
把U加入到子集簇C(未标记)
有T→aU
}
此外,求ε的传递闭包要利用栈这一数据结构做辅助,其伪代码如下:
//求e-closure(T)的伪代码
将T中的所有状态全都压入栈S、集合U
while(S非空){
t←取栈顶元素;
for(每个从t状态能通过空串转换得到的状态s)
if(s不在U中){
把状态s加入U;
把状态s压入S;
}
returnU;
//集合U即为所求的ε闭包
再在伪代码的基础上来编写这些核心函数就方便多了,具体代码如下:
set<
char>
e_closure(set<
T,TriadG[],intN)//求ε的传递闭包
{
set<
U=T;
//U用来存放T中元素的ε闭包
stack<
S;
//辅助栈
:
iteratorit;
//用于集合遍历的迭代器
for(it=U.begin();
it!
=U.end();
it++)//将U中的元素全部压栈
S.push(*it);
chart;
while(!
S.empty())//栈非空
{
t=S.top();
//栈顶元素
S.pop();
for(inti=0;
i<
N;
i++)//查找元素的ε闭包
{
if(G[i].start==t&
&
G[i].edge=='
*'
)//找到元素的ε闭包
{
U.insert(G[i].end);
//将其放入集合U
S.push(G[i].end);
//将其压栈
}
}
}
returnU;
voiddetermined(TriadG[],intN,char*input,intn){//确定化函数的实现
cout<
<
endl<
"
确定后的DFA:
endl;
boolmarked[MAX_NODES];
//用于标示集合
for(inti=0;
i<
MAX_NODES;
i++)
marked[i]=false;
C[MAX_NODES];
//存放确定化过程中产生的集合
chars0=G[0].start;
T0,T1;
T0.insert(s0);
T1=e_closure(T0,G,N);
//始态的ε闭包
C[0]=T1;
i=0;
while(!
C[i].empty()&
marked[i]==false&
MAX_NODES){
marked[i]=true;
for(intj=0;
j<
n;
j++){
if(input[j]!
='
){
set<
U=e_closure(move(C[i],input[j],G,N),G,N);
if(!
U.empty()){
boolinC=false;
intk=0;
while(!
C[k].empty()&
k<
if(U==C[k]){
inC=true;
break;
}
k++;
}
if(!
inC){
k=0;
while(!
k++;
C[k]=U;
cout<
→"
input[j]<
k<
}
}
}
i++;
//下面求出确定化后的终态
终态为:
;
C[i].empty()){
boolis_final_state=false;
set<
for(it=C[i].begin();
=C[i].end();
it++){
if(*it=='
#'
is_final_state=true;
break;
if(is_final_state)cout<
"
3.调试分析
优点分析:
NFA的输入只要求输入边的条数即可开始输入组成FA的基本结构(即三元组),而有多少引起状态转换的输入都交给程序自己去完成,这一点就显得很简洁,对于用户来说也便捷!
缺点分析:
没有可视化,整个程序的输入输出是通过控制台完成的。
解决方法:
可适宜的使用MFC可视化编程完成(这个有余力可以考虑一下)。
4.用户手册
该程序的使用十分简单,直接按要求输入相应数据就是。
5.测试数据与测试结果
课本P59例4.8:
6.总结
优点通过这次的实习,对编译原理NFA、DFA与之间的等价转换有了更加深刻的理解,也学会了利用伪代码来设计程序,由框架到细节的实现,这种设计相当便利高效。
团队成员之间交流思想取长补短也让我学到了好多思想和方法。
7.源代码
#include<
stack>
iostream>
usingnamespacestd;
Triad[],int);
move(set<
char,Triad[],int);
voiddetermined(Triad[],int,char*,int);
constintMAX_NODES=20;
intmain()
intN;
请输入边数:
cin>
>
Triad*G=newTriad[N];
请输入正规文法(*代表ε,#代表终态,约定输入时先输入以始态开始的三元组):
i++){
cin>
G[i].start>
G[i].edge>
G[i].end;
Edge;
for(intj=0;
Edge.insert(G[j].edge);
intn=Edge.size();
char*input=newchar[n];
j=0;
for(it=Edge.begin();
=Edge.end();
input[j]=*it;
j++;
determined(G,N,input,n);
return0;
T,TriadG[],intN)
it++)
S.empty())
i++)
)
I,chara,TriadG[],intN){
U;
for(it=I.begin();
=I.end();
for(inti=0;
if(G[i].start==*it&
G[i].edge==a)
returnU;
voiddetermined(TriadG[],intN,char*input,intn){
//下面被注释代码可用于输出图中求出来的集合
/*
cout<
*it<
*/
"