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;j<sum;j+) String s6=tokenizer.nextToken(); s4=s4+s6+'n' Pj=s6.toCharArray();/將產生式轉換為數組保存 1.3.2 輸出部分非終結字符用一個數組N保

6、存輸出： String s1=jTextField2.getText();/獲取VN char c=s1.toCharArray(); while(i<c.length)if(ci!=',')Nm=ci;m+;i+;終結字符用一個數組T保存： for(j=0;j<Pi.length;j+) if(Pij!=':'&&Pij!='='&&Pij!='|'&&Is(N, Pij)=0&&Is(T, Pij)=0) Tm=Pij; m+; 對于文法G的輸出還是用

7、String s，在獲取的文法名的基礎上加上文法內容，文法內容為后面加上： String s=jTextField1.getText();/s用于輸出文法s=s+"=("+s1+"," String s3="" i=0; while(i<m) if(i+1<m) s3=s3+Ti+','/將終結字符串中的字符加上，輸出 else s3=s3 +Ti;/終結字符串的最后一個字符不用加， i+; s=s+s3+",P,"+c0+')' jTextField3.setText(

8、s);產生式規則的輸出用String s4表示： String s4=""for(j=0;j<sum;j+) String s6=tokenizer.nextToken(); s4=s4+s6+'n' jTextArea2.setText(s4);對于判定結果的輸出，用String s5表示： String s5=""/根據算法結果決定輸入的文法為哪種類型，則對應給s5賦不同字符串case 1:if(flag=1) s5=s5+"該文法是Chomsky0 型文法（即短語結構文法）!"else s5=s5+&quo

9、t;該文法是Chomsky1 型文法（即上下文有關文法）!"dase 2: if(flag=1) s5=s5+"該文法是Chomsky2 型文法（即上下文無關文法）!"else s5=s5+"該文法是Chomsky3 型文法（即正規文法）!"1.3.3 判定過程 具體的判定算法由各種方法的特點所決定： 首先，因為于2型方法與3型文法的產生式的左部都是單個非終結符，所以若待判定方法的左部是單個非終結符，則可確定其為2型或3型方法，此時已將4種方法分為兩組，即0型與1型一組、2型與3型一組； 其次，對于2型與3型文法，因為3型文法是對2型文法的進一

10、步限制。即2型文法產生式右部是由終結符和非終結符組成的符號串，有以下形式的產生式： A:=ð ，其中A屬于VN，ð屬于終結符和非終結符組成的符號串。 而3型文法限制產生式右部是單一終結符或單一終結符跟著單一非終結符，即： A:=a 或A:=aB所以，可通過對產生式的右部判斷來區分2型與3型文法。 最后，對于0型與1型文法，因為0型文法產生式的左部與右部都是符號串，沒任何限制，所以可以通過1型文法的限制來區分；1型文法的限制如下所示： := ，其中1| 且1型文法的左部必須有非終結字符。2. 設計2.1 數據結構 定義了以下字符串類型數據：String s ：用于接受用戶輸入

11、的文法名與輸出最終的完整文法，如：接受輸入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 s2： 用

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

13、.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.JLabel

14、 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; 輸出完

15、整文法定義的框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. 判斷文法每個產

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

17、型文法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中int s=

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

19、ar R,int j,int sum,char T,char N)int flag=0; String s5=""switch(j)case 1: /通過傳遞的參數知，為0、1型，case 1中為判斷具體是0型還是1型文法for(int i=0;i<sum;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;k<sum1+1;k+)while(k2<Ri.length&&Rik2!='|')k2+;if(i2>k2-j2)flag=1;br