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

1、編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱(chēng)消除文法的左遞歸實(shí)驗(yàn)時(shí)間2010.11.1院系 計(jì)算機(jī)科學(xué)與技術(shù)班級(jí) 20081. 試驗(yàn)?zāi)康妮斎耄喝我獾纳舷挛臒o(wú)關(guān)文法。輸出：消除了左遞歸的等價(jià)文法。2. 實(shí)驗(yàn)原理1 直接左遞歸的消除消除產(chǎn)生式中的直接左遞歸是比較容易的。例如假設(shè)非終結(jié)符P的規(guī)則為P Pa / B其中，B是不以P開(kāi)頭的符號(hào)串。那么，我們可以把 P的規(guī)則改寫(xiě)為如下的非直 接左遞歸形式：PBPPaP/ &這兩條規(guī)則和原來(lái)的規(guī)則是等價(jià)的，即兩種形式從P推出的符號(hào)串是相同的。設(shè)有簡(jiǎn)單表達(dá)式文法GE:E E+T/ TTT*F/ F (E) / I經(jīng)消除直接左遞歸后得到如下文法：ETEE+TE / &T FTT*F

2、T / &F( E) / I考慮更一般的情況，假定關(guān)于非終結(jié)符 P的規(guī)則為P P al / P a2 / / P an / 沏 / 礎(chǔ) / / j3m其中，ai (1= 1 , 2，n)都不為&,而每個(gè)Bj (j = 1, 2，m )都不以P 開(kāi)頭，將上述規(guī)則改寫(xiě)為如下形式即可消除 P的直接左遞歸：PB P / B P / Bm PP aiP / a2 P / / an P / 2 間接左遞歸的消除直接左遞歸見(jiàn)諸于表面，利用以上的方法可以很容易將其消除，即把直接左 遞歸改寫(xiě)成直接右遞歸。然而文法表面上不存在左遞歸并不意味著該文法就不存 在左遞歸了。有些文法雖然表面上不存在左遞歸，但卻隱藏著左遞

3、歸。例如，設(shè) 有文法GS:S Qc/ cQ Rb/ bRf Sa/ a雖不具有左遞歸，但S、Q、R都是左遞歸的，因?yàn)榻?jīng)過(guò)若干次推導(dǎo)有S Qc Rbc SabcQ Rb Sab QcabR Sa Qca Rbca就顯現(xiàn)出其左遞歸性了，這就是間接左遞歸文法。消除間接左遞歸的方法是，把間接左遞歸文法改寫(xiě)為直接左遞歸文法，然后用消除直接左遞歸的方法改寫(xiě)文法。如果一個(gè)文法不含有回路，即形如 P P的推導(dǎo)，也不含有以&為右部的產(chǎn)生式，那么就可以采用下述算法消除文法的所有左遞歸。消除左遞歸算法：(1) 把文法G的所有非終結(jié)符按任一順序排列，例如，Ai，A2，,An。(2) for (i = 1 ； i=n

4、； i+ )for (j = 1; j=i 1; j+ ) 把形如Aif Aj 丫的產(chǎn)生式改寫(xiě)成Aif1 丫 / 2 丫 / 6k 丫其中Ajf1 / 2 / 是關(guān)于的Aj全部規(guī)則；消除Ai規(guī)則中的直接左遞歸；(3) 化簡(jiǎn)由(2)所得到的文法，即去掉多余的規(guī)則。利用此算法可以將上述文法進(jìn)行改寫(xiě)，來(lái)消除左遞歸。首先，令非終結(jié)符的排序?yàn)?R、Q、S。對(duì)于R，不存在直接左遞歸。把 R代換后的Q不含有直接左遞歸，將其代入S, S的規(guī)則變?yōu)镾Sabc/ abc/ bc/ c。此時(shí)，S存在直接左遞歸。在消除了 S的直接左遞歸后，得到整個(gè)文法為：S abcS / bcS/ cSS abcS/ &Q Sab/

5、 ab/ bRSa/ a可以看到從文法開(kāi)始符號(hào) S出發(fā)，永遠(yuǎn)無(wú)法達(dá)到Q和R,所以關(guān)于Q和R 的規(guī)則是多余的，將其刪除并化簡(jiǎn)，最后得到文法 GS為：S abcS/ bcS / cSS abcS/ &當(dāng)然如果對(duì)文法非終結(jié)符排序的不同，最后得到的文法在形式上可能不一樣，但它們都是等價(jià)的。例如，如果對(duì)上述非終結(jié)符排序選為S、Q、R,那么最后得到的文法 GR為：R bcaR/ caR/ aR R bcaR/ 容易證明上述兩個(gè)文法是等價(jià)的。3.實(shí)驗(yàn)內(nèi)容消除左遞歸算法：(1)把文法G的所有非終結(jié)符按任一順序排列，例如，Al，A2,，An (2)for (i = 1 ； i=n ; i+ )for(j = 1

6、; j=i 1; j+ ) 把形如AiAj 丫的產(chǎn)生式改寫(xiě)成AifSl 丫 / 2 丫 / 6k 丫其中Aj1 / 2 / k是關(guān)于的Aj全部規(guī)則；消除Ai規(guī)則中的直接左遞歸；化簡(jiǎn)由（2）所得到的文法，即去掉多余的規(guī)則。利用此算法可以將上述文法進(jìn)行改寫(xiě)，來(lái)消除左遞歸4. 實(shí)驗(yàn)代碼/#i nclude stdafx.h#in clude#in cludeusing n amespace std;struct WF/定義一個(gè)產(chǎn)生式結(jié)構(gòu)體stri ng left; / 定義產(chǎn)生式的左部string right; / 定義產(chǎn)生式的右部;void Removin g(WF *p,char *q,i nt

7、 n ,i nt count) int coun t1= n;int flag=O;for(i nt i=O;i n;i+)判斷第一個(gè)非終結(jié)符是否存在直接左遞歸if(pieftO=qO)if(pi.leftO=pi.rightO)flag+;if(flag!=O)如果存在直接左遞歸則消除直接左遞歸for(i nt i=O;i n ;i+)if(pi.leftO=qO)if(pi.leftO=pi.rightO)stri ng str;str=pi.right.substr(1,i nt (pi.right.le ngth();stri ng temp=pi.left;stri ng temp仁

8、”;pi.left=temp+temp1;pi.right=st r+pi.left;elsestri ng temp=pi.left;stri ng temp仁”; temp=temp+temp1; pi.right=pi.right+temp;stri ng str=”;pcou nt1.left=p0.left0+str;pcou nt1.right=*; for( i=0;i = coun t;i+)for(i nt j=0;j i;j+)for(i nt g=0;g n; g+)if(qi=pgeft0)if(p g.right0=qj)for(int h=0;h n*n;h+)if

9、(ph.left0=qj&nt (ph.left.length()=1)stri ng str;str=pg.right.substr(1,i nt (pg.right.le ngth();p+cou nt1.left=p g.left;pco un t1.right=ph.right+str;pg.left=; pg.right=;for( i=0;i = coun t;i+)flag=0;for(int j=O;j n*n;j+) if(pjeftO=qi) if(pjeftO=pj.rightO) flag+;if(flag!=0)for(i nt j=0;j = n*n ;j+)if(

10、pj.left0=qi) if(pj.left0=pj.right0) stri ng str;str=pj.right.substr(1,i nt (pj.right.le ngth(); stri ng temp=pj.left;stri ng temp仁”;pj.left=temp+temp1; pj.right=str+pj.left;elsestri ng temp=pj.left;stri ng temp1=”;temp=temp+temp1; pj.right=pj.right+temp;stri ng str=”;p+co un t1 .l eft=qi+str;pcou nt

11、1.right=*;int Delete(WF *p,i nt n)return 0;int main() int i,j,flag=0,co un t=1, n;cout請(qǐng)輸入文法產(chǎn)生式個(gè)數(shù)n : n;WF *p=new WF50;cout請(qǐng)輸入文法的個(gè)產(chǎn)生式：endl;for(i=0;i pi.left;cout pi.right;coute ndl;coute ndl;cout即輸入的文法產(chǎn)生式為：e ndl;for(i=0;i n ;i+)coutvvpi.rightvve ndl;cout*“e ndl;char q20;對(duì)產(chǎn)生式的非終結(jié)符排序并存取在字符數(shù)組qqO=pO.leftO

12、;把產(chǎn)生式的第一個(gè)非終結(jié)符存入q中for(i=1;i n;i+)對(duì)非終結(jié)符排序并存取flag=O;for(j=0;ji;j+)if(pi.left=pj.left)flag+;if(flag=O)qcou nt+=pi.leftO;coun t-;Removi ng(p,q, n, cou nt);/調(diào)用消除遞歸子函數(shù)Delete(p ,n);/刪除無(wú)用產(chǎn)生式coutvv消除遞歸后的文法產(chǎn)生式為：endl;for(i=O;i = coun t;i+)for(i nt j=O;j = n*n ;j+)if( (pj.leftO=qi) & int (pj.left.le ngth()=1 )co

13、utvvpj.rightvve ndl;else con ti nue;for( j=O;j = n*n ;j+)if( (pjeftO=qi) & int (pj.left.length()=2 )coutvvpj.rightvve ndl;else con ti nue; return 0;5. 實(shí)驗(yàn)結(jié)果消除直接左遞歸:消除間接左遞歸:6. 實(shí)驗(yàn)心得一個(gè)文法是含有左遞歸的，如果存在非終結(jié)符P , P Pa含有左遞歸的文法將使上述的自上而下的分析過(guò)程陷入無(wú)限循環(huán)，即當(dāng)試圖用P去匹配輸入串時(shí)，就會(huì)出現(xiàn)在沒(méi)有吃進(jìn)任何輸入符號(hào)的情況下，又得重新 要求P去進(jìn)行新的匹配。因此，使用自上而下分析法必須消除文法的左遞歸性。對(duì)文法中一切左遞歸的消除要求文法中不含回路即無(wú) A A的推導(dǎo)。滿(mǎn)足這個(gè)要求