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

实验三：正规文法到正规式的转换一：要求输入任意的正规文法,输出相应的正规式二：实验目的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(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忽视了c+语言中的头文件应当去掉.h，须再另加上using namespace std;2：规则分解不对，导致结果出错。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; for(j=0;jstrings.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;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;else if(noend.find(pi.rightj)100)noend+=pi.rightj;int zero(Chomsky *p)/0型文法int flag(0),count(0); int i,j; for(i=0;in;i+) for(j=0;j=A&pi.leftj0)flag=0;count+;else break; /左部没有非终结符，结束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; return 0; /不属于1型文法else if(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型文法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=A&pi.right0=A&pi.right10) cout此文法属于2型文法，即上下文无关文法。endl; i=n; return 0;else if(flag=0) cout此文法属于3型文法，即正规文法。endl; return 1; else return 0; void 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(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的形式 flag=pi.right.length(); if(pi.right.length()2&A=pi.right1&pi.right1=Z&pi.right2=|) for(j=1;jflag-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;i1) for(j=0;jn;j+) if(pi.left=pj.left&j!=i) for(m=0;mpj.right.length();m+) if(A=pj.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=; pm.right=; break; /再次合并左部相等的产生式 for(i=0;in;i+) for(j=0;j1) pi.right=pi.right+|+(+pj.right+); pj.left=; pj.right=; else pi.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);if(three(p)/只有当输入为正规文法时才进行转换，否则实验退出