chomsky文法类型的判断.doc

编译原理实验报告实验名称 Chomsky文法类型判断 实验时间 2014-4-2 院系 计算机科学与技术学院 班级 2011级科技（3）班 学号 E01114375 姓名 张练钢 1. 实验目的（1）通过实验进一步理解chomsky文法类型判断的的依据，理解每个类型文法的特点。（2）进一步理解4种文法类型之间的包含关系。（3）体会这种理论对于计算机科学发展的深刻影响，特别是对程序设计语言的设计、编译方法和计算复杂性等方面的重大作用。通过上机实现文法类型的自动判别。2.实验原理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.实验内容（1）理解四种文法类型的特点，并利用他们之间包含关系0型1型2型3型；即L0 L1 L2 L对所属类型作出判断。（2）通过编程自动实现将输入的文法判断出其所属类型。4.实验心得本实验的上机实现需注意一下几点：（1）数据的表示，利用struct constring front;string end;/定义每个产生式的结构如A:=a 则front=A,end=a;因为每个文法都有多个产生式，我们将这多个文法依次存入一个string类型的test数组中，然后再将每个产生式分解成前端和后端的格式以便于分析每个产生式所属的类型。（2）在对文法进行判断前先对每个产生式作出判断，那么所有产生式中文法类型最低的那个产生式所属的类型即为该文法所属的类型。（3）在对每个每个产生的类型做出判断时要充分利用四种文法类型之间的包含关系以简化程序。如3型文法和2型文法的产生前端都为一个非终端符我们可以先利用这个特点先判断一个产生式是否属于3型文法或2型文法，如果不符合以上条件然后在判断其是否属于1型或0型文法。（4）在代码的编写过程中注意代码的结构以方便阅读。5.实验代码与结果/* 作者： 张练钢（E01114375） 完成时间：2014-4-5 程序任务：chomsky文法类型的判断 运行环境：vc+ 6.0 */#include#include#includeusing namespace std;struct constring front;string end;/定义每个产生式的结构如A:=a 则front=A,end=a;string VNT;/非终端符集合string VT;/终端符集合void decompose(string s, con &res)/该函数负责将输入的每个产生式转换成con结构如A:=a 则front=A,end=a;int flag1=0,flag2=0;for(int i=0;is.size();i+)if(si=:)flag1=i;else if(si=)flag2=i;res.front=s.substr(0,flag1-1);res.end=s.substr(flag2+1,s.size()-1);bool isBelongToVNT(char s)/判断一个字符是否属于非终端字符for(int i=0;iVNT.size();i+)if(VNTi=s)return 1;return 0;bool isBelongToVT(char s)/判断一个字符是否属于终端字符for(int i=0;iVT.size();i+)if(VTi=s)return 1;return 0;bool isBelongToV(char s)/判断一个字符是否属于VNT U NTstring tem=VNT+VT;/因为终端符和非终端符没有交集所以两个字符串直接连接的结果即为VNT U NTfor(int i=0;item.size();i+)if(temi=s)return 1;return 0;int judgeTypeOfP(con sen)/判断每个产生式的类型int flag=0;for(int i=0;isen.front.size();i+)if(isBelongToV(sen.fronti)=0)/如果产生式前端中含有非V中的元素则不属于任何文法类型flag=1;break;if(flag=1)return -1;flag=0;for(i=0;isen.end.size();i+)if(isBelongToV(sen.endi)=0 & sen.endi!=e)/如果产生式后端端中含有非V中的元素(空e除外)则不属于任何文法类型flag=1;break;if(flag=1)return -1;if(sen.front.size()=1)/若产生式的前端是一个非终端符则判断其是2型文法还是3型文法char tem=sen.front0;if(isBelongToVNT(tem)/如果front为非终端符则先判断该产生式是不是正规文法或2型文法的结构if(sen.end.size()=1)if(isBelongToVT(sen.end0)/如果是A:=a则属于正规文法return 3;elsereturn 2; /因为该产生式的前端是非终端字符所以满足2型文法的要求已经包含S:=e(e为空)else if(sen.end.size()=2)if(isBelongToVNT(sen.end1)&isBelongToVT(sen.end0)/如果是A:=aB则属于正规文法return 3;elsereturn 2;/else if(sen.end.size()=2)/if(isBelongToVNT(tem)elsereturn -1; /如果产生的前端没有非终端符则不符合任何类型的文法/if(sen.front.size()=1)else int flag=0;for(int i=0;i=sen.front.size()/如果产生式-满足|=|则符合1型文法的要求，否则就是零型文法return 1;elsereturn 0;void judge(int res100,int count)/根据每个产生式的类型判断文法的类型int j,flag=1;switch(res0)case 3:for(j=0;jcount;j+)if(resj3)flag=0;break;if(flag=1)cout这是 3 型文法 endl;/如果所有的产生式都是3型文法则该文法为3型文法break;case 2:flag=1;for( j=0;jcount;j+)if(resj2)flag=0;break;if(flag=1)cout这是 2 型文法 endl;/如果所有的产生式都是2型及以上类型文法则该文法为2型文法break;case 1:flag=1;for(j=0;jcount;j+)if(resj1)flag=0;break;if(flag=1)cout这是 1 型文法 endl;/如果所有的产生式都是1型及以上类型文法则该文法为1型文法break;case 0:flag=1;for(j=0;jcount;j+)if(resj0)flag=0;break;if(flag=1)cout这是 0 型文法 endl;/如果所有的产生式都是0型及以上类型文法则该文法为0型文法break;default :cout这不是任何类型的文法 endl;int main()int count=0; /记录输入产生式的个数string test100; /存放每个文法的产生式char tem100; /临时输入的字符串int res100; /用于存放每个产生式的判别结果cout请先输入非终端符：tem;VNT=tem;cout请输入终端符号tem;VT=tem;cout请输入产生式：最后一条产生式以EOF结束tem )testc