编译原理实验1Chomsky文法类型判断

1、编译原理实验Chomsky文法类型判断编译原理实验报告实验名称Chomsky文法类型判断实验时间2014年4月2日院系计算机科学与技术学院班级科技(2)班学号E01114174姓名徐帅1 .试验目的输入：一组任意的规则。输出：相应的Chomsky文法的类型。2 .实验原理1. 0型文法（短语文法）如果对于某文法G,P中的每个规则具有下列形式：U：=V其中u£V+,vGV,则称该文法G为0型文法或短语文法，简写为PSG。0型文法或短语结构文法的相应语言称为0型语言或短语结构语言L。这种文法由于没有其他任何限制，因此0型文法也称为无限制文法，其相应的语言称为无限制性语言。任何0型语言都是

2、递归可枚举的，故0型语言又称递归可枚举集。这种语言可由图灵机（Turning）来识别。2. 1型文法（上下文有关文法）如果对于某文法G,P中的每个规则具有下列形式：xUy:=xuy其中U£V、；u£V+；x,y£V则称该文法G为1型文法或上下文有关文法,也称上下文敏感文法，简写为CSG。1型文法的规则左部的U和右部的u具有相同的上文x和下文y,利用该规则进行推导时，要用u替换U,必须在前面有x和后面有y的情况下才能进行，显示了上下文有关的特性。1型文法所确定的语言为1型语言匕，1型语言可由线性有界自动机来识别。3. 2型文法（上下文无关文法）如果对于某文法G,P中

3、的每个规则具有下列形式：U:=u其中U£R；uev+,则称该文法G为2型文法或上下文无关文法，简写为CFGo按照这条规则，对于上下文无关文法，利用该规则进行推导时，无需考虑非终结符U所在的上下文，总能用u替换U,或者将u归约为U,显示了上下文无关的特点。2型文法所确定的语言为2型语言L2,2型语言可由非确定的下推自动机来识别。一般定义程序设计语言的文法是上下文无关的。如C语言便是如此。因此，上下文无关文法及相应语言引起了人们较大的兴趣与重视。4. 3型文法（正则文法，线性文法）如果对于某文法G,P中的每个规则具有下列形式：U二=T或U二=WT其中TCVT；U,WVN,则称I亥无法G为

4、左线性文法。如果对于某文法G,P中的每个规则具有下列形式：U二=T或U二=TW其中TCVT；U,WEVn,则称Ig文法G为右线性文法。左线性文法和右线性文法通称为3型文法或正则文法，有时又称为有穷状态文法，简写为RG按照定义，对于正则文法应用规则时，单个非终结符号只能被替换为单个终结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个终结符号加上单个非终结符号。3型文法所确定的语言为3型语言匕，3型语言可由确定的有限状态自动机来识别。在常见的程序设计语言中，多数与词法有关的文法属于3型文法。可以看出，上述4类文法，从0型到3型，产生式限制越来越强，其后一类都是前一类的子集，而描述语

5、言的功能越来越弱，四类文法及其表示的语言之间的关系可表示为：0型二1型二2型二3型；即LonLQL2nL33.1. 验内容该实验用C+进行编译,利用函数功能，调用不同的函数来判定0型文法,1型文法,2型文法，3型文法的判断。主要提高我们对文法类型的理解，也提高了我们编程的动手能力.理论与实践结合，加深对文法概念的理解.1 .实验心得1 .明确四种文法的定义，根据文法定义的不同，利用程序将其区分开2 .事先画好实验的流程图，可以帮助解决问题5 .实验代码与结果#include<iostream>#include<string>usingnamespacestd;intm;

6、文法产生式的个数charVn100;/记录非终结字符charVt100;/记录终结字符typedefstructGZ定义一个产生式结构体stringleft;定义产生式的左部stringright;/定义产生式的右部stringwhole;定义整个产生式GZ;boolwenfa0(GZ*p)判断0型文法inti,j;for(i=0;i<m;i+)/遍历所有的产生式for(j=0;j<pi.left.length();j+)/遍历整个产生式左式每一个字符if(pi.leftU>='A')&&(pi.leftj<=Z)判断产生式左边是否含有非

7、终结符break;if(j=pi.left.length()break;elsecontinue;if(i=m)return1;/说明该文法是0型elsecout<<“该文法不是0型文法！"<<endl;return0;boolwenfa1(GZ*p)判断1型文法inti;if(wenfa0(p)for(i=0;i<m;i+)遍历所有的产生式if(pi.rightlength()>=pi.leftlength()判断产生式右边是否大于左边continue;elsebreak;if(i=m)return1;/说明该文法是1型elsecout<&

8、lt;“该文法是0型文法！"<<endl;return0;elsereturn0;boolwenfa2(GZ*p)判断2型文法inti;if(wenfa1(p)for(i=0;i<m;i+)遍历所有的产生式if(pi.leftlength()=1&&(pi.left0>'A'&&pi.left0<'Z')continue;elsebreak;if(i=m)return1;/说明该文法是2型elsecout<<“该文法是1型文法！"<<endl;return0

9、;elsereturn0;boolwenfa3(GZ*p)判断3型文法inti;if(wenfa2(p)for(i=0;i<m;i+)遍历所有的产生式if(pi.rightO>='a'&&Pi.right0<='z')&&Pi.right.length()>=1&&pi.right.length()<=2)判断产生式右边第一个字符是否是终结符以及规定左边的字符个数为1或2if(pi.right.length()=2)&&(pi.right1>='a'

10、;&&pi.right1<='z')break;elsecontinue;elsebreak;if(i=m)cout<<“该文法是3型文法！"<<endl;return1;elsecout<<“该文法是2型文法！"<<endl;return0;elsereturn0;voidoutput(GZ*p)输由终结符和非终结符inti,j,k;intvn=0;/记录非终结字符个数intvt=0;记录终结字符个数for(i=0;i<m;i+)/遍历整个产生式for(j=0;j<pi.wh

11、ole.length();j+)遍历产生式的整个字符if(pi.wholej>='A'&&pi.wholej<='Z')/判断字符是否为非终结字符for(k=0;k<=vn;k+)/遍历整个非终结符集合,判断是否有重复if(Vnk=pi.wholej)break;elsecontinue;if(k>vn)说明没有重复Vnvn=pi.wholej;vn+;if(pi.wholej>='a'&&pi.wholej<='z')/判断字符是否为非终结字符for(k=0;k

12、<=vt;k+)/遍历整个非终结符集合，判断是否有重复if(Vtk=pi.wholej)break;elsecontinue;if(k>vt)/说明没有重复Vtvt=pi.wholej;vt+;cout<<"n"cout<<“非终结符为:n"for(i=0;i<vn;i+)/输由非终结字符cout<<Vni<<""cout<<"n"cout«,nM;coutw”终结符为:nM;for(i=0;i<vt;i+)/输出非终结字符cout«Vti«MM;cout«,nM;voidmain()(intij;stringin;记录输入的产生式cout«M请输入文法产生式的个数!n"cin»m;GZ*p=newGZm;cout«"请再输入文法规则An”；for(i=0;i<m;i+)/输入产生式数组(cin»in;for(j