編譯原理實驗二：壓縮文法的等價變換

1、實驗二：壓縮文法的等價變換一：要求輸入：任意的上下文無關(guān)文法輸出：等價的壓縮了的文法要求：除了可查看壓縮了的文法，還可查看刪除了哪些規(guī)則二：實驗?zāi)康牧私馕姆ǖ暮喕簩嶒炘韯h除文法中的有害規(guī)則和多余規(guī)則有害規(guī)則：若文法中有如U:=U的規(guī)則，則這就是有害規(guī)則，它會引起二義性，而無任何用處。多余規(guī)則：（1）某條規(guī)則U:=u的左部非終結(jié)符U（U不是識別符號），不在任何其他規(guī)則右部出現(xiàn)，即所有的推導(dǎo)始終不會用到此規(guī)則。【不可到達】（2）在推導(dǎo)句子的過程中，一旦使用了該規(guī)則，將推不出任何終結(jié)符號串。即該規(guī)則中含有推不出任何終結(jié)符號串的非終結(jié)符?！静豢山K止】四：數(shù)據(jù)結(jié)構(gòu)與算法struct Chomsky

2、string left; string right; ;void apart(Chomsky *p,int i) /分開產(chǎn)生式左右部void VNVT(Chomsky *p)/求VN和VTint zero(Chomsky *p)/0型文法int one(Chomsky *p)/1型文法int two(Chomsky *p)/2型文法void shanchu(Chomsky *p)/刪除多余規(guī)則與有害規(guī)則五：出錯分析1：變量重復(fù)定義導(dǎo)致了一些小錯誤2：程序太長缺少也導(dǎo)致了錯誤3：后面刪除規(guī)則的程序出錯了，沒有調(diào)試成功。六：實驗結(jié)果與分析不是上下文無關(guān)文法的：2型文法的壓縮：七：源代碼#inclu

3、de<iostream>#include<string>using namespace std;#define max 50int NONE=1;int RELEFT=1;string strings,noend,end;/非終結(jié)符與終結(jié)符存儲int n;/產(chǎn)生式總數(shù)int flag;struct Chomskystring left; string right; ; void apart(Chomsky *p,int i) /分開產(chǎn)生式左右部int j; for(j=0;j<strings.length();j+)if(stringsj='-')

4、pi.left=strings.substr(0,j);pi.right=strings.substr(j+1,strings.length()-j);void VNVT(Chomsky *p)/求VN和VTint i,j;for(i=0;i<n;i+) for(j=0;j<(int)pi.left.length();j+) if(pi.leftj>='A'&&pi.leftj<='Z')/非終結(jié)符判斷if(noend.find(pi.leftj)>100)noend+=pi.leftj; elseif(end.fi

5、nd(pi.leftj)>100)end+=pi.leftj;for(j=0;j<(int)pi.right.length();j+) if(!(pi.rightj>='A'&&pi.rightj<='Z')/終結(jié)符判斷if(end.find(pi.rightj)>100)end+=pi.rightj;else if(noend.find(pi.rightj)>100)noend+=pi.rightj;int zero(Chomsky *p)/0型文法int flag(0),count(0); int i,j;

6、 for(i=0;i<n;i+) for(j=0;j<(int)pi.left.length();j+)if(pi.leftj>='A'&&pi.leftj<='Z') /有否非終結(jié)符flag+;if(flag>0)flag=0;count+;else break; /左部沒有非終結(jié)符，結(jié)束if(count=n) return 1; /屬于0型文法elsecout<<endl<<"所輸產(chǎn)生式不屬于任何文法。"<<endl;NONE=0;return 0;int

7、one(Chomsky *p)/1型文法int flag(0); int i; if(zero(p)for(i=0;i<n;i+) if(pi.right.length()<pi.left.length() /右部長度是否小于左部flag+;break;elseflag-;if(flag>0)cout<<endl<<"此文法屬于0型文法，即短語文法。"<<endl; return 0; /不屬于1型文法else if(flag=0)return 1; /屬于1型文法elsereturn 0;int two(Chomsky

8、 *p)/2型文法int flag(0); int i; if(one(p)for(i=0;i<n;i+)if(pi.left.length()!=1)|!(pi.left0>='A'&&pi.left0<='Z') /左部不屬于一個字符或不屬于非終結(jié)符flag+;break;else flag-;if(flag>0)cout<<endl<<"此文法屬于1型文法，即上下文有關(guān)文法。"<<endl; return 0; /不屬于2型文法else if(flag=0)co

9、ut<<"次文法屬于2型文法"<<endl;return 1;/屬于2型文法elsereturn 0;void shanchu(Chomsky *p)/刪除多余規(guī)則與有害規(guī)則if(two(p)cout<<"此文法屬于上下文無關(guān)文法，可進行文法壓縮，實驗繼續(xù)"<<endl;int i,j;for(i=0;i<n;i+) /有害規(guī)則的判斷if(pi.left.length()=pi.right.length()for(j=0;j<(int)pi.left.length();j+)if(pi.left

10、j!=pi.rightj) /不為有害規(guī)則j-; break;/次規(guī)則不是有害規(guī)則if(j=pi.left.length()-1)/此條規(guī)則為有害規(guī)則，刪除cout<<"刪除此條有害規(guī)則"<<pi.left<<"->"<<pi.right<<endl;n-;for(int k=0;k<(int)noend.length();k+)/多余規(guī)則中不可到達的判斷for(i=0;i<n;i+) for(j=0;j<(int)pi.right.length();j+)if(noen

11、dk!=pi.rightj)continue;else i-;break;if(i=n-1)/此條規(guī)則為多余規(guī)則for(i=0;i<n;i+)if(pi.leftj=noendk|pi.rightj=noendk)cout<<"刪除此條多余規(guī)則"<<pi.left<<"->"<<pi.right<<endl;n-;for(k=0;k<(int)noend.length();k+)/多余規(guī)則中不可終止的判斷cout<<"壓縮后的文法是："<<endl;for(i=0;i<n;i+)cout<<pi.left<<"->"<<pi.right<<endl;elsecout<<"此文法不是上下文無關(guān)文法，實驗結(jié)束"<<endl;void main()int i; cout<<".編譯原理實驗二：壓縮文法的等價變換."<<endl; cout<<"請輸入產(chǎn)生式總數(shù)及各產(chǎn)生式："<&