編譯原理方法分類

1、編號： 實習(xí)一二三四五六七八九十總評教師簽名成績實習(xí)題目： 文法分類 專業(yè)（班）： 13級計科六班 學(xué)生學(xué)號： 2013311500123 學(xué)生姓名： 劉 冠 佐 任課教師： 杜卓敏 評語及建議：年 10 月 13 日編號： 實習(xí)一二三四五六七八九十總評教師簽名成績武漢大學(xué)計算機(jī)學(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） 要求按照軟件工程的原則進(jìn)行實習(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型文法的進(jìn)一步限制。即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