編譯原理實(shí)驗(yàn)八：非LL(1)文法到LL(1)文法的轉(zhuǎn)換.doc

實(shí)驗(yàn)八：非LL(1)文法到LL(1)文法的轉(zhuǎn)換一：要求輸入：非LL(1)文法輸出：LL(1)文法二：實(shí)驗(yàn)?zāi)康?掌握LL(1)文法2熟悉運(yùn)用C+語言對消除左遞歸的使用三：實(shí)驗(yàn)原理直接左遞歸的消除消除產(chǎn)生式中的直接左遞歸是比較容易的。例如假設(shè)非終結(jié)符P的規(guī)則為PP / 其中，是不以P開頭的符號串。那么，我們可以把P的規(guī)則改寫為如下的非直接左遞歸形式： PP PP / 這兩條規(guī)則和原來的規(guī)則是等價的，即兩種形式從P推出的符號串是相同的。 設(shè)有簡單表達(dá)式文法GE： EE+T/ T TT*F/ F F（E）/ I經(jīng)消除直接左遞歸后得到如下文法： ETE E +TE/ TFTT *FT/ F（E）/ I考慮更一般的情況，假定關(guān)于非終結(jié)符P的規(guī)則為PP1 / P2 / Pn / 1 / 2 /m其中，i（I1，2，n）都不為，而每個j（j1，2，m）都不以P開頭，將上述規(guī)則改寫為如下形式即可消除P的直接左遞歸：P1 P / 2 P /m PP 1P / 2 P / n P /間接左遞歸的消除直接左遞歸見諸于表面，利用以上的方法可以很容易將其消除，即把直接左遞歸改寫成直接右遞歸。然而文法表面上不存在左遞歸并不意味著該文法就不存在左遞歸了。有些文法雖然表面上不存在左遞歸，但卻隱藏著左遞歸。例如，設(shè)有文法GS：SQc/ cQRb/ bRSa/ a雖不具有左遞歸，但S、Q、R都是左遞歸的，因?yàn)榻?jīng)過若干次推導(dǎo)有SQcRbcSabcQRbSabQcabRSaQcaRbca就顯現(xiàn)出其左遞歸性了，這就是間接左遞歸文法。消除間接左遞歸的方法是，把間接左遞歸文法改寫為直接左遞歸文法，然后用消除直接左遞歸的方法改寫文法。如果一個文法不含有回路，即形如PP的推導(dǎo)，也不含有以為右部的產(chǎn)生式，那么就可以采用下述算法消除文法的所有左遞歸。消除左遞歸算法：（1） 把文法G的所有非終結(jié)符按任一順序排列，例如，A1，A2，An。（2） for （i1；i=n；i+）for （j1；j=i1；j+）把形如AiAj的產(chǎn)生式改寫成Ai1 /2 /k 其中Aj1 /2 /k是關(guān)于的Aj全部規(guī)則； 消除Ai規(guī)則中的直接左遞歸； （3） 化簡由（2）所得到的文法，即去掉多余的規(guī)則。利用此算法可以將上述文法進(jìn)行改寫，來消除左遞歸。首先，令非終結(jié)符的排序?yàn)镽、Q、S。對于R，不存在直接左遞歸。把R代入到Q中的相關(guān)規(guī)則中，則Q的規(guī)則變?yōu)镼Sab/ ab/ b。代換后的Q不含有直接左遞歸，將其代入S，S的規(guī)則變?yōu)镾Sabc/ abc/ bc/ c。此時，S存在直接左遞歸。在消除了S的直接左遞歸后，得到整個文法為：SabcS/ bcS/ cSS abcS/ QSab/ ab/ bRSa/ a可以看到從文法開始符號S出發(fā)，永遠(yuǎn)無法達(dá)到Q和R，所以關(guān)于Q和R的規(guī)則是多余的，將其刪除并化簡，最后得到文法GS為：SabcS/ bcS/ cSS abcS/ 當(dāng)然如果對文法非終結(jié)符排序的不同，最后得到的文法在形式上可能不一樣，但它們都是等價的。例如，如果對上述非終結(jié)符排序選為S、Q、R，那么最后得到的文法GR為： RbcaR/ caR/ aRR bcaR/ 容易證明上述兩個文法是等價的。四：數(shù)據(jù)結(jié)構(gòu)與算法typedef struct Chomsky /定義一個產(chǎn)生式結(jié)構(gòu)體 string left; /定義產(chǎn)生式的左部 string right; /定義產(chǎn)生式的右部Chomsky;void apart(Chomsky *p,int i) /分開產(chǎn)生式左右部，i代表產(chǎn)生式的編號int zero(Chomsky *p)/0型文法int one(Chomsky *p)/1型文法int two(Chomsky *p)/2型文法int remove(Chomsky *p,int n)/消除左遞歸五：出錯分析1：空符號表示錯誤，前后不一致2：文法判斷參數(shù)傳遞錯誤六：實(shí)驗(yàn)結(jié)果與分析不是二型文法的：是二型文法的：七：源代碼#include#includeusing namespace std;typedef struct Chomsky /定義一個產(chǎn)生式結(jié)構(gòu)體 string left; /定義產(chǎn)生式的左部 string right; /定義產(chǎn)生式的右部Chomsky;int n;/產(chǎn)生式總數(shù)string strings;/存儲產(chǎn)生式char q20;void apart(Chomsky *p,int i) /分開產(chǎn)生式左右部，i代表產(chǎn)生式的編號int j; for(j=0;jstrings.length();j+)if(stringsj=-)pi.left=strings.substr(0,j);/從0開始的j長度的子串，即0j-1pi.right=strings.substr(j+1,strings.length()-j);/從j+1開始的后面子串int zero(Chomsky *p)/0型文法int flag(0),count(0); int i,j; for(i=0;in;i+) for(j=0;j=A&pi.leftj0)/說明某一個產(chǎn)生式左部有非終結(jié)符flag=0;/下個產(chǎn)生式判斷前清零count+;/左部存在非終結(jié)符的產(chǎn)生式 個數(shù)加1else break; /左部沒有非終結(jié)符，結(jié)束if(count=n) return 1; /屬于0型文法elsecoutendl所輸產(chǎn)生式不屬于任何文法。endl;return 0;int one(Chomsky *p)/1型文法int flag(0); int i; if(zero(p)for(i=0;in;i+) if(pi.right.length()0)coutendl此文法屬于0型文法，即短語文法。endl; return 0; /不屬于1型文法else if(flag=0)return 1; /屬于1型文法elsereturn 0;int two(Chomsky *p)/2型文法int flag(0); int i; if(one(p)for(i=0;i=A&pi.left00)coutendl此文法屬于1型文法，即上下文有關(guān)文法。endl; return 0; /不屬于2型文法else if(flag=0)return 1; /屬于2型文法elsereturn 0;int remove(Chomsky *p,int n)/消除左遞歸/把文法的所有非終結(jié)符按某一順序排序 int i,j,count=1,count1=n,flag=0,m,x; q0=p0.left0; for(i=1;in;i+) for(j=0;ji;j+)if(pi.left=pj.left)break;if(j=i)qcount+=pi.left0; count-; for(i=0;in;i+)/判斷第一個非終結(jié)符是否存在直接左遞歸 if(pi.left0=q0&pi.left0=pi.right0) flag+;if(flag!=0)/消除第一個非終結(jié)符的直接左遞歸 for(i=0;in;i+) if(pi.left0=q0) if(pi.left0=pi.right0) pi.left=pi.left+; pi.right=pi.right.substr(1,pi.right.length()+pi.left; elsepi.right=pi.right+pi.left+; pcount1.left=p0.left; pcount1+.right=#;/用#代替空產(chǎn)生式 /消一切左遞歸 for(m=0;m=count;m+) for(i=0;in;i+) if(pi.left0=qm) for(j=0;jcount1;j+) for(x=m+1;x=count;x+) if(pj.left0=qx&pj.right0=qm) pcount1.left=pj.left; pcount1.right=pi.right+pj.right.substr(1,pj.right.length(); count1=count1+1; for(j=0;jcount1;j+) for(x=m+1;x=count;x+) if(pj.right0=qm&pj.left0=qx) pj.right=;pj.left=; for(x=0,flag=0;xcount1;x+)/判斷第m個非終結(jié)符是否存在直接左遞歸 if(px.left0=qm&px.left0=px.right0) flag+; /消直接左遞歸if(flag!=0) for(i=0;icount1;i+)if(pi.left0=qm) if(pi.left0=pi.right0) pi.left=pi.left+; pi.right=pi.right.substr(1,pi.right.length()+pi.left; pcount1.left=pi.left; pcount1.right=#;/用#代替空產(chǎn)生式 else pi.right=pi.right+pi.left+; count1=count1+1; count1-; return count1;void main( )int i,j,count1;cout.編譯原理實(shí)驗(yàn)八：非LL(1)文法到LL(1)文法的轉(zhuǎn)換.endl; cout請輸入產(chǎn)生式總數(shù)及各產(chǎn)生式：endl其中左右部之間用-表示，空用#表示n;Chomsky *p=new Chomsky50; / 初始化產(chǎn)生式數(shù)組for(i=0;istrin