消除文法的左遞歸實(shí)驗(yàn)

1、編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱消除文法的左遞歸實(shí)驗(yàn)時(shí)間院系 班級(jí) 學(xué)號(hào) 姓名叮叮小文庫(kù)1. 試驗(yàn)?zāi)康恼莆蘸屠斫庀筮f歸(包括直接左遞歸和間接左遞歸)在構(gòu)建LL(1)文法的作用和目的掌握消除左遞歸(包括直接左遞歸和間接左遞歸)的方法和步驟。寫出對(duì)于輸入任意的上下文無(wú)關(guān)文法可以輸出消除了左遞歸的等價(jià)文法。2. 實(shí)驗(yàn)原理直接左遞歸的消除消除產(chǎn)生式中的直接左遞歸是比較容易的。例如假設(shè)非終結(jié)符P的規(guī)則為P Pa/ B其中，B是不以P開頭的符號(hào)串。那么，我們可以把 P的規(guī)則改寫為如下的非直接左遞歸形式：P尸P P 考慮更一般的情況，假定關(guān)于非終結(jié)符 P的規(guī)則為P P a / P o2 / / P an / 3

2、1 / 32 / / pm其中，a (I = 1, 2,，n)都不為而每個(gè)pj (j = 1, 2,，m) 都不以P開頭，將上述規(guī)則改寫為如下形式即可消除 P的直接左遞歸：P pl P/ 32 P/pm PP 01P / a P/ an P/間接左遞歸的消除直接左遞歸見(jiàn)諸于表面，利用以上的方法可以很容易將其消除, 即把直接左遞歸改寫成直接右遞歸。然而文法表面上不存在左遞歸并 不意味著該文法就不存在左遞歸了。有些文法雖然表面上不存在左遞 歸，但卻隱藏著左遞歸。消除間接左遞歸的方法是，把間接左遞歸文法改寫為直接左遞歸文法，然后用消除直接左遞歸的方法改寫文法。消除左遞歸算法：把文法G的所有非終結(jié)符按

3、任一順序排列，例如，A1 , A2，,An。for(i = 1；iv=n;i+)for(j = 1；j=i -1； j+) 把形如Ai f Aj 丫的產(chǎn)生式改寫成 Ai f 81 y/ 2 丫/ ck 丫其中Aj f 81 / 32 /8是關(guān)于的Aj全部規(guī)則；消除Ai規(guī)則中的直接左遞歸；化簡(jiǎn)由(2)所得到的文法，即去掉多余的規(guī)則。3.實(shí)驗(yàn)內(nèi)容利用消除左遞歸算法上機(jī)了實(shí)現(xiàn)對(duì)于輸入任意的上下文無(wú)關(guān)文法可以輸出消除了左遞歸的等價(jià)文法。4.實(shí)驗(yàn)心得通過(guò)本次試驗(yàn)更加清晰的理解了消除左遞歸在構(gòu)建LL(1)文法的重要作用，以及如何的消除文法中的左遞歸。在本次試驗(yàn)中原本想用Pf Pal |Pa2 |Pa |B

4、1 |超|師這種相同左部的產(chǎn)生式右部用或連所以只有分開書接起來(lái)形式來(lái)消除左遞歸但是在實(shí)現(xiàn)上不是很容易， 寫利用消除左遞歸的算法來(lái)實(shí)現(xiàn).5.實(shí)驗(yàn)代碼與結(jié)果源代碼(C)#in clude#in cludestruct Node/定義產(chǎn)生式結(jié)構(gòu)char left20;產(chǎn)生式左部char right50;產(chǎn)生式右部int flags;P30；int count=O;產(chǎn)生式數(shù)量void creat()int i;printf(輸入產(chǎn)生式數(shù)量：”)；scan f(%d,&count);for(i=0;ico un t;i+)flushall();printf(輸入第%d條產(chǎn)生式的左部:,i+1);gets

5、(Pi.left);flushall();prin tf(n ”);printf(輸入第%d條產(chǎn)生式的右部:,i+1);gets(Pi.right);flushall();prin tf(n ”);Pi.flags=0;printf( *n);printf(你輸入的產(chǎn)生式是:n);for(i=0;i%sn,Pi.left,Pi.right);void Replace(char *ch1,char ch220)int i;char ch320; strcpy(ch3,ch2);for(i=0;i(i nt)strle n( ch3);i+)ch3i=ch3i+1; strcat(ch1,ch3)

6、;void Sort(char *ch1,char ch22)int i;for(i=0;i(i nt)strle n(ch1);i+) ch1i=ch1i+1;strcat(ch1,ch2);void Analysis()/消除間接左遞歸int i,j,flags=0;char ch50;int num=co unt;for(i=0;i nu m;i+)flags=0;for(j=0;ji;j+)if(Pi.rightO=PjeftO)strcpy(ch,Pj.right); strcpy(Pcou nt.left,Pi.left); Replace(ch,Pi.right); strcpy

7、(Pco un t.right,ch); Pcou nt.flags=0;flags=1;coun t+; if(flags=1)Pi.flags=1;void Analysis1()消除直接左遞歸int i,j;char ch50;char chx2;int num=co unt;int flagsl;strcpy(chx,*1);for(i=0;inum;i+)消除直接左遞歸flags 1=0;if(Pi.flags=0)if(Pi.left0=Pi.right0)flags1=1;if(flags1=1)chxO=Pi.leftO;strcpy(Pco unt.l eft,chx);st

8、rcpy(ch,Pi.right);Sort(ch,chx);strcpy(Pco un t.right,ch);Pcou nt.flags=0;Pi.flags=1;coun t+;for(j=0;j nu m;j+)if(j!=i&Pj.leftO!=Pj.rightO&Pj.flags=0&Pj.leftO=Pi.leftO)Pcou nt.leftO=Pi.leftO;strcpy(Pco un t.right,strcat(Pj.right,chx);Pcou nt.flags=0;Pj.flags=1;coun t+;strcpy(Pco unt.l eft,chx);strcpy(Pcount.right,e );Pcou nt.flags=0;coun t+;voi