編譯原理實驗文法的判斷

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

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

3、終結(jié)符，Vt*，則G是3型文法或正規(guī)文法。四、實驗思路本實驗采取C+來完成，用大寫字母A到Z表示非終結(jié)符，小寫字符a到z表示終結(jié)符。實驗流程圖1、接受產(chǎn)生式首先建立一個結(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實現(xiàn)接受產(chǎn)生式功能的思路為：先確定要輸入的產(chǎn)生式數(shù)目n，用for循環(huán)實現(xiàn)產(chǎn)生式的存儲。2、文法類型的判斷函數(shù)Grammer實現(xiàn)判斷文法類型的功能并且輸出文法的類型。其實現(xiàn)功能的思路為：a.對rule數(shù)組中每一個產(chǎn)生式進(jìn)行判斷，以

4、“->”中的“-”作為判斷條件，將產(chǎn)生式分為左部和右部分別計算左部和右部的長度。若youb小于左部則不是1型文法。輸出0型文法；若右部大于或等于左部，則繼續(xù)判斷。b.判斷文法是否為2型文法，經(jīng)過a步驟的執(zhí)行，若文法為1型文法，只需在此基礎(chǔ)上判斷文法的左部是否只有一個非終結(jié)符。通過判斷條件zuo=1&&'A'<=a.ruleizuo-1&&a.ruleizuo-1<='Z'確定是否為2型文法，若不滿足判斷條件則為1型文法，進(jìn)行輸出，若滿足則繼續(xù)判斷。c.判斷文法是否為3型文法，經(jīng)過b步驟的執(zhí)行，若文法為2型文法，只

5、需在此基礎(chǔ)上判斷文法的右部是否為B或形式或者是B或形式。通過判斷條件一(you=2)&&(a.ruleinum+1>='a')&&(a.ruleinum+1<='z')&&(a.ruleinum+2>='A')&&(a.ruleinum+2<='Z')|(you=1)&&(a.ruleinum+1>='a')&&(a.ruleinum+1<='z')判斷是否滿足B或形式

6、，通過判斷條件二(you=2)&&(a.ruleinum+1>='A')&&(a.ruleinum+1<='Z')&&(a.ruleinum+2>='a')&&(a.ruleinum+2<='z')|(you=1)&&(a.ruleinum+1>='a')&&(a.ruleinum+1<='z')判斷是否滿足B或形式。若所有產(chǎn)生式同時滿足判斷條件一或者同時滿足判斷條件二

7、，則為3型文法進(jìn)行輸出。否則為2型文法進(jìn)行輸出。3、將文法以四元組形式輸出函數(shù)output實現(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。五、實驗小結(jié)我運用C+解決了此次實驗的文法類型判斷的問題，在實際解決問題的過程中，

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

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

10、更加的熟練。同時，對于文法的四元組的定義更加的熟悉，并且對于運用C+解決編譯原理的問題有了一定的基礎(chǔ)。六、附件1、源代碼#include<iostream>#include<string>using namespace std;struct siyuanzuchar Vn50;char Vt50;string rule20;int input(siyuanzu *a)int n,i;cout<<"請輸入產(chǎn)生式數(shù)目:"cin>>n;cout<<"請輸入產(chǎn)生式:n"for(i=0;i<n;i+

11、)cin>>(*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;i<n;i+)length=a.rulei.length();for(j=0;j<length;j+)if(a.ruleij!='-'&&a.ruleij!='>')if(a.ruleij>='A'&&a.ruleij<='Z')xk1=a

12、.ruleij;k1+;elseyk2=a.ruleij;k2+;for(i=0;i<k1-1;i+)for(j=i+1;j<k1;j+)if(xi=xj)xj='!'for(i=0;i<k1;i+)if(xi!='!')a.Vnm1=xi;m1+;for(i=0;i<k2-1;i+)for(j=i+1;j<k2;j+)if(yi=yj)yj='!'for(i=0;i<k2;i+)if(yi!='!')a.Vtm2=yi;m2+;cout<<"四元組G=(Vn,Vt,P,S

13、)"<<endl;cout<<"其中非終結(jié)符Vn="for(i=0;i<m1-1;i+)cout<<a.Vni<<","cout<<a.Vnm1-1;cout<<""cout<<endl;cout<<"終結(jié)符Vt="for(i=0;i<m2-1;i+)cout<<a.Vti<<","cout<<a.Vtm2-1;cout<<&quo

14、t;"cout<<endl;cout<<"P由下列產(chǎn)生式組成:"<<endl;for(i=0;i<n;i+)cout<<a.rulei<<endl;cout<<"開始符為:S"<<endl;void Grammer(siyuanzu a,int n)int i,j,length,num,zuo,you;char c;for(i=0;i<n;i+)num=0;length=a.rulei.length();for(j=0;j<length;j+)

15、c=a.ruleij;num+;if(c='-')break;zuo=num-1;you=length-(num+1);if(you>=zuo)continue;elsebreak;if(i=n)for(i=0;i<n;i+)num=0;length=a.rulei.length();for(j=0;j<length;j+)c=a.ruleij;num+;if(c='-')break;zuo=num-1;if(zuo=1&&'A'<=a.ruleizuo-1&&a.ruleizuo-1<

16、;='Z')continue;elsebreak;if(i=n)for(i=0;i<n;i+)num=0;length=a.rulei.length();for(j=0;j<length;j+)c=a.ruleij;num+;if(c='-')break;you=length-(num+1);if(you=2)&&(a.ruleinum+1>='a')&&(a.ruleinum+1<='z')&&(a.ruleinum+2>='A')&a

17、mp;&(a.ruleinum+2<='Z')|(you=1)&&(a.ruleinum+1>='a')&&(a.ruleinum+1<='z')continue;else break;if(i=n)cout<<"文法類型:3型文法"<<endl;elsefor(i=0;i<n;i+)num=0;length=a.rulei.length();for(j=0;j<length;j+)c=a.ruleij;num+;if(c='

18、-')break;you=length-(num+1);if(you=2)&&(a.ruleinum+1>='A')&&(a.ruleinum+1<='Z')&&(a.ruleinum+2>='a')&&(a.ruleinum+2<='z')|(you=1)&&(a.ruleinum+1>='a')&&(a.ruleinum+1<='z')continue;else break;if(i=n)cout<<"文法類型:3型文法"<<endl;elsecout<<"文法類型:2型文法"<<endl;elsecout<<"文法類型:1型文法"<<endl;e