編譯原理實(shí)驗(yàn)報(bào)告3

實(shí)驗(yàn)三 詞法分析——有窮自動(dòng)機(jī)的應(yīng)用實(shí)驗(yàn)?zāi)康模阂唬狠斎胝齽t文法二：FA1．生成FA(DFA或NFA)2．運(yùn)行FA，DFA（自動(dòng)）；NFA（交互）3．**NFA→DFA實(shí)驗(yàn)設(shè)想： 對(duì)輸入的文法存儲(chǔ)并判斷是確定的有窮狀態(tài)自動(dòng)機(jī)還是不確定是有窮狀態(tài)自動(dòng)機(jī)，并給出標(biāo)準(zhǔn)的表示形式，若是DFA，可直接測(cè)試一個(gè)符號(hào)串是否是文法的句子，即能否被有窮狀態(tài)機(jī)接受，給出過(guò)程及結(jié)果；若是NFA，首先將其轉(zhuǎn)化為DFA，再測(cè)試一個(gè)符號(hào)串是否是文法的句子，亦即是否能被DFA接受。例如：輸入文法規(guī)則的數(shù)目： 7輸入開始狀態(tài) :S輸入文法Z::=ZaZ::=BbZ::=AaB::=AbB::=bA::=BaA::=a此為確定有窮狀態(tài)自動(dòng)機(jī)!DFAD=({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輸入要推導(dǎo)的符號(hào)串 :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)=Z該符號(hào)串能被有窮狀態(tài)所接受 !輸入文法規(guī)則的數(shù)目： 7輸入開始狀態(tài) :S輸入規(guī)則:Z::=AbZ::=BaZ::=ZcA::=BaA::=aB::=AbB::=b文法規(guī)則存儲(chǔ)完畢!此為非確定有窮狀態(tài)自動(dòng)機(jī) !NFAN=({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轉(zhuǎn)化為DFA!DFAN'=({[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]}輸入要推導(dǎo)的字符串 :ababcM'([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]屬于終止?fàn)顟B(tài)集合!該字符串能被有窮狀態(tài)所接受!實(shí)驗(yàn)結(jié)果：參考程序#include<iostream.h>#include<String.h>structLeftItem;structRightNode //存儲(chǔ)狀態(tài)轉(zhuǎn)換關(guān)系中弧與終止?fàn)顟B(tài)結(jié)點(diǎn)結(jié)構(gòu){chartran;charnextstate;RightNode*nextsibling;RightNode(charx,chary){tran=x; nextstate=y; nextsibling=NULL;}};structLeftItem{

//存儲(chǔ)狀態(tài)轉(zhuǎn)換關(guān)系中初始狀態(tài)結(jié)點(diǎn)結(jié)構(gòu)charstate;RightNode*link;};structStateItem

//存放確定化的

NFA狀態(tài)結(jié)點(diǎn)結(jié)構(gòu){charnewstates[10];StateItem(){newstates[0]='\0';}};//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////intCheckState(LeftItemArray[],intsize){RightNode*p;RightNode*q;for(inti=0;i<size;i++){p=Array[i].link;q=p->nextsibling;if(q==NULL) return1;while(q!=NULL){if(p->tran==q->tran)return0;q=q->nextsibling;}}return1;}intCheckExist(StateItemSArray[],int&length,chartemp[])將NFA確定化創(chuàng)建二維矩陣時(shí)判別新產(chǎn)生的狀態(tài)是否在狀態(tài)數(shù)組中存儲(chǔ)過(guò){inti=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;returnm;}elsereturnk;}intgetcount1(LeftItemArray[],intsize)

//取得

FA中狀態(tài)的個(gè)數(shù){chartemp[20];intlen=0,count=0;inti,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;}}returncount;}intgetcount2(LeftItemArray[],intsize)

//取得

FA中輸入字母的個(gè)數(shù){chartemp[20];intlen=0,count=0;inti,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])if(j==len){

break;count++;temp[len]=pNode->tran;len++;}pNode=pNode->nextsibling;}}returncount;}intgetstate(RightNode*pNode,chararc){

//判定一個(gè)狀態(tài)是否能通過(guò)一條弧進(jìn)入下一狀態(tài)while(pNode){if(pNode->tran==arc) return1;pNode=pNode->nextsibling;}return0;}voidSort(charA[],intn){

//將取得的新?tīng)顟B(tài)進(jìn)行排序for(inti=n-1;i>0;i--)for(intj=0;j<i;j++){if(A[j+1]<A[j]){chartemp=A[j+1];A[j+1]=A[j];A[j]=temp;}}}voidBianli1(LeftItemArray[],intsize)

//輸出

FA中有窮非空的狀態(tài)集合{chartemp[20];intlen=0;inti,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])if(j==len){

break;if(len==0)cout<<pNode->nextstate;elsecout<<","<<pNode->nextstate;temp[len]=pNode->nextstate;len++;}pNode=pNode->nextsibling;}}}voidBianli2(LeftItemArray[],intsize)輸出FA中有窮的輸入字母表{chartemp[20];intlen=0;inti,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;}}}voidBianli31(LeftItemArray[],intsize)//輸出DFA狀態(tài)轉(zhuǎn)換關(guān)系的集合 M{inti;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;}}}voidBianli32(LeftItemArray[],intsize)

//輸出

NFA狀態(tài)轉(zhuǎn)換關(guān)系集合

M{charK[20];intlen=0;inti,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])if(j==len){

break;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;}}}voidInitiate(LeftItemArray[],intsize,charTArray[])

//將

FA

中的輸入字母表存入數(shù)組

TArray[]{intlen=0;inti,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])if(j==len){

break;TArray[len]=pNode->tran;len++;}pNode=pNode->nextsibling;}}}voidGetState(LeftItemArray[],intsize,charnstate[],chararc,chartemp[])將NFA確定化創(chuàng)建二維矩陣時(shí)取得新?tīng)顟B(tài){inti=0;while(nstate[i]!='\0'){for(intj=0;j<size;j++){if(Array[j].state==nstate[i]){RightNode*p=Array[j].link;while(p!=NULL){if(p->tran==arc){intk=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++;}}voidChange(StateItemSArray[],chartemp[],int&length,intMArray[][20],intindex,inti)//取得新?tīng)顟B(tài)后對(duì)狀態(tài)數(shù)組以及狀態(tài)轉(zhuǎn)換矩陣進(jìn)行對(duì)應(yīng)變化{intk;if(temp[0]!='\0'){k=CheckExist(SArray,length,temp);MArray[index][i]=k;if(k==length)strcpy(SArray[length].newstates,temp);}}charFindNewState(LeftItemArray[],intsize,charS,chararc){

//得到當(dāng)前狀態(tài)的下一狀態(tài)inti;for(i=0;i<size;i++){if(Array[i].state==S){RightNode*p=Array[i].link;while(p!=NULL){if(p->tran==arc)p=p->nextsibling;

returnp->nextstate;}}}returnNULL;}intFindy(charTArray[],chars){

//取得輸入字母在字母表中的下表inti=0;while(TArray[i]!='\0'){if(TArray[i]==s)

returni;i++;}}voidCreateFA1(LeftItemArray[],intsize,charstart,charend)根據(jù)輸入文法創(chuàng)建FA{if(CheckState(Array,size)){cout<<"此為確定有窮狀態(tài)自動(dòng)機(jī) !"<<endl;cout<<"DFAD=(";}else{cout<<"此為非確定有窮狀態(tài)自動(dòng)機(jī) !"<<endl;cout<<"NFAN=(";}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);}voidCreateFA2(LeftItemArray[],intsize,charstart,charend,StateItemSArray[],charTArray[],int&length,intMArray[][20])//將NFA轉(zhuǎn)換為DFA{chartemp[20];intindex=0;inti;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);}voidDisplay(StateItemSArray[],charTArray[],intMArray[][20],intx,inty,charstart,charend)輸出確定化的NFA{inti,j,k;cout<<"將NFA轉(zhuǎn)化為DFA!"<<endl;cout<<"DFAN'=({";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].newstates<<"]"<<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;}voidRunFA1(LeftItemArray[],intsize,charstart,charend){charTD[20];inti=0,j;chars=start;cout<<"請(qǐng)輸入要推導(dǎo)的符號(hào)串 :";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<<"該符號(hào)串能被有窮狀態(tài)所接受 !"<<endl<<endl;elsecout<<"該符號(hào)串不能被有窮狀態(tài)所接受 !"<<endl<<endl;}elsecout<<"該符號(hào)串不能被有窮狀態(tài)所接受 !"<<endl<<endl;}voidRunFA2(StateItemSArray[],charTArray[],intstart,intend,intMArray[][20]){charTD[20];inti,j,k,x,y;chars=start;cout<<"請(qǐng)輸入要推導(dǎo)的字符串 :";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<<"]"<<" 屬于終止?fàn)顟B(tài)集合 !"<<endl;cout<<"該字符串能被有窮狀態(tài)所接受 !"<<endl<<endl;}elsecout<<"該字符串不能被有窮狀態(tài)所接受 !"<<endl<<endl;}elsecout<<"該字符串不能被有窮狀態(tài)所接受 !"<<endl<<endl;}//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////voidmain(){intsize=0,sign=0;inti,j,n,sel;intcount1,count2;intlength=0;charstart;charend;chartemp[10];intMArray[20][20];RightNode*p;cout<<"請(qǐng)輸入文法規(guī)則的數(shù)目：cin>>n;cout<<"請(qǐng)輸入開始狀態(tài) :";cin>>start;LeftItem*Array=newLeftItem[n];for(i=0;i<n;i++){

";

//得到初始狀態(tài)do{cout<<"請(qǐng)輸入第"<<i+1<<"條規(guī)則:";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=newRightNode(temp[5],temp[0]);size++;}else{for(p=Array[j].link;p->nextsibling!=NULL;p=p->nextsibling){}p->nextsibling=newRightNode(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].li