1编译原理实验报告实验名称Chomsky文法类型判断实验时间2014.04.02院系计算机科学与技术学院班级XXXXXXXXX学号XXXXXXX姓名XXXX21.试验目的:上机实验有助于我们发现理论课学习中无法发现的问题,通过上机实验操作,进一步加深对理论课所学的“Chomsky文法类型判断”的理解,同时提升自己的编程能力,为以后的学习打下良好的基础。2.实验原理①0型文法(短语文法)如果对于某文法G,P中的每个规则具有下列形式:u-v其中u∈V+,v∈V*,则称该文法G为0型文法或短语文法,简写为PSG。0型文法或短语结构文法的相应语言称为0型语言或短语结构语言L0。这种文法由于没有其他任何限制,因此0型文法也称为无限制文法,其相应的语言称为无限制性语言。任何0型语言都是递归可枚举的,故0型语言又称递归可枚举集。这种语言可由图灵机(Turning)来识别。②1型文法(上下文有关文法)如果对于某文法G,P中的每个规则具有下列形式:xUy-xuy其中U∈VN;u∈V+;x,y∈V*,则称该文法G为1型文法或上下文有关文法,也称上下文敏感文法,简写为CSG。1型文法的规则左部的U和右部的u具有相同的上文x和下文y,利用该规则进行推导时,要用u替换U,必须在前面有x和后面有y的情况下才能进行,显示了上下文有关的特性。1型文法所确定的语言为1型语言L1,1型语言可由线性有界自动机来识别。③2型文法(上下文无关文法)如果对于某文法G,P中的每个规则具有下列形式:U-u其中U∈VN;u∈V+,则称该文法G为2型文法或上下文无关文法,简写为CFG。按照这条规则,对于上下文无关文法,利用该规则进行推导时,无需考虑非终结符U所在的上下文,总能用u替换U,或者将u归约为U,显示了上下文无关的特点。2型文法所确定的语言为2型语言L2,2型语言可由非确定的下推自动机来识别。一般定义程序设计语言的文法是上下文无关的。如C语言便是如此。因此,上下文无关文法及相应语言引起了人们较大的兴趣与重视。④3型文法(正则文法,线性文法)如果对于某文法G,P中的每个规则具有下列形式:U-T或U-WT其中T∈VT;U,W∈VN,则称该文法G为左线性文法。如果对于某文法G,P中的每个规则具有下列形式:3U-=T或U-TW其中T∈VT;U,W∈VN,则称该文法G为右线性文法。左线性文法和右线性文法通称为3型文法或正则文法,有时又称为有穷状态文法,简写为RG。按照定义,对于正则文法应用规则时,单个非终结符号只能被替换为单个终结符号,或被替换为单个非终结符号加上单个终结符号,或者被替换为单个终结符号加上单个非终结符号。3型文法所确定的语言为3型语言L3,3型语言可由确定的有限状态自动机来识别。在常见的程序设计语言中,多数与词法有关的文法属于3型文法。可以看出,上述4类文法,从0型到3型,产生式限制越来越强,其后一类都是前一类的子集,而描述语言的功能越来越弱,四类文法及其表示的语言之间的关系可表示为:0型1型2型3型;即L0L1L2L33.实验内容输入:一组任意的规则。输出:相应的Chomsky文法的类型。注意事项:⑴文法的输入应简便。⑵指明是哪一类Chomsky文法,并给出相应的四元组形式:G=(VN,VT,P,S)。说明:简单起见,可以不考虑0型文法类。4.实验心得本次实验,我最大的体会就是我们不仅要熟练地掌握书本上的知识,更重要的是能够把学到的知识应用到上机编程中,这样才能算是真正学会了书本上所讲的知识。在编写代码的过程中,我发现自己对3型文法的概念没有理解清楚,认为在对某个3型文法进行判断时,可以同时使用左线性文法和右线性文法,结果实际测试的过程中发现了错误,后来向别的同学请教及时发现并改正了错误;在对文法的各个要素进行输入的过程中,我也遇到了问题,主要是各种输入非法的情况考虑不周全,后来经过改正,修改了自己发现的所有错误,并及时改正了在测试中发现的问题,但仍无法保证所有的边界情况都考虑周全,这也是本实验所欠缺的地方,以后我会继续努力。我想,学习是个持之以恒的过程,如果真正想学好编译原理的话,光靠实验课的时间是远远不够的,所以以后我一定要加强学习,坚持不懈,一切努力都是值得的。45.实验代码与结果本实验使用java语言编写,编程工具是eclipse,实验运行结果如下:⑴几种非法输入测试①产生式左部不含有非终结符:②产生式的左部含有非法字符。还有一些其他的非法输入,在此就不一一举例。⑵正确的输入:①数据一:(3型文法)G=({S,A,B},{1,2},P,S),P={S-1A,S-1,A-2B,B-1B,B-2S};首先是数据的输入:输入包括:非终结符集和终结符集的输入、产生式的个数、依次输入产生式的左部和右部以及开始符。5实验结果:②数据二:(2型文法)G=({S},{0,1},P,S),P={S-0S1,S-01};数据的输入:6实验结果:实验源代码如下:importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;;publicclassChomsky{String[]left=newString[10];//产生式左部String[]right=newString[10];//产生式右部StringVn=newString();//非终结符集合StringVt=newString();//终结符集合int[]type=newint[20];//标记文法的类型charstart;//开始符intcount;//产生式的个数booleanmark1=true,mark2=true;publicvoidGetIn(BufferedReaderf)//输入方法{try7{booleanmark=true;System.out.println(||实验一:Chomsky文法类型判断||\n);System.out.println(请输入非终结符集Vn:);Vn=f.readLine();System.out.println(请输入终结符集Vt:);Vt=f.readLine();StringV=Vn+Vt;System.out.println(请输入产生式的个数:);Strings=f.readLine();count=Integer.parseInt(s);for(inti=0;icount;i++)//输入产生式左部{System.out.println(请输入第+(i+1)+个产生式的左部:);left[i]=f.readLine();if((IsVh(left[i],V))==true){for(intj=0;jleft[i].length();j++){if(IsChar(left[i].charAt(j),Vn)==true){mark=true;break;}if((j+1)==left[i].length())mark=false;}}else{System.out.println(输入非法!);System.exit(0);}}if(mark==false){System.out.println(产生式左部皆为终结符号,输入非法!);System.exit(0);}for(inti=0;icount;i++)//输入产生式右部{System.out.println(请输入第+(i+1)+个产生式的右部:);right[i]=f.readLine();if(right[i]!=null)8{if((IsVh(right[i],V))==false){System.out.println(输入非法!);System.exit(0);}}}System.out.println(请输入开始符:);start=(char)f.read();for(inti=0;icount;i++){if(IsChar(start,left[i])==true){if(IsChar(start,Vn)==true){break;}else{System.out.println(开始符为终结符,输入非法!);System.exit(0);}}else{if((i+1)==count){System.out.println(产生式左部不含有开始符,输入非法!);System.exit(0);}}}System.out.println(输入成功!\n);OutPut();}catch(IOExceptione){System.err.println(发生异常:+e);e.printStackTrace();}}publicvoidOutPut()//输出方法{9System.out.println(生成的文法G为:);System.out.print(G=({);for(inti=0;iVn.length();i++){System.out.print(Vn.charAt(i));if((i+1)!=Vn.length())System.out.print(,);}System.out.print(},{);for(inti=0;iVt.length();i++){System.out.print(Vt.charAt(i));if((i+1)!=Vt.length())System.out.print(,);}System.out.println(},P,+start+));System.out.print(P={);for(inti=0;icount;i++){System.out.print(left[i]+-+right[i]);if((i+1)!=count)System.out.print(,);}System.out.println(};);Recognize();}publicvoidRecognize()//判别方法{for(inti=0;icount;i++){if(right[i].length()=left[i].length())//1型文法判别条件{type[i]=1;if(IsVh(left[i],Vn)==true&&(left[i].length()==1))//2型文法判别条件{type[i]=2;if(right[i].length()==1&&IsChar(right[i].charAt(0),Vt))type[i]=3;if(right[i].length()==2&&mark1==true){if(IsChar(right[i].charAt(0),Vt)&&IsChar(right[i].charAt(1),Vn))type[i]=3;else10type[i]=2;mark2=false;}if(right[i].length()==2&&mark2==true){if(IsChar(right[i].charAt(0),Vn)&&IsChar(right[i].charAt(1),Vt))type[i]=3;elsetype[i]=2;mark1=false;}}elsetype[i]=1;}elsetype[i]=0;}intmin=type[0];for(inti=1;icount;i++){if(type[i]=min)min=type[i];}System.out.println(G是+min+型文法.);}publicbooleanIsVh(Stringstr,StringVh)//判断字符串是否在某个集合中{for(intj=0;jstr.length();j++){for(intk=0;kVh.length();k++){if(str.charAt(j)==Vh.charAt(k))break;if((k+1)==Vh.length())returnfalse;}}returntrue;}publicbooleanIsChar(cha