編譯原理實(shí)驗(yàn)文法的判斷

1、文法類型的判斷和推導(dǎo)序列的生成 目錄一、實(shí)驗(yàn)名稱2二、實(shí)驗(yàn)?zāi)康?三、實(shí)驗(yàn)原理21、文法G定義為四元組(Vn,Vt,P,S)22、文法類型的判斷2四、實(shí)驗(yàn)思路21、接受產(chǎn)生式32、文法類型的判斷33、將文法以四元組形式輸出4五、實(shí)驗(yàn)小結(jié)41、文法類型的判斷條件42、產(chǎn)生式的存儲問題53、文法以四元組形式輸出問題5六、附件51、源代碼52、運(yùn)行結(jié)果截圖10一、實(shí)驗(yàn)名稱文法類型的判斷和推導(dǎo)序列的生成二、實(shí)驗(yàn)?zāi)康妮斎耄阂唤M任意的文法規(guī)則和任意符號串。輸出：相應(yīng)的Chomsky文法類型和推導(dǎo)。三、實(shí)驗(yàn)原理1、文法G定義為四元組(Vn,Vt,P,S)其中Vn為非終結(jié)符（或語法實(shí)體，或變量）集：Vt為終結(jié)符

2、集；P為規(guī)則（-）的集合，(VnVt)*且至少包含一個(gè)非終結(jié)符，(VnVt)*；Vn，Vt和P是非空有窮集。S稱作識別符或開始符，它是一個(gè)非終結(jié)符，至少要在一條規(guī)則中作為左部出現(xiàn)。2、文法類型的判斷a.設(shè)G=(Vn,Vt,P,S)為一文法，若P中的每一個(gè)產(chǎn)生式-均滿足|=|，僅僅S-除外，則文法G是1型或上下文有關(guān)的。b.設(shè)G=(Vn,Vt,P,S)，若P中的每一個(gè)產(chǎn)生式-滿足: 是一個(gè)非終結(jié)符，(VnVt)*，則此文法稱為2型的或上下文無關(guān)的。c. 設(shè)G=(Vn,Vt,P,S)，若P中的每一個(gè)產(chǎn)生式的形式都是A-B或A-，其中A和B都是終結(jié)符，Vt*，則G是3型文法或正規(guī)文法。四、實(shí)驗(yàn)思路本

3、實(shí)驗(yàn)采取C+來完成，用大寫字母A到Z表示非終結(jié)符，小寫字符a到z表示終結(jié)符。實(shí)驗(yàn)流程圖1、接受產(chǎn)生式首先建立一個(gè)結(jié)構(gòu)體siyuanzu，其成員有非終結(jié)符集合數(shù)組Vn，終結(jié)符集合數(shù)組Vt以及產(chǎn)生式集合數(shù)組rule，通過函數(shù)input來接受從鍵盤輸入的產(chǎn)生式，并且存儲于string類字符串?dāng)?shù)組rule中。函數(shù)input實(shí)現(xiàn)接受產(chǎn)生式功能的思路為：先確定要輸入的產(chǎn)生式數(shù)目n，用for循環(huán)實(shí)現(xiàn)產(chǎn)生式的存儲。2、文法類型的判斷函數(shù)Grammer實(shí)現(xiàn)判斷文法類型的功能并且輸出文法的類型。其實(shí)現(xiàn)功能的思路為：a.對rule數(shù)組中每一個(gè)產(chǎn)生式進(jìn)行判斷，以“-”中的“-”作為判斷條件，將產(chǎn)生式分為左部和右部分別

4、計(jì)算左部和右部的長度。若youb小于左部則不是1型文法。輸出0型文法；若右部大于或等于左部，則繼續(xù)判斷。b.判斷文法是否為2型文法，經(jīng)過a步驟的執(zhí)行，若文法為1型文法，只需在此基礎(chǔ)上判斷文法的左部是否只有一個(gè)非終結(jié)符。通過判斷條件zuo=1&A=a.ruleizuo-1&a.ruleizuo-1=a)&(a.ruleinum+1=A)&(a.ruleinum+2=a)&(a.ruleinum+1=A)&(a.ruleinum+1=a)&(a.ruleinum+2=a)&(a.ruleinum+1=z)判斷是否滿足B或形式。若所有產(chǎn)生式同時(shí)滿足判斷條件一或者同時(shí)滿足判斷條件二，則為3型文法進(jìn)行輸

5、出。否則為2型文法進(jìn)行輸出。3、將文法以四元組形式輸出函數(shù)output實(shí)現(xiàn)輸出文法四元組形式的功能。具體思路為：a.將存放產(chǎn)生式的string類數(shù)組rule一分為二，用x數(shù)組存放rule中所有的大寫字母即非終結(jié)符，用y數(shù)組存放rule中所有的小寫字母即終結(jié)符。b.用雙重for循環(huán)給x和y數(shù)組中重復(fù)的字符標(biāo)記，重復(fù)的字符全部賦值為“！”c.將x數(shù)組中非“！”元素賦值給非終結(jié)符集Vn，將y數(shù)組中非“！”元素賦值給終結(jié)符集Vt。d.按照格式分別輸出非終結(jié)符集Vn，終結(jié)符集Vt，產(chǎn)生式P以及開始符S。五、實(shí)驗(yàn)小結(jié)我運(yùn)用C+解決了此次實(shí)驗(yàn)的文法類型判斷的問題，在實(shí)際解決問題的過程中，主要遇到了以下幾個(gè)問

6、題：1、文法類型的判斷條件編譯原理書本上給出了幾類文法類型的定義，但是在實(shí)際的解決問題過程中，需要將書本上給的判斷條件轉(zhuǎn)換為C+語言中的判斷條件，這需要對文法類型的定義有很好的理解。我通過判斷產(chǎn)生式右部是否大于等于左部確定1型文法，在此基礎(chǔ)上判斷產(chǎn)生式左部是否為一個(gè)非終結(jié)符確定2型文法，最后在2型文法的基礎(chǔ)上判斷產(chǎn)生式是否全部滿足B或形式或者是B或形式確定3型文法。最終解決了文法類型判斷條件的問題。2、產(chǎn)生式的存儲問題實(shí)驗(yàn)要求最少輸入五條產(chǎn)生式，我最初是選擇用C語言解決存儲問題，但是發(fā)現(xiàn)C語言中對于字符串的處理不夠靈活，于是選擇了C+來解決。C+中可以用string類型來定義字符串?dāng)?shù)組，并且可

7、以通過length函數(shù)求每個(gè)字符串的長度，這樣給每條產(chǎn)生式的判斷都帶來了極大的便捷。3、文法以四元組形式輸出問題實(shí)驗(yàn)需要輸出文法的四元組，即需要輸出非終結(jié)符集Vn，終結(jié)符集Vt，產(chǎn)生式P以及開始符S，由于我將產(chǎn)生式存儲在string類數(shù)組rule中，因此，需要將rule中的元素分為兩類，大寫字母為非終結(jié)符，小寫字母為終結(jié)符。但是分好類的數(shù)組存在元素重復(fù)的問題，我通過一個(gè)雙重for循環(huán)給重復(fù)元素標(biāo)記為“！”，再將非“！”元素賦值給字符數(shù)組Vn和Vt，解決了元素重復(fù)問題。最后需要安排一下輸出的格式即解決了這個(gè)問題。通過本次實(shí)驗(yàn)，我深入的了解了文法類型的判斷，對于文法類型的判斷也更加的熟練。同時(shí)，對

8、于文法的四元組的定義更加的熟悉，并且對于運(yùn)用C+解決編譯原理的問題有了一定的基礎(chǔ)。六、附件1、源代碼#include#includeusing namespace std;struct siyuanzuchar Vn50;char Vt50;string rule20;int input(siyuanzu *a)int n,i;coutn;cout請輸入產(chǎn)生式:n;for(i=0;i(*a).rulei;return n;void output(siyuanzu a,int n)int i,j,length,k1=0,k2=0,m1=0,m2=0;char x50,y50;for(i=0;in

9、;i+)length=a.rulei.length();for(j=0;j)if(a.ruleij=A&a.ruleij=Z)xk1=a.ruleij;k1+;elseyk2=a.ruleij;k2+;for(i=0;ik1-1;i+)for(j=i+1;jk1;j+)if(xi=xj)xj=!;for(i=0;ik1;i+)if(xi!=!)a.Vnm1=xi;m1+;for(i=0;ik2-1;i+)for(j=i+1;jk2;j+)if(yi=yj)yj=!;for(i=0;ik2;i+)if(yi!=!)a.Vtm2=yi;m2+;cout四元組G=(Vn,Vt,P,S)endl;co

10、ut其中非終結(jié)符Vn=;for(i=0;im1-1;i+)couta.Vni,;couta.Vnm1-1;cout;coutendl;cout終結(jié)符Vt=;for(i=0;im2-1;i+)couta.Vti,;couta.Vtm2-1;cout;coutendl;coutP由下列產(chǎn)生式組成:endl;for(i=0;in;i+)couta.ruleiendl;cout開始符為:Sendl;void Grammer(siyuanzu a,int n)int i,j,length,num,zuo,you;char c;for(i=0;in;i+)num=0;length=a.rulei.leng

11、th();for(j=0;j=zuo)continue;elsebreak;if(i=n)for(i=0;in;i+)num=0;length=a.rulei.length();for(j=0;jlength;j+)c=a.ruleij;num+;if(c=-)break;zuo=num-1;if(zuo=1&A=a.ruleizuo-1&a.ruleizuo-1=Z)continue;elsebreak;if(i=n)for(i=0;in;i+)num=0;length=a.rulei.length();for(j=0;j=a)&(a.ruleinum+1=A)&(a.ruleinum+2=

12、a)&(a.ruleinum+1=z)continue;else break;if(i=n)cout文法類型:3型文法endl;elsefor(i=0;in;i+)num=0;length=a.rulei.length();for(j=0;j=A)&(a.ruleinum+1=a)&(a.ruleinum+2=a)&(a.ruleinum+1=z)continue;else break;if(i=n)cout文法類型:3型文法endl;elsecout文法類型:2型文法endl;elsecout文法類型:1型文法endl;elsecout文法類型:0型文法endl;int main()int n,r;siyuanzu a;while(1)cout-文法類型判斷（E21414020 陳國柱）-endl;cout 1.輸入產(chǎn)生式endl;cout 2.輸出文法類型及四元組endl;cout 3.結(jié)束endl;cout輸入功能號:r;if(r3|