編譯原理實驗八非LL文法到LL文法的變換編譯原理實驗八非LL文法到LL文法的變換編譯原理實驗八非LL文法到LL文法的變換實驗八：非LL(1)文法到LL(1)文法的變換一：要求輸入：非LL(1)文法輸出：LL(1)文法二：實驗目的1．掌握LL(1)文法2．熟習運用C++語言對除掉左遞歸的使用三：實驗原理直接左遞歸的除掉除掉產生式中的直接左遞歸是比較簡單的。比方假設非終結符P的規則為P→Pα/β此中，β是不以形式：

P開頭的符號串。那么，我們可以把P→βP’

P的規則改寫為以下的非直接左遞歸P’→αP’

/

ε這兩條規則和本來的規則是等價的，即兩種形式從設有簡單表達式文法G[E]：E→E+T/TT→T*F/FF→（E）/I

P推出的符號串是相同的。經除掉直接左遞歸后獲取以下文法：→TE’’→+TE’/εT→FT’T’→*FT’/εF→（E）/I考慮更一般的狀況，假設關于非終結符P的規則為P→Pα1/Pα2//Pαn/β1/β2//βm此中，αi（I＝1，2，，n）都不為ε，而每個βj（j＝1，2，，m）都不以P開頭，將上述規則改寫為以下形式即可除掉P的直接左遞歸：P→β1P’/β2P’//βmP’P’→α1P’/α2P’//αnP’/ε間接左遞歸的除掉直接左遞歸見諸于表面，利用以上的方法可以很簡單將其除掉，即把直接左遞歸改寫成直接右遞歸。可是文法表面上不存在左遞歸其實不意味著該文法就不存在左遞歸了。有些文法固然表面上不存在左遞歸，但卻隱蔽著左遞歸。比方，設有文法G[S]：S→Qc/cQ→Rb/bR→Sa/a雖不擁有左遞歸，但S、Q、R都是左遞歸的，由于經過若干次推導有SQcRbcSabcQRbSabQcabRSaQcaRbca就顯現出其左遞歸性了，這就是間接左遞歸文法。除掉間接左遞歸的方法是，把間接左遞歸文法改寫為直接左遞歸文法，而后用除掉直接左遞歸的方法改寫文法。假如一個文法不含有回路，即形如PP的推導，也不含有以ε為右部的產生式，那么就可以采納下述算法除掉文法的所有左遞歸。除掉左遞歸算法：（1）把文法G的所有非終結符按任一序次擺列，比方，A1，A2，，An。（2）for（i＝1；i<=n；i++）for（j＝1；j<=i－1；j++）{把形如Ai→Ajγ的產生式改寫成Ai→δ1γ/δ2γ//δkγ此中Aj→δ1/δ2//δk是關于的Aj所有規則；除掉Ai規則中的直接左遞歸；}3）化簡由（2）所獲取的文法，即去掉剩余的規則。利用此算法可以將上述文法進行改寫，來除掉左遞歸。第一，令非終結符的排序為R、Q、S。關于R，不存在直接左遞歸。把R代入到相關規則中，則Q的規則變成Q→Sab/ab/b。代換后的Q不含有直接左遞歸，將其代入S，S的規則變成S→Sabc/abc/bc/c此時，S存在直接左遞歸。在除掉了S的直接左遞歸后，獲取整個文法為：S→abcS’/bcS'/cS'

Q中的。S’→abcS'/

εQ→Sab/ab/bR→Sa/a可以看到從文法開始符號S出發，永久沒法達到的，將其刪除并化簡，最后獲取文法G[S]為：S→abcS'/bcS’/cS'

Q和

R，因此關于

Q和R的規則是剩余S'

→abcS'/

ε自然假如對文法非終結符排序的不一樣，是等價的。比方，假如對上述非終結符排序選為R→bcaR'/caR'/aR’

最后獲取的文法在形式上可能不一樣樣，S、Q、R，那么最后獲取的文法

但它們都G[R]為：R'

→bcaR'/

ε簡單證明上述兩個文法是等價的。四：數據結構與算法typedefstructChomsky

//

定義一個產生式結構體{stringleft;//定義產生式的左部stringright;//定義產生式的右部}Chomsky;voidapart(Chomsky*p,inti)//分開產生式左右部，intzero(Chomsky*p)//0型文法intone(Chomsky*p)//1型文法inttwo(Chomsky*p)//2型文法intremove(Chomsky*p,intn)//除掉左遞歸

i代表產生式的編號五：出錯解析1：空符號表示錯誤，前后不一致2：文法判斷參數傳達錯誤六：實驗結果與解析不是二型文法的：是二型文法的：七：源代碼#include<iostream>#include<string>usingnamespacestd;typedefstructChomsky//定義一個產生式結構體{stringleft;//定義產生式的左部stringright;//定義產生式的右部}Chomsky;intn;//產生式總數stringstrings;//儲存產生式charq[20];voidapart(Chomsky*p,inti)//

分開產生式左右部，

i代表產生式的編號{intj;for(j=0;j<strings.length();j++)if(strings[j]=='-'){p[i].left=strings.substr(0,j);//從0開始的j長度的子串，即0~j-1p[i].right=strings.substr(j+1,strings.length()-j);//從j+1開始的后邊子串}}intzero(Chomsky*p)//0型文法{intflag(0),count(0);inti,j;for(i=0;i<n;i++){for(j=0;j<(int)p[i].left.length();j++){if(p[i].left[j]>='A'&&p[i].left[j]<='Z')//有否非終結符flag++;//非終結符個數加

1}if(flag>0)//{

說明某一個產生式左部有非終結符flag=0;//下個產生式判斷前清零count++;//左部存在非終結符的產生式

個數加

1}elsebreak;//左部沒有非終結符，結束}if(count==n)return1;//屬于

0型文法else{cout<<endl<<"所輸產生式不屬于任何文法。"<<endl;return0;}}intone(Chomsky*p)//1型文法{intflag(0);inti;if(zero(p)){for(i=0;i<n;i++){if(p[i].right.length()<p[i].left.length())//右部長度能否小于左部，不是1型{flag++;break;}}}else//即不是0型文法flag--;//flag=-1if(flag>0){cout<<endl<<"此文法屬于0型文法，即短語文法。"<<endl;return0;//不屬于1型文法}elseif(flag==0)return1;//屬于1型文法elsereturn0;}inttwo(Chomsky*p)//2型文法{intflag(0);inti;if(one(p)){for(i=0;i<n;i++)if((p[i].left.length()!=1)||!(p[i].left[0]>='A'&&p[i].left[0]<='Z'))//左部不屬于一個字符或不屬于非終結符{flag++;//則不為2型break;}}else//不為1型，flag=-1flag--;if(flag>0){cout<<endl<<"此文法屬于1型文法，即上下文相關文法。"<<endl;return0;//不屬于2型文法}elseif(flag==0){return1;//屬于2型文法}elsereturn0;}intremove(Chomsky*p,intn)//除掉左遞歸{//把文法的所有非終結符按某一序次排序inti,j,count=1,count1=n,flag=0,m,x;q[0]=p[0].left[0];for(i=1;i<n;i++){for(j=0;j<i;j++){if(p[i].left==p[j].left)break;}if(j==i)q[count++]=p[i].left[0];}count--;for(i=0;i<n;i++)//判斷第一個非終結符能否存在直接左遞歸if(p[i].left[0]==q[0]&&p[i].left[0]==p[i].right[0])flag++;if(flag!=0)//除掉第一個非終結符的直接左遞歸{for(i=0;i<n;i++){if(p[i].left[0]==q[0]){if(p[i].left[0]==p[i].right[0]){p[i].left=p[i].left+"'";p[i].right=p[i].right.substr(1,p[i].right.length())+p[i].left;}elsep[i].right=p[i].right+p[i].left+"'";}}p[count1].left=p[0].left;p[count1++].right="#";//用#取代空產生式}//消全部左遞歸for(m=0;m<=count;m++){for(i=0;i<n;i++){if(p[i].left[0]==q[m]){for(j=0;j<count1;j++){for(x=m+1;x<=count;x++)if(p[j].left[0]==q[x]&&p[j].right[0]==q[m]){p[count1].left=p[j].left;p[count1].right=p[i].right+p[j].right.substr(1,p[j].right.length());count1=count1+1;}}}}for(j=0;j<count1;j++){for(x=m+1;x<=count;x++)if(p[j].right[0]==q[m]&&p[j].left[0]==q[x]){p[j].right="";p[j].left="";}}for(x=0,flag=0;x<count1;x++)//判斷第m個非終結符能否存在直接左遞歸if(p[x].left[0]==q[m]&&p[x].left[0]==p[x].right[0])flag++;消直接左遞歸if(flag!=0){for(i=0;i<count1;i++){if(p[i].left[0]==q[m]){if(p[i].left[0]==p[i].right[0]){p[i].left=p[i].left+"'";p[i].right=p[i].right.substr(1,p[i].right.length())+p[i].left;p[count1].left=p[i].left;p[count1].right="#";//用#取代空產生式}elsep[i].right=p[i].right+p[i].left+"'";}}count1=count1+1;}}count1--;returncount1;}voidmain(){inti,j,count1;cout<<"...............編譯原理實驗八：非cout<<"請輸入產生式總數及各產生式：示"<<endl;

LL(1)文法到"<<endl<<"

LL(1)文法的變換此中左右部之間用

................"<<endl;'-'表示，空用'#'表cin>>n;Chomsky*p=newChomsky[50];//初始化產生式數組for(i=0;i<n;i++){cin>>strings;