c實(shí)現(xiàn)消除文法左遞歸

1、編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱消除文法的左遞歸實(shí)驗(yàn)時(shí)間院系 計(jì)算機(jī)科學(xué)與技術(shù)班級2008學(xué)號JB084193姓名 潘亞飛1. 試驗(yàn)?zāi)康妮斎耄喝我獾纳舷挛臒o關(guān)文法。輸出：消除了左遞歸的等價(jià)文法。2. 實(shí)驗(yàn)原理1直接左遞歸的消除消除產(chǎn)生式中的直接左遞歸是比較容易的。例如假設(shè)非終結(jié)符P 的規(guī)則為Pf Pa / B其中，B是不以P開頭的符號用。那么，我們可以把 P的規(guī)則改寫為如下的非直接左遞歸形式：P-BP'P' - a P' /£這兩條規(guī)則和原來的規(guī)則是等價(jià)的，即兩種形式從P 推出的符號串是相同的。設(shè)有簡單表達(dá)式文法GE：E - E+T/ TT - T*F/ FF - (

2、 E) / I經(jīng)消除直接左遞歸后得到如下文法：E - TE'E ' +TE' / £T -FT'T' -*FT' / £F - ( E) / I考慮更一般的情況，假定關(guān)于非終結(jié)符P 的規(guī)則為P-Pa 1 / P a2 / / P an/ 儲/ 02 / 0 m其中，a i (I=1, 2,，n)都不為£ ,而每個(gè)0j (j=1, 2,，nm都不以P 開頭，將上述規(guī)則改寫為如下形式即可消除P 的直接左遞歸：4 B 1 P' / 02 P' / Bm P'P'-aiP' / a 2

3、 P' / / an P' / &2間接左遞歸的消除直接左遞歸見諸于表面，利用以上的方法可以很容易將其消除，即把直接左遞歸改寫成直接右遞歸。然而文法表面上不存在左遞歸并不意味著該文法就不存在左遞歸了。有些文法雖然表面上不存在左遞歸，但卻隱藏著左遞歸。例如，設(shè)有文法GS：Sf Qc/ cCH Rb/ bRr Sa/ a雖不具有左遞歸，但S、Q R都是左遞歸的，因?yàn)榻?jīng)過若干次推導(dǎo)有S Qc Rbc SabcQ Rb Sab QcabR Sa Qca Rbca就顯現(xiàn)出其左遞歸性了，這就是間接左遞歸文法。消除間接左遞歸的方法是，把間接左遞歸文法改寫為直接左遞歸文法，然后用消除直

4、接左遞歸的方法改寫文法。如果一個(gè)文法不含有回路，即形如 P P的推導(dǎo)，也不含有以8為右部的產(chǎn)生式，那么就可以采用下述算法消除文法的所有左遞歸。消除左遞歸算法：(1) 把文法G的所有非終結(jié)符按任一順序排列，例如， A, 4,A(2) for (i = 1; i<=n ； i+ )for (j = 1; j<=i 1; j+ ) 把形如A-A y的廣生式改寫成 A-"丫 / S1 2 y / S' k y其中A-" / ” / 6 k是關(guān)于的A全部規(guī)則；消除Ai 規(guī)則中的直接左遞歸；( 3) 化簡由(2)所得到的文法，即去掉多余的規(guī)則。利用此算法可以將上述文

5、法進(jìn)行改寫，來消除左遞歸。首先，令非終結(jié)符的排序?yàn)?R Q S。對于R,不存在直接左遞歸。把 R代 入到Q中的相關(guān)規(guī)則中，則Q的規(guī)則變?yōu)镼HSab/ ab/ b。代換后的Q不含有直接左遞歸，將其代入S,S的規(guī)則變?yōu)镾-Sabc/ abc/ bc/ c。此時(shí)，S存在直接左遞歸。在消除了 S的直接左遞歸后，得到整個(gè)文法為：Sf abcS' / bcS'/ cS'S' -abcS'/ £QH Sab/ ab/ bRH* Sa/ a可以看到從文法開始符號 S出發(fā)，永遠(yuǎn)無法達(dá)到Q和R,所以關(guān)于Q和R的 規(guī)則是多余的，將其刪除并化簡，最后得到文法GS為：S

6、f abcS'/ bcS ' / cS'S' -abcS'/ £當(dāng)然如果對文法非終結(jié)符排序的不同，最后得到的文法在形式上可能不一樣，但它們都是等價(jià)的。例如，如果對上述非終結(jié)符排序選為S、Q R,那么最后得到的文法 GR為： R-bcaR'/ caR'/ aR 'R' - bcaR'/ £容易證明上述兩個(gè)文法是等價(jià)的。3.1. 實(shí)驗(yàn)內(nèi)容消除左遞歸算法：(1)把文法G的所有非終結(jié)符按任一順序排列，例如， A, 4,，A。(2)for(i = 1; i<=n ; i+ )for (j = 1;

7、j<=i 1; j+ ) 把形如A-A y的廣生式改寫成 Af占1丫 / S1 2 y / S' k y 其中A-" / ” / 6 k是關(guān)于的A全部規(guī)則； 消除Ai 規(guī)則中的直接左遞歸；(3) 化簡由(2)所得到的文法，即去掉多余的規(guī)則。利用此算法可以將上述文法進(jìn)行改寫，來消除左遞歸。4. 實(shí)驗(yàn)代碼eft0=q0)if(pi.left0=pi.right0)flag+;if(flag!=0)eft0=q0)if(pi.left0=pi.right0)string str;str=pi.(1,int (pi.();string temp=pi.left;string t

8、emp1="'"pi.left=temp+temp1;pi.right=str+pi.left;elsestring temp=pi.left;string temp1="'"temp=temp+temp1;pi.right=pi.right+temp;string str="'"pcount1.left=p0.left0+str;pcount1.right=" & "for( i=0;i <= count;i+)for(int j=0;j < i;j+)for(int

9、g=0;g < n;g+)if(qi=pg.left0)if(pg.right0=qj)for(int h=0;h < n*n;h+)if(ph.left0=qj&&int (ph.()=1)string str;str=pg.(1,int (pg.();p+count1.left=pg.left;pcount1.right=ph.right+str;pg.left=""pg.right=""for( i=0;i <= count;i+)flag=0;for(int j=0;j < n*n;j+)if(pj.lef

10、t0=qi)if(pj.left0=pj.right0) flag+;if(flag!=0)for(int j=0;j <= n*n;j+)if(pj.left0=qi)if(pj.left0=pj.right0)string str;str=pj.(1,int (pj.();string temp=pj.left;string temp1="'"pj.left=temp+temp1;pj.right=str+pj.left;elsestring temp=pj.left;string temp1="'"temp=temp+temp

11、1;pj.right=pj.right+temp;)string str=;p+count1.left=qi+str;pcount1.right=" £)int Delete(WF *p,int n)(return 0;)int main()(int ij,flag=0,count=1,n;coutvv"請輸入文法產(chǎn)生式個(gè)數(shù)n： "«endl;cin»n;WF *p=new WF50;coutvv”請輸入文法的個(gè)產(chǎn)生式："«endl;for(i=0;i<n;i+)eft;cout«"-&g

12、t;"«endl;cin»pi.right;cout«endl;)cout«endl;coutvv”即輸入的文法產(chǎn)生式為："«endl; for(i=0;i < n;i+)cout«pi.left«"->"«pi.right«endl;coutv v”*” v vend I .char q 2 0; eft 0; eft=p j. I eft)flag+;if(flag=O)qcount+=pi.left0;)count-;Removing(p,q,n,

13、count);eft0=qi) && int (pj.()尸=1 ) cout<<pj.left«"->"«pj.right«endl;else continue;for( j=O;j <= n*n;j+)if( (pU.leftO=qi) && int (pj.()尸=2 ) cout<<pj.left«"->"«pj.right«endl;else continue;return 0;)5. 實(shí)驗(yàn)結(jié)果消除直接左遞歸：消除間接左遞歸:6. 實(shí)驗(yàn)心得一個(gè)文法是含有左遞歸的，如果存在非終結(jié)符 P , P Pa含有左遞歸的文法將使上述的自上而下的分析過程陷入無限循環(huán)，即當(dāng)試圖用 P 去匹配輸入串時(shí)，就會出現(xiàn)在沒有吃進(jìn)任何輸入符號的情況下，又得重新要求 P 去進(jìn)行新的匹配。因此，使用自上而下分析法必須消除文法的左遞歸性。對文法中一切左遞歸的消除要求文法中不含回路即無A A的推導(dǎo)。