實(shí)驗(yàn)一：Chomsky文法類型判斷

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

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

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

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

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

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

7、編程工具是eclipse，實(shí)驗(yàn)運(yùn)行結(jié)果如下：幾種非法輸入測(cè)試產(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)生式的個(gè)數(shù)、依次輸入產(chǎn)生式的左部和右部以及開(kāi)始符。實(shí)驗(yàn)結(jié)果：數(shù)據(jù)二：(2型文法)G=(S, 0, 1, P , S) ,P= S-0S1, S-01 ;數(shù)據(jù)的輸入：實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)源代碼如下：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; /開(kāi)始符int count; /產(chǎn)生式的個(gè)數(shù)boolean mark1=true,mark2=tr

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

10、int i=0;icount;i+) /輸入產(chǎn)生式左部System.out.println(請(qǐng)輸入第+(i+1)+個(gè)產(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é)符號(hào),輸入非法！); System.exit(0);for(int i=0;icount;i+) /輸入產(chǎn)生式右部System.out.println(請(qǐng)輸入第+(i+1)+個(gè)產(chǎn)生式的右部：);righti=f.readLine();if(righti!=null)if(IsVh(righti,V)=false)System.out.println(輸入非法！); System.exit(0);System.out.println(請(qǐng)輸入開(kāi)始符：);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(開(kāi)始符為終結(jié)符,輸入非法！);System.exit(0);elseif(i+1)=count)System.out.println(產(chǎn)生式左部不含有開(kāi)始符，輸入非法！);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) /判斷字符串是否在某個(gè)集合中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) /判斷字符是否在某