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

實驗三：正規(guī)文法到正規(guī)式的轉(zhuǎn)換一：要求輸入任意的正規(guī)文法,輸出相應的正規(guī)式二：實驗目的熟練掌握正規(guī)文法到正規(guī)式的轉(zhuǎn)換規(guī)則理解正規(guī)文法和正規(guī)式的等價性三：實驗原理1.一個正規(guī)語言可以由正規(guī)文法定義，也可以由正規(guī)式定義，對任意一個正規(guī)文法，存在一個定義同一個語言的正規(guī)式，反之，對每個正規(guī)式，存在生成同一個語言的正規(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ù)五：出錯分析1:#include<iostream>忽視了c++語言中的頭文件應當去掉.h，須再另加上usingnamespacestd;2：規(guī)則分解不對，導致結(jié)果出錯。3：太多循環(huán)嵌套容易造成程序出錯，養(yǎng)成把括號提前打好的習慣。六：實驗結(jié)果與分析不是正規(guī)文法的不能轉(zhuǎn)換：是正規(guī)文法的才可以轉(zhuǎn)換：七：源代碼#include<iostream>#include<string>usingnamespacestd;#definemax50intNONE=1;stringstrings,noend,end;//非終結(jié)符與終結(jié)符存儲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'))//左部不屬于一個字符或不屬于非終結(jié)符{flag++;break;}}elseflag--;if(flag>0){cout<<endl<<"此文法屬于1型文法，即上下文有關文法。"<<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'))//右部字符個數(shù)不是1或2，或首字符是非終結(jié)符{flag++;break;}elseif((p[i].right.length()==2)&&!(p[i].right[1]>='A'&&p[i].right[1]<='Z'))//第二個字符不是非終結(jié)符{flag++;break;}}elseflag--;if(flag>0){cout<<"此文法屬于2型文法，即上下文無關文法。"<<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)//當所有產(chǎn)生式的右部均為終結(jié)符構(gòu)成時停止轉(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<<"....................編譯原理實驗三：正規(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