編譯原理實(shí)驗(yàn)一:CHOMSKY文法類型_第1頁(yè)
編譯原理實(shí)驗(yàn)一:CHOMSKY文法類型_第2頁(yè)
編譯原理實(shí)驗(yàn)一:CHOMSKY文法類型_第3頁(yè)
編譯原理實(shí)驗(yàn)一:CHOMSKY文法類型_第4頁(yè)
編譯原理實(shí)驗(yàn)一:CHOMSKY文法類型_第5頁(yè)
已閱讀5頁(yè),還剩14頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱 Chomsky文法類型判斷實(shí)驗(yàn)時(shí)間 2013年10月29日 院系 計(jì)算機(jī)科學(xué)與電子技術(shù)系 班級(jí) 11計(jì)算機(jī)軟件 學(xué)號(hào)JV****** JV****** JP******試驗(yàn)?zāi)康模菏炀氄莆账姆N文法類型的概念及區(qū)別。2.設(shè)計(jì)一個(gè)Chomsky文法類型判別器,判斷0型、1型、2型和3型文法。實(shí)驗(yàn)原理:1?設(shè)G=(Vn,Vt,P,S),如果它的每個(gè)產(chǎn)生式a->B是這樣一種結(jié)構(gòu):aW(VnUVt)*且至少含有一個(gè)非終結(jié)符,而B(niǎo)U(VnUVt)*,則G是一個(gè)0型文法。設(shè)G=(Vn,Vt,P,S)為一文法,若P中的每一個(gè)產(chǎn)生式a->B均滿足I&1>=1aI,僅僅S->£除外,則文法G是1型或上下文有關(guān)的。設(shè)G=(Vn,Vt,P,S)為一文法,若P中的每一個(gè)產(chǎn)生式a->B均滿足:a是一個(gè)非終結(jié)符,B匕(VnUVt)*,則此文法稱為2型的或上下文無(wú)關(guān)的。設(shè)G=(Vn,Vt,P,S)為一文法,若P中的每一個(gè)產(chǎn)生式的形式都是A-〉aB或A-〉a,其中A和B都是非終結(jié)符,a=Vt*,則G是3型文法或正規(guī)文法。5.4個(gè)文法類的定義是逐漸增加限制的,因此可采用自頂向下的算法。實(shí)驗(yàn)內(nèi)容:1.程序清單如下:#include"stdafx.h"#include<iostream>#include<string>usingnamespacestd;typedefstructCSS //定義一個(gè)產(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)生式左部每一個(gè)字符{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;//如果每個(gè)產(chǎn)生時(shí)都能找到非終結(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)生式左部長(zhǎng)度是否大于右部break;if(i==n)return1;else{cout〈〈"該文法是0型文法"〈〈endl;return0;}}elsereturn0;}boolSecond(CSS*p,intn)//判斷2型文法{inti;if(First(p,n)) //同上,先判斷低級(jí)文法是否成立{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)生式左部長(zhǎng)度是否為一,左部第一個(gè)是否是非終結(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)生式右部字符個(gè)數(shù)是否在12之間,判斷右部第一個(gè)字符是否是非終結(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〈〈"請(qǐng)輸入文法產(chǎn)生式個(gè)數(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");程序運(yùn)行結(jié)果:測(cè)試用例1:7S->aSBES->aBEEB->BaB->abbB->bbbE->beeE->ee測(cè)試用例2:1型文法:7S->aSBES->aBEEB->BEaB->abbB->bbbE->beeE->ee運(yùn)行結(jié)果:

測(cè)試用例3:2型文法:9S->aABA->bBS->bBB->bBS->aB->bA->aAB->aA->aS運(yùn)彳丁結(jié)果::*F: 夾\b±any±\Debug\biaayi.exe"請(qǐng)輸人文法產(chǎn)主式個(gè)斟弘fi->bES->bBB->bBS->aE->bA—E->afi->aS3型文法:9S->aAA->bBS->bBB->bBS->aB->bA->aAB->aA->aS運(yùn)行結(jié)果見(jiàn)下頁(yè):4?實(shí)驗(yàn)心得:通過(guò)Chomsky文法類型判斷實(shí)驗(yàn)的實(shí)際操作,知道和理解了該理論在計(jì)算機(jī)中是怎樣執(zhí)行的,對(duì)該理論在實(shí)踐中的應(yīng)用有深刻的理解。在這次課程設(shè)計(jì)中,我們組就是按照實(shí)驗(yàn)指導(dǎo)的思想來(lái)完成。力口深了理解了文法規(guī)則的不同定義形式,培養(yǎng)了實(shí)踐動(dòng)手能力和程序開(kāi)發(fā)能力。壓縮文法等價(jià)變換2007-12-2813:30:33|分類:默認(rèn)分類|舉報(bào)|字號(hào)訂閱#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();〃壓縮文法等價(jià)變換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"請(qǐng)輸入您的文法中所包含的規(guī)則數(shù)"vvendl;cin>>count;coutvv"輸入文法的識(shí)別符:"vvendl;cin>>id;for(i=O;ivcount;i++){coutvv"請(qǐng)輸入規(guī)則"vvi+1vv"的左端:";cin>>left_1[i];coutvv"請(qǐng)輸入規(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"展開(kāi)輸出文法"vvendl;for(i=0;ivsize;i++)coutvvleft_2[i]vv"::="vvright_2[i]vvendl;coutvv"下面進(jìn)行壓縮文法等價(jià)變換"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());}〃查找加了標(biāo)記的非終結(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;〃將加了標(biāo)記的非終結(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ī)則的標(biāo)記存儲(chǔ)起來(lái),以便下面用,看條件1是否有改動(dòng)vectorvchar>lt;add_letter(lt,id);〃標(biāo)識(shí)符放入lt中do{intlen=lt.size();if(p[i]==O){if(find(lt,left_2[i])二二true){p[i]=1;〃加標(biāo)記intm=0;for(;right_2[i][m]!二、O';)m二m+1;intlength二m;〃規(guī)則右部的長(zhǎng)度stringtemp=right_2[i];〃將規(guī)則的右部暫時(shí)存在temp中for(j=0;j<length;j++)if(isalpha(temp[j])&&isupper(temp[j]))〃尋找大寫(xiě)字母{add_letter(lt,temp[j]);〃將新找到的字母放進(jìn)數(shù)組}}}if(len==lt.size())break;//lt中沒(méi)有新添加的非終結(jié)符則跳出}while(1);for(j=0;jvn;j++)〃掃描所有規(guī)則看是否有未加標(biāo)記的switch(p[j]){case0:p[j]=3;break;〃沒(méi)有加標(biāo)記的規(guī)則將其p[]設(shè)置為3case1:break;case3:break;}}coutvv"判斷條件Tvvendl;〃for(intx=0;xvn;x++)coutvvp[k];//coutvvendl;for(intl=0;lvn;l++)〃若條件1有改動(dòng),則返回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個(gè)規(guī)則右部是否全為終結(jié)符,若是,則將其左部加標(biāo)記,并添加到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)〃對(duì)剩余的沒(méi)加標(biāo)記的規(guī)則的操作,{stringtemp二right_2[i];intstr_len=temp.len

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論