- 1 -实验三词法分析——有穷自动机的应用实验目的:一:输入正则文法二:FA1.生成FA(DFA或NFA)2.运行FA,DFA(自动);NFA(交互)3.**NFA→DFA实验设想:对输入的文法存储并判断是确定的有穷状态自动机还是不确定是有穷状态自动机,并给出标准的表示形式,若是DFA,可直接测试一个符号串是否是文法的句子,即能否被有穷状态机接受,给出过程及结果;若是NFA,首先将其转化为DFA,再测试一个符号串是否是文法的句子,亦即是否能被DFA接受。
例如:输入文法规则的数目:7输入开始状态: S输入文法Z::=Za Z::=Bb Z::=Aa B::=Ab B::=b A::=Ba A::=a此为确定有穷状态自动机!DFA D=({Z,A,B},{a,b},M,S,{Z}) 其中M:M(Z,a)=ZM(B,b)=ZM(B,a)=AM(A,a)=ZM(A,b)=BM(S,b)=BM(S,a)=A输入要推导的符号串:ababaaM(S,ababaa)=M(M(S,a),babaa)=M(A,babaa)=M(M(A,b),abaa)=M(B,abaa)=M(M(B,a),baa)=M(A,baa)=M(M(A,b),aa)=M(B,aa)=M(M(B,a),a)=M(A,a)- 1 -=Z该符号串能被有穷状态所接受!输入文法规则的数目:7输入开始状态: S输入规则:Z::=Ab Z::=Ba Z::=Zc A::=Ba A::=a B::=Ab B::=b 文法规则存储完毕!此为非确定有穷状态自动机!NFA N=({Z,B,A},{b,a,c},M,{S},{Z})其中M:M(A,a)=$M(A,b)={Z,B}M(A,c)=$M(B,a)={Z,A}M(B,b)=$M(B,c)=$M(Z,a)=$M(Z,b)=$M(Z,c)={Z}M(S,a)={A}M(S,b)={B}M(S,c)=$将NFA转化为DFA!DFA N'=({[S],[B],[A],[AZ],[BZ],[Z]},{[b],[a],[c]}, M',[S],F') 其中M':M'([S],b)=[B]M'([S],a)=[A]M'([B],a)=[AZ]M'([A],b)=[BZ]M'([AZ],b)=[BZ]M'([AZ],c)=[Z]M'([BZ],a)=[AZ]M'([BZ],c)=[Z]M'([Z],c)=[Z]其中F'={[AZ],[BZ],[Z]} 输入要推导的字符串:ababc M'([S],ababc)=M'(M'([S],a),babc)=M'([A],babc)=M'(M'([A],b),abc)=M'([BZ],abc)=M'(M'([BZ],a),bc)=M'([AZ],bc)=M'(M'([AZ],b),c)=M'([BZ],c)=[Z][Z]属于终止状态集合!该字符串能被有穷状态所接受!参考程序#include<iostream.h>#include<String.h>struct LeftItem;struct RightNode //存储状态转换关系中弧与终止状态结点结构{char tran;char nextstate;RightNode* nextsibling;RightNode(char x,char y){tran=x; nextstate=y; nextsibling=NULL;}};struct LeftItem //存储状态转换关系中初始状态结点结构{char state;RightNode* link;};struct StateItem //存放确定化的NFA状态结点结构{char newstates[10];StateItem(){newstates[0]='\0';}};/////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// /// int CheckState(LeftItem Array[],int size){RightNode* p;RightNode* q;for(int i=0;i<size;i++){p=Array[i].link;q=p->nextsibling;if(q==NULL) return 1;while(q!=NULL){if(p->tran==q->tran) return 0;q=q->nextsibling;}}return 1;}int CheckExist(StateItem SArray[],int& length,char temp[])//将NFA确定化创建二维矩阵时判别新产生的状态是否在状态数组中存储过{ int i=0,k,m;while(i<=length){if(strlen(SArray[i].newstates)==strlen(temp)) {if(strcmp(SArray[i].newstates,temp)==0){k=i;break;}}i++;}if(i>length){length++;m=length;return m;}elsereturn k;}int getcount1(LeftItem Array[],int size) //取得FA中状态的个数{ char temp[20];int len=0,count=0;int i,j;RightNode* pNode;for(i=0;i<size;i++){pNode=Array[i].link;while(pNode){for(j=0;j<len;j++)if(pNode->nextstate==temp[j]) break;if(j==len){count++;temp[len]=pNode->nextstate;len++;}pNode=pNode->nextsibling;}}return count;}int getcount2(LeftItem Array[],int size) //取得FA中输入字母的个数{ char temp[20];int len=0,count=0;int i,j;RightNode* pNode;for(i=0;i<size;i++){pNode=Array[i].link;while(pNode){for(j=0;j<len;j++)if(pNode->tran==temp[j]) break;if(j==len){count++;temp[len]=pNode->tran;len++;}pNode=pNode->nextsibling;}}return count;}int getstate(RightNode* pNode,char arc) //判定一个状态是否能通过一条弧进入下一状态{while(pNode){if(pNode->tran==arc) return 1;pNode=pNode->nextsibling;}return 0;}void Sort(char A[],int n) //将取得的新状态进行排序{for(int i=n-1;i>0;i--)for(int j=0;j<i;j++){if(A[j+1]<A[j]){char temp=A[j+1];A[j+1]=A[j];A[j]=temp;}}}void Bianli1(LeftItem Array[],int size) //输出FA中有穷非空的状态集合{char temp[20];int len=0;int i,j;RightNode* pNode;for(i=0;i<size;i++){pNode=Array[i].link;while(pNode){for(j=0;j<len;j++)if(pNode->nextstate==temp[j]) break;if(j==len){if(len==0) cout<<pNode->nextstate;elsecout<<","<<pNode->nextstate;temp[len]=pNode->nextstate;len++;}pNode=pNode->nextsibling;}}}void Bianli2(LeftItem Array[],int size) //输出FA中有穷的输入字母表{char temp[20];int len=0;int i,j;RightNode* pNode;for(i=0;i<size;i++){pNode=Array[i].link;while(pNode){for(j=0;j<len;j++)if(pNode->tran==temp[j]) break; if(j==len){if(len==0) cout<<pNode->tran; elsecout<<","<<pNode->tran;temp[len]=pNode->tran;len++;}pNode=pNode->nextsibling;}}}void Bianli31(LeftItem Array[],int size)//输出DFA状态转换关系的集合M{int i;RightNode* pNode;for(i=0;i<size;i++){pNode=Array[i].link;while(pNode!=NULL){cout<<" M("<<Array[i].state<<","<<pNode->tran <<")="<<pNode->nextstate<<endl;pNode=pNode->nextsibling;}}}void Bianli32(LeftItem Array[],int size) //输出NFA状态转换关系集合M {char K[20];int len=0;int i,j;RightNode* pNode;RightNode* qNode;for(i=0;i<size;i++){pNode=Array[i].link;while(pNode){for(j=0;j<len;j++)if(pNode->tran==K[j]) break;if(j==len){K[len]=pNode->tran;len++;}pNode=pNode->nextsibling;}}Sort(K,len);for(i=0;i<size;i++){for(j=0;j<len;j++){pNode=Array[i].link;cout<<" M("<<Array[i].state<<","<<K[j]<<")="; if(getstate(pNode,K[j])){cout<<"{";while(pNode){if(pNode->tran==K[j]){qNode=pNode->nextsibling; cout<<pNode->nextstate; break;}pNode=pNode->nextsibling;}while(qNode){if(qNode->tran==K[j])cout<<","<<qNode->nextstate; qNode=qNode->nextsibling;}cout<<"}"<<endl;}elsecout<<"$"<<endl;}}}void Initiate(LeftItem Array[],int size,char TArray[]) //将FA中的输入字母表存入数组TArray[] {int len=0;int i,j;RightNode* pNode;for(i=0;i<size;i++){pNode=Array[i].link;while(pNode){for(j=0;j<len;j++)if(pNode->tran==TArray[j]) break;if(j==len){TArray[len]=pNode->tran;len++;}pNode=pNode->nextsibling;}}}void GetState(LeftItem Array[],int size,char nstate[],char arc,char temp[])//将NFA确定化创建二维矩阵时取得新状态{int i=0;while(nstate[i]!='\0'){for(int j=0;j<size;j++){if(Array[j].state==nstate[i]) {RightNode* p=Array[j].link; while(p!=NULL){if(p->tran==arc){int k=0;while(temp[k]!='\0'){if(p->nextstate==temp[k]) break; k++;}if(temp[k]=='\0'){temp[k]=p->nextstate;temp[k+1]='\0';}}p=p->nextsibling;}}}i++;}}void Change(StateItem SArray[],char temp[],int& length,intMArray[][20],int index,int i) //取得新状态后对状态数组以及状态转换矩阵进行对应变化{int k;if(temp[0]!='\0'){k=CheckExist(SArray,length,temp);MArray[index][i]=k;if(k==length)strcpy(SArray[length].newstates,temp);}}char FindNewState(LeftItem Array[],int size,char S,char arc) //得到当前状态的下一状态{int i;for(i=0;i<size;i++){if(Array[i].state==S){RightNode* p=Array[i].link;while(p!=NULL){if(p->tran==arc) return p->nextstate;p=p->nextsibling;}}}return NULL;}int Findy(char TArray[],char s) //取得输入字母在字母表中的下表{ int i=0;while(TArray[i]!='\0'){if(TArray[i]==s) return i;i++;}}void CreateFA1(LeftItem Array[],int size,char start,char end) //根据输入文法创建FA{if(CheckState(Array,size)){cout<<"此为确定有穷状态自动机!"<<endl; cout<<"DFA D=(";}else{cout<<"此为非确定有穷状态自动机!"<<endl; cout<<"NFA N=(";}cout<<"{";Bianli1(Array,size);cout<<"},{";Bianli2(Array,size);cout<<"},M,";if(CheckState(Array,size)) cout<<start; else cout<<"{"<<start<<"}";cout<<","<<"{"<<end<<"})"<<endl;cout<<"其中M:"<<endl;if(CheckState(Array,size))Bianli31(Array,size);elseBianli32(Array,size);}void CreateFA2(LeftItem Array[],int size,char start,charend,StateItem SArray[],char TArray[],int& length,int MArray[][20]) //将NFA转换为DFA{char temp[20];int index=0;int i;do{i=0;while(TArray[i]!='\0'){temp[0]='\0';GetState(Array,size,SArray[index].newstates,TArray[i],temp);Sort(temp,strlen(temp));Change(SArray,temp,length,MArray,index,i);i++;}index++;}while(index<=length);}void Display(StateItem SArray[],char TArray[],int MArray[][20],int x,int y,char start,char end)//输出确定化的NFA{int i,j,k;cout<<"将NFA转化为DFA!"<<endl;cout<<"DFA N'=({";for(i=0;i<x;i++){if(i==0) cout<<"["<<SArray[i].newstates<<"]"; else cout<<",["<<SArray[i].newstates<<"]";}cout<<"},{";for(i=0;i<y;i++){if(i==0) cout<<"["<<TArray[i]<<"]";elsecout<<",["<<TArray[i]<<"]";}cout<<"}, M',["<<start<<"],F')"<<endl;cout<<"其中M':"<<endl;for(i=0;i<x;i++)for(j=0;j<y;j++){if(MArray[i][j]!=-1){k=MArray[i][j];cout<<"M'(["<<SArray[i].newstates<<"],"<<TArray[j]<<")=["<<SArray[k].newst ates<<"]"<<endl;}}cout<<"其中F'={";k=0;for(i=0;i<x;i++){j=0;while(SArray[i].newstates[j]!='\0'){if(SArray[i].newstates[j]==end) break;j++;}if(SArray[i].newstates[j]!='\0'){if(k==0) cout<<"["<<SArray[i].newstates<<"]";elsecout<<",["<<SArray[i].newstates<<"]";k++;}}cout<<"}"<<endl;}void RunFA1(LeftItem Array[],int size,char start,char end) {char TD[20];int i=0,j;char s=start;cout<<"请输入要推导的符号串:"; cin>>TD;cout<<" M("<<s<<",";for(j=0;TD[j]!='\0';j++)cout<<TD[j];cout<<")"<<endl;while(TD[i]!='\0'){if(TD[i+1]!='\0'){cout<<"=M(M("<<s<<","<<TD[i]<<"),"; for(j=i+1;TD[j]!='\0';j++)cout<<TD[j];cout<<")"<<endl;}s=FindNewState(Array,size,s,TD[i]); if(s==NULL) break;if(TD[i+1]=='\0')cout<<"="<<s<<endl;else{cout<<"=M("<<s<<",";for(j=i+1;TD[j]!='\0';j++)cout<<TD[j];cout<<")"<<endl;}i++;}if(TD[i]=='\0'){if(s==end)cout<<"该符号串能被有穷状态所接受!"<<endl<<endl; elsecout<<"该符号串不能被有穷状态所接受!"<<endl<<endl;}elsecout<<"该符号串不能被有穷状态所接受!"<<endl<<endl;}void RunFA2(StateItem SArray[],char TArray[],int start,int end,int MArray[][20]){char TD[20];int i,j,k,x,y;char s=start;cout<<"请输入要推导的字符串:";cin>>TD;cout<<" M'(["<<s<<"],";for(i=0;TD[i]!='\0';i++)cout<<TD[i];cout<<")"<<endl;x=0;i=0;while(TD[i]!='\0'){if(TD[i+1]!='\0'){cout<<"=M'(M'([";cout<<SArray[x].newstates; cout<<"]";cout<<","<<TD[i]<<"),";for(j=i+1;TD[j]!='\0';j++) cout<<TD[j];cout<<")"<<endl;}y=Findy(TArray,TD[i]);x=MArray[x][y];if(x==-1) break;if(TD[i+1]=='\0'){cout<<"=";cout<<"["<<SArray[x].newstates<<"]"<<endl; }else{cout<<"=M'(";cout<<"["<<SArray[x].newstates<<"],";for(j=i+1;TD[j]!='\0';j++)cout<<TD[j];cout<<")"<<endl;}i++;}if(TD[i]=='\0'){for(k=0;SArray[x].newstates[k]!='\0';k++)if(SArray[x].newstates[k]==end) break;if(SArray[x].newstates[k]!='\0'){cout<<"["<<SArray[x].newstates<<"]"<<"属于终止状态集合!"<<endl;cout<<"该字符串能被有穷状态所接受!"<<endl<<endl;}elsecout<<"该字符串不能被有穷状态所接受!"<<endl<<endl;}elsecout<<"该字符串不能被有穷状态所接受!"<<endl<<endl;}/////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// /// void main(){int size=0,sign=0;int i,j,n,sel;int count1,count2;int length=0;char start;char end;char temp[10];int MArray[20][20];RightNode* p;cout<<"请输入文法规则的数目:"; cin>>n;cout<<"请输入开始状态: ";cin>>start; //得到初始状态LeftItem* Array=new LeftItem[n]; for(i=0;i<n;i++){do{cout<<"请输入第"<<i+1<<"条规则:";cin>>temp;}while(strlen(temp)>6);if(strlen(temp)==6){for(j=0;j<size;j++)if(Array[j].state==temp[4]) break;if(j==size){Array[size].state=temp[4];Array[size].link=new RightNode(temp[5],temp[0]);size++;}else{for(p=Array[j].link;p->nextsibling!=NULL;p=p->nextsibling) {} p->nextsibling=new RightNode(temp[5],temp[0]);}}else{for(j=0;j<size;j++)if(Array[j].state==start) break;if(j==size){Array[size].state=start;Array[size].link=new RightNode(temp[4],temp[0]);size++;}else{for(p=Array[j].link;p->nextsibling!=NULL;p=p->nextsibling) {} p->nextsibling=new RightNode(temp[4],temp[0]);}}}end=Array[0].link->nextstate; //得到终止状态cout<<endl<<"文法规则存储完毕!"<<endl<<endl; count1=getcount1(Array,size);count2=getcount2(Array,size);StateItem* SArray=new StateItem[100];char* TArray=new char[count2+1];SArray[0].newstates[0]=start;SArray[0].newstates[1]='\0';Initiate(Array,size,TArray);TArray[count2]='\0';for(i=0;i<20;i++)for(j=0;j<20;j++)MArray[i][j]=-1;cout<<endl;aaa:cout<<"-----生成FA请按1-----"<<endl;cout<<"-----运行FA请按2-----"<<endl;cout<<"-----退出请按3-------"<<endl;do{cin>>sel;}while(sel!=1&&sel!=2&&sel!=3);switch(sel){case 1:CreateFA1(Array,size,start,end); //根据输入文法建立FAif(!CheckState(Array,size)) //将NFA确定化{CreateFA2(Array,size,start,end,SArray,TArray,length,MArray); Display(SArray,TArray,MArray,length+1,count2,start,end);}sign++;break;case 2:if(sign==0){cout<<"请先生成FA!"<<endl;goto aaa;}if(CheckState(Array,size))RunFA1(Array,size,start,end); //运行DFA elseRunFA2(SArray,TArray,start,end,MArray); //运行确定化的NFA break;case 3:break;}if(sel!=3) goto aaa;}。
