《编译原理实验Chomsky文法类型判断》由会员分享，可在线阅读，更多相关《编译原理实验Chomsky文法类型判断（8页珍藏版）》请在金锄头文库上搜索。
1、1. 实验目的输入：一组任意的规则。输出：相应的Chomsky 文法的类型。2. 实验原理10型文法（短语文法）如果对于某文法G，P中的每个规则具有下列形式： u: = v其中uV，vV*，则称该文法G为0型文法或短语文法，简写为PSG。0型文法或短语结构文法的相应语言称为0型语言或短语结构语言L0。这种文法由于没有其他任何限制，因此0型文法也称为无限制文法，其相应的语言称为无限制性语言。任何0型语言都是递归可枚举的，故0型语言又称递归可枚举集。这种语言可由图灵机（Turning）来识别。21型文法（上下文有关文法）如果对于某文法G，P中的每个规则具有下列形式： xUy: = xuy其中UVN
2、；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归约
3、为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型文法或正则文法，有时又称为有穷状态文法，简写为R
4、G。按照定义，对于正则文法应用规则时，单个非终结符号只能被替换为单个终结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个终结符号加上单个非终结符号。3型文法所确定的语言为3型语言L3，3型语言可由确定的有限状态自动机来识别。在常见的程序设计语言中，多数与词法有关的文法属于3型文法。可以看出，上述4类文法，从0型到3型，产生式限制越来越强，其后一类都是前一类的子集，而描述语言的功能越来越弱，四类文法及其表示的语言之间的关系可表示为：0型1型2型3型；即L0 L1 L2 L33. .实验内容输入一组规则，指明是哪一类Chomsky 文法，并给出相应的四元组形式：G=(VN,VT,P
5、,S)。4. 实验心得通过本次实验，我了解到了如何判断一组产生式是属于哪种文法。文法的定义是逐渐增加限制的，5.实验代码与结果#include#includeusing namespace std;typedef struct Stringstring left,right;/记录当前产生式的左边和右边String;int leftlength,rightlength;/记录当前产生式的左边和右边的长度String create(string t,String s)/建立结构体，记录当前规则的左边和右边int i=0;for(i=0;i)s.left=t.substr(0,i);leftlen
6、gth=i;s.right=t.substr(i+2,t.length();rightlength=t.length()-leftlength-2;break;if(i=t.length()cout输入有误。endl;return s;int flag=0;/记录3型文法中产生式是否同为左线型或右线性int zero=0,first=0,second=0,third=0,low=6;/记录当前产生式属于哪种类型，low用来记录当前所有产生式中最低级int Zero(String s)/判断是否为0型文法int i;for(i=0;i=A&s.lefti=Z)/判断字符是否是非终结符，是则结束b
7、reak;if(i=leftlength)/遍历中左部未找到非终结字符，不是0型文法cout该文法不是0型文法endl;return 0;else/属于0型文法，type加0zero=1;return 1;int First(String s)/判断是否为1型文法if(Zero(s)/先判断是否是0型文法/判断产生式左部长度是否小于右部或者右部长度为0，这是属于1型文法if(leftlength=A&s.left0=a&s.right0=a&s.right0=A&s.right1=A&s.right0=a&s.right1=z)/左线性文法third=1;flag+=2;return 1;el
8、se/不是3型文法，但是2型文法return 0;elsereturn 0;/不是2型文法int main()int n=0,k=0;int jk;string t,stand=z;String s;cout请输入一组任意的规则（以“z”结束），空子串用“”表示：t;while(t!=stand)s=create(t,s);n+;zero=first=second=third=0;Third(s);if(third)/记录当前产生式的文法类型jk=3;else if(second)jk=2;else if(first)jk=1;else if(zero)jk=0;low=lowt;if(low=3)if(flag%n=0)cout这是3型文法。;else if(low=2)cout这是2型文法。;else if(low=1)cout这是1型文法。;else if(low=0)cout这是0型文法。;else if(low=2)cout这是2型文法。;else if(low=1)cout这是1型文法。;else if(low=0)cout这是0型文法。;return 0;运行结果：
