chomsky文法類型的判斷Word版

1、傳播優(yōu)秀Word版文檔 ，希望對您有幫助，可雙擊去除！編譯原理實(shí)驗(yàn)報告實(shí)驗(yàn)名稱 Chomsky文法類型判斷 實(shí)驗(yàn)時間 2014-4-2 院系 計算機(jī)科學(xué)與技術(shù)學(xué)院 班級 2011級科技（3）班 學(xué)號 E01114375 姓名 張練鋼 傳播優(yōu)秀Word版文檔 ，希望對您有幫助，可雙擊去除！1. 實(shí)驗(yàn)?zāi)康模?）通過實(shí)驗(yàn)進(jìn)一步理解chomsky文法類型判斷的的依據(jù)，理解每個類型文法的特點(diǎn)。（2）進(jìn)一步理解4種文法類型之間的包含關(guān)系。（3）體會這種理論對于計算機(jī)科學(xué)發(fā)展的深刻影響，特別是對程序設(shè)計語言的設(shè)計、編譯方法和計算復(fù)雜性等方面的重大作用。通過上機(jī)實(shí)現(xiàn)文法類型的自動判別。2.實(shí)驗(yàn)原理10型文法（

2、短語文法）如果對于某文法G，P中的每個規(guī)則具有下列形式：u: = v其中uV，vV*，則稱該文法G為0型文法或短語文法，簡寫為PSG。0型文法或短語結(jié)構(gòu)文法的相應(yīng)語言稱為0型語言或短語結(jié)構(gòu)語言L0。這種文法由于沒有其他任何限制，因此0型文法也稱為無限制文法，其相應(yīng)的語言稱為無限制性語言。任何0型語言都是遞歸可枚舉的，故0型語言又稱遞歸可枚舉集。這種語言可由圖靈機(jī)（Turning）來識別。21型文法（上下文有關(guān)文法）如果對于某文法G，P中的每個規(guī)則具有下列形式：xUy: = xuy其中UVN；uV；x，yV*，則稱該文法G為1型文法或上下文有關(guān)文法，也稱上下文敏感文法，簡寫為CSG。1型文法的規(guī)

3、則左部的U和右部的u具有相同的上文x和下文y，利用該規(guī)則進(jìn)行推導(dǎo)時，要用u替換U，必須在前面有x和后面有y的情況下才能進(jìn)行，顯示了上下文有關(guān)的特性。1型文法所確定的語言為1型語言L1，1型語言可由線性有界自動機(jī)來識別。32型文法（上下文無關(guān)文法）如果對于某文法G，P中的每個規(guī)則具有下列形式：U : = u其中UVN；uV，則稱該文法G為2型文法或上下文無關(guān)文法，簡寫為CFG。按照這條規(guī)則，對于上下文無關(guān)文法，利用該規(guī)則進(jìn)行推導(dǎo)時，無需考慮非終結(jié)符U所在的上下文，總能用u替換U，或者將u歸約為U，顯示了上下文無關(guān)的特點(diǎn)。傳播優(yōu)秀Word版文檔 ，希望對您有幫助，可雙擊去除！2型文法所確定的語言為

4、2型語言L2，2型語言可由非確定的下推自動機(jī)來識別。一般定義程序設(shè)計語言的文法是上下文無關(guān)的。如C語言便是如此。因此，上下文無關(guān)文法及相應(yīng)語言引起了人們較大的興趣與重視。43型文法（正則文法，線性文法）如果對于某文法G，P中的每個規(guī)則具有下列形式：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é)符號

5、只能被替換為單個終結(jié)符號，或被替換為單個非終結(jié)符號加上單個終結(jié)符號，或者被替換為單個終結(jié)符號加上單個非終結(jié)符號。3型文法所確定的語言為3型語言L3，3型語言可由確定的有限狀態(tài)自動機(jī)來識別。在常見的程序設(shè)計語言中，多數(shù)與詞法有關(guān)的文法屬于3型文法?？梢钥闯?，上述4類文法，從0型到3型，產(chǎn)生式限制越來越強(qiáng)，其后一類都是前一類的子集，而描述語言的功能越來越弱，四類文法及其表示的語言之間的關(guān)系可表示為：0型1型2型3型；即L0 L1 L2 L3.實(shí)驗(yàn)內(nèi)容（1）理解四種文法類型的特點(diǎn)，并利用他們之間包含關(guān)系0型1型2型3型；即L0 L1 L2 L對所屬類型作出判斷。（2）通過編程自動實(shí)現(xiàn)將輸入的文法判斷

6、出其所屬類型。4.實(shí)驗(yàn)心得本實(shí)驗(yàn)的上機(jī)實(shí)現(xiàn)需注意一下幾點(diǎn)：（1）數(shù)據(jù)的表示，利用struct constring front;string end;/定義每個產(chǎn)生式的結(jié)構(gòu)如A:=a 則front=A,end=a;因?yàn)槊總€文法都有多個產(chǎn)生式，我們將這多個文法依次存入一個string類型的test數(shù)組中，然后再將每個產(chǎn)生式分解成前端和后端的格式以便于分析每個產(chǎn)生式所屬的類型。傳播優(yōu)秀Word版文檔 ，希望對您有幫助，可雙擊去除?。?）在對文法進(jìn)行判斷前先對每個產(chǎn)生式作出判斷，那么所有產(chǎn)生式中文法類型最低的那個產(chǎn)生式所屬的類型即為該文法所屬的類型。（3）在對每個每個產(chǎn)生的類型做出判斷時要充分利用四種

7、文法類型之間的包含關(guān)系以簡化程序。如3型文法和2型文法的產(chǎn)生前端都為一個非終端符我們可以先利用這個特點(diǎn)先判斷一個產(chǎn)生式是否屬于3型文法或2型文法，如果不符合以上條件然后在判斷其是否屬于1型或0型文法。（4）在代碼的編寫過程中注意代碼的結(jié)構(gòu)以方便閱讀。5.實(shí)驗(yàn)代碼與結(jié)果/* 作者： 張練鋼（E01114375） 完成時間：2014-4-5 程序任務(wù)：chomsky文法類型的判斷 運(yùn)行環(huán)境：vc+ 6.0 */#include#include#includeusing namespace std;struct constring front;string end;/定義每個產(chǎn)生式的結(jié)構(gòu)如A:=a

8、則front=A,end=a;string VNT;/非終端符集合string VT;/終端符集合void decompose(string s, con &res)/該函數(shù)負(fù)責(zé)將輸入的每個產(chǎn)生式轉(zhuǎn)換成con結(jié)構(gòu)如A:=a 則front=A,end=a;int flag1=0,flag2=0;for(int i=0;is.size();i+)if(si=:)flag1=i;else if(si=)flag2=i;res.front=s.substr(0,flag1-1);res.end=s.substr(flag2+1,s.size()-1);傳播優(yōu)秀Word版文檔 ，希望對您有幫助，可雙擊去

9、除！bool isBelongToVNT(char s)/判斷一個字符是否屬于非終端字符for(int i=0;iVNT.size();i+)if(VNTi=s)return 1;return 0;bool isBelongToVT(char s)/判斷一個字符是否屬于終端字符for(int i=0;iVT.size();i+)if(VTi=s)return 1;return 0;bool isBelongToV(char s)/判斷一個字符是否屬于VNT U NTstring tem=VNT+VT;/因?yàn)榻K端符和非終端符沒有交集所以兩個字符串直接連接的結(jié)果即為VNT U NTfor(int

10、i=0;item.size();i+)if(temi=s)return 1;return 0;int judgeTypeOfP(con sen)/判斷每個產(chǎn)生式的類型int flag=0;for(int i=0;isen.front.size();i+)if(isBelongToV(sen.fronti)=0)/如果產(chǎn)生式前端中含有非V中的元素則不屬于任何文法類型flag=1;傳播優(yōu)秀Word版文檔 ，希望對您有幫助，可雙擊去除！break;if(flag=1)return -1;flag=0;for(i=0;isen.end.size();i+)if(isBelongToV(sen.endi

11、)=0 & sen.endi!=e)/如果產(chǎn)生式后端端中含有非V中的元素(空e除外)則不屬于任何文法類型flag=1;break;if(flag=1)return -1;if(sen.front.size()=1)/若產(chǎn)生式的前端是一個非終端符則判斷其是2型文法還是3型文法char tem=sen.front0;if(isBelongToVNT(tem)/如果front為非終端符則先判斷該產(chǎn)生式是不是正規(guī)文法或2型文法的結(jié)構(gòu)if(sen.end.size()=1)if(isBelongToVT(sen.end0)/如果是A:=a則屬于正規(guī)文法return 3;elsereturn 2; /因?yàn)?/p>

12、該產(chǎn)生式的前端是非終端字符所以滿足2型文法的要求已經(jīng)包含S:=e(e為空)else if(sen.end.size()=2)if(isBelongToVNT(sen.end1)&isBelongToVT(sen.end0)/如果是A:=aB則屬于正規(guī)文法return 3;elsereturn 2;/else if(sen.end.size()=2)傳播優(yōu)秀Word版文檔 ，希望對您有幫助，可雙擊去除！/if(isBelongToVNT(tem)elsereturn -1; /如果產(chǎn)生的前端沒有非終端符則不符合任何類型的文法/if(sen.front.size()=1)else int flag

13、=0;for(int i=0;i=sen.front.size()/如果產(chǎn)生式-滿足|=|則符合1型文法的要求，否則就是零型文法return 1;elsereturn 0;void judge(int res100,int count)/根據(jù)每個產(chǎn)生式的類型判斷文法的類型int j,flag=1;switch(res0)case 3:for(j=0;jcount;j+)if(resj3)傳播優(yōu)秀Word版文檔 ，希望對您有幫助，可雙擊去除！flag=0;break;if(flag=1)cout這是 3 型文法 endl;/如果所有的產(chǎn)生式都是3型文法則該文法為3型文法break;case 2:

14、flag=1;for( j=0;jcount;j+)if(resj2)flag=0;break;if(flag=1)cout這是 2 型文法 endl;/如果所有的產(chǎn)生式都是2型及以上類型文法則該文法為2型文法break;case 1:flag=1;for(j=0;jcount;j+)if(resj1)flag=0;break;if(flag=1)cout這是 1 型文法 endl;/如果所有的產(chǎn)生式都是1型及以上類型文法則該文法為1型文法break;case 0:flag=1;傳播優(yōu)秀Word版文檔 ，希望對您有幫助，可雙擊去除！for(j=0;jcount;j+)if(resj0)flag

15、=0;break;if(flag=1)cout這是 0 型文法 endl;/如果所有的產(chǎn)生式都是0型及以上類型文法則該文法為0型文法break;default :cout這不是任何類型的文法 endl;int main()int count=0; /記錄輸入產(chǎn)生式的個數(shù)string test100; /存放每個文法的產(chǎn)生式char tem100; /臨時輸入的字符串int res100; /用于存放每個產(chǎn)生式的判別結(jié)果cout請先輸入非終端符：tem;VNT=tem;cout請輸入終端符號tem;VT=tem;cout請輸入產(chǎn)生式：最后一條產(chǎn)生式以EOF結(jié)束tem )testcount+=tem;for(int i=0;icount;i+)con s;decompose(testi,s);resi=jud