编译原理报告：NFA转DFA(详解-附源代码)(共11页).doc
精选优质文档-倾情为你奉上编译原理实习报告学号：*班级：*姓名：*日期：2015目录1. 题目及需求分析32. 设计分析33. 调试分析74. 用户手册75. 测试结果76. 总结77. 源代码8题目：NFA转换为等价的DFA实习时间：2015.10.12【问题描述】以定理“设L为一个由不确定的有穷自动机接受的集合，则存在一个接受L的确定的有穷自动机”为理论基础，设计算法实现将不确定的有穷自动机(NFA)转换为与之等价的确定的有穷自动机(DFA)。【基本要求】 确定能够表示FA的合适的结构，以便FA的输入和输出 设计的算法既要成功实现题目要求的功能，又要高效、鲁棒 程序中的函数、变量等命名要规则，可读性要强(易懂)1 需求分析(1) 要将以状态转换图表示的NFA转换为DFA，首先应设计一个结构来表示FA，以便图形式的FA便于输入和输出。(2) 设计合适的算法来实现NFA的确定化，这里用子集法来构造等价的DFA。(3) 测试数据:课本P59例4.8 转换前的NFA 转换后的DFA2设计（1） 数据结构设计由于FA是一个图，可想到用图的存储结构来存储FA，但是，FA中两个结点之间的路径可以不只一条，这让想考虑用邻接矩阵来存储的FA处理起来有点复杂，我采用的是“结点-边-结点”式的三元组来表示FA。FA有多少条边就应该有多少个这样的三元组，以一个数组来存放这些三元组，那么一个FA就可以表示出来了。此外，由子集法的步骤可见，集合(set)这一结构应该使用，set结构符合我们数学的集合要求，不含相同元素，并且两个集合间还可以进行比较是否相等，十分有利于我们的程序实现。表示FA的结构：/Triad(三元组)：S aB即（S,a,B）struct Triad char start; char edge; char end;集合与栈使用库里面的标准集合、栈。即包含头文件set、stack（2） 文件结构程序不是很复杂，加之使用到的数据结构是标准库里的，文件只有一个N2D.cpp，其中有#include<set>和#include<starck>。（3） 程序基本框架概览 struct Triad ; / FA的基本组成结构int main() 初始化工作； 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、集合Uwhile(S非空) t 取栈顶元素; for(每个从t状态能通过空串转换得到的状态s) if(s不在U中) 把状态s加入U; 把状态s压入S; return U; /集合U即为所求的闭包 再在伪代码的基础上来编写这些核心函数就方便多了，具体代码如下：set<char> e_closure(set<char> T, Triad G, int N) /求的传递闭包 set<char> U = T; /U用来存放T中元素的闭包stack<char> S; /辅助栈set<char>:iterator it; /用于集合遍历的迭代器for (it = U.begin(); it != U.end(); it+) /将U中的元素全部压栈S.push(*it); char t; while (!S.empty() /栈非空 t = S.top(); /栈顶元素S.pop(); for (int i=0;i<N;i+) /查找元素的闭包 if (Gi.start= t && Gi.edge='*') /找到元素的闭包 U.insert(Gi.end); /将其放入集合US.push(Gi.end); /将其压栈 return U; void determined(Triad G, int N, char* input, int n) /确定化函数的实现cout<<endl<<"确定后的DFA:"<<endl;bool markedMAX_NODES; /用于标示集合for(int i=0; i<MAX_NODES; i+)markedi=false;set<char> CMAX_NODES; /存放确定化过程中产生的集合char s0=G0.start;set<char> T0,T1;T0.insert(s0); T1=e_closure(T0, G, N); /始态的闭包C0=T1;i=0;while(!Ci.empty() && markedi=false && i<MAX_NODES)markedi=true;for(int j=0; j<n; j+)if(inputj != '*')set<char> U=e_closure(move(Ci, inputj, G, N), G, N);if(!U.empty() bool inC=false;int k=0;while(!Ck.empty() && k<MAX_NODES)if(U=Ck)inC=true;break;k+;if(!inC)k=0;while(!Ck.empty() && k<MAX_NODES)k+;Ck=U;cout<<i<<""<<inputj<<k<<endl;i+;/下面求出确定化后的终态cout<<"终态为:"i=0;while(!Ci.empty()bool is_final_state=false;set<char>:iterator it;for (it = Ci.begin(); it != Ci.end(); it+)if(*it = '#')is_final_state=true;break; if(is_final_state) cout<<i<<","i+;cout<<endl;3 调试分析优点分析：NFA的输入只要求输入边的条数即可开始输入组成FA的基本结构(即三元组)，而有多少引起状态转换的输入都交给程序自己去完成，这一点就显得很简洁，对于用户来说也便捷！缺点分析：没有可视化，整个程序的输入输出是通过控制台完成的。解决办法：可合适的使用MFC可视化编程完成(这个有余力可以考虑一下)。4 用户手册 该程序的使用十分简单，直接按要求输入相应数据就是。5 测试数据及测试结果 课本P59例4.8：6 总结优点通过这次的实习，对编译原理NFA、DFA及之间的等价转换有了更加深刻的理解，也学会了利用伪代码来设计程序，由框架到细节的实现，这种设计相当便利高效。团队成员之间交流思想取长补短也让我学到了好多思想和方法。7.源代码#include<set> #include<stack> #include<iostream> using namespace std; /Triad(三元组)：S aB即（S,a,B）struct Triadchar start;char edge;char end;set<char> e_closure(set<char>, Triad, int) ;set<char> move(set<char>, char, Triad, int);void determined(Triad , int, char*, int);const int MAX_NODES=20;int main() int N;cout<<"请输入边数:"<<endl;cin>>N;Triad* G=new TriadN;cout<<"请输入正规文法(*代表,#代表终态,约定输入时先输入以始态开始的三元组):"<<endl;for(int i=0; i<N; i+)cin>>Gi.start>>Gi.edge>>Gi.end;set<char> Edge;for(int j=0; j<N; j+)Edge.insert(Gj.edge);int n=Edge.size();char* input=new charn;set<char>:iterator it;j=0;for (it = Edge.begin(); it != Edge.end(); it+)inputj=*it;j+;determined(G, N, input, n);return 0; set<char> e_closure(set<char> T, Triad G, int N) set<char> U = T; stack<char> S; set<char>:iterator it;for (it = U.begin(); it != U.end(); it+) S.push(*it); char t; while (!S.empty() t = S.top();S.pop(); for (int i=0;i<N;i+) if (Gi.start= t && Gi.edge='*') U.insert(Gi.end); S.push(Gi.end); return U; set<char> move(set<char> I, char a, Triad G, int N)set<char> U;set<char>:iterator it;for (it = I.begin(); it != I.end(); it+) for(int i=0; i<N; i+)if (Gi.start= *it && Gi.edge=a)U.insert(Gi.end);return U; void determined(Triad G, int N, char* input, int n)cout<<endl<<"确定后的DFA:"<<endl;bool markedMAX_NODES;for(int i=0; i<MAX_NODES; i+)markedi=false;set<char> CMAX_NODES;char s0=G0.start;set<char> T0,T1;T0.insert(s0);T1=e_closure(T0, G, N);C0=T1;i=0;while(!Ci.empty() && markedi=false && i<MAX_NODES)markedi=true;/下面被注释代码可用于输出图中求出来的集合/*set<char>:iterator it;cout<<i<<":"for (it = Ci.begin(); it != Ci.end(); it+) cout<<*it<<","cout<<endl;*/for(int j=0; j<n; j+)if(inputj != '*')set<char> U=e_closure(move(Ci, inputj, G, N), G, N);if(!U.empty() bool inC=false;int k=0;while(!Ck.empty() && k<MAX_NODES)if(U=Ck)inC=true;break;k+;if(!inC)k=0;while(!Ck.empty() && k<MAX_NODES)k+;Ck=U;cout<<i<<""<<inputj<<" "<<k<<endl;i+;/下面求出确定化后的终态cout<<"终态为:"i=0;while(!Ci.empty()bool is_final_state=false;set<char>:iterator it;for (it = Ci.begin(); it != Ci.end(); it+)if(*it = '#')is_final_state=true;break; if(is_final_state) cout<<i<<","i+;cout<<endl;专心-专注-专业
