編譯原理實(shí)驗(yàn)三：正規(guī)文法到正規(guī)式的轉(zhuǎn)換

實(shí)驗(yàn)三：正規(guī)文法到正規(guī)式的轉(zhuǎn)換一：要求輸入任意的正規(guī)文法,輸出相應(yīng)的正規(guī)式二：實(shí)驗(yàn)?zāi)康氖炀氄莆照?guī)文法到正規(guī)式的轉(zhuǎn)換規(guī)則理解正規(guī)文法和正規(guī)式的等價(jià)性三：實(shí)驗(yàn)原理1.一個(gè)正規(guī)語言可以由正規(guī)文法定義，也可以由正規(guī)式定義，對任意一個(gè)正規(guī)文法，存在一個(gè)定義同一個(gè)語言的正規(guī)式，反之，對每個(gè)正規(guī)式，存在生成同一個(gè)語言的正規(guī)文法2正規(guī)文法與正規(guī)式的轉(zhuǎn)換規(guī)則：1．A-〉xB,B->y則：A=xy2．A-〉xA,A->y則：A-〉x*y3．A-〉x，A-〉y則：A=x|y四：數(shù)據(jù)結(jié)構(gòu)與算法structChomsky{stringleft;stringright;};voidapart(Chomsky*p,inti)//分開產(chǎn)生式左右部voidVNVT(Chomsky*p)//求VN和VTintzero(Chomsky*p)//0型文法intone(Chomsky*p)//1型文法inttwo(Chomsky*p)//2型文法intthree(Chomsky*p)//3型文法voidchange(Chomsky*p)//正規(guī)文法到正規(guī)式的轉(zhuǎn)換函數(shù)五：出錯(cuò)分析1:#include<iostream>忽視了c++語言中的頭文件應(yīng)當(dāng)去掉.h，須再另加上usingnamespacestd;2：規(guī)則分解不對，導(dǎo)致結(jié)果出錯(cuò)。3：太多循環(huán)嵌套容易造成程序出錯(cuò)，養(yǎng)成把括號(hào)提前打好的習(xí)慣。六：實(shí)驗(yàn)結(jié)果與分析不是正規(guī)文法的不能轉(zhuǎn)換：是正規(guī)文法的才可以轉(zhuǎn)換：七：源代碼#include<iostream>#include<string>usingnamespacestd;#definemax50intNONE=1;stringstrings,noend,end;//非終結(jié)符與終結(jié)符存儲(chǔ)intn;//產(chǎn)生式總數(shù)structChomsky{stringleft;stringright;};voidapart(Chomsky*p,inti)//分開產(chǎn)生式左右部{intj;for(j=0;j<strings.length();j++)if(strings[j]=='-'){p[i].left=strings.substr(0,j);p[i].right=strings.substr(j+1,strings.length()-j);}}voidVNVT(Chomsky*p)//求VN和VT{inti,j;for(i=0;i<n;i++){for(j=0;j<(int)p[i].left.length();j++){if((p[i].left[j]>='A'&&p[i].left[j]<='Z'))//非終結(jié)符判斷{if(noend.find(p[i].left[j])>100)noend+=p[i].left[j];}else{if(end.find(p[i].left[j])>100)end+=p[i].left[j];}}for(j=0;j<(int)p[i].right.length();j++){if(!(p[i].right[j]>='A'&&p[i].right[j]<='Z'))//終結(jié)符判斷{if(end.find(p[i].right[j])>100)end+=p[i].right[j];}else{if(noend.find(p[i].right[j])>100)noend+=p[i].right[j];}}}}intzero(Chomsky*p)//0型文法{intflag(0),count(0);inti,j;for(i=0;i<n;i++){for(j=0;j<(int)p[i].left.length();j++){if(p[i].left[j]>='A'&&p[i].left[j]<='Z')//有否非終結(jié)符flag++;}if(flag>0){flag=0;count++;}elsebreak;//左部沒有非終結(jié)符，結(jié)束}if(count==n)return1;//屬于0型文法else{cout<<endl<<"所輸產(chǎn)生式不屬于任何文法。"<<endl;NONE=0;return0;}}intone(Chomsky*p)//1型文法{intflag(0);inti;if(zero(p)){for(i=0;i<n;i++){if(p[i].right.length()<p[i].left.length())//右部長度是否小于左部{flag++;break;}}}elseflag--;if(flag>0){cout<<endl<<"此文法屬于0型文法，即短語文法。"<<endl;return0;//不屬于1型文法}elseif(flag==0)return1;//屬于1型文法elsereturn0;}inttwo(Chomsky*p)//2型文法{intflag(0);inti;if(one(p)){for(i=0;i<n;i++)if((p[i].left.length()!=1)||!(p[i].left[0]>='A'&&p[i].left[0]<='Z'))//左部不屬于一個(gè)字符或不屬于非終結(jié)符{flag++;break;}}elseflag--;if(flag>0){cout<<endl<<"此文法屬于1型文法，即上下文有關(guān)文法。"<<endl;return0;//不屬于2型文法}elseif(flag==0){return1;//屬于2型文法}elsereturn0;}intthree(Chomsky*p)//3型文法{intflag=0;inti;if(two(p)){for(i=0;i<n;i++)if(!(p[i].right.length()==1||p[i].right.length()==2)||(p[i].right[0]>='A'&&p[i].right[0]<='Z'))//右部字符個(gè)數(shù)不是1或2，或首字符是非終結(jié)符{flag++;break;}elseif((p[i].right.length()==2)&&!(p[i].right[1]>='A'&&p[i].right[1]<='Z'))//第二個(gè)字符不是非終結(jié)符{flag++;break;}}elseflag--;if(flag>0){cout<<"此文法屬于2型文法，即上下文無關(guān)文法。"<<endl;i=n;return0;}elseif(flag==0){cout<<"此文法屬于3型文法，即正規(guī)文法。"<<endl;return1;}elsereturn0;}voidchange(Chomsky*p)//正規(guī)文法到正規(guī)式的轉(zhuǎn)換函數(shù){inti,j,m,flag;//合并產(chǎn)生式for(i=0;i<n;i++)for(j=i+1;j<n;j++){if((p[i].left==p[j].left)&&(p[i].right[1]==p[j].right[1])){if(p[i].right[1]==p[j].right[1]&&p[i].left[0]==p[j].right[1])//合并形如A->aA,A->bA的產(chǎn)生式為A->aA|bA的形式{p[i].right=p[i].right+"|"+p[j].right;p[j].left="";p[j].right="";}elseif(p[i].right[1]==p[j].right[1]&&p[i].left[0]!=p[j].right[1])//合并形如S->aA,S->bA的產(chǎn)生式為S->aA|bA的形式{p[i].right=p[i].right+"|"+p[j].right;p[j].left="";p[j].right="";}}if(p[i].right.length()==1&&p[j].right.length()==1&&p[i].left==p[j].left)//合并形如S->a,S->b，S->c的產(chǎn)生式為S->a|b|c的形式{p[i].right=p[i].right+"|"+p[j].right;p[j].left="";p[j].right="";}}for(i=0;i<n;i++)//提取形如S->aA|bA的公因式為S->(a|b)A的形式{flag=p[i].right.length();if(p[i].right.length()>2&&'A'<=p[i].right[1]&&p[i].right[1]<='Z'&&p[i].right[2]=='|'){for(j=1;j<flag-1;j=j+3){p[i].right[j]='';}if(j==flag-1)p[i].right="("+p[i].right.substr(0,p[i].right.length()-1)+")"+p[i].right.substr(p[i].right.length()-1);}}for(i=0;i<n;i++){if(p[i].left[0]==p[i].right[p[i].right.length()-1]&&p[i].right.length()>1){for(j=0;j<n;j++)if(p[i].left==p[j].left&&j!=i){for(m=0;m<p[j].right.length();m++)if('A'<=p[j].right[m]&&p[j].right[m]<='Z')break;if(m==p[j].right.length()){p[i].right=p[i].right.substr(0,p[i].right.length()-1)+"*"+"("+p[j].right+")";p[j].right="";p[j].left="";}}}}flag=n;while(flag>=0)//當(dāng)所有產(chǎn)生式的右部均為終結(jié)符構(gòu)成時(shí)停止轉(zhuǎn)換for(i=0,flag=flag-1;i<n;i++)for(j=0;j<p[i].right.length();j++)if('A'<=p[i].right[j]&&p[i].right[j]<='Z'){for(m=0;m<n;m++){if(p[m].left[0]==p[i].right[j]&&m!=i){p[i].right=p[i].right.substr(0,j)+p[m].right+p[i].right.substr(j+1);p[m].left="";p[m].right="";break;}}}//再次合并左部相等的產(chǎn)生式for(i=0;i<n;i++)for(j=0;j<n;j++){if(p[i].left[0]==p[j].left[0]&&i!=j){if(p[j].right.length()>1){p[i].right=p[i].right+"|"+"("+p[j].right+")";p[j].left="";p[j].right="";}else{p[i].right=p[i].right+"|"+p[j].right;p[j].left="";p[j].right="";}}}}voidmain(){inti,j;cout<<"....................編譯原理實(shí)驗(yàn)三：正規(guī)文法到正規(guī)式的轉(zhuǎn)換...................."<<endl;cout<<"請輸入正規(guī)文法（三型文法）的產(chǎn)生式總數(shù)及各產(chǎn)生式："<<endl<<"其中左右部之間用'-'表示，空用'#'表示"<<endl;cin>>n;Chomsky*p=newChomsky[max];for(i=0;i<n;i++){cin>>strings;ap