编译原理实验有穷自动机.docx

#include<iostream> 
#include<string> 
#include<vector> 
using namespace std; 
#define max 100 
struct edge{ 
string first;//边的初始结点
string change;//边的条件
string last;//边的终点
}; 
int N;//NFA的边数
vector<int> value; //求状态集合I的&-闭包，用&代替“空“
string closure(string a,edge *b) 
{ inti,j; 
for(i=0;i<a.length();i++) 
{ 
for(j=0;j<N;j++) 
{ 
if(b[j].first[0]==a[i]&&b[j].change=="&") 
{ 
a=a+b[j].last[0]; 
} 
} 
} 
return a; 
}  //状态集合I的a弧转换 
string move(string jihe,charch,edge *b) 
{ 
inti,j; 
string s=""; 
for(i=0;i<jihe.length();i++)  
{ 
 for(j=0;j<N;j++)
{ 
if(b[j].first[0]==jihe[i]&&b[j].change[0]==ch) 
s=s+b[j].last; 
} 
} 
return s; 
} 
string sort(string t) 
{ 
intk,i,j; 
chartt; 
for(i=0;i<t.length()-1;i++) 
{ 
k=i; 
for(j=i+1;j<t.length();j++) 
{ 
if(t[j]<t[k])k=j; 
} 
tt=t[k];t[k]=t[i];t[i]=tt; 
} 
return t;
} 
void main() 
{ 
inti,j,x=0,h,length,m,d=0; 
string Change;//输入符号
string First,Last;//初态，终态，
string T[max],ss; 
edge *b=new edge[max]; 
cout<<"请输入各边信息：起点条件（空用&表示）终点，以输入#结束。"<<endl; 
for(i=0;i<max;i++) 
{ 
cin>>b[i].first; 
if(b[i].first=="#")break; 
else 
 cin>>b[i].change>>b[i].last; 
} 
N=i; 
cout<<"请输入该NFA的初态及终态："<<endl; 
cin>>First>>Last; 
cout<<"请输入此NFA状态中的输入符号即边上的条件:"<<endl; 
cin>>Change; 
T[x]=closure(First,b); 
T[x]=sort(T[x]); 
value.push_back(0); 
i=0; 
while(value[i]==0&&value.size()) 
{ 
value[i]=1; 
for(j=0;j<Change.length();j++) 
{ 
ss=""; 
ss=move(T[i],Change[j],b); 
length=value.size(); 

for(h=0;h<length;h++) 
{ 
 if(T[h]==sort(closure(ss,b)))break; 
} 
if(h==length) 
{ 
T[++x]=sort(closure(ss,b)); 
value.push_back(0); 
 }
} 
i++; 
} 
edge *DFA=new edge[max]; 
for(i=0;i<=x;i++)//构造DFA的各边
{ 
for(j=0;j<Change.length();j++) 
{ 
DFA[d].first=T[i]; 
DFA[d].change=Change[j]; 
ss=""; 
ss=sort(closure(move(T[i],Change[j],b),b)); 
for(m=0;m<=x;m++) 
if(ss==T[m])DFA[d++].last=T[m]; 
} 
} 
cout<<"此NFA构造的DFA的各边信息如下："<<endl<<"起点条件终点"<<endl; 
for(i=0;i<d;i++) 
{
for(m=0;m<=x;m++) 
{ 
if(DFA[i].first==T[m])cout<<m<<" "<<DF
A[i].change; 
}
for(m=0;m<=x;m++) 
if(DFA[i].last==T[m])cout<<" "<<m<<endl;; 
} 
cout<<"该DFA的初态为："; 
for(m=0;m<=x;m++) 
{ 
for(j=0;j<T[m].length();j++) 
{ 
ss=T[m]; 
if(ss[j]==First[0])cout<<m<<endl; 

} 
} 
cout<<"该DFA的终态为："; 
for(m=0;m<=x;m++) 
{ 
for(j=0;j<T[m].length();j++) 
{ 
ss=T[m]; 
if(ss[j]==Last[0])cout<<m<<"  "; 
} 
} 
cout<<endl; 
system("pause"); 
}