編譯原理-方法分類

1、編號： 實習(xí)一二三四五六七八九十總評教師簽名成績實習(xí)題目： 文法分類 專業(yè)（班）： 13級計科六班 學(xué)生學(xué)號： 2013311500123 學(xué)生姓名： 劉 冠 佐 任課教師： 杜卓敏 評語及建議：年 10 月 13 日編號： 實習(xí)一二三四五六七八九十總評教師簽名成績武漢大學(xué)計算機學(xué)院編譯原理課程實習(xí)報告編 號： 實習(xí)題目： 文法分類 專業(yè)（班）： 2013級計科六班 學(xué)生學(xué)號： 2013311500123 學(xué)生姓名： 劉 冠 佐 任課教師： 杜卓敏 年 10 月 13 日1. 題目：文法分類2. 目的：熟悉和掌握文法的形式定義及各成分的含義，正確識別文法的類型。3. 要求：（1） 主要功能：識

2、別各類Chomsky文法（2） 系統(tǒng)輸入：任意的文法G的Vn,P和S（3） 系統(tǒng)輸出： a)文法的形式化表示G=(Vn,Vt,P,S) b)文法的Chomsky類型(0型、1型、2型、3型）（4）為了簡單期間，文發(fā)符號都采用單字符符號（5）有獨到個后選式的產(chǎn)生式允許采用縮寫形式（:=1/2/n)作為產(chǎn)生式的輸入形式（6）提交算法描述，最好提供某樣詳細(xì)設(shè)計表示（如程序框圖、偽碼等），而不用提交源程序清單4.程序運行實例：輸入： 提示輸入文法：GN 提示輸入Vn：N,D 提示依次輸入產(chǎn)生式規(guī)則：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型文法（即上下文無關(guān)文法）。1. 問題定義與分析1.1 實習(xí)目的 熟悉和掌握文法的形式定義及各成分的含義，正確識別文法的類型。1.2 實習(xí)要求 （1） 主要功能：識別各類 Chomsky文法 （2） 系統(tǒng)輸入：任意的文法 G 的 VN，P和 S （3） 系統(tǒng)輸出： a) 文法的形式化表示 G=(VN，VT，P，S) b) 文法的 Chomsky類型（0型、1型、2型、3型） （4） 為簡單起見，文法符號都采用單字符符號。 （5） 有多個候選式的產(chǎn)生式允許采用縮寫形式（:

4、= 1|2|n）作為產(chǎn)生式的輸入形式 （6） 要求按照軟件工程的原則進行實習(xí)設(shè)計，提交實習(xí)報告，即必要的軟件工程文檔（可將主要內(nèi)容壓縮成一個文檔） ，內(nèi)容至少包括：問題定義和分析、設(shè)計（數(shù)據(jù)結(jié)構(gòu)、算法、界面等） 、主要測試用例（應(yīng)如實提供測試結(jié)果）等。最好提供某種詳細(xì)設(shè)計表示（如程序框圖、偽碼等），而不用提交源程序清單。 1.3 要求分析1.3.1 輸入部分對于文法G用字符串String s保存；非終結(jié)字符集合VN，用數(shù)組c保存，String s1=jTextField2.getText();/獲取VN,char c=s1.toCharArray()；產(chǎn)生式規(guī)則P的用二維數(shù)組P保存：char

5、P=new char1020; String s2=jTextArea1.getText();/獲取產(chǎn)生式規(guī)則 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();/將產(chǎn)生式轉(zhuǎn)換為數(shù)組保存 1.3.2 輸出部分非終結(jié)字符用一個數(shù)組N保存輸出： String s1=jTextFiel

6、d2.getText();/獲取VN char c=s1.toCharArray(); while(ic.length)if(ci!=,)Nm=ci;m+;i+;終結(jié)字符用一個數(shù)組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，在獲取的文法名的基礎(chǔ)上加上文法內(nèi)容，文法內(nèi)容為后面加上： String s=jTextField1.getText();/s用于輸出文法s=s+=(+s1+,; String s3=; i=0; wh

7、ile(im) if(i+1m) s3=s3+Ti+,;/將終結(jié)字符串中的字符加上，輸出 else s3=s3 +Ti;/終結(jié)字符串的最后一個字符不用加， i+; s=s+s3+,P,+c0+); jTextField3.setText(s);產(chǎn)生式規(guī)則的輸出用String s4表示： String s4=;for(j=0;jsum;j+) String s6=tokenizer.nextToken(); s4=s4+s6+n; jTextArea2.setText(s4);對于判定結(jié)果的輸出，用String s5表示： String s5=;/根據(jù)算法結(jié)果決定輸入的文法為哪種類型，則對應(yīng)給s

8、5賦不同字符串case 1:if(flag=1) s5=s5+該文法是Chomsky0 型文法（即短語結(jié)構(gòu)文法）!;else s5=s5+該文法是Chomsky1 型文法（即上下文有關(guān)文法）!;dase 2: if(flag=1) s5=s5+該文法是Chomsky2 型文法（即上下文無關(guān)文法）!;else s5=s5+該文法是Chomsky3 型文法（即正規(guī)文法）!;1.3.3 判定過程 具體的判定算法由各種方法的特點所決定： 首先，因為于2型方法與3型文法的產(chǎn)生式的左部都是單個非終結(jié)符，所以若待判定方法的左部是單個非終結(jié)符，則可確定其為2型或3型方法，此時已將4種方法分為兩組，即0型與1型

9、一組、2型與3型一組； 其次，對于2型與3型文法，因為3型文法是對2型文法的進一步限制。即2型文法產(chǎn)生式右部是由終結(jié)符和非終結(jié)符組成的符號串，有以下形式的產(chǎn)生式： A:= ，其中A屬于VN，屬于終結(jié)符和非終結(jié)符組成的符號串。 而3型文法限制產(chǎn)生式右部是單一終結(jié)符或單一終結(jié)符跟著單一非終結(jié)符，即： A:=a 或A:=aB所以，可通過對產(chǎn)生式的右部判斷來區(qū)分2型與3型文法。 最后，對于0型與1型文法，因為0型文法產(chǎn)生式的左部與右部都是符號串，沒任何限制，所以可以通過1型文法的限制來區(qū)分；1型文法的限制如下所示： := ，其中1| 且1型文法的左部必須有非終結(jié)字符。2. 設(shè)計2.1 數(shù)據(jù)結(jié)構(gòu) 定義了

10、以下字符串類型數(shù)據(jù)：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字符串轉(zhuǎn)換為數(shù)組char N=new char10 ：用于保存去除，的純非終結(jié)字符如：輸入 S，A，B，C 則 s1=S,A,B,C; c=S,A,B,C; N=S A B Cchar T=new char20 ：用于保存純終結(jié)字符如： 其中一個產(chǎn)生式規(guī)則P為N：=1|2|3|4 ， 則T=1 2 3 4String s

11、2： 用于獲取產(chǎn)生式規(guī)則StringTokenizer tokenizer ：用于按回車符區(qū)分不同產(chǎn)生式，以便按序分別獲取產(chǎn)生式char P=new char1020 ：用于將產(chǎn)生式規(guī)則用二維數(shù)組保存String s4 ：用于輸出產(chǎn)生式規(guī)則的字符串 String s5 ：用于輸出判定結(jié)果，即輸出為哪一類文法若為2型文法，則s5=“該文法是Chomsky2 型文法（即上下文無關(guān)文法）!”以下是各個控件的定義： private javax.swing.JButton jButton1; 確定按鈕 private javax.swing.JButton jButton2; 清空按鈕private j

12、avax.swing.JButton jButton3; 退出按鈕靜態(tài)文本的輸出，即在界面上顯示輸入、輸出、方法等提示文字： 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; 輸入產(chǎn)生式規(guī)則框 private javax.swing.JTextArea jTextArea2; 輸出產(chǎn)生式規(guī)則框 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算法描述如下： 對于輸入的產(chǎn)生式規(guī)則：1. 判斷是否為合法的文法：是轉(zhuǎn)4，否繼續(xù)；2. 提示有誤，是否重新輸入：是轉(zhuǎn)1，否繼續(xù)；3. 退出系統(tǒng)。4. 通過產(chǎn)生式規(guī)則的左部，確定文法類型是2、3型還是0、1型，定義變量fI作為區(qū)分此兩大類方法：fI=1（表示為0、1型），繼續(xù)；fI=2（表示為2、3型），轉(zhuǎn)9（fI用于控制switch語句執(zhí)行）；5. 判斷每個產(chǎn)生式左部是否都含有非終結(jié)字符：否，轉(zhuǎn)8；是，繼續(xù)；6. 判斷文

15、法每個產(chǎn)生式規(guī)則左部的字符串的數(shù)量是否小于等于右部的字符串的數(shù)量：是，繼續(xù)；否，轉(zhuǎn)8；7. 此文法為1型文法；8. 此文法為0型文法；9. 判斷每個產(chǎn)生式規(guī)則右部字符數(shù)是否小于等于2：是，繼續(xù)；否，轉(zhuǎn)13；10. 判斷每個產(chǎn)生式規(guī)則右部字符數(shù)為1的字符是否為終結(jié)字符：是，繼續(xù)；否，轉(zhuǎn)13；11. 判斷每個產(chǎn)生式規(guī)則右部字符數(shù)為2的字符串是否為一個終結(jié)符后面跟著一個非終結(jié)符：是，繼續(xù)；否，轉(zhuǎn)13；12. 此文法為3型文法；13. 此文法為2型文法；NNNNNYYYY此文法為1型文法每個產(chǎn)生式左部皆含VN？每個產(chǎn)生式左部字符數(shù)目小于等于右部字符的數(shù)目？Sum0=2時，為一終結(jié)符跟著一非終結(jié)字符？此

16、文法為3型文法N開始輸入文法、VN、P文法合法？重新輸入？Y結(jié)束N產(chǎn)生式左部皆為一個非終結(jié)字符？YfI=1fI=2NY每個產(chǎn)生式右部字符數(shù)sum0皆小于等于2？Sum0=1時，此字符為終結(jié)字符？此文法為2型文法此文法為0型文法Y2.2.1程序流程圖如下： 2.3. 界面3. 程序運行實例 3.1 3 型文法 3.2 2 型文法 3.3 1 型文法 3.4 0 型文法 3.5 非合法文法輸入選是，繼續(xù)輸入：選否，退出程序。對于清空按鈕，點擊則清空所有文本框；對于退出按鈕，點擊則退出程序。4. 程序核心源代碼 public int Is(char a,char c) /判斷字符c是否在數(shù)組a中in

17、t s=0,f=0;while(sa.length)if(as=c)f=1;s+;return f;public int Sum(char a) /計算數(shù)組a中字符|的數(shù)目int s=0,i=0;for(i=0;ia.length;i+) if(ai=|) s+;return s;/ 以下代碼為判定輸入的文法為哪類文法，參數(shù)R是存在二維數(shù)組中的產(chǎn)生式規(guī)則，參/ 數(shù)j是通過之前的代碼已確定該文法為0、1型（j=1）還是2、3型(j=2)，參數(shù)sum / 是產(chǎn)生式規(guī)則的數(shù)量，參數(shù)T是終結(jié)字符的數(shù)組，參數(shù)N是非終結(jié)字符的數(shù)組。public void Classify(char R,int j,int

18、 sum,char T,char N)int flag=0; String s5=;switch(j)case 1: /通過傳遞的參數(shù)知，為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;break;elsek2+;j2=k2; if(flag=1)break;i+; if(flag=1) s5=s5+該文法是Chomsky0 型文法（即短語結(jié)構(gòu)文法）!;else s5=s5+該文法是Chomsky1 型文法（即上下文有關(guān)文法）!;break;case 2: /通過傳遞的參數(shù)知，為2、3型，case 2中為判斷具體是2型還是3型文法for(int i=0;isum;i+)int i1=4,j1=4,l,sum0;sum0