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

下載本文檔

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

文檔簡(jiǎn)介

編譯原理實(shí)驗(yàn)告實(shí)名

文法型斷實(shí)時(shí)

年10月29院

計(jì)機(jī)學(xué)電技系班

算軟學(xué)

JP114065姓

韓強(qiáng)

徐維

試驗(yàn)?zāi)康模菏煸O(shè)計(jì)一個(gè)Chomsky文法斷0型、、型和實(shí)驗(yàn)原理:G=(Vn,Vt,P,S),如果它的每個(gè)產(chǎn)生α->βα(Vn∪*而β∈∪*則個(gè)0若P式α->β|βα僅法G是若P式α->βα,∈∪*為2型的或上下文設(shè)若中或,其中A和B都是非,∈*則G是實(shí)驗(yàn)內(nèi)容:

#include"stdafx.h"#include<iostream>#include<string>usingnamespacestd;typedefstructCSS定義一個(gè)產(chǎn)生式結(jié)構(gòu)體{stringleft;//定義產(chǎn)生式的部stringright;定產(chǎn)生式的右部}CSS;boolZero(CSSn)判型法{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è)生時(shí)都能找到非終結(jié)符}boolFirst(CSS*p,intn)判斷文法{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)判斷型法{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)判斷文法{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){該法屬于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)用文法類(lèi)型判斷,自頂向下system("pause");

}測(cè)試用例1:7S->aSBES->aBEEB->BaB->abbB->bbbE->beeE->ee運(yùn)行結(jié)果:測(cè)試用例2:文法:S->aBEEB->BEaB->abbE->beeE->ee運(yùn)行結(jié)果:

測(cè)試用例3:文法:S->aABA->bBS->aA->aAA->aS運(yùn)行結(jié)果:測(cè)試用例4:

文法:S->aAA->bBS->aA->aAA->aS運(yùn)行結(jié)果見(jiàn)下頁(yè):實(shí)驗(yàn)心得:過(guò)Chomsky文法類(lèi)型判斷實(shí)驗(yàn)的實(shí)際操作該

壓縮文法價(jià)變換2007-12-2813:30:33|分類(lèi):默認(rèn)分類(lèi)|舉報(bào)字號(hào)訂#include<iostream>#include<vector>usingnamespacebools_1(charid,char*left_2,charright_2[30][50],intn,intbools_2(charid,char*left_2,charright_2[30][50],intn,intboolfind(vector<char>&,char);boolend();voidadd_letter(vector<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ù)判斷條件2由c1,c2的返回值決定}voidmain(){help();charleft_1[30],right_1[30][50],left_2[30],right_2[30][50];intp[30]={0};intcount,i,j;chardo{cout<<"輸入您的文法中所包含的規(guī)則數(shù)"<<endl;cin>>count;cout<<"入文法的識(shí)別符:"<<endl;cin>>id;for(i=0;i<count;i++){cout<<"輸入規(guī)則"<<i+1<<"左端:cin>>left_1[i];cout<<"輸入規(guī)則"<<i+1<<"右端:cin>>right_1[i];}intsize=0;for(i=0;i<count;i++)

{intpos=0;left_2[size]=left_1[i];for(j=0;j<right_1[i][j]!='\0';j++){if(right_1[i][j]=='|'){right_2[size][pos]='\0';pos=0;left_2[++size]=left_1[i];}elseright_2[size][pos++]=right_1[i][j];}right_2[size][pos]='\0';size++;}cout<<"開(kāi)輸出文法"<<endl;for(i=0;i<size;i++)cout<<left_2[i]<<"::="<<right_2[i]<<endl;cout<<"面進(jìn)行壓縮文法等價(jià)變換"<<endl;compress(id,left_2,right_2,size,p);cout<<"縮后的結(jié)果:"<<endl;for(i=0;i<size;i++)

if(p[i]!=3)cout<<left_2[i]<<"::="<<right_2[i]<<endl;}while(!end());}//查找加了標(biāo)記的非終結(jié)符boolfind(<char>m){for(inti=0;p[i]!='\0';i++)if(p[i]==m)returntrue;returnfalse;}boolend(){charcout<<"想退出嗎?[Y/N]";cin>>m;if(m=='y'||m=='Y')true;elsereturn}

//將加了標(biāo)記的非終結(jié)符放到中voidadd_letter(vector<char>&p,charm){intlen=p.size();for(inti=0;i<len;i++)if(m==p[i])p.push_back(m);}//判斷條件bools_1(charid,char*left_2,char(*right_2)[50],intn,int{intnew_p[30],j;for(intk=0;k<n;k++)new_p[k]=p[k];//new_p[k]將上一次規(guī)則的標(biāo)記存儲(chǔ)起來(lái),以便下面用,看條件1否有改動(dòng)vector<char>add_letter(lt,id);//標(biāo)識(shí)符放入lt中do{intlen=lt.size();for(inti=0;i<n;i++)

if(p[i]==0){if(find(lt,left_2[i])==true){p[i]=1;//標(biāo)記intm=0;for(;right_2[i][m]!='\0';)m=m+1;intlength=m;//規(guī)則右部的長(zhǎng)度stringtemp=right_2[i];//將規(guī)則的右部暫時(shí)存在for(j=0;j<length;j++)if(isalpha(temp[j])&&isupper(temp[j]))//尋找大寫(xiě)字母{將新找到的字母放進(jìn)數(shù)組}}}if(len==lt.size())break;//lt中沒(méi)有新添加的非終結(jié)符則跳出}while(1);for(j=0;j<n;j++)//掃描所有規(guī)則看是否有未加標(biāo)記的{

switch(p[j]){case0:p[j]=3;break;//沒(méi)有加標(biāo)記的規(guī)則將其設(shè)置為3case1:break;case3:break;}}cout<<"斷條件"<<endl;//for(intx=0;x<n;x++)cout<<p[k];//cout<<endl;for(intl=0;l<n;l++)//條件1改動(dòng),則返回falseif(p[l]!=new_p[l])returnfalse;returntrue;}//判斷條件bools_2(charid,char*left_2,char(*right_2)[50],int*p){intnew_p[50];

for(intk=0;k<n;k++){new_p[k]=p[k];}cout<<endl;vector<char>for(inti=0;i<n;i++){if(p[i]==1){intm=0;for(;right_2[i][m]!='\0';)m=m+1;intlen=m;stringtemp=right_2[i];for(int看第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;x<n;x++)cout<<p[k];//cout<<endl;do{intlen=lt.size();for(inti=0;i<n;i++){if(p[i]==0)//對(duì)剩余的沒(méi)加標(biāo)記的規(guī)則的操作,{stringtemp=right_2[i];intstr_len=temp.length();for(intj=0;j<str_len;j++)if(isalpha(temp[j])&&isupper(temp[j]))if(find(lt,temp[j])==false)break;if(j==str_len){規(guī)則右部終結(jié)符以加標(biāo)記的規(guī)則左部加標(biāo)記,并添加非終結(jié)符到lt中p[i]=1;}

}}新標(biāo)記添加,}while(1);for(intj=0;j<n;j++)//對(duì)沒(méi)添加標(biāo)記的規(guī)則的標(biāo)記符p[i]設(shè)置為3{switch(p[j]){case0:p[j]=3;break;case1:break;case

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 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ì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論