编译原理实验三：正规文法到正规式的转换

实验三：正规文法到正规式的转换一：要求输入任意的正规文法,输出相应的正规式二：实验目的熟练掌握正规文法到正规式的转换规则理解正规文法和正规式的等价性三：实验原理1.一个正规语言可以由正规文法定义，也可以由正规式定义，对任意一个正规文法，存在一个定义同一个语言的正规式，反之，对每个正规式，存在生成同一个语言的正规文法2正规文法与正规式的转换规则：1．A-〉xB,B->y则：A=xy2．A-〉xA,A->y则：A-〉x*y3．A-〉x，A-〉y则：A=x|y四：数据结构与算法structChomsky{stringleft;stringright;};voidapart(Chomsky*p,inti)//分开产生式左右部voidVNVT(Chomsky*p)//求VN和VTintzero(Chomsky*p)//0型文法intone(Chomsky*p)//1型文法inttwo(Chomsky*p)//2型文法intthree(Chomsky*p)//3型文法voidchange(Chomsky*p)//正规文法到正规式的转换函数五：出错分析1:#include<iostream>忽视了c++语言中的头文件应当去掉.h，须再另加上usingnamespacestd;2：规则分解不对，导致结果出错。3：太多循环嵌套容易造成程序出错，养成把括号提前打好的习惯。六：实验结果与分析不是正规文法的不能转换：是正规文法的才可以转换：七：源代码#include<iostream>#include<string>usingnamespacestd;#definemax50intNONE=1;stringstrings,noend,end;//非终结符与终结符存储intn;//产生式总数structChomsky{stringleft;stringright;};voidapart(Chomsky*p,inti)//分开产生式左右部{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'))//非终结符判断{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'))//终结符判断{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')//有否非终结符flag++;}if(flag>0){flag=0;count++;}elsebreak;//左部没有非终结符，结束}if(count==n)return1;//属于0型文法else{cout<<endl<<"所输产生式不属于任何文法。"<<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'))//左部不属于一个字符或不属于非终结符{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'))//右部字符个数不是1或2，或首字符是非终结符{flag++;break;}elseif((p[i].right.length()==2)&&!(p[i].right[1]>='A'&&p[i].right[1]<='Z'))//第二个字符不是非终结符{flag++;break;}}elseflag--;if(flag>0){cout<<"此文法属于2型文法，即上下文无关文法。"<<endl;i=n;return0;}elseif(flag==0){cout<<"此文法属于3型文法，即正规文法。"<<endl;return1;}elsereturn0;}voidchange(Chomsky*p)//正规文法到正规式的转换函数{inti,j,m,flag;//合并产生式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的产生式为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的产生式为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的产生式为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)//当所有产生式的右部均为终结符构成时停止转换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;}}}//再次合并左部相等的产生式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<<"....................编译原理实验三：正规文法到正规式的转换...................."<<endl;cout<<"请输入正规文法（三型文法）的产生式总数及各产生式："<<endl<<"其中左右部之间用'-'表示，空用'#'表示"<<endl;cin>>n;Chomsky*p=newChomsky[max];for(i=0;i<n;i++){cin>>strings;apart(p,i);}VNVT(p);if(three(p))//只有当输入为正规文法时才进行转换，否则实验退出！！{cout<<"转换后的正规式为："<<endl;change(p);for(i=0;i<n;i++)//输出转换后的文法{if(p[i].left[0]!=NULL){cout<<p[i].left<<"=";for(j=0;j<p[i].right.length();j++){if(p[i].right[j]!='')cout<<p[i].right[j];}}}}elsecout<<"该文法不属于正规文法，实验结束!!"<<endl;}PAGE2