#include<iostream> #include<string.h> using namespace std; class grammer { private: int flag;//判别是NFA还是DFA的标识符 char K[50];//有穷非空状态集合 char E[50];//有穷非空的输入字母表 char str[50];//存放待识别的字符串 char ch[20][20];//存放从 K*E到 K的映射 public: char**p; //数组指针 int line; //确定行的位置 int m;//要识别的字符串长度 int VN;//控制非终结符号输出的变量 int VT;//控制终结符号输出的变量 int i,j; grammer() //构造函数 { int i; line=0; cout<<"输入要输入文法的个数："<<endl; int n; //文法个数 cin>>n; line=n; //每输入一个规则，行作相应的变动 p=new char*[n]; //申请空间，用来存放规则 for(i=0;i<n;i++) for(i=0;i<n;i++) { p[i]=new char[50]; //用来存放第i个规则 } for( i=0;i<line;i++) for(int j=0;j<50;j++) //将所用的字符都用‘ ’字符填充 p[i][j]=' '; //清空位置，用来存放文法 cout<<"输入文法："<<endl; for( i=0;i<n;i++) //按行输入每一个文法规则 { cin>>p[i]; } for( i=0;i<20;i++) { for(int j=0;j<20;j++) { ch[i][j]=' ';//将存放映射的数组初始化 } } } //求出有穷非空的输入字母表 void zhongjie() { VT=0; for(int i=0;i<line;i++) for(int j=0;j<6;j++) { char temp=p[i][j]; if(!((temp>='A'&&temp<='Z'||temp==':'||temp=='='||temp==' ')) { bool state=true; for(int k=0;k<VT;k++) { if(temp==E[k]) {state=false;break;} } if(state=true) E[VT++]=temp; } } } //求出有穷非空的状态集合 void Search_big() { VN=0; for(int i=0;i<line;i++) for(int j=0;j<6;j++) { char temp=p[i][j]; if(temp>='A'&&temp<='Z') { bool state=true; for(int k=0;k<VN;k++) { if(temp==K[k]) {state=false;break;} } if(state=true) K[VN++]=temp; } } } //输入待识别的字符串 void string() { for(i=0;i<50;i++) { str[i]=' '; } cout<<"请输入要识别的字符串长度: "; cin>>m; cout<<endl; cout<<"请输入要识别的字符串: "; for(i=0;i<m;i++) { cin>>str[i]; } } //输出待识别的字符串 void print_s() { for(int k=0;k<m;k++) { cout<<str[K]; } cout<<")"; } //识别字符串 void shibie() { int count=0; char G='S'; print_1(); Search_big(); for(i=0;i<m;i++) { while(str[i]!=' ') { for(j=0;j<line;j++) { if(G==ch[j][2]&&str[i]==ch[j][4]) { G=ch[j][7]; if(G==K[0]) { cout<<"="; for(int s=0;s<6;s++) { cout<<ch[j][s]; } cout<<"="<<G; cout<<endl; break; } else { cout<<"="<<"M"<<"("; for(int s=0;s<6;s++) { cout<<ch[j][s]; } } int length=m; for(int t=0;t<length;t++) { str[t]=str[t+1]; } length--; cout<<","; for(int q=0;q<length;q++) { cout<<str[q]; } cout<<")"; cout++; } } } if(count==m) { cout<<"该文法可被识别!"; break; } else { cout<<"该文法不可被识别!"; break; } } } //输出映射集合 void print_1() { for(i=0;i<line;i++) { ch[i][0]='M'; ch[i][1]='('; ch[i][3]=','; ch[i][5]=')'; ch[i][6]='='; if((if((p[i][4]>='A'&&p[i][4]<='Z')&&(p[i][5]>='a'&&p[i][5]<='z')) { ch[i][2]=p[i][4];ch[i][4]=p[i][5];ch[i][7]=p[i][0]; } else if((p[i][4]>='a'&&p[i][4]<='z')&&(p[i][5]>='A'&&p[i][5]<='Z')) { ch[i][2]=p[i][5];ch[i][4]=p[i][4];ch[i][7]=p[i][0]; } else { ch[i][2]='S';ch[i][4]=p[i][4];ch[i][7]=p[i][0]; } } } //转换过程 void print_2() { print_1(); for(i=0;i<line;i++) { int x=8; for(int j=i+1;j<line;j++) { if(ch[i][2]==ch[j][2]&&ch[i][4]==ch[j][4]) { ch[i][x]=ch[j][7]; x++; for(int K1=j;K1<line;K1++) for(int K2=0;K2<=7;K2++) ch[K1][K2]=ch[K1+1][K2]; line--; } else break; } } } void print_D() { print_1(); cout<<"M:"<<endl; for(i=0;i<line;i++) { for(j=0;j<=7;j++) { cout<<ch[i][j]; if(j==7) cout<<endl; } } } void print_N() { print_2(); cout<<"M:"<<endl; for(i=0;i<line;i++) { for(j=0;j<7;j++) { cout<<ch[i][j]; } cout<<"{"; for(j=7;j<strlen(ch[i]);j++) {cout<<ch[i][j];} cout<<"}"<<endl; } } void print()//输出五元组 { Search_big(); cout<<"DFA N={{"<<"S"<<","; for(int i=0;i<VN-1;i++) { cout<<K[i]; cout<<","; } cout<<K[VN-1]; cout<<"}"<<","; zhongjie(); cout<<"}"; for(int j=0;j<VT-1;j++) { cout<<E[j]; cout<<','; } cout<<E[VT-1]; cout<<"}";<<","; cout<<"M"<<","; cout<<"S"<<","; cout<<"{"<<K[0]<<"}"<<")"<<endl; } void Identify() { for(i=0;i<=line-1;i++) { for(j=i+1;j<=line;j++) { char templ=p[i][4]; char temp2=p[i][5]; char temp3=p[j][4]; char temp4=p[j][5]; if(temp1==temp3&&temp2==temp4) { cout<<"该有穷状态自动机是NFA. "; print_N(); break; } else { cout<<"该有穷状态自动机是DFA. "; print_D(); break; } } } } }; int main() { grammer a; cout<<"----------------------------------------- "; cout<<"正规文法构造有穷状态自动机! "; cout<<"----------------------------------------- "; cout<<"输入完成，输出有穷状态自动机(五元组):"<<endl; cout<<endl; a.print(); a.Identify(); cout<<endl<<endl; cout<<"----------------------------------------- "; cout<<"运行有穷状态自动机! "; cout<<"----------------------------------------- "; a.string(); cout<<"有穷状态自动机DFA识别过程如下: "; cout<<"M"<<"("<<"S"<<","; a.print_s(); a.shibie(); system("pause"); }
运行结果：
