编译原理方法分类.doc

《编译原理方法分类.doc》由会员分享，可在线阅读，更多相关《编译原理方法分类.doc（18页珍藏版）》请在三一办公上搜索。

1、编号： 实习一二三四五六七八九十总评教师签名成绩实习题目： 文法分类 专业（班）： 13级计科六班 学生学号： 2013311500123 学生姓名： 刘 冠 佐 任课教师： 杜卓敏 评语及建议：年 10 月 13 日编号： 实习一二三四五六七八九十总评教师签名成绩武汉大学计算机学院编译原理课程实习报告编 号： 实习题目： 文法分类 专业（班）： 2013级计科六班 学生学号： 2013311500123 学生姓名： 刘 冠 佐 任课教师： 杜卓敏 年 10 月 13 日1. 题目：文法分类2. 目的：熟悉和掌握文法的形式定义及各成分的含义，正确识别文法的类型。3. 要求：（1） 主要功能：识

2、别各类Chomsky文法（2） 系统输入：任意的文法G的Vn,P和S（3） 系统输出： a)文法的形式化表示G=(Vn,Vt,P,S) b)文法的Chomsky类型(0型、1型、2型、3型）（4）为了简单期间，文发符号都采用单字符符号（5）有独到个后选式的产生式允许采用缩写形式（:=1/2/n)作为产生式的输入形式（6）提交算法描述，最好提供某样详细设计表示（如程序框图、伪码等），而不用提交源程序清单4.程序运行实例：输入： 提示输入文法：GN 提示输入Vn：N,D 提示依次输入产生式规则：N：=ND/D D：=0/1/2/3/4/5/6/7/8/9输出： 文法GN=(N,D,0，1，2，3，

3、4，5，6，7，8，9,P,N) P: N：=ND/D D：=0/1/2/3/4/5/6/7/8/9 该文法是Chomsky2型文法（即上下文无关文法）。1. 问题定义与分析1.1 实习目的 熟悉和掌握文法的形式定义及各成分的含义，正确识别文法的类型。1.2 实习要求 （1） 主要功能：识别各类 Chomsky文法 （2） 系统输入：任意的文法 G 的 VN，P和 S （3） 系统输出： a) 文法的形式化表示 G=(VN，VT，P，S) b) 文法的 Chomsky类型（0型、1型、2型、3型） （4） 为简单起见，文法符号都采用单字符符号。 （5） 有多个候选式的产生式允许采用缩写形式（:

4、= 1|2|n）作为产生式的输入形式 （6） 要求按照软件工程的原则进行实习设计，提交实习报告，即必要的软件工程文档（可将主要内容压缩成一个文档） ，内容至少包括：问题定义和分析、设计（数据结构、算法、界面等） 、主要测试用例（应如实提供测试结果）等。最好提供某种详细设计表示（如程序框图、伪码等），而不用提交源程序清单。 1.3 要求分析1.3.1 输入部分对于文法G用字符串String s保存；非终结字符集合VN，用数组c保存，String s1=jTextField2.getText();/获取VN,char c=s1.toCharArray()；产生式规则P的用二维数组P保存：char

5、P=new char1020; String s2=jTextArea1.getText();/获取产生式规则 StringTokenizer tokenizer=new StringTokenizer(s2); int sum=tokenizer.countTokens(); int j; String s4=; for(j=0;jsum;j+) String s6=tokenizer.nextToken(); s4=s4+s6+n; Pj=s6.toCharArray();/将产生式转换为数组保存 1.3.2 输出部分非终结字符用一个数组N保存输出： String s1=jTextFiel

6、d2.getText();/获取VN char c=s1.toCharArray(); while(ic.length)if(ci!=,)Nm=ci;m+;i+;终结字符用一个数组T保存： for(j=0;jPi.length;j+) if(Pij!=:&Pij!=&Pij!=|&Is(N, Pij)=0&Is(T, Pij)=0) Tm=Pij; m+; 对于文法G的输出还是用String s，在获取的文法名的基础上加上文法内容，文法内容为后面加上： String s=jTextField1.getText();/s用于输出文法s=s+=(+s1+,; String s3=; i=0; wh

7、ile(im) if(i+1m) s3=s3+Ti+,;/将终结字符串中的字符加上，输出 else s3=s3 +Ti;/终结字符串的最后一个字符不用加， i+; s=s+s3+,P,+c0+); jTextField3.setText(s);产生式规则的输出用String s4表示： String s4=;for(j=0;jsum;j+) String s6=tokenizer.nextToken(); s4=s4+s6+n; jTextArea2.setText(s4);对于判定结果的输出，用String s5表示： String s5=;/根据算法结果决定输入的文法为哪种类型，则对应给s

8、5赋不同字符串case 1:if(flag=1) s5=s5+该文法是Chomsky0 型文法（即短语结构文法）!;else s5=s5+该文法是Chomsky1 型文法（即上下文有关文法）!;dase 2: if(flag=1) s5=s5+该文法是Chomsky2 型文法（即上下文无关文法）!;else s5=s5+该文法是Chomsky3 型文法（即正规文法）!;1.3.3 判定过程 具体的判定算法由各种方法的特点所决定： 首先，因为于2型方法与3型文法的产生式的左部都是单个非终结符，所以若待判定方法的左部是单个非终结符，则可确定其为2型或3型方法，此时已将4种方法分为两组，即0型与1型

9、一组、2型与3型一组； 其次，对于2型与3型文法，因为3型文法是对2型文法的进一步限制。即2型文法产生式右部是由终结符和非终结符组成的符号串，有以下形式的产生式： A:= ，其中A属于VN，属于终结符和非终结符组成的符号串。 而3型文法限制产生式右部是单一终结符或单一终结符跟着单一非终结符，即： A:=a 或A:=aB所以，可通过对产生式的右部判断来区分2型与3型文法。 最后，对于0型与1型文法，因为0型文法产生式的左部与右部都是符号串，没任何限制，所以可以通过1型文法的限制来区分；1型文法的限制如下所示： := ，其中1| 且1型文法的左部必须有非终结字符。2. 设计2.1 数据结构 定义了

10、以下字符串类型数据：String s ：用于接受用户输入的文法名与输出最终的完整文法，如：接受输入s=GN，输出s=GN（N,D, 0,1,2,3,4,5,6,7,8,9, P, N） String s1：用于获取VNchar c=s1.toCharArray() ：用于将s1字符串转换为数组char N=new char10 ：用于保存去除，的纯非终结字符如：输入 S，A，B，C 则 s1=S,A,B,C; c=S,A,B,C; N=S A B Cchar T=new char20 ：用于保存纯终结字符如： 其中一个产生式规则P为N：=1|2|3|4 ， 则T=1 2 3 4String s

11、2： 用于获取产生式规则StringTokenizer tokenizer ：用于按回车符区分不同产生式，以便按序分别获取产生式char P=new char1020 ：用于将产生式规则用二维数组保存String s4 ：用于输出产生式规则的字符串 String s5 ：用于输出判定结果，即输出为哪一类文法若为2型文法，则s5=“该文法是Chomsky2 型文法（即上下文无关文法）!”以下是各个控件的定义： private javax.swing.JButton jButton1; 确定按钮 private javax.swing.JButton jButton2; 清空按钮private j

12、avax.swing.JButton jButton3; 退出按钮静态文本的输出，即在界面上显示输入、输出、方法等提示文字： private javax.swing.JLabel jLabel1; private javax.swing.JLabel jLabel2; private javax.swing.JLabel jLabel3; private javax.swing.JLabel jLabel4; private javax.swing.JLabel jLabel5; private javax.swing.JLabel jLabel6;private javax.swing.JL

13、abel jLabel7; private javax.swing.JLabel jLabel8; private javax.swing.JTextArea jTextArea1; 输入产生式规则框 private javax.swing.JTextArea jTextArea2; 输出产生式规则框 private javax.swing.JTextField jTextField1; 输入文法名框 private javax.swing.JTextField jTextField2; 输入文法的VN的框 private javax.swing.JTextField jTextField3;

14、 输出完整文法定义的框private javax.swing.JTextField jTextField4; 输出是哪类文法的框如下图所示：2.2. 算法及程序流程图2.2.1算法描述如下： 对于输入的产生式规则：1. 判断是否为合法的文法：是转4，否继续；2. 提示有误，是否重新输入：是转1，否继续；3. 退出系统。4. 通过产生式规则的左部，确定文法类型是2、3型还是0、1型，定义变量fI作为区分此两大类方法：fI=1（表示为0、1型），继续；fI=2（表示为2、3型），转9（fI用于控制switch语句执行）；5. 判断每个产生式左部是否都含有非终结字符：否，转8；是，继续；6. 判断文

15、法每个产生式规则左部的字符串的数量是否小于等于右部的字符串的数量：是，继续；否，转8；7. 此文法为1型文法；8. 此文法为0型文法；9. 判断每个产生式规则右部字符数是否小于等于2：是，继续；否，转13；10. 判断每个产生式规则右部字符数为1的字符是否为终结字符：是，继续；否，转13；11. 判断每个产生式规则右部字符数为2的字符串是否为一个终结符后面跟着一个非终结符：是，继续；否，转13；12. 此文法为3型文法；13. 此文法为2型文法；NNNNNYYYY此文法为1型文法每个产生式左部皆含VN？每个产生式左部字符数目小于等于右部字符的数目？Sum0=2时，为一终结符跟着一非终结字符？此

16、文法为3型文法N开始输入文法、VN、P文法合法？重新输入？Y结束N产生式左部皆为一个非终结字符？YfI=1fI=2NY每个产生式右部字符数sum0皆小于等于2？Sum0=1时，此字符为终结字符？此文法为2型文法此文法为0型文法Y2.2.1程序流程图如下： 2.3. 界面3. 程序运行实例 3.1 3 型文法 3.2 2 型文法 3.3 1 型文法 3.4 0 型文法 3.5 非合法文法输入选是，继续输入：选否，退出程序。对于清空按钮，点击则清空所有文本框；对于退出按钮，点击则退出程序。4. 程序核心源代码 public int Is(char a,char c) /判断字符c是否在数组a中in

17、t s=0,f=0;while(sa.length)if(as=c)f=1;s+;return f;public int Sum(char a) /计算数组a中字符|的数目int s=0,i=0;for(i=0;ia.length;i+) if(ai=|) s+;return s;/ 以下代码为判定输入的文法为哪类文法，参数R是存在二维数组中的产生式规则，参/ 数j是通过之前的代码已确定该文法为0、1型（j=1）还是2、3型(j=2)，参数sum / 是产生式规则的数量，参数T是终结字符的数组，参数N是非终结字符的数组。public void Classify(char R,int j,int

18、 sum,char T,char N)int flag=0; String s5=;switch(j)case 1: /通过传递的参数知，为0、1型，case 1中为判断具体是0型还是1型文法for(int i=0;isum;i+) int flag0=0; int i2=0,j2,k=0,k2; int sum1=Sum(Ri);while(Rii2!=:) if(Is(N, Rii2)=1) flag0=1; i2+; if(flag0=0) flag=1; break; j2=i2+3;k2=j2;for (k=0;ksum1+1;k+)while(k2k2-j2)flag=1;brea

19、k;elsek2+;j2=k2; if(flag=1)break;i+; if(flag=1) s5=s5+该文法是Chomsky0 型文法（即短语结构文法）!;else s5=s5+该文法是Chomsky1 型文法（即上下文有关文法）!;break;case 2: /通过传递的参数知，为2、3型，case 2中为判断具体是2型还是3型文法for(int i=0;isum;i+)int i1=4,j1=4,l,sum0;sum0=Sum(Ri);for(int k=0;ksum0+1;k+) while(j1=3) flag=1; break; else if(Is(T,Rii1)=1&(Is(N,Rii1+1)=1|Rii1+1=|) j1+; i1=j1; continue; else flag=1; break; if(flag=1) break;i+; if(flag=1) s5=s5+该文法是Chomsky2 型文法（即上下文无关文法）!;else s5=s5+该文法是Chomsky3 型文法（即正规文法）!;break; jTextField4.setText(s5); /在显示框中显示文法类型