實驗一：Chomsky文法類型判斷

1、精選優(yōu)質(zhì)文檔-傾情為你奉上編譯原理實驗報告實驗名稱 Chomsky文法類型判斷 實驗時間 2014.04.02 院系 計算機科學(xué)與技術(shù)學(xué)院 班級 XXXXXXXXX 學(xué)號 XXXXXXX 姓名 XXXX 1.試驗?zāi)康模荷蠙C實驗有助于我們發(fā)現(xiàn)理論課學(xué)習(xí)中無法發(fā)現(xiàn)的問題，通過上機實驗操作，進一步加深對理論課所學(xué)的“Chomsky文法類型判斷”的理解，同時提升自己的編程能力，為以后的學(xué)習(xí)打下良好的基礎(chǔ)。2.實驗原理 0型文法（短語文法）如果對于某文法G，P中的每個規(guī)則具有下列形式：u - v其中uV，vV*，則稱該文法G為0型文法或短語文法，簡寫為PSG。0型文法或短語結(jié)構(gòu)文法的相應(yīng)語言稱為0型語言

2、或短語結(jié)構(gòu)語言L0。這種文法由于沒有其他任何限制，因此0型文法也稱為無限制文法，其相應(yīng)的語言稱為無限制性語言。任何0型語言都是遞歸可枚舉的，故0型語言又稱遞歸可枚舉集。這種語言可由圖靈機（Turning）來識別。 1型文法（上下文有關(guān)文法）如果對于某文法G，P中的每個規(guī)則具有下列形式：xUy - xuy其中UVN；uV；x，yV*，則稱該文法G為1型文法或上下文有關(guān)文法，也稱上下文敏感文法，簡寫為CSG。1型文法的規(guī)則左部的U和右部的u具有相同的上文x和下文y，利用該規(guī)則進行推導(dǎo)時，要用u替換U，必須在前面有x和后面有y的情況下才能進行，顯示了上下文有關(guān)的特性。1型文法所確定的語言為1型語言L

3、1，1型語言可由線性有界自動機來識別。 2型文法（上下文無關(guān)文法）如果對于某文法G，P中的每個規(guī)則具有下列形式：U - u其中UVN；uV，則稱該文法G為2型文法或上下文無關(guān)文法，簡寫為CFG。按照這條規(guī)則，對于上下文無關(guān)文法，利用該規(guī)則進行推導(dǎo)時，無需考慮非終結(jié)符U所在的上下文，總能用u替換U，或者將u歸約為U，顯示了上下文無關(guān)的特點。2型文法所確定的語言為2型語言L2，2型語言可由非確定的下推自動機來識別。一般定義程序設(shè)計語言的文法是上下文無關(guān)的。如C語言便是如此。因此，上下文無關(guān)文法及相應(yīng)語言引起了人們較大的興趣與重視。 3型文法（正則文法，線性文法）如果對于某文法G，P中的每個規(guī)則具有

4、下列形式：U - T 或 U - WT其中TVT；U,WVN，則稱該文法G為左線性文法。如果對于某文法G，P中的每個規(guī)則具有下列形式：U -= T 或 U - TW其中TVT；U, WVN，則稱該文法G為右線性文法。左線性文法和右線性文法通稱為3型文法或正則文法，有時又稱為有窮狀態(tài)文法，簡寫為RG。按照定義，對于正則文法應(yīng)用規(guī)則時，單個非終結(jié)符號只能被替換為單個終結(jié)符號，或被替換為單個非終結(jié)符號加上單個終結(jié)符號，或者被替換為單個終結(jié)符號加上單個非終結(jié)符號。3型文法所確定的語言為3型語言L3，3型語言可由確定的有限狀態(tài)自動機來識別。在常見的程序設(shè)計語言中，多數(shù)與詞法有關(guān)的文法屬于3型文法?？梢钥?/p>

5、出，上述4類文法，從0型到3型，產(chǎn)生式限制越來越強，其后一類都是前一類的子集，而描述語言的功能越來越弱，四類文法及其表示的語言之間的關(guān)系可表示為：0型1型2型3型；即L0 L1 L2 L33.實驗內(nèi)容輸入：一組任意的規(guī)則。輸出：相應(yīng)的Chomsky 文法的類型。注意事項：文法的輸入應(yīng)簡便。指明是哪一類Chomsky文法，并給出相應(yīng)的四元組形式：G=（VN，VT，P，S）。說明：簡單起見，可以不考慮0型文法類。4.實驗心得本次實驗，我最大的體會就是我們不僅要熟練地掌握書本上的知識，更重要的是能夠把學(xué)到的知識應(yīng)用到上機編程中，這樣才能算是真正學(xué)會了書本上所講的知識。在編寫代碼的過程中，我發(fā)現(xiàn)自己對

6、3型文法的概念沒有理解清楚，認為在對某個3型文法進行判斷時，可以同時使用左線性文法和右線性文法，結(jié)果實際測試的過程中發(fā)現(xiàn)了錯誤，后來向別的同學(xué)請教及時發(fā)現(xiàn)并改正了錯誤；在對文法的各個要素進行輸入的過程中，我也遇到了問題，主要是各種輸入非法的情況考慮不周全，后來經(jīng)過改正，修改了自己發(fā)現(xiàn)的所有錯誤，并及時改正了在測試中發(fā)現(xiàn)的問題，但仍無法保證所有的邊界情況都考慮周全，這也是本實驗所欠缺的地方，以后我會繼續(xù)努力。我想，學(xué)習(xí)是個持之以恒的過程，如果真正想學(xué)好編譯原理的話，光靠實驗課的時間是遠遠不夠的，所以以后我一定要加強學(xué)習(xí)，堅持不懈，一切努力都是值得的。5.實驗代碼與結(jié)果本實驗使用java語言編寫，

7、編程工具是eclipse，實驗運行結(jié)果如下：幾種非法輸入測試產(chǎn)生式左部不含有非終結(jié)符： 產(chǎn)生式的左部含有非法字符。還有一些其他的非法輸入，在此就不一一舉例。正確的輸入：數(shù)據(jù)一：(3型文法)G=(S, A, B, 1, 2, P, S) ,P=S-1A, S-1, A-2B, B-1B, B-2S ;首先是數(shù)據(jù)的輸入：輸入包括：非終結(jié)符集和終結(jié)符集的輸入、產(chǎn)生式的個數(shù)、依次輸入產(chǎn)生式的左部和右部以及開始符。實驗結(jié)果：數(shù)據(jù)二：(2型文法)G=(S, 0, 1, P , S) ,P= S-0S1, S-01 ;數(shù)據(jù)的輸入：實驗結(jié)果：實驗源代碼如下：import java.io.BufferedRea

8、der;import java.io.IOException;import java.io.InputStreamReader;public class Chomsky String left=new String10; /產(chǎn)生式左部String right=new String10; /產(chǎn)生式右部String Vn=new String(); /非終結(jié)符集合String Vt=new String(); /終結(jié)符集合int type=new int20; /標(biāo)記文法的類型char start; /開始符int count; /產(chǎn)生式的個數(shù)boolean mark1=true,mark2=tr

9、ue; public void GetIn(BufferedReader f) /輸入方法tryboolean mark=true;System.out.println(|實驗一：Chomsky文法類型判斷|n);System.out.println(請輸入非終結(jié)符集Vn：);Vn=f.readLine();System.out.println(請輸入終結(jié)符集Vt：);Vt=f.readLine();String V=Vn+Vt;System.out.println(請輸入產(chǎn)生式的個數(shù)：);String s=f.readLine();count=Integer.parseInt(s);for(

10、int i=0;icount;i+) /輸入產(chǎn)生式左部System.out.println(請輸入第+(i+1)+個產(chǎn)生式的左部：);lefti=f.readLine();if(IsVh(lefti,V)=true)for(int j=0;jlefti.length();j+)if(IsChar(lefti.charAt(j),Vn)=true)mark=true;break;if(j+1)=lefti.length()mark=false;elseSystem.out.println(輸入非法！); System.exit(0);if(mark=false)System.out.printl

11、n(產(chǎn)生式左部皆為終結(jié)符號,輸入非法！); System.exit(0);for(int i=0;icount;i+) /輸入產(chǎn)生式右部System.out.println(請輸入第+(i+1)+個產(chǎn)生式的右部：);righti=f.readLine();if(righti!=null)if(IsVh(righti,V)=false)System.out.println(輸入非法！); System.exit(0);System.out.println(請輸入開始符：);start=(char)f.read();for(int i=0;icount;i+)if(IsChar(start,lef

12、ti)=true)if(IsChar(start,Vn)=true)break;elseSystem.out.println(開始符為終結(jié)符,輸入非法！);System.exit(0);elseif(i+1)=count)System.out.println(產(chǎn)生式左部不含有開始符，輸入非法！);System.exit(0);System.out.println(輸入成功！n);OutPut();catch(IOException e)System.err.println(發(fā)生異常：+e);e.printStackTrace();public void OutPut() /輸出方法System

13、.out.println(生成的文法G為：);System.out.print(G=();for(int i=0;iVn.length();i+)System.out.print(Vn.charAt(i);if(i+1)!=Vn.length()System.out.print(,);System.out.print(,);for(int i=0;iVt.length();i+)System.out.print(Vt.charAt(i);if(i+1)!=Vt.length()System.out.print(,);System.out.println(,P,+start+);System.o

14、ut.print(P=);for(int i=0;i+righti);if(i+1)!=count)System.out.print(, );System.out.println(;);Recognize();public void Recognize() /判別方法for(int i=0;i=lefti.length() /1型文法判別條件typei=1;if(IsVh(lefti,Vn)=true&(lefti.length()=1) /2型文法判別條件typei=2;if(righti.length()=1&IsChar(righti.charAt(0),Vt)typei=3;if(ri

15、ghti.length()=2&mark1=true)if(IsChar(righti.charAt(0),Vt)&IsChar(righti.charAt(1),Vn)typei=3;elsetypei=2;mark2=false;if(righti.length()=2&mark2=true)if(IsChar(righti.charAt(0),Vn)&IsChar(righti.charAt(1),Vt)typei=3;elsetypei=2;mark1=false;elsetypei=1;elsetypei=0;int min=type0;for(int i=1;icount;i+)if(typei=min)min=typei;System.out.println(G是+min+型文法.);public boolean IsVh(String str,String Vh) /判斷字符串是否在某個集合中for(int j=0;jstr.length();j+) for(int k=0;kVh.length();k+)if(str.charAt(j)=Vh.charAt(k)break;if(k+1)=Vh.length()return false; return true;public boolean IsChar(char c,String Vh) /判斷字符是否在某