编译原理实验报告3.doc

《编译原理实验报告3.doc》由会员分享，可在线阅读，更多相关《编译原理实验报告3.doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验三 词法分析有穷自动机的应用实验目的：一： 输入正则文法二：FA1 生成FA(DFA或NFA)2 运行FA，DFA（自动）；NFA（交互）3 *NFADFA实验设想： 对输入的文法存储并判断是确定的有穷状态自动机还是不确定是有穷状态自动机，并给出标准的表示形式，若是DFA，可直接测试一个符号串是否是文法的句子， 即能否被有穷状态机接受，给出过程及结果；若是NFA，首先将其转化为DFA，再测试一个符号串是否是文法的句子，亦即是否能被DFA接受。例如：输入文法规则的数目：7输入开始状态: S输入文法 Z:=Za Z:=Bb Z:=Aa B:=Ab B:=b A:=Ba A:=a 此为确定有穷状

2、态自动机!DFA D=(Z,A,B,a,b,M,S,Z)其中M: M(Z,a)=Z M(B,b)=Z M(B,a)=A M(A,a)=Z M(A,b)=B M(S,b)=B M(S,a)=A 输入要推导的符号串:ababaa M(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)=Z该符号串能被有穷状态所接受!输入文法规则的数目：7输入开始状态: S输入规则:Z:=Ab Z:=Ba Z:=Zc A:

3、=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)=

4、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)=ZZ属于终止状态集合!该字符串能被有穷状态所接受!实验结果：参考程序#include#includestruct LeftItem;struct RightNode /存储状态转换关系中弧与终止状态结点结构 char tran; char nextstate; RightNode* nextsi

5、bling; RightNode(char x,char y) tran=x; nextstate=y; nextsibling=NULL;struct LeftItem /存储状态转换关系中初始状态结点结构char state; RightNode* link;struct StateItem /存放确定化的NFA状态结点结构char newstates10; StateItem() newstates0=0;int CheckState(LeftItem Array,int size) RightNode* p; RightNode* q;for(int i=0;inextsibling;

6、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(ilength)length+;m=length;return m;else return k;int getcount1(LeftItem Array,int size) /取得FA中状态的个数 char temp

7、20; int len=0,count=0;int i,j;RightNode* pNode;for(i=0;isize;i+)pNode=Arrayi.link;while(pNode) for(j=0;jnextstate=tempj) break;if(j=len) count+; templen=pNode-nextstate;len+;pNode=pNode-nextsibling; return count;int getcount2(LeftItem Array,int size) /取得FA中输入字母的个数 char temp20; int len=0,count=0;int

8、i,j;RightNode* pNode;for(i=0;isize;i+)pNode=Arrayi.link;while(pNode) for(j=0;jtran=tempj) break;if(j=len) count+; templen=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

9、;return 0;void Sort(char A,int n) /将取得的新状态进行排序for(int i=n-1;i0;i-)for(int j=0;ji;j+)if(Aj+1Aj)char temp=Aj+1;Aj+1=Aj;Aj=temp;void Bianli1(LeftItem Array,int size) /输出FA中有穷非空的状态集合 char temp20; int len=0;int i,j;RightNode* pNode;for(i=0;isize;i+)pNode=Arrayi.link;while(pNode) for(j=0;jnextstate=tempj)

10、 break;if(j=len) if(len=0) coutnextstate;elsecout,nextstate; templen=pNode-nextstate;len+;pNode=pNode-nextsibling;void Bianli2(LeftItem Array,int size) /输出FA中有穷的输入字母表 char temp20; int len=0;int i,j;RightNode* pNode;for(i=0;isize;i+)pNode=Arrayi.link;while(pNode) for(j=0;jtran=tempj) break;if(j=len)

11、if(len=0) couttran;elsecout,tran; templen=pNode-tran;len+;pNode=pNode-nextsibling;void Bianli31(LeftItem Array,int size) /输出DFA状态转换关系的集合M int i; RightNode* pNode; for(i=0;isize;i+) pNode=Arrayi.link; while(pNode!=NULL)cout M(Arrayi.state,tran)=nextstatenextsibling;void Bianli32(LeftItem Array,int si

12、ze) /输出NFA状态转换关系集合M char K20; int len=0;int i,j;RightNode* pNode;RightNode* qNode;for(i=0;isize;i+)pNode=Arrayi.link;while(pNode) for(j=0;jtran=Kj) break;if(j=len) Klen=pNode-tran;len+;pNode=pNode-nextsibling; Sort(K,len);for(i=0;isize;i+) for(j=0;jlen;j+) pNode=Arrayi.link;cout M(Arrayi.state,Kj)=;

13、if(getstate(pNode,Kj) couttran=Kj) qNode=pNode-nextsibling; coutnextstate; break; pNode=pNode-nextsibling; while(qNode) if(qNode-tran=Kj) cout,nextstate; qNode=qNode-nextsibling; coutendl;elsecout$endl;void Initiate(LeftItem Array,int size,char TArray) /将FA中的输入字母表存入数组TArrayint len=0;int i,j;RightNod

14、e* pNode;for(i=0;isize;i+)pNode=Arrayi.link;while(pNode) for(j=0;jtran=TArrayj) break;if(j=len) TArraylen=pNode-tran;len+;pNode=pNode-nextsibling;void GetState(LeftItem Array,int size,char nstate,char arc,char temp) /将NFA确定化创建二维矩阵时取得新状态int i=0;while(nstatei!=0) for(int j=0;jtran=arc) int k=0; while(

15、tempk!=0) if(p-nextstate=tempk) break; k+; if(tempk=0) tempk=p-nextstate; tempk+1=0; p=p-nextsibling; i+;void Change(StateItem SArray,char temp,int& length,int MArray20,int index,int i)/取得新状态后对状态数组以及状态转换矩阵进行对应变化int k;if(temp0!=0)k=CheckExist(SArray,length,temp);MArrayindexi=k;if(k=length)strcpy(SArr

16、aylength.newstates,temp);char FindNewState(LeftItem Array,int size,char S,char arc) /得到当前状态的下一状态int i;for(i=0;itran=arc) return p-nextstate;p=p-nextsibling;return NULL;int Findy(char TArray,char s) /取得输入字母在字母表中的下表int i=0; while(TArrayi!=0)if(TArrayi=s) return i;i+;void CreateFA1(LeftItem Array,int s

17、ize,char start,char end)/根据输入文法创建FA if(CheckState(Array,size) cout此为确定有穷状态自动机!endl; coutDFA D=(; else cout此为非确定有穷状态自动机!endl; coutNFA N=(; cout; Bianli1(Array,size); cout,; Bianli2(Array,size); cout,M,; if(CheckState(Array,size) coutstart; else coutstart; cout,end)endl; cout其中M:endl; if(CheckState(Ar

18、ray,size) Bianli31(Array,size); else Bianli32(Array,size);void CreateFA2(LeftItem Array,int size,char start,char end,StateItem SArray,char TArray,int& length,int MArray20)/将NFA转换为DFA char temp20;int index=0;int i;doi=0;while(TArrayi!=0) temp0=0;GetState(Array,size,SArrayindex.newstates,TArrayi,temp)

19、;Sort(temp,strlen(temp);Change(SArray,temp,length,MArray,index,i);i+; index+;while(index=length);void Display(StateItem SArray,char TArray,int MArray20,int x,int y,char start,char end)/输出确定化的NFAint i,j,k;cout将NFA转化为DFA!endl; coutDFA N=(;for(i=0;ix;i+)if(i=0) coutSArrayi.newstates;else cout,SArrayi.n

20、ewstates; cout,;for(i=0;iy;i+)if(i=0) coutTArrayi;elsecout,TArrayi; cout, M,start,F)endl; cout其中M:endl;for(i=0;ix;i+) for(j=0;jy;j+) if(MArrayij!=-1)k=MArrayij;cout M(SArrayi.newstates,TArrayj)=SArrayk.newstatesendl;cout其中F=;k=0;for(i=0;ix;i+)j=0;while(SArrayi.newstatesj!=0) if(SArrayi.newstatesj=en

21、d) break; j+;if(SArrayi.newstatesj!=0)if(k=0) coutSArrayi.newstates;else cout,SArrayi.newstates;k+; coutendl;void RunFA1(LeftItem Array,int size,char start,char end) char TD20;int i=0,j;char s=start;coutTD;cout M(s,;for(j=0;TDj!=0;j+) coutTDj; cout)endl;while(TDi!=0)if(TDi+1!=0) cout=M(M(s,TDi),; fo

22、r(j=i+1;TDj!=0;j+) coutTDj; cout)endl;s=FindNewState(Array,size,s,TDi); if(s=NULL) break;if(TDi+1=0)cout=sendl;else cout=M(s,; for(j=i+1;TDj!=0;j+) coutTDj; cout)endl;i+;if(TDi=0)if(s=end)cout该符号串能被有穷状态所接受!endlendl; else cout该符号串不能被有穷状态所接受!endlendl; else cout该符号串不能被有穷状态所接受!endlendl;void RunFA2(State

23、Item SArray,char TArray,int start,int end,int MArray20) char TD20;int i,j,k,x,y;char s=start;coutTD; cout M(s,;for(i=0;TDi!=0;i+) coutTDi; cout)endl; x=0; i=0;while(TDi!=0) if(TDi+1!=0) cout=M(M(; coutSArrayx.newstates; cout; cout,TDi),; for(j=i+1;TDj!=0;j+) coutTDj; cout)endl; y=Findy(TArray,TDi);

24、x=MArrayxy; if(x=-1) break; if(TDi+1=0) cout=; coutSArrayx.newstatesendl; else cout=M(; coutSArrayx.newstates,; for(j=i+1;TDj!=0;j+) coutTDj; cout)endl;i+; if(TDi=0)for(k=0;SArrayx.newstatesk!=0;k+)if(SArrayx.newstatesk=end) break;if(SArrayx.newstatesk!=0)coutSArrayx.newstates属于终止状态集合!endl;cout该字符串能

25、被有穷状态所接受!endlendl;else cout该字符串不能被有穷状态所接受!endlendl; else cout该字符串不能被有穷状态所接受!endlendl;void main() int size=0,sign=0; int i,j,n,sel; int count1,count2; int length=0; char start; char end; char temp10; int MArray2020; RightNode* p; coutn; coutstart; /得到初始状态 LeftItem* Array=new LeftItemn; for(i=0;in;i+)

26、 do cout请输入第i+1temp; while(strlen(temp)6); if(strlen(temp)=6) for(j=0;jnextsibling!=NULL;p=p-nextsibling) p-nextsibling=new RightNode(temp5,temp0); else for(j=0;jnextsibling!=NULL;p=p-nextsibling) p-nextsibling=new RightNode(temp4,temp0); end=Array0.link-nextstate; /得到终止状态 coutendl文法规则存储完毕!endlendl;

27、 count1=getcount1(Array,size); count2=getcount2(Array,size); StateItem* SArray=new StateItem100; char* TArray=new charcount2+1; SArray0.newstates0=start; SArray0.newstates1=0; Initiate(Array,size,TArray); TArraycount2=0; for(i=0;i20;i+) for(j=0;j20;j+) MArrayij=-1;coutendl;aaa: cout-生成FA请按1-endl; co

28、ut-运行FA请按2-endl; cout-退出请按3-sel; while(sel!=1&sel!=2&sel!=3); switch(sel) case 1: CreateFA1(Array,size,start,end); /根据输入文法建立FA if(!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 else RunFA2(SArray,TArray,start,end,MArray); /运行确定化的NFA break; case 3: break; if(sel!=3) goto aaa;