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

編譯原理實驗告實名

文法型斷實時

年10月29院

計機學電技系班

算軟學

JP114065姓

唐

韓強

徐維

試驗目的：熟設計一個Chomsky文法斷0型、、型和實驗原理：G=(Vn,Vt,P,S)，如果它的每個產(chǎn)生α->βα(Vn∪*而β∈∪*則個0若P式α->β|βα僅法G是若P式α->βα，∈∪*為2型的或上下文設若中或，其中A和B都是非，∈*則G是實驗內(nèi)容：

#include"stdafx.h"#include<iostream>#include<string>usingnamespacestd;typedefstructCSS定義一個產(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)生式左部每一個字符{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;//如果每個生時都能找到非終結(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)生式左部長度是否大于右部break;}

if(i==n)return1;else{cout<<"該法是0型法<<endl;return0;}}elsereturn0;}boolSecond(CSS*p,intn)判斷型法{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)判斷文法{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){該法屬于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");

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

測試用例3：文法：S->aABA->bBS->aA->aAA->aS運行結(jié)果：測試用例4：

文法：S->aAA->bBS->aA->aAA->aS運行結(jié)果見下頁：實驗心得：過Chomsky文法類型判斷實驗的實際操作該

壓縮文法價變換2007-12-2813:30:33|分類：默認分類|舉報字號訂#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();//壓縮文法等價變換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<<"入文法的識別符:"<<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<<"開輸出文法"<<endl;for(i=0;i<size;i++)cout<<left_2[i]<<"::="<<right_2[i]<<endl;cout<<"面進行壓縮文法等價變換"<<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());}//查找加了標記的非終結(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}

//將加了標記的非終結(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ī)則的標記存儲起來，以便下面用，看條件1否有改動vector<char>add_letter(lt,id);//標識符放入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;//標記intm=0;for(;right_2[i][m]!='\0';)m=m+1;intlength=m;//規(guī)則右部的長度stringtemp=right_2[i];//將規(guī)則的右部暫時存在for(j=0;j<length;j++)if(isalpha(temp[j])&&isupper(temp[j]))//尋找大寫字母{將新找到的字母放進數(shù)組}}}if(len==lt.size())break;//lt中沒有新添加的非終結(jié)符則跳出}while(1);for(j=0;j<n;j++)//掃描所有規(guī)則看是否有未加標記的{

switch(p[j]){case0:p[j]=3;break;//沒有加標記的規(guī)則將其設置為3case1:break;case3:break;}}cout<<"斷條件"<<endl;//for(intx=0;x<n;x++)cout<<p[k];//cout<<endl;for(intl=0;l<n;l++)//條件1改動，則返回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個規(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;x<n;x++)cout<<p[k];//cout<<endl;do{intlen=lt.size();for(inti=0;i<n;i++){if(p[i]==0)//對剩余的沒加標記的規(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é)符以加標記的規(guī)則左部加標記，并添加非終結(jié)符到lt中p[i]=1;}

}}新標記添加，}while(1);for(intj=0;j<n;j++)//對沒添加標記的規(guī)則的標記符p[i]設置為3{switch(p[j]){case0:p[j]=3;break;case1:break;case