編譯原理實驗一：CHOMSKY文法類型

編譯原理實驗報告實驗名稱 Chomsky文法類型判斷實驗時間 2013年10月29日 院系 計算機科學與電子技術(shù)系 班級 11計算機軟件 學號JV****** JV****** JP******試驗目的：熟練掌握四種文法類型的概念及區(qū)別。2.設(shè)計一個Chomsky文法類型判別器，判斷0型、1型、2型和3型文法。實驗原理：1?設(shè)G=(Vn,Vt,P,S),如果它的每個產(chǎn)生式a->B是這樣一種結(jié)構(gòu)：aW(VnUVt)*且至少含有一個非終結(jié)符，而BU(VnUVt)*,則G是一個0型文法。設(shè)G=(Vn,Vt,P,S)為一文法，若P中的每一個產(chǎn)生式a->B均滿足I&1>=1aI,僅僅S->￡除外，則文法G是1型或上下文有關(guān)的。設(shè)G=(Vn,Vt,P,S)為一文法，若P中的每一個產(chǎn)生式a->B均滿足：a是一個非終結(jié)符，B匕(VnUVt)*，則此文法稱為2型的或上下文無關(guān)的。設(shè)G=(Vn,Vt,P,S)為一文法，若P中的每一個產(chǎn)生式的形式都是A-〉aB或A-〉a，其中A和B都是非終結(jié)符，a=Vt*,則G是3型文法或正規(guī)文法。5.4個文法類的定義是逐漸增加限制的，因此可采用自頂向下的算法。實驗內(nèi)容：1.程序清單如下：#include"stdafx.h"#include<iostream>#include<string>usingnamespacestd;typedefstructCSS //定義一個產(chǎn)生式結(jié)構(gòu)體{stringleft;//定義產(chǎn)生式的左部stringright;//定義產(chǎn)生式的右部}CSS;boolZero(CSS*p,intn)//判斷0型文法{inti,j;for(i=0;i〈n;i++)//循環(huán)n次，即遍歷所有產(chǎn)生式{for(j=0;j〈p[i].left.length();j++)//遍歷產(chǎn)生式左部每一個字符{if(p[i].left[j]>='A'&&p[i].left[j]〈='Z') //判斷字符是否是非終結(jié)符break;}if(j==p[i].left.length()){cout〈〈"該文法不是0型文法"〈〈endl;return0;break;}}if(i==n)return1;//如果每個產(chǎn)生時都能找到非終結(jié)符}boolFirst(CSS*p,intn) //判斷1型文法{inti;if(Zero(p,n)) //先判斷是否是0型文法{for(i=0;i〈n;i++){if((p[i].left.length()>p[i].right.length())&&p[i].right.length()!=NULL)//判斷產(chǎn)生式左部長度是否大于右部break;if(i==n)return1;else{cout〈〈"該文法是0型文法"〈〈endl;return0;}}elsereturn0;}boolSecond(CSS*p,intn)//判斷2型文法{inti;if(First(p,n)) //同上，先判斷低級文法是否成立{for(i=0;i〈n;i++) //同上，遍歷所有文法產(chǎn)生式{if((p[i].left.length()!=1)||!(p[i].left[0]>='A'&&p[i].left[0]〈='Z'))//判斷產(chǎn)生式左部長度是否為一，左部第一個是否是非終結(jié)符break;}if(i==n)return1;else{cout〈〈"該文法是1型文法"〈〈endl;return0;}}elsereturn0;}voidThird(CSS*p,intn) //判斷3型文法{inti;if(Second(p,n)) //同上，先判斷是否是2型文法{for(i=0;i〈n;i++)//同上，遍歷文法所有的產(chǎn)生式{if((p[i].right.length()==0)||(p[i].right.length()>=3)||(p[i].right[0]>='A'&&p[i].right[0]〈='Z'))//判斷產(chǎn)生式右部字符個數(shù)是否在12之間，判斷右部第一個字符是否是非終結(jié)符break;if(i==n){for(i=0;i<n;i++){if(p[i].right.length()==2){if(!(p[i].right[1]>='A'&&p[i].right[1]<='Z'))break;}}if(i==n){cout〈〈"該文法屬于3型文法"〈〈endl;}elsecout〈〈"該文法屬于2型文法"〈〈endl;}elsecout〈〈"該文法屬于2型文法"〈〈endl;}elsecout〈〈"結(jié)束"〈〈endl;}voidmain(){inti,j,n;stringinput;cout〈〈"請輸入文法產(chǎn)生式個數(shù)N：";cin>>n;CSS*p=newCSS[n];//初始化產(chǎn)生式數(shù)組for(i=0;i〈n;i++) //輸入產(chǎn)生式數(shù)組{input.erase();//清除cin>>input; //輸入for(j=0;j〈input.length();j++)//改變輸入數(shù)據(jù)的形式{if(input[j]=='-'){p[i].left=input.substr(0,j);p[i].right=input.substr(j+2,input.length());}}}Third(p,n); //調(diào)用文法類型判斷，自頂向下system("pause");程序運行結(jié)果:測試用例1：7S->aSBES->aBEEB->BaB->abbB->bbbE->beeE->ee測試用例2：1型文法：7S->aSBES->aBEEB->BEaB->abbB->bbbE->beeE->ee運行結(jié)果：

測試用例3：2型文法：9S->aABA->bBS->bBB->bBS->aB->bA->aAB->aA->aS運彳丁結(jié)果：:*F: 夾\b±any±\Debug\biaayi.exe"請輸人文法產(chǎn)主式個斟弘fi->bES->bBB->bBS->aE->bA—E->afi->aS3型文法：9S->aAA->bBS->bBB->bBS->aB->bA->aAB->aA->aS運行結(jié)果見下頁:4?實驗心得：通過Chomsky文法類型判斷實驗的實際操作，知道和理解了該理論在計算機中是怎樣執(zhí)行的，對該理論在實踐中的應用有深刻的理解。在這次課程設(shè)計中，我們組就是按照實驗指導的思想來完成。力口深了理解了文法規(guī)則的不同定義形式，培養(yǎng)了實踐動手能力和程序開發(fā)能力。壓縮文法等價變換2007-12-2813:30:33|分類：默認分類|舉報|字號訂閱#includeviostream>#includevvector>usingnamespacestd;bools_1(charid,char*left_2,charright_2[30][50],intn,int*p);bools_2(charid,char*left_2,charright_2[30][50],intn,int*p);boolfind(vector<char>&,char);boolend();voidadd」etter(vector<char>&,char);voidhelp();〃壓縮文法等價變換voidcompress(charid,charleft_2[],charright_2[30][50],intsz,intp[]){do{boolc1=s_1(id,left_2,right_2,sz,p);boolc2=s_2(id,left_2,right_2,sz,p);if(c1&&c2)break;}while(1);//是否繼續(xù)判斷條件1或2。由c1,c2的返回值決定}voidmain(){help();charleft_1[3O],right_1[3O][5O],left_2[30],right_2[30][50];intp[30]={0};intcount,i,j;charid;do{coutvv"請輸入您的文法中所包含的規(guī)則數(shù)"vvendl;cin>>count;coutvv"輸入文法的識別符:"vvendl;cin>>id;for(i=O;ivcount;i++){coutvv"請輸入規(guī)則"vvi+1vv"的左端："；cin>>left_1[i];coutvv"請輸入規(guī)則"vvi+1vv"的右端："；cin>>right_1[i];}intsize=0;{intpos=0;left_2[size]=left_1[i];for(j=0;jvright_1[i][j]!二、O';j++){if(right_1[i][j]==T){right_2[size][pos]二、O';pos=0;left_2[++size]=left_1[i];}elseright_2[size][pos++]=right_1[i][j];}right_2[size][pos]='\0';size++;}coutvv"展開輸出文法"vvendl;for(i=0;ivsize;i++)coutvvleft_2[i]vv"::="vvright_2[i]vvendl;coutvv"下面進行壓縮文法等價變換"vvendl;compress(id,left_2,right_2,size,p);coutvv"壓縮后的結(jié)果："vvendl;if(p[i]!=3)coutvvleft_2[i]vv"::二"vvright_2[i]vvendl;}while(!end());}〃查找加了標記的非終結(jié)符boolfind(vectorvchar>&p,charm){for(inti=0;p[i]!='\0';i++)if(p[i]==m)returntrue;returnfalse;}boolend(){charm;coutvv"你想退出嗎？[Y/N]";cin>>m;if(m=='y'||m=='Y')returntrue;elsereturnfalse;〃將加了標記的非終結(jié)符放到p中voidadd_letter(vectorvchar>&p,charm){intlen二p.size();for(inti=0;ivlen;i++)if(m==p[i])return;p.push_back(m);}〃判斷條件1bools_1(charid,char*left_2,char(*right_2)[50],intn,int*p){intnew_p[30],j;for(intk=0;kvn;k++)new_p[k]=p[k];//new_p[k]將上一次規(guī)則的標記存儲起來，以便下面用，看條件1是否有改動vectorvchar>lt;add_letter(lt,id);〃標識符放入lt中do{intlen=lt.size();if(p[i]==O){if(find(lt,left_2[i])二二true){p[i]=1；〃加標記intm=0;for(;right_2[i][m]!二、O';)m二m+1;intlength二m;〃規(guī)則右部的長度stringtemp=right_2[i];〃將規(guī)則的右部暫時存在temp中for(j=0;j<length;j++)if(isalpha(temp[j])&&isupper(temp[j]))〃尋找大寫字母{add_letter(lt,temp[j]);〃將新找到的字母放進數(shù)組}}}if(len==lt.size())break;//lt中沒有新添加的非終結(jié)符則跳出}while(1);for(j=0;jvn;j++)〃掃描所有規(guī)則看是否有未加標記的switch(p[j]){case0:p[j]=3;break;〃沒有加標記的規(guī)則將其p[]設(shè)置為3case1:break;case3:break;}}coutvv"判斷條件Tvvendl;〃for(intx=0;xvn;x++)coutvvp[k];//coutvvendl;for(intl=0;lvn;l++)〃若條件1有改動，則返回falseif(p[l]!=new_p[l])returnfalse;returntrue;}〃判斷條件2bools_2(charid,char*left_2,char(*right_2)[50],intn,int*p){intnew_p[50];for(intk=O;kvn;k++){new_p[k]二p[k];}coutvvendl;vectorvchar>It;for(inti=0;ivn;i++){if(p[i]==1){intm=0;for(;right_2[i][m]!='\0';)m=m+1;intlen=m;stringtemp=right_2[i];for(intj=O;jvlen;j++)〃看第i個規(guī)則右部是否全為終結(jié)符，若是，則將其左部加標記，并添加到lt中if(isalpha(temp[j])&&isupper(temp[j]))break;if(j==len){add_letter(lt,left_2[i]);p[i]=1;}}//for(intx=0;xvn;x++)coutvvp[k];//coutvvendl;do{intlen=lt.size();for(inti=0;ivn;i++){if(p[i]==O)〃對剩余的沒加標記的規(guī)則的操作，{stringtemp二right_2[i];intstr_len=temp.len