消除文法的左遞歸實驗

1、編譯原理實驗報告實驗名稱消除文法的左遞歸實驗時間院系 班級 學號 姓名叮叮小文庫1. 試驗?zāi)康恼莆蘸屠斫庀筮f歸(包括直接左遞歸和間接左遞歸)在構(gòu)建LL(1)文法的作用和目的掌握消除左遞歸(包括直接左遞歸和間接左遞歸)的方法和步驟。寫出對于輸入任意的上下文無關(guān)文法可以輸出消除了左遞歸的等價文法。2. 實驗原理直接左遞歸的消除消除產(chǎn)生式中的直接左遞歸是比較容易的。例如假設(shè)非終結(jié)符P的規(guī)則為P Pa/ B其中，B是不以P開頭的符號串。那么，我們可以把 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)都不為而每個pj (j = 1, 2,，m) 都不以P開頭，將上述規(guī)則改寫為如下形式即可消除 P的直接左遞歸：P pl P/ 32 P/pm PP 01P / a P/ an P/間接左遞歸的消除直接左遞歸見諸于表面，利用以上的方法可以很容易將其消除, 即把直接左遞歸改寫成直接右遞歸。然而文法表面上不存在左遞歸并 不意味著該文法就不存在左遞歸了。有些文法雖然表面上不存在左遞 歸，但卻隱藏著左遞歸。消除間接左遞歸的方法是，把間接左遞歸文法改寫為直接左遞歸文法，然后用消除直接左遞歸的方法改寫文法。消除左遞歸算法：把文法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ī)則中的直接左遞歸；化簡由(2)所得到的文法，即去掉多余的規(guī)則。3.實驗內(nèi)容利用消除左遞歸算法上機了實現(xiàn)對于輸入任意的上下文無關(guān)文法可以輸出消除了左遞歸的等價文法。4.實驗心得通過本次試驗更加清晰的理解了消除左遞歸在構(gòu)建LL(1)文法的重要作用，以及如何的消除文法中的左遞歸。在本次試驗中原本想用Pf Pal |Pa2 |Pa |B

4、1 |超|師這種相同左部的產(chǎn)生式右部用或連所以只有分開書接起來形式來消除左遞歸但是在實現(xiàn)上不是很容易， 寫利用消除左遞歸的算法來實現(xiàn).5.實驗代碼與結(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