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

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

2、sky *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忽视了 c+语言中的头文件应当去掉.h ，须再另加上 using namespace std;2：规则分解不对，导致结果出错。3：太多循环嵌套容易造成程序出错，养成把括号提前打好的习惯。2

3、六：实验结果与分析不是正规文法的不能转换：3是正规文法的才可以转换：七：源代码#include#includeusing 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;4for(j=0;jstrings.length();j+)if(stringsj=-)pi.left=strings.substr(0,

4、j);pi.right=strings.substr(j+1,strings.length()-j);void VNVT(Chomsky *p)/求 VN与 VTint i,j;for(i=0;in;i+)for(j=0;j=A&pi.leftj100)noend+=pi.leftj;elseif(end.find(pi.leftj)100)end+=pi.leftj;for(j=0;j=A&pi.rightj100)end+=pi.rightj;elseif(noend.find(pi.rightj)100)noend+=pi.rightj;int zero(Chomsky *p)/0型文法

5、int flag(0),count(0);5int i,j;for(i=0;in;i+)for(j=0;j=A&pi.leftj0)flag=0;count+;elsebreak; /左部没有非终结符，结束if(count=n)return 1; /属于 0 型文法elsecoutendl 所输产生式不属于任何文法。endl;NONE=0;return 0;int one(Chomsky *p)/1型文法int flag(0);int i;if(zero(p)for(i=0;in;i+)if(pi.right.length()0)coutendl 此文法属于 0 型文法，即短语文法。 endl

6、;return 0;/不属于 1 型文法elseif(flag=0)return 1; /属于 1 型文法elsereturn 0;int two(Chomsky *p)/2型文法int flag(0);int i;if(one(p)for(i=0;i=A&pi.left00)coutendl 此文法属于 1 型文法，即上下文有关文法。endl;return 0;/不属于 2 型文法elseif(flag=0)return 1; /属于 2 型文法elsereturn 0;7int three(Chomsky *p)/3型文法int flag=0;int i;if(two(p)for(i=0;

7、i=A&pi.right0=A&pi.right10)cout此文法属于 2 型文法，即上下文无关文法。endl;i=n;return 0;elseif(flag=0)cout 此文法属于 3 型文法，即正规文法。 endl; return 1;elsereturn 0;8void change(Chomsky *p)/正规文法到正规式的转换函数int i,j,m,flag;/合并产生式for (i=0;in;i+)for(j=i+1;jaA,A-bA 的产生式为 A-aA|bA 的形式pi.right=pi.right+|+pj.right;pj.left=;pj.right=;elseif

8、(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,S-b ，S-c 的产生式为 S-a|b|c的形式pi.right=pi.right+|+pj.right;pj.left=;pj.right=;for(i=0;iaA|bA 的公因式为 S-(a|b)A的形式fla

9、g=pi.right.length();if(pi.right.length()2&A=pi.right1&pi.right1=Z&pi.right2=|)for(j=1;jflag-1;j=j+3)9pi.rightj= ;if(j=flag-1)pi.right=(+pi.right.substr(0,pi.right.length()-1)+)+pi.ri ght.substr(pi.right.length()-1);for(i=0;i1)for(j=0;jn;j+)if(pi.left=pj.left&j!=i)for(m=0;mpj.right.length();m+)if(A=p

10、j.rightm&pj.rightm=0)/ 当所有产生式的右部均为终结符构成时停止转换 for(i=0,flag=flag-1;in;i+)for(j=0;jpi.right.length();j+)if(A=pi.rightj&pi.rightj=Z)for(m=0;mn;m+)if(pm.left0=pi.rightj&m!=i)pi.right=pi.right.substr(0,j)+pm.right+pi.right.substr(j+1);pm.left=;10pm.right=;break;/ 再次合并左部相等的产生式 for(i=0;in;i+)for(j=0;j1)pi.r

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