編譯原理實(shí)驗(yàn)1Chomsky文法類型判斷

1、編譯原理實(shí)驗(yàn)Chomsky文法類型判斷編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱Chomsky文法類型判斷實(shí)驗(yàn)時(shí)間2014年4月2日院系計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院班級(jí)科技(2)班學(xué)號(hào)E01114174姓名徐帥1 .試驗(yàn)?zāi)康妮斎耄阂唤M任意的規(guī)則。輸出：相應(yīng)的Chomsky文法的類型。2 .實(shí)驗(yàn)原理1. 0型文法（短語文法）如果對(duì)于某文法G,P中的每個(gè)規(guī)則具有下列形式：U：=V其中u£V+,vGV,則稱該文法G為0型文法或短語文法，簡寫為PSG。0型文法或短語結(jié)構(gòu)文法的相應(yīng)語言稱為0型語言或短語結(jié)構(gòu)語言L。這種文法由于沒有其他任何限制，因此0型文法也稱為無限制文法，其相應(yīng)的語言稱為無限制性語言。任何0型語言都是

2、遞歸可枚舉的，故0型語言又稱遞歸可枚舉集。這種語言可由圖靈機(jī)（Turning）來識(shí)別。2. 1型文法（上下文有關(guān)文法）如果對(duì)于某文法G,P中的每個(gè)規(guī)則具有下列形式：xUy:=xuy其中U£V、；u£V+；x,y£V則稱該文法G為1型文法或上下文有關(guān)文法,也稱上下文敏感文法，簡寫為CSG。1型文法的規(guī)則左部的U和右部的u具有相同的上文x和下文y,利用該規(guī)則進(jìn)行推導(dǎo)時(shí)，要用u替換U,必須在前面有x和后面有y的情況下才能進(jìn)行，顯示了上下文有關(guān)的特性。1型文法所確定的語言為1型語言匕，1型語言可由線性有界自動(dòng)機(jī)來識(shí)別。3. 2型文法（上下文無關(guān)文法）如果對(duì)于某文法G,P中

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

4、左線性文法。如果對(duì)于某文法G,P中的每個(gè)規(guī)則具有下列形式：U二=T或U二=TW其中TCVT；U,WEVn,則稱Ig文法G為右線性文法。左線性文法和右線性文法通稱為3型文法或正則文法，有時(shí)又稱為有窮狀態(tài)文法，簡寫為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型文法所確定的語言為3型語言匕，3型語言可由確定的有限狀態(tài)自動(dòng)機(jī)來識(shí)別。在常見的程序設(shè)計(jì)語言中，多數(shù)與詞法有關(guān)的文法屬于3型文法?？梢钥闯?，上述4類文法，從0型到3型，產(chǎn)生式限制越來越強(qiáng)，其后一類都是前一類的子集，而描述語

5、言的功能越來越弱，四類文法及其表示的語言之間的關(guān)系可表示為：0型二1型二2型二3型；即LonLQL2nL33.1. 驗(yàn)內(nèi)容該實(shí)驗(yàn)用C+進(jìn)行編譯,利用函數(shù)功能，調(diào)用不同的函數(shù)來判定0型文法,1型文法,2型文法，3型文法的判斷。主要提高我們對(duì)文法類型的理解，也提高了我們編程的動(dòng)手能力.理論與實(shí)踐結(jié)合，加深對(duì)文法概念的理解.1 .實(shí)驗(yàn)心得1 .明確四種文法的定義，根據(jù)文法定義的不同，利用程序?qū)⑵鋮^(qū)分開2 .事先畫好實(shí)驗(yàn)的流程圖，可以幫助解決問題5 .實(shí)驗(yàn)代碼與結(jié)果#include<iostream>#include<string>usingnamespacestd;intm;

6、文法產(chǎn)生式的個(gè)數(shù)charVn100;/記錄非終結(jié)字符charVt100;/記錄終結(jié)字符typedefstructGZ定義一個(gè)產(chǎn)生式結(jié)構(gòu)體stringleft;定義產(chǎn)生式的左部stringright;/定義產(chǎn)生式的右部stringwhole;定義整個(gè)產(chǎn)生式GZ;boolwenfa0(GZ*p)判斷0型文法inti,j;for(i=0;i<m;i+)/遍歷所有的產(chǎn)生式for(j=0;j<pi.left.length();j+)/遍歷整個(gè)產(chǎn)生式左式每一個(gè)字符if(pi.leftU>='A')&&(pi.leftj<=Z)判斷產(chǎn)生式左邊是否含有非

7、終結(jié)符break;if(j=pi.left.length()break;elsecontinue;if(i=m)return1;/說明該文法是0型elsecout<<“該文法不是0型文法！"<<endl;return0;boolwenfa1(GZ*p)判斷1型文法inti;if(wenfa0(p)for(i=0;i<m;i+)遍歷所有的產(chǎn)生式if(pi.rightlength()>=pi.leftlength()判斷產(chǎn)生式右邊是否大于左邊continue;elsebreak;if(i=m)return1;/說明該文法是1型elsecout<&

8、lt;“該文法是0型文法！"<<endl;return0;elsereturn0;boolwenfa2(GZ*p)判斷2型文法inti;if(wenfa1(p)for(i=0;i<m;i+)遍歷所有的產(chǎn)生式if(pi.leftlength()=1&&(pi.left0>'A'&&pi.left0<'Z')continue;elsebreak;if(i=m)return1;/說明該文法是2型elsecout<<“該文法是1型文法！"<<endl;return0

9、;elsereturn0;boolwenfa3(GZ*p)判斷3型文法inti;if(wenfa2(p)for(i=0;i<m;i+)遍歷所有的產(chǎn)生式if(pi.rightO>='a'&&Pi.right0<='z')&&Pi.right.length()>=1&&pi.right.length()<=2)判斷產(chǎn)生式右邊第一個(gè)字符是否是終結(jié)符以及規(guī)定左邊的字符個(gè)數(shù)為1或2if(pi.right.length()=2)&&(pi.right1>='a'

10、;&&pi.right1<='z')break;elsecontinue;elsebreak;if(i=m)cout<<“該文法是3型文法！"<<endl;return1;elsecout<<“該文法是2型文法！"<<endl;return0;elsereturn0;voidoutput(GZ*p)輸由終結(jié)符和非終結(jié)符inti,j,k;intvn=0;/記錄非終結(jié)字符個(gè)數(shù)intvt=0;記錄終結(jié)字符個(gè)數(shù)for(i=0;i<m;i+)/遍歷整個(gè)產(chǎn)生式for(j=0;j<pi.wh

11、ole.length();j+)遍歷產(chǎn)生式的整個(gè)字符if(pi.wholej>='A'&&pi.wholej<='Z')/判斷字符是否為非終結(jié)字符for(k=0;k<=vn;k+)/遍歷整個(gè)非終結(jié)符集合,判斷是否有重復(fù)if(Vnk=pi.wholej)break;elsecontinue;if(k>vn)說明沒有重復(fù)Vnvn=pi.wholej;vn+;if(pi.wholej>='a'&&pi.wholej<='z')/判斷字符是否為非終結(jié)字符for(k=0;k

12、<=vt;k+)/遍歷整個(gè)非終結(jié)符集合，判斷是否有重復(fù)if(Vtk=pi.wholej)break;elsecontinue;if(k>vt)/說明沒有重復(fù)Vtvt=pi.wholej;vt+;cout<<"n"cout<<“非終結(jié)符為:n"for(i=0;i<vn;i+)/輸由非終結(jié)字符cout<<Vni<<""cout<<"n"cout«,nM;coutw”終結(jié)符為:nM;for(i=0;i<vt;i+)/輸出非終結(jié)字符cout«Vti«MM;cout«,nM;voidmain()(intij;stringin;記錄輸入的產(chǎn)生式cout«M請輸入文法產(chǎn)生式的個(gè)數(shù)!n"cin»m;GZ*p=newGZm;cout«"請?jiān)佥斎胛姆ㄒ?guī)則An”；for(i=0;i<m;i+)/輸入產(chǎn)生式數(shù)組(cin»in;for(j