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

1、实验三：正规文法到正规式的转换一：要求输入任意的正规文法,输出相应的正规式二：实验目的1. 熟练掌握正规文法到正规式的转换规则2. 理解正规文法和正规式的等价性三：实验原理1.一个正规语言可以由正规文法定义，也可以由正规式定义，对任意一个正规文法，存在一个定义同一个语言的正规式，反之，对每个正规式，存在生成同一个语言的正规文法2正规文法与正规式的转换规则： 1 A-xB,B->y则：A=xy 2A-xA,A->y 则：A-x*y 3A-x，A-y 则：A=x|y四：数据结构与算法struct Chomskystring left; string right; ;void apart

2、(Chomsky *p,int i) /分开产生式左右部void VNVT(Chomsky *p)/求VN和VTint zero(Chomsky *p)/0型文法int one(Chomsky *p)/1型文法int two(Chomsky *p)/2型文法int three(Chomsky *p)/3型文法void change(Chomsky *p)/正规文法到正规式的转换函数五：出错分析1: #include<iostream>忽视了c+语言中的头文件应当去掉.h，须再另加上using namespace std;2：规则分解不对，导致结果出错。3：太多循环嵌套容易造成程序出

3、错，养成把括号提前打好的习惯。六：实验结果与分析不是正规文法的不能转换：是正规文法的才可以转换：七：源代码#include<iostream>#include<string>using namespace std;#define max 50int NONE=1;string strings,noend,end;/非终结符与终结符存储int n;/产生式总数struct Chomskystring left;string right; ; void apart(Chomsky *p,int i) /分开产生式左右部int j; for(j=0;j<strings.

4、length();j+)if(stringsj='-')pi.left=strings.substr(0,j);pi.right=strings.substr(j+1,strings.length()-j);void VNVT(Chomsky *p)/求VN和VTint i,j;for(i=0;i<n;i+) for(j=0;j<(int)pi.left.length();j+) if(pi.leftj>='A'&&pi.leftj<='Z')/非终结符判断if(noend.find(pi.leftj)&g

5、t;100)noend+=pi.leftj; elseif(end.find(pi.leftj)>100)end+=pi.leftj;for(j=0;j<(int)pi.right.length();j+) if(!(pi.rightj>='A'&&pi.rightj<='Z')/终结符判断if(end.find(pi.rightj)>100)end+=pi.rightj;else if(noend.find(pi.rightj)>100)noend+=pi.rightj;int zero(Chomsky *p

6、)/0型文法int flag(0),count(0); int i,j; for(i=0;i<n;i+) for(j=0;j<(int)pi.left.length();j+)if(pi.leftj>='A'&&pi.leftj<='Z') /有否非终结符flag+;if(flag>0)flag=0;count+;else break; /左部没有非终结符，结束if(count=n) return 1; /属于0型文法elsecout<<endl<<"所输产生式不属于任何文法。&qu

7、ot;<<endl;NONE=0;return 0;int one(Chomsky *p)/1型文法int flag(0); int i; if(zero(p)for(i=0;i<n;i+) if(pi.right.length()<pi.left.length() /右部长度是否小于左部flag+;break;elseflag-;if(flag>0)cout<<endl<<"此文法属于0型文法，即短语文法。"<<endl; return 0; /不属于1型文法else if(flag=0)return 1;

8、 /属于1型文法elsereturn 0;int two(Chomsky *p)/2型文法int flag(0); int i; if(one(p)for(i=0;i<n;i+)if(pi.left.length()!=1)|!(pi.left0>='A'&&pi.left0<='Z') /左部不属于一个字符或不属于非终结符flag+;break;else flag-;if(flag>0)cout<<endl<<"此文法属于1型文法，即上下文有关文法。"<<endl;

9、 return 0; /不属于2型文法else if(flag=0)return 1; /属于2型文法elsereturn 0;int three(Chomsky *p)/3型文法int flag=0;int i;if(two(p) for(i=0;i<n;i+) if(!(pi.right.length()=1|pi.right.length()=2)|(pi.right0>='A'&&pi.right0<='Z') /右部字符个数不是1或2，或首字符是非终结符 flag+; break; else if(pi.right.l

10、ength()=2)&&!(pi.right1>='A'&&pi.right1<='Z') /第二个字符不是非终结符 flag+; break; else flag-;if(flag>0) cout<<"此文法属于2型文法，即上下文无关文法。"<<endl; i=n; return 0;else if(flag=0) cout<<"此文法属于3型文法，即正规文法。"<<endl; return 1; else return 0

11、; void change(Chomsky *p)/正规文法到正规式的转换函数int i,j,m,flag; /合并产生式for (i=0;i<n;i+)for(j=i+1;j<n;j+)if(pi.left=pj.left)&&(pi.right1=pj.right1)if(pi.right1=pj.right1&&pi.left0=pj.right1)/合并形如A->aA,A->bA的产生式为A->aA|bA的形式 pi.right=pi.right+"|"+pj.right; pj.left="&

12、quot; pj.right=""elseif(pi.right1=pj.right1&&pi.left0!=pj.right1)/合并形如S->aA,S->bA的产生式为S->aA|bA的形式 pi.right=pi.right+"|"+pj.right; pj.left="" pj.right="" if(pi.right.length()=1&&pj.right.length()=1&&pi.left=pj.left)/合并形如S->a,

13、S->b，S->c的产生式为S->a|b|c的形式pi.right=pi.right+"|"+pj.right; pj.left="" pj.right=""for(i=0;i<n;i+)/提取形如S->aA|bA的公因式为S->(a|b)A的形式 flag=pi.right.length(); if(pi.right.length()>2&&'A'<=pi.right1&&pi.right1<='Z'&&am

14、p;pi.right2='|') for(j=1;j<flag-1;j=j+3) pi.rightj=' ' if(j=flag-1) pi.right="("+pi.right.substr(0,pi.right.length()-1)+")"+pi.right.substr(pi.right.length()-1); for(i=0;i<n;i+) if(pi.left0=pi.rightpi.right.length()-1&&pi.right.length()>1) for(j=0

15、;j<n;j+) if(pi.left=pj.left&&j!=i) for(m=0;m<pj.right.length();m+) if('A'<=pj.rightm&&pj.rightm<='Z')break; if(m=pj.right.length() pi.right=pi.right.substr(0,pi.right.length()-1)+"*"+"("+pj.right+")" pj.right="" pj.l

16、eft="" flag=n; while(flag>=0)/当所有产生式的右部均为终结符构成时停止转换 for(i=0,flag=flag-1;i<n;i+) for(j=0;j<pi.right.length();j+) if('A'<=pi.rightj&&pi.rightj<='Z') for(m=0;m<n;m+) if(pm.left0=pi.rightj&&m!=i) pi.right=pi.right.substr(0,j)+pm.right+pi.right.

17、substr(j+1); pm.left="" pm.right="" break; /再次合并左部相等的产生式 for(i=0;i<n;i+) for(j=0;j<n;j+) if(pi.left0=pj.left0&&i!=j) if(pj.right.length()>1) pi.right=pi.right+"|"+"("+pj.right+")" pj.left="" pj.right="" else pi.ri

18、ght=pi.right+"|"+pj.right; pj.left="" pj.right="" void main()int i,j; cout<<".编译原理实验三：正规文法到正规式的转换."<<endl; cout<<"请输入正规文法（三型文法）的产生式总数及各产生式："<<endl<<"其中左右部之间用'-'表示，空用'#'表示"<<endl; cin>>n; Chomsky *p=new Chomskymax; for(i=0;i<n;i+)cin>>strings; apart(p,i); VNVT(p);if(three(p)/只有当输入为正规文法时才进行