生成chomsky文法

《生成chomsky文法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、实验名称生成Chomsky文法二、实验原理1．0型文法（短语文法）如果对于某文法G，P中的每个规则具有下列形式：u::=v其中u∈V＋，v∈V*，则称该文法G为0型文法或短语文法，简写为PSG。0型文法或短语结构文法的相应语言称为0型语言或短语结构语言L0。这种文法由于没有其他任何限制，因此0型文法也称为无限制文法，其相应的语言称为无限制性语言。任何0型语言都是递归可枚举的，故0型语言又称递归可枚举集。这种语言可由图灵机（Turning）来识别。2．1型文法（上下文有关文法）如果对于某文法G，P中的每个规则具有下列形式：xUy::=xuy其中U∈VN；u∈

2、V＋；x，y∈V*，则称该文法G为1型文法或上下文有关文法，也称上下文敏感文法，简写为CSG。1型文法的规则左部的U和右部的u具有相同的上文x和下文y，利用该规则进行推导时，要用u替换U，必须在前面有x和后面有y的情况下才能进行，显示了上下文有关的特性。1型文法所确定的语言为1型语言L1，1型语言可由线性有界自动机来识别。3．2型文法（上下文无关文法）如果对于某文法G，P中的每个规则具有下列形式：U::=u其中U∈VN；u∈V＋，则称该文法G为2型文法或上下文无关文法，简写为CFG。按照这条规则，对于上下文无关文法，利用该规则进行推导时，无需考虑非终结符U所在

3、的上下文，总能用u替换U，或者将u归约为U，显示了上下文无关的特点。2型文法所确定的语言为2型语言L2，2型语言可由非确定的下推自动机来识别。一般定义程序设计语言的文法是上下文无关的。如C语言便是如此。因此，上下文无关文法及相应语言引起了人们较大的兴趣与重视。4．3型文法（正则文法，线性文法）如果对于某文法G，P中的每个规则具有下列形式：U::=T或U::=WT其中T∈VT；U,W∈VN，则称该文法G为左线性文法。如果对于某文法G，P中的每个规则具有下列形式：U::=T或U::=TW其中T∈VT；U,W∈VN，则称该文法G为右线性文法。左线性文法和右线性文法通

4、称为3型文法或正则文法，有时又称为有穷状态文法，简写为RG。按照定义，对于正则文法应用规则时，单个非终结符号只能被替换为单个终结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个终结符号加上单个非终结符号。3型文法所确定的语言为3型语言L3，3型语言可由确定的有限状态自动机来识别。在常见的程序设计语言中，多数与词法有关的文法属于3型文法。可以看出，上述4类文法，从0型到3型，产生式限制越来越强，其后一类都是前一类的子集，而描述语言的功能越来越弱，四类文法及其表示的语言之间的关系可表示为：0型1型2型3型；即L0L1L2L3一、实验目的要求输入：一

5、组任意的文法规则输出：相应的Chomsky文法四、注意事项1）文法的输入应简便2）指明是哪一类Chomsky文法，给出相应的四元组形式。五、实验心得以及实验过程中遇到的问题：本次实验开始先是把课本好好的看了几遍，想找地方下手，之后便把Chomsky文法的判断归结为字符串的处理，但在实验过程中，为了处理方便，对于像+、*等这种符号没有纳入其中，只是规定非终结符Vn的范围是A~Z，终结符的范围是a~z/0~9,而且规定了个数；对产生式定义了其左部和右部，并且规定了其长度，便于处理；另外开始对不是文法的不知道怎么判断，后来根据各种文法之间的关系得出：只要不是0型文法

6、就不是文法，所以在0型文法判断的过程中结尾设置了一个返回值-1，当返回值为-1的时候就不是文法。六、实验源代码#include#defineMaxVn21//定义非终结符元素个数上限#defineMaxVt21//定义终结符元素个数上限#defineMaxPNum20//定义规则个数上限#defineMaxPLen22//定义产生式最大长度20charVn[MaxVn],Vt[MaxVt];//定义非终结符集与终结符集intVnNum,VtNum,PNum;//定义实际的Vn,Vt元素个数和产生式个数typedefstructPro//定义产

7、生式{charleft[MaxPLen];//左部charright[MaxPLen];//右部}Pro;Propro[MaxPNum];//=====================================================================intInputInt(intmaxnum)//输入并检查输入数据的合法性,保证输入数据为整数{charch;inti=0;fflush(stdin);ch=getchar();while(ch==''){printf("t输入不能为空..请重新输入");fflush(std

8、in);ch=getchar();}w