消除左遞歸實(shí)驗(yàn)報(bào)告材料

1、編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱 消除文法左遞歸實(shí)驗(yàn)時(shí)間2014年12月12日院系軟件工程班級(jí)軟件工程（2）班學(xué)號(hào)E01214215翼實(shí)驗(yàn)?zāi)康模狠斎耄喝我獾纳舷挛臒o(wú)關(guān)文法。輸出：消除了左遞歸的等價(jià)文法。實(shí)驗(yàn)原理：1直接左遞歸的消除消除產(chǎn)生式中的直接左遞歸是比較容易的。例如假設(shè)非終結(jié)符P的規(guī)則為P Pa / B其中，B是不以P開(kāi)頭的符號(hào)串。那么，我們可以把 P的規(guī)則改寫(xiě)為如下的非 直接左遞歸形式：PB P'P'a P' /£這兩條規(guī)則和原來(lái)的規(guī)則是等價(jià)的，即兩種形式從P推出的符號(hào)串是相同的。設(shè)有簡(jiǎn)單表達(dá)式文法GE:E E+T/ TT T*F/ FF ( E) / I經(jīng)消

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

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

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

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

6、bcS'/ bcS ' / cS'S' f abcS'/ £當(dāng)然如果對(duì)文法非終結(jié)符排序的不同，最后得到的文法在形式上可能不一 樣，但它們都是等價(jià)的。例如，如果對(duì)上述非終結(jié)符排序選為S、Q R,那么最后得到的文法 GR為： R f bcaR'/ caR'/ aR 'R' f bcaR'/ £容易證明上述兩個(gè)文法是等價(jià)的。實(shí)驗(yàn)容：指明是否存在左遞歸，以及左遞歸的類型。對(duì)于直接左遞歸，可將其改為直 接右遞歸；對(duì)于間接左遞歸(也稱文法左遞歸)，則應(yīng)按照算法給出非終結(jié)符不 同排列的等價(jià)的消除左遞歸后的文法

7、。(應(yīng)該有 n!種)實(shí)驗(yàn)代碼與結(jié)果：#i nclude<stdio.h> #in clude<stdlib.h> #i nclude<stri ng.h> #defi ne N 20char PNN;/ 存放文法char QN;/存放非終結(jié)符char RNN;/存放含有間接左遞歸的產(chǎn)生式char strNN, str1NN;int spN; /標(biāo)記無(wú)用的產(chǎn)生式int r , count=0,count1=0;int direct(char PNN);/ 判斷直接左遞歸int indirect(char PNN);/ 判斷間接左遞歸void directRem

8、ove(char PNN); void in directRemove(char PNN); void perm(char strNN, i nt i, i nt n);/消除直接左遞歸/消除間接左遞歸/實(shí)現(xiàn)全排列int main()printf("請(qǐng)輸入文法P產(chǎn)生式的個(gè)數(shù):");sca nf("%d/n",&r);printf("請(qǐng)輸入各條產(chǎn)生式，產(chǎn)生式的左部跟右部用-> 連接:n");for(int k=O;k<r;k+)sca nf("%s",Pk);if(strle n(Pk)=4) s

9、trcpy(str1cou nt1+,Pk);elsestrcpy(strcou nt+,Pk);if(direct(P)=1)directRemove(P);else if(in direct(P)=2)perm(str , 0, count-1);elseprintf("經(jīng)判斷該文法不含有左遞歸!n");return 0; int direct(char PNN) int flag=0;for(i nt i=O;i<r;i+)if(Pi3=Pi0)flag+; break;if(flag>0)printf("經(jīng)判斷該文法含有直接左遞歸 return

10、 1;elsereturn 0;int indirect(char PNN)int flag=0;for(i nt i=0;i<r;i+)for(i nt k=1;k<r;k+)if(Pi+k0=Pi3)flag+; break;if(flag>0) break;if(flag>0)printf("經(jīng)判斷該文法含有間接左遞歸 return 2;elsereturn 0;!n");!n");void directRemove(char PNN)int k,j=4;memset(sp,0,sizeof(sp);for(i nt i=0;i<

11、;r;i+)if(Pi3=Pi0)Pi3=Pi2;Pi2=Pi1; Pi1=''' while(Pij!=0) j+;Pij=Pi0;Pij+1='''spi=1; for(k=0;k<4;k+) Prk=Pik;Prk='$' spr=1;elsej=3; while(Pij!=0)j+;Pij=Pi0;Pij+1=''' spi=1;prin tf("n消除直接左遞歸后的文法為:n");for(i nt t=0;t< r+1;t+)if(spt=1)prin tf(&qu

12、ot;%sn",Pt);void indirectRemove(char PNN)int flag,flag1=0,r仁r;int i,j,k,t,e=0,g=0;Qe=Pe0;for(i=1;i<r;i+)int flag=O;for(i nt k=O;k<=e;k+)if(PiO!=Qk) flag+;if(flag=(e+1)e+;Qe=PiO;prin tf("n非終結(jié)符序列為：sn", Q);for(j=0;j<e;j+)int nu mber=0;for(i nt z=0;z<r;z+)if(Pz0=Qj)nu mber+;if

13、(nu mber>1)r1+;for(i=0;i<r;i+)for(k=1;k<r;k+)if(Pi0=Pi+k3)&&(flag 仁=0)for(i nt y=0;Pi+ky!=0;y+)Rg y=Pi+ky;flag仁1;int m=3;while(Pim!=0)m+;int t=m-3;int n=4;while(Pi+k n!=0)n+;for(i nt s=n-1;s>=4;s-) Pi+ks+t-1=Pi+ks;for(i nt u=3;u<3+t;u+)Pi+ku=Piu;break;else if(Pi0=R g 3)&&a

14、mp;(flag1=1) for(i nt y=O;R gy!=O;y+) P-iy=R g y; int m=3;while(Pim!=O) m+;int t=m-3;int n=4;while(Pr1-1 n!=0) n+;for(i nt s=n-1;s>=4;s-) Pr1-1s+t-1=Pr1-1s;for(i nt u=3;u<3+t;u+)Pr1-1u=Piu; break;flag 仁0;g+;memset(sp,0,sizeof(sp);for(i=0;i<r1;i+)if(Pi0=Qe)if(Pi3=Pi0)Pi3=Pi2;Pi2=Pi1; Pi1=

15、9;'' while(Pij!=0) j+;Pij=Pi0;Pij+1=''' spi=1; for(k=0;k<4;k+)Pr1k=Pik;Pr1k='$' spr1=1;elsej=3;while(Pij!=O)j+；Pij=PiO； Pij+1='''； spi=1;printf("消除間接左遞歸后的文法為:n");for(t=0;t<=r1;t+)if(spt=1)prin tf("%sn",Pt);void perm(char strNN, i nt i, i nt n)int k=0,j=0;char tempN;if(i = n)memset(P , 0, sizeof(P); while(k<co unt)strcpy(Pk, strk); k+;while(kvr)strcpy(Pk, str1k-cou nt); k+;in directRemove(P);elsefor(j=i;j<=n ;j+)strcpy(temp, strj); strcpy(strj, stri); strcpy(stri, temp); perm(str , i+1, n); strcpy(temp, strj);strcpy