生成Chomsky文法.docx

一、 实验名称 生成Chomsky文法二、 实验原理 10型文法（短语文法）如果对于某文法G，P中的每个规则具有下列形式：u: = v其中uV，vV*，则称该文法G为0型文法或短语文法，简写为PSG。0型文法或短语结构文法的相应语言称为0型语言或短语结构语言L0。这种文法由于没有其他任何限制，因此0型文法也称为无限制文法，其相应的语言称为无限制性语言。任何0型语言都是递归可枚举的，故0型语言又称递归可枚举集。这种语言可由图灵机（Turning）来识别。21型文法（上下文有关文法）如果对于某文法G，P中的每个规则具有下列形式：xUy: = xuy其中UVN；uV；x，yV*，则称该文法G为1型文法或上下文有关文法，也称上下文敏感文法，简写为CSG。1型文法的规则左部的U和右部的u具有相同的上文x和下文y，利用该规则进行推导时，要用u替换U，必须在前面有x和后面有y的情况下才能进行，显示了上下文有关的特性。1型文法所确定的语言为1型语言L1，1型语言可由线性有界自动机来识别。32型文法（上下文无关文法）如果对于某文法G，P中的每个规则具有下列形式：U : = u其中UVN；uV，则称该文法G为2型文法或上下文无关文法，简写为CFG。按照这条规则，对于上下文无关文法，利用该规则进行推导时，无需考虑非终结符U所在的上下文，总能用u替换U，或者将u归约为U，显示了上下文无关的特点。2型文法所确定的语言为2型语言L2，2型语言可由非确定的下推自动机来识别。一般定义程序设计语言的文法是上下文无关的。如C语言便是如此。因此，上下文无关文法及相应语言引起了人们较大的兴趣与重视。43型文法（正则文法，线性文法）如果对于某文法G，P中的每个规则具有下列形式：U : = T 或 U : = WT其中TVT；U,WVN，则称该文法G为左线性文法。如果对于某文法G，P中的每个规则具有下列形式：U : = T 或 U : = TW其中TVT；U, WVN，则称该文法G为右线性文法。左线性文法和右线性文法通称为3型文法或正则文法，有时又称为有穷状态文法，简写为RG。按照定义，对于正则文法应用规则时，单个非终结符号只能被替换为单个终结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个终结符号加上单个非终结符号。3型文法所确定的语言为3型语言L3，3型语言可由确定的有限状态自动机来识别。在常见的程序设计语言中，多数与词法有关的文法属于3型文法。可以看出，上述4类文法，从0型到3型，产生式限制越来越强，其后一类都是前一类的子集，而描述语言的功能越来越弱，四类文法及其表示的语言之间的关系可表示为：0型1型2型3型；即L0 L1 L2 L3 三、 实验目的要求 输入：一组任意的文法规则输出：相应的Chomsky文法四、 注意事项1）文法的输入应简便 2）指明是哪一类Chomsky文法，给出相应的四元组形式。五、实验心得以及实验过程中遇到的问题： 本次实验开始先是把课本好好的看了几遍，想找地方下手，之后便把Chomsky文法的判断归结为字符串的处理，但在实验过程中，为了处理方便，对于像+、*等这种符号没有纳入其中，只是规定非终结符Vn的范围是AZ，终结符的范围是az/09,而且规定了个数；对产生式定义了其左部和右部，并且规定了其长度，便于处理；另外开始对不是文法的不知道怎么判断，后来根据各种文法之间的关系得出：只要不是0型文法就不是文法，所以在0型文法判断的过程中结尾设置了一个返回值-1，当返回值为-1的时候就不是文法。六、实验源代码#include #define MaxVn 21 /定义非终结符元素个数上限#define MaxVt 21 /定义终结符元素个数上限#define MaxPNum 20 /定义规则个数上限#define MaxPLen 22 /定义产生式最大长度20char VnMaxVn,VtMaxVt;/定义非终结符集与终结符集int VnNum,VtNum,PNum; /定义实际的Vn,Vt元素个数和产生式个数typedef struct Pro /定义产生式char leftMaxPLen; /左部char rightMaxPLen;/右部Pro;Pro proMaxPNum;/=int InputInt(int maxnum) /输入并检查输入数据的合法性,保证输入数据为整数char ch;int i = 0;fflush(stdin);ch = getchar();while(ch=n)printf(t输入不能为空.请重新输入n);fflush(stdin);ch = getchar();while(ch!=n)if(ch9|chmaxnum)printf(输入数据不能大于%d!重新输入:,maxnum);i=InputInt(maxnum);return i;/=bool CheckExist(int num,char ch,char *v)/检查字符ch是否在字符数组v中int i;for(i=0;i请输入非终结符集(元素个数不超过20个,范围为A-Z)n Vn:);/输入非终结符 while(c=getchar()!=n&i=A&c输入的非终结符集合Vn为: );for(i=0;i请输入终结符集(元素个数不超过20个,范围为a-z,0-9)n Vt:);/输入终结符 fflush(stdin);i=0;while(c=getchar()!=n&i=a&c=0&c输入的终结符集合Vt为: ); for(i=0;i请输入产生式个数：); /输入产生式fflush(stdin);PNum=InputInt(MaxPNum);printf(请输入产生式（以-分隔开产生式左部与右部，如：S-bA ）n);for(i=0;iPNum;i+)printf(产生式%d:,i+1);fflush(stdin);j=0;flag=true;while(c=getchar()!=n&jMaxPLen)if(c=-)proi.leftj=0;flag=false;j=0;if(flag&c!=-)proi.leftj=c;j+; if(!flag&c!=-)proi.rightj=c;j+; proi.rightj=0;/=int Judge()/文法类型判断int i,j,len1,len2;bool flag,flag2;char ch;/-for(i=0;iPNum;i+)/0型文法判断j=0;flag2=false;while(ch=proi.leftj)!=0)flag=false;if(CheckExist(VnNum,ch,Vn)flag=true;flag2=true;if(!flag&(!CheckExist(VtNum,ch,Vt)return -1; /不是0型文法j+;if(!flag2)return -1; /左部没有非终结符j=0; while(ch=proi.rightj)!=0)flag=false;if(CheckExist(VnNum,ch,Vn)flag=true;if(!flag&(!CheckExist(VtNum,ch,Vt)return -1; /不是0型文法j+;/- for(i=0;ilen2)return 0;/不是1型文法/-for(i=0;i1)return 1;/不是2型文法/-for(i=0;iPNum;i+)/3型文法判断len2=0;j=0;flag=false;flag2=false;while(ch=proi.rightj)!=0) if(CheckExist(VtNum,ch,Vt)flag=true;if(CheckExist(VnNum,ch,Vn)flag2=true;len2+;j+;if(!flag|len22)return 2;/不是3型文法if(len2=2)if(!flag2)return 2;return 3;/是3型文法/=void Display()/显示输出文法int i,j;printf( 文法G=();for(i=0;iVnNum-1;i+)printf(%c,Vni);printf(%c,VnVnNum-1);for(i=0;iVtNum-1;i+)printf(%c,Vti);printf(%c,P,%c),其中P由下列产生式组成：n,VtVtNum-1,pro0.left0);for(i=0;i);j=0;while(pr