编译原理实验文法的判断

1、文法类型的判断和推导序列的生成 目录一、实验名称2二、实验目的2三、实验原理21、文法G定义为四元组(Vn,Vt,P,S)22、文法类型的判断2四、实验思路21、接受产生式32、文法类型的判断33、将文法以四元组形式输出4五、实验小结41、文法类型的判断条件42、产生式的存储问题53、文法以四元组形式输出问题5六、附件51、源代码52、运行结果截图10一、实验名称文法类型的判断和推导序列的生成二、实验目的输入：一组任意的文法规则和任意符号串。输出：相应的Chomsky文法类型和推导。三、实验原理1、文法G定义为四元组(Vn,Vt,P,S)其中Vn为非终结符（或语法实体，或变量）集：Vt为终结符

2、集；P为规则（->）的集合，(VnVt)*且至少包含一个非终结符，(VnVt)*；Vn，Vt和P是非空有穷集。S称作识别符或开始符，它是一个非终结符，至少要在一条规则中作为左部出现。2、文法类型的判断a.设G=(Vn,Vt,P,S)为一文法，若P中的每一个产生式->均满足|>=|，仅仅S->除外，则文法G是1型或上下文有关的。b.设G=(Vn,Vt,P,S)，若P中的每一个产生式->满足: 是一个非终结符，(VnVt)*，则此文法称为2型的或上下文无关的。c. 设G=(Vn,Vt,P,S)，若P中的每一个产生式的形式都是A->B或A->，其中A和B都是

3、终结符，Vt*，则G是3型文法或正规文法。四、实验思路本实验采取C+来完成，用大写字母A到Z表示非终结符，小写字符a到z表示终结符。实验流程图1、接受产生式首先建立一个结构体siyuanzu，其成员有非终结符集合数组Vn，终结符集合数组Vt以及产生式集合数组rule，通过函数input来接受从键盘输入的产生式，并且存储于string类字符串数组rule中。函数input实现接受产生式功能的思路为：先确定要输入的产生式数目n，用for循环实现产生式的存储。2、文法类型的判断函数Grammer实现判断文法类型的功能并且输出文法的类型。其实现功能的思路为：a.对rule数组中每一个产生式进行判断，以

4、“->”中的“-”作为判断条件，将产生式分为左部和右部分别计算左部和右部的长度。若youb小于左部则不是1型文法。输出0型文法；若右部大于或等于左部，则继续判断。b.判断文法是否为2型文法，经过a步骤的执行，若文法为1型文法，只需在此基础上判断文法的左部是否只有一个非终结符。通过判断条件zuo=1&&'A'<=a.ruleizuo-1&&a.ruleizuo-1<='Z'确定是否为2型文法，若不满足判断条件则为1型文法，进行输出，若满足则继续判断。c.判断文法是否为3型文法，经过b步骤的执行，若文法为2型文法，只

5、需在此基础上判断文法的右部是否为B或形式或者是B或形式。通过判断条件一(you=2)&&(a.ruleinum+1>='a')&&(a.ruleinum+1<='z')&&(a.ruleinum+2>='A')&&(a.ruleinum+2<='Z')|(you=1)&&(a.ruleinum+1>='a')&&(a.ruleinum+1<='z')判断是否满足B或形式

6、，通过判断条件二(you=2)&&(a.ruleinum+1>='A')&&(a.ruleinum+1<='Z')&&(a.ruleinum+2>='a')&&(a.ruleinum+2<='z')|(you=1)&&(a.ruleinum+1>='a')&&(a.ruleinum+1<='z')判断是否满足B或形式。若所有产生式同时满足判断条件一或者同时满足判断条件二

7、，则为3型文法进行输出。否则为2型文法进行输出。3、将文法以四元组形式输出函数output实现输出文法四元组形式的功能。具体思路为：a.将存放产生式的string类数组rule一分为二，用x数组存放rule中所有的大写字母即非终结符，用y数组存放rule中所有的小写字母即终结符。b.用双重for循环给x和y数组中重复的字符标记，重复的字符全部赋值为“！”c.将x数组中非“！”元素赋值给非终结符集Vn，将y数组中非“！”元素赋值给终结符集Vt。d.按照格式分别输出非终结符集Vn，终结符集Vt，产生式P以及开始符S。五、实验小结我运用C+解决了此次实验的文法类型判断的问题，在实际解决问题的过程中，

8、主要遇到了以下几个问题：1、文法类型的判断条件编译原理书本上给出了几类文法类型的定义，但是在实际的解决问题过程中，需要将书本上给的判断条件转换为C+语言中的判断条件，这需要对文法类型的定义有很好的理解。我通过判断产生式右部是否大于等于左部确定1型文法，在此基础上判断产生式左部是否为一个非终结符确定2型文法，最后在2型文法的基础上判断产生式是否全部满足B或形式或者是B或形式确定3型文法。最终解决了文法类型判断条件的问题。2、产生式的存储问题实验要求最少输入五条产生式，我最初是选择用C语言解决存储问题，但是发现C语言中对于字符串的处理不够灵活，于是选择了C+来解决。C+中可以用string类型来定

9、义字符串数组，并且可以通过length函数求每个字符串的长度，这样给每条产生式的判断都带来了极大的便捷。3、文法以四元组形式输出问题实验需要输出文法的四元组，即需要输出非终结符集Vn，终结符集Vt，产生式P以及开始符S，由于我将产生式存储在string类数组rule中，因此，需要将rule中的元素分为两类，大写字母为非终结符，小写字母为终结符。但是分好类的数组存在元素重复的问题，我通过一个双重for循环给重复元素标记为“！”，再将非“！”元素赋值给字符数组Vn和Vt，解决了元素重复问题。最后需要安排一下输出的格式即解决了这个问题。通过本次实验，我深入的了解了文法类型的判断，对于文法类型的判断也

10、更加的熟练。同时，对于文法的四元组的定义更加的熟悉，并且对于运用C+解决编译原理的问题有了一定的基础。六、附件1、源代码#include<iostream>#include<string>using namespace std;struct siyuanzuchar Vn50;char Vt50;string rule20;int input(siyuanzu *a)int n,i;cout<<"请输入产生式数目:"cin>>n;cout<<"请输入产生式:n"for(i=0;i<n;i+

11、)cin>>(*a).rulei;return n;void output(siyuanzu a,int n)int i,j,length,k1=0,k2=0,m1=0,m2=0;char x50,y50;for(i=0;i<n;i+)length=a.rulei.length();for(j=0;j<length;j+)if(a.ruleij!='-'&&a.ruleij!='>')if(a.ruleij>='A'&&a.ruleij<='Z')xk1=a

12、.ruleij;k1+;elseyk2=a.ruleij;k2+;for(i=0;i<k1-1;i+)for(j=i+1;j<k1;j+)if(xi=xj)xj='!'for(i=0;i<k1;i+)if(xi!='!')a.Vnm1=xi;m1+;for(i=0;i<k2-1;i+)for(j=i+1;j<k2;j+)if(yi=yj)yj='!'for(i=0;i<k2;i+)if(yi!='!')a.Vtm2=yi;m2+;cout<<"四元组G=(Vn,Vt,P,S

13、)"<<endl;cout<<"其中非终结符Vn="for(i=0;i<m1-1;i+)cout<<a.Vni<<","cout<<a.Vnm1-1;cout<<""cout<<endl;cout<<"终结符Vt="for(i=0;i<m2-1;i+)cout<<a.Vti<<","cout<<a.Vtm2-1;cout<<&quo

14、t;"cout<<endl;cout<<"P由下列产生式组成:"<<endl;for(i=0;i<n;i+)cout<<a.rulei<<endl;cout<<"开始符为:S"<<endl;void Grammer(siyuanzu a,int n)int i,j,length,num,zuo,you;char c;for(i=0;i<n;i+)num=0;length=a.rulei.length();for(j=0;j<length;j+)

15、c=a.ruleij;num+;if(c='-')break;zuo=num-1;you=length-(num+1);if(you>=zuo)continue;elsebreak;if(i=n)for(i=0;i<n;i+)num=0;length=a.rulei.length();for(j=0;j<length;j+)c=a.ruleij;num+;if(c='-')break;zuo=num-1;if(zuo=1&&'A'<=a.ruleizuo-1&&a.ruleizuo-1<

16、;='Z')continue;elsebreak;if(i=n)for(i=0;i<n;i+)num=0;length=a.rulei.length();for(j=0;j<length;j+)c=a.ruleij;num+;if(c='-')break;you=length-(num+1);if(you=2)&&(a.ruleinum+1>='a')&&(a.ruleinum+1<='z')&&(a.ruleinum+2>='A')&a

17、mp;&(a.ruleinum+2<='Z')|(you=1)&&(a.ruleinum+1>='a')&&(a.ruleinum+1<='z')continue;else break;if(i=n)cout<<"文法类型:3型文法"<<endl;elsefor(i=0;i<n;i+)num=0;length=a.rulei.length();for(j=0;j<length;j+)c=a.ruleij;num+;if(c='

18、-')break;you=length-(num+1);if(you=2)&&(a.ruleinum+1>='A')&&(a.ruleinum+1<='Z')&&(a.ruleinum+2>='a')&&(a.ruleinum+2<='z')|(you=1)&&(a.ruleinum+1>='a')&&(a.ruleinum+1<='z')continue;else break;if(i=n)cout<<"文法类型:3型文法"<<endl;elsecout<<"文法类型:2型文法"<<endl;elsecout<<"文法类型:1型文法"<<endl;e