chomsky文法类型的判断

1、编译原理实验报告实验名称Chomsky文法类型判断实验时间2014-4-2院系计算机科学与技术学院班级2011级科技（3）班学号E011143万姓名张练钢1.实验目的(1)通过实验进一步理解Chomsky文法类型判断的的依据，理解每个类型文法 的特点。(2)进一步理解4种文法类型之间的包含关系。(3)体会这种理论对于计算机科学发展的深刻影响，特别是对程序设计语言的 设计、编译方法和计算复杂性等方面的重大作用。通过上机实现文法类型的自动 判别。2 .实验原理1 . o型文法(短语文法)如杲对于某文法G, P中的每个规则具有下列形式：U： = V其中uGV+, vV,则称该文法G为()型文法或短语

2、文法，简写为PSG。0型文法或短语结构文法的相应语言称为0型语言或短语结构语言Uo这种 文法由于没有其他任何限制，因此0型文法也称为无限制文法，其相应的语言称 为无限制性语言。任何()型语言都是递归可枚举的，故。型语言又称递归可枚举 集。这种语言可由图灵机(Turning)来识别。2 .1型文法(上下文有关文法)如果对于某文法G, P中的每个规则具有下列形式：xUy: = xiivJJ其中UGV、； uGV+； x, yGV,则称该文法G为1型文法或上下文有关文 法，也称上下文敏感文法，简写为CSG。1型文法的规则左部的U和右部的u具有相同的上文x和下文y,利用该规 则进行推导时，要用u替换U

3、,必须在前面有x和后面有y的情况下才能进行， 显示了上下文有关的特性。1型文法所确定的语言为1型语言L.,1型语言可由线性有界自动机来识别。3.2型文法（上下文无关文法）如杲对于某文法G, P中的每个规则具有下列形式：U : 二 u其中UGV、； uV-,则称该文法G为2型文法或上下文无关文法，简写为 CFG。按照这条规则，对于上下文无关文法，利用该规则进行推导时，无需考虑非 终结符U所在的上下文，总能用u替换U,或者将归约为U,显示了上下文无 关的特点。2型文法所确定的语言为2型语言L2, 2型语言可由非确定的下推自动机来 识别。一般定义程序设计语言的文法是上下文无关的。如C语言便是如此。因

4、此, 上下文无关文法及相应语言引起了人们较大的兴趣与重视。4. 3型文法（正则文法，线性文法）如杲对于某文法G, P中的每个规则具有下列形式:U: = T 或 U :二 WT其中TGVt；则称该文法G为左线性文法。如果对于某文法G, P中的每个规则具有下列形式：U := T 或 U :二 TW其中TVt； G,WVn,则称该文法G为右线性文法。左线性文法和右线性文法通称为3型文法或正则文法，有时又称为有穷状态 文法，简写为RG。按照定义，对于正则文法应用规则时，单个非终结符号只能被替换为单个终 结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个终结 符号加上单个非终结符号。3型

5、文法所确定的语言为3型语言3型语言可由确定的有限状态自动机 来识别。在常见的程序设计语言中，多数与词法有关的文法属于3型文法。可以看出，上述4类文法，从。型到3型，产生式限制越来越强，其后一 类都是前一类的子集，而描述语言的功能越来越弱，四类文法及其表示的语言 之间的关系可表示为：0 型n 1 型2 型n 3 型；即 LQ Lq L,z> L3 .实验内容(1)理解四种文法类型的特点，并利用他们之间包含关系()型>1型>2 型=>3型；即3户L2=> L对所属类型作出判断。(2)通过编程自动实现将输入的文法判断出其所属类型。4 .实验心得本实验的上机实现需注意一下

6、几点：(0数据的表示，利用struct constring front;string end;；定义每个产生式的结构如A:=a则front=A,cnd=a;因为每个文法都有多个产生式，我们将这多个文法依次存入一个string类型 的gt数组中，然后再将每个产生式分解成前端和后端的梏式以便于分析每个产 生式所属的类型。(2)在对文法进行判断前先对每个产生式作出判断，那么所有产生式中文 法类型最低的那个产生式所属的类型即为该文法所属的类型。(3)在对每个每个产生的类型做出判断时要充分利用四种文法类型之间的 包含关系以简化程序。如3型文法和2型文法的产生前端都为一个非终端符我们 可以先利用这个特点先

7、判断一个产生式是否属于3型文法或2型文法，如果不符 合以上条件然后在判断其是否属于1型或()型文法。(4)在代码的编写过程中注意代码的结构以方便阅读。5 .实验代码与结果/*作者： 张练钢(E01114375)完成时间：2014-4-5程序任务：Chomsky文法类型的判断运行环境：vc+ 6.0*/#includc<iostrcam>#includc<string>#includc<vcctor>using namespace std;struct constring front; string end;；定义每个产生式的结构如A:=a则froni=A,c

8、nd=a;string VNT;/非终端符集合 string VT; 终端符集合void dccomp()sc(string s, con &rcs)a 则 front=A,end=a;/该函数负责将输入的每个产生式转换成con结构如A:= int flagl=0,flag2=0;f()r(int i=O;i<s.sizc();i+) Hagi =i; else if(si='=") flag2=i; rcs.fn)nt=s.substr(O,flagl-l); d=s.substr(flag2+1 ,s.sizc()-l);bool isBclongT()VN

9、T(char s)/判断一个字符是否属于非终端字符 fbr(int i=Op<VNT.sizeO+) if(VNTi=s) return 1; return 0;bool isBcl()ngT()VT(char s)判断一个字符是否属于终端字符for(int i=Op<VT.sizeO；i+)if(VTi=s)return 1;return 0;bool isBclongT<)V(char s)判断一个字符是否属于VNT U NTstring tcm=VNT+VT;因为终端符和非终端符没有交集所以两个字符串直接连接的结 果即为VNTUNTf()r(int i=0;i<t

10、cm.sizc();i+)if(lcmi=s)return 1;return 0;int judgcTypc()fP(con sen)判断每个产生式的类型int flag=O;f()r(int i=0;i<scn.front.sizc();i+)(1珏电1。1吆六代"911电)=0)如果产生式前端中含有非V中的元素则不属于任 何文法类型flag=l;break;if(flag=l)return -1;flag=0;f()r(i=O;i<d.sizc();i+)if(isBck)ngT(>V(di)=O && smendi!=V)如果产生式后端端中含有

11、非 V 中 的元素(空''除外)则不属于任何文法类型flag=l;break;if(flag= = l)return -1;if(sen.front sizc()=1)若产生式的前端是一个非终端符则判断其是2型文法还是3型文法 char tcm=sen.fr()ntO;if(isBelongToVNT(tem)如果front为非终端符则先判断该产生式是不是正规文法或2型文法的结构 if(d.sizcQ=1) (1电89。1以1六叮3】曰】80)如果是A:=a则属于正规文法 return 3;elsereturn 2; /因为该产生式的前端是非终端字符所以满足2型文法的 要求巳经

12、包含S:=u(u为空)else if(scii.ciid.sizc0=2) if(isBclongT(>VNT(dl)&&isBclongT()T(d0)/ 如果是 A:=aB 则属于正规文法 return 3; elsereturn 2;/clsc if(d.sizc()=2)/if(isBclongToVNT(tem) else return-1;如果产生的前端没有非终端符则不符合任何类型的文法/i f(scn.frontsizcO=1)else ( int flag=O;f()r(int i=0;i<scn.fr(>iiLsizcO；i+) ：电8。吟丁

13、。小华5任皿臼)先判断其是否含有非终端符，如果没有则不符 合任何文法类型 flag=l; break;)if(flag=O)return -1;elseif(S-&8以0>=5皿缶皿*12助如果产生式心邛满足|阳>=|0(|则符合1型文 法的要求，否则就是零型文法return 1;elsereturn 0;void judgc(int rcs1003nt count)/根据每个产生式的类型判断文法的类型int j,flag=l;sntch(rcsO)(ease 3:f()r(j=0;j <count;j+)if(rcsj<3)flag=0;break;if(fl

14、ag=l)coutvv”这是3型文法“vvmdl；如果所有的产生式都是3型文法则该文法 为3型文法break;case 2:flag=l；fbr( j=0;j<count;j+)if(rcsj<2)flag=0;break;if(flag=l)coutvv”这是2型文法“vvedl；如果所有的产生式都是 法则该文法为2型文法break;case 1:flag=l;f()r(j=0;j <count;j+)if(rcsj<l)flag=O;break;if(flag=l)coutvv”这是1型文法“vvmdl;如果所有的产生式都是 法则该文法为1型文法break;ease

15、 0:flag=l;for(j=0;j < co unt;j+)if(rcsj<0)flag=0;break;if(flag=l)coutvv”这是0型文法“vvmdl；如果所有的产生式都是法则该文法为0型文法型及以上类型文型及以上类型文型及以上类型文break; default:coutvv"这不是任何类型的文法,«cndl; int main。int count=0;记录输入产生式的个数string tcst10(q； 存放每个文法的产生式chariemtlOO;临时输入的字符串int rcs1OO;用于存放每个产生式的判别结果coutvv”请先输入非终端符

16、：Vendl;cin»tcm;VNT=icm;cout<"请输入终端符号"<<cndl;cin»tcm;VT=km;coutv<”请输入产生式：最后一条产生式以EOF结束"vndl； while(cin»tem)tcstcount+=tcm;f()r(int i=0;i<count;i+)(con s;decofnpose(testi ,s);resi=judgcTypeOfP(s);/对每个产生式的类型做出判断judgc(rus,coum); 对文法类型作出判断count=0;return 0;)结果：(0 0型文法：(2) 1型文法_口 xs "F:缰译原理实药chosky文法关里识知Debugchosky文法类型识别.exe请先输入非终端符，flBCD请输入终端符号aibcd请输入产生式：最后一条产生或