编译原理报告NFA转DFA详解附源代码.doc

编译原理实习报告

学号：******
班级：******
姓名：******
日期：2015

目录

1. 题目及需求分析……………………………………………3
2. 设计分析……………………………………………………3
3. 调试分析……………………………………………………7
4. 用户手册……………………………………………………7
5. 测试结果……………………………………………………7
6. 总结…………………………………………………………7
7. 源代码………………………………………………………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 转换后的DFA
2．设计
（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、集合U
while(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 (G[i].start== t && G[i].edge=='*') //找到元素的ε闭包
{
U.insert(G[i].end); //将其放入集合U
S.push(G[i].end); //将其压栈
}
}
}
return U;
}

void determined(Triad G[], int N, char* input, int n){ //确定化函数的实现
cout<<endl<<"确定后的DFA:"<<endl;
bool marked[MAX_NODES]; //用于标示集合
for(int i=0; i<MAX_NODES; i++)
marked[i]=false;
set<char> C[MAX_NODES]; //存放确定化过程中产生的集合
char s0=G[0].start;
set<char> T0,T1;
T0.insert(s0);
T1=e_closure(T0, G, N); //始态的ε闭包
C[0]=T1;
i=0;
while(!C[i].empty() && marked[i]==false && i<MAX_NODES){
marked[i]=true;
for(int j=0; j<n; j++){
if(input[j] != '*'){
set<char> U=e_closure(move(C[i], input[j], G, N), G, N);
if(!U.empty()) {
bool inC=false;
int k=0;
while(!C[k].empty() && k<MAX_NODES){
if(U==C[k]){
inC=true;
break;
}
k++;
}
if(!inC){
k=0;
while(!C[k].empty() && k<MAX_NODES){
k++;
}
C[k]=U;
}
cout<<i<<"→"<<input[j]<<k<<endl;
}
}
}
i++;
}
//下面求出确定化后的终态
cout<<"终态为:";
i=0;
while(!C[i].empty()){
bool is_final_state=false;
set<char>::iterator it;
for (it = C[i].begin(); it != C[i].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 Triad{
char 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 Triad[N];
cout<<"请输入正规文法(*代表ε,#代表终态,约定输入时先输入以始态开始的三元组):"<<endl;
for(int i=0; i<N; i++){
cin>>G[i].start>>G[i].edge>>G[i].end;
}

set<char> Edge;
for(int j=0; j<N; j++){
Edge.insert(G[j].edge);
}

int n=Edge.size();
char* input=new char[n];
set<char>::iterator it;
j=0;
for (it = Edge.begin(); it != Edge.end(); it++){
input[j]=*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 (G[i].start== t && G[i].edge=='*')
{
U.insert(G[i].end);
S.push(G[i].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 (G[i].start== *it && G[i].edge==a)
U.insert(G[i].end);
}
return U;

}

void determined(Triad G[], int N, char* input, int n){
cout<<endl<<"确定后的DFA:"<<endl;
bool marked[MAX_NODES];
for(int i=0; i<MAX_NODES; i++)
marked[i]=false;
set<char> C[MAX_NODES];

char s0=G[0].start;
set<char> T0,T1;
T0.insert(s0);
T1=e_closure(T0, G, N);
C[0]=T1;

i=0;
while(!C[i].empty() && marked[i]==false && i<MAX_NODES){
marked[i]=true;
//下面被注释代码可用于输出图中求出来的集合
/*
set<char>::iterator it;
cout<<i<<":";
for (it = C[i].begin(); it != C[i].end(); it++)
cout<<*it<<",";
cout<<endl;
*/
for(int j=0; j<n; j++){
if(input[j] != '*'){
set<char> U=e_closure(move(C[i], input[j], G, N), G, N);
if(!U.empty()) {
bool inC=false;
int k=0;
while(!C[k].empty() && k<MAX_NODES){
if(U==C[k]){
inC=true;
break;
}
k++;
}

if(!inC){
k=0;
while(!C[k].empty() && k<MAX_NODES){
k++;
}
C[k]=U;
}
cout<<i<<"→"<<input[j]<<" "<<k<<endl;
}
}
}
i++;
}

//下面求出确定化后的终态
cout<<"终态为:";
i=0;
while(!C[i].empty()){
bool is_final_state=false;
set<char>::iterator it;
for (it = C[i].begin(); it != C[i].end(); it++){
if(*it == '#'){
is_final_state=true;
break;
}
}
if(is_final_state) cout<<i<<",";
i++;
}
cout<<endl;

}