編譯原理實驗二消除文法的左遞歸

1、編譯原理實驗報告實驗名稱 消除文法的左遞歸 實驗時間 2013年11月12日 院系 計算機(jī)科學(xué)與電子技術(shù)系 班級 11計算機(jī)軟件 學(xué)號 JV114001 JV114095 JP114065 姓名 唐茹 韓強(qiáng)強(qiáng) 徐思維 1.試驗?zāi)康模狠斎耄喝我獾纳舷挛臒o關(guān)文法。輸出：消除了左遞歸的等價文法。2.實驗原理：1直接左遞歸的消除消除產(chǎn)生式中的直接左遞歸是比較容易的。例如假設(shè)非終結(jié)符P的規(guī)則為：PP / 其中，是不以P開頭的符號串。那么，我們可以把P的規(guī)則改寫為如下的非直接左遞歸形式： PP PP / 這兩條規(guī)則和原來的規(guī)則是等價的，即兩種形式從P推出的符號串是相同的。 設(shè)有簡單表達(dá)式文法GE： EE+

2、T/ T TT*F/ F F（E）/ I經(jīng)消除直接左遞歸后得到如下文法： ETE E +TE/ TFTT *FT/ F（E）/ I考慮更一般的情況，假定關(guān)于非終結(jié)符P的規(guī)則為PP1 / P2 / Pn / 1 / 2 /m其中，i（I1，2，n）都不為，而每個j（j1，2，m）都不以P開頭，將上述規(guī)則改寫為如下形式即可消除P的直接左遞歸：P1 P / 2 P /m PP 1P / 2 P / n P /2間接左遞歸的消除直接左遞歸見諸于表面，利用以上的方法可以很容易將其消除，即把直接左遞歸改寫成直接右遞歸。然而文法表面上不存在左遞歸并不意味著該文法就不存在左遞歸了。有些文法雖然表面上不存在左遞

3、歸，但卻隱藏著左遞歸。例如，設(shè)有文法GS：SQc/ cQRb/ bRSa/ a雖不具有左遞歸，但S、Q、R都是左遞歸的，因為經(jīng)過若干次推導(dǎo)有SQcRbcSabcQRbSabQcabRSaQcaRbca就顯現(xiàn)出其左遞歸性了，這就是間接左遞歸文法。消除間接左遞歸的方法是，把間接左遞歸文法改寫為直接左遞歸文法，然后用消除直接左遞歸的方法改寫文法。如果一個文法不含有回路，即形如PP的推導(dǎo)，也不含有以為右部的產(chǎn)生式，那么就可以采用下述算法消除文法的所有左遞歸。消除左遞歸算法：（1） 把文法G的所有非終結(jié)符按任一順序排列，例如，A1，A2，An。（2） for （i1；i=n；i+）for （j1；j=i

4、1；j+）把形如AiAj的產(chǎn)生式改寫成Ai1 /2 /k 其中Aj1 /2 /k是關(guān)于的Aj全部規(guī)則； 消除Ai規(guī)則中的直接左遞歸； （3） 化簡由（2）所得到的文法，即去掉多余的規(guī)則。利用此算法可以將上述文法進(jìn)行改寫，來消除左遞歸。首先，令非終結(jié)符的排序為R、Q、S。對于R，不存在直接左遞歸。把R代入到Q中的相關(guān)規(guī)則中，則Q的規(guī)則變?yōu)镼Sab/ ab/ b。代換后的Q不含有直接左遞歸，將其代入S，S的規(guī)則變?yōu)镾Sabc/ abc/ bc/ c。此時，S存在直接左遞歸。在消除了S的直接左遞歸后，得到整個文法為：SabcS/ bcS/ cSS abcS/ QSab/ ab/ bRSa/ a可以看

5、到從文法開始符號S出發(fā)，永遠(yuǎn)無法達(dá)到Q和R，所以關(guān)于Q和R的規(guī)則是多余的，將其刪除并化簡，最后得到文法GS為：SabcS/ bcS/ cSS abcS/ 當(dāng)然如果對文法非終結(jié)符排序的不同，最后得到的文法在形式上可能不一樣，但它們都是等價的。例如，如果對上述非終結(jié)符排序選為S、Q、R，那么最后得到的文法GR為： RbcaR/ caR/ aRR bcaR/ 容易證明上述兩個文法是等價的。3.實驗內(nèi)容：消除左遞歸算法：（4） 把文法G的所有非終結(jié)符按任一順序排列，例如，A1，A2，An。（5） for （i1；i=n；i+）for （j1；j=i1；j+）把形如AiAj的產(chǎn)生式改寫成Ai1 /2 /

6、k其中Aj1 /2 /k是關(guān)于的Aj全部規(guī)則；消除Ai規(guī)則中的直接左遞歸；（6） 化簡由（2）所得到的文法，即去掉多余的規(guī)則。利用此算法可以將上述文法進(jìn)行改寫，來消除左遞歸。注意事項：指明是否存在左遞歸，以及左遞歸的類型。對于直接左遞歸，可將其改為直接右遞歸；對于間接左遞歸（也稱文法左遞歸），則應(yīng)按照算法給出非終結(jié)符不同排列的等價的消除左遞歸后的文法。（應(yīng)該有n！種）4.實驗代碼與結(jié)果：#include stdafx.h#include#include#define N 20char PNN; /規(guī)則集char QN; /規(guī)則集,存放間接左遞歸消除后的部分規(guī)則char RNN; /用來存放規(guī)則

7、的初始值int r; /實際輸入的規(guī)則的個數(shù)int direct(char PNN); /直接左遞歸函數(shù)int indirect(char PNN); /間接左遞歸函數(shù)void directRemove(char PNN); /消除直接左遞歸函數(shù)void indirectRemove(char PNN); /消除間接左遞歸函數(shù)int direct(char PNN) /定義直接左遞歸函數(shù) int flag=0; for(int i=0;i0)printf(經(jīng)判斷該文法含有直接左遞歸!n);return 1; /屬于直接接左遞歸 else return 0; /不屬于直接左遞歸int indir

8、ect(char PNN) /定義間接左遞歸函數(shù) int flag=0; for(int i=0;ir;i+)for(int k=1;k0) break; if(flag0) printf(經(jīng)判斷該文法含有間接左遞歸!n);return 2; /屬于間接左遞歸 else return 0; /不屬于間接左遞歸void directRemove(char PNN) /定義消除直接左遞歸的函數(shù)int j=4;for(int i=0;ir;i+)if(Pi3=Pi0) Pi3=Pi2; Pi2=Pi1; Pi1=; while(Pij!=0) j+;Pij=Pi0;Pij+1=;for(int k=

9、0;k4;k+) /包含空的一條規(guī)則 Prk=Pik;Prk=*;elsej=3;while(Pij!=0) j+;Pij=Pi0;Pij+1=; printf(n消除直接左遞歸后的文法為:n);printf(n);printf(*代表)n);printf(n);for(int t=0;tr+1;t+) printf(%sn,Pt);void indirectRemove(char PNN) /定義消除間接左遞歸的函數(shù) int flag,flag1=0,copy=r;int e=0; Qe=Pe0; /統(tǒng)計規(guī)則中不同的左部 for(int i=1;ir;i+)flag=0;for(int k=

10、0;k=e;k+)if(Pi0!=Qk)flag+;if(flag=(e+1)e+;Qe=Pi0; int g=0;for(int j=0;je;j+)int number=0;for(int z=0;z1) copy+; /如果有相同左部則規(guī)則總數(shù)加一 for(i=0;ir;i+) for(int k=1;k=4;s-)Pi+ks+t-1=Pi+ks;for(int u=3;u=4;s-)Pcopy-1s+t-1=Pcopy-1s;for(int u=3;u3+t;u+)Pcopy-1u=Piu;break; flag1=0;g+;printf(首次消除間接左遞歸后的直接左遞歸文法為:n);

11、for(int t=0;tcopy;t+) printf(%sn,Pt);printf(n); for(i=0;icopy;i+)if(Pi0=Qe)if(Pi3=Pi0) Pi3=Pi2;Pi2=Pi1;Pi1=;while(Pij!=0)j+;Pij=Pi0;Pij+1=;for(int k=0;k4;k+) /包含空的一條規(guī)則Pcopyk=Pik;Pcopyk=*;elsej=3;while(Pij!=0) j+;Pij=Pi0;Pij+1=; printf(再次消除直接左遞歸后的文法為:n);printf(n);printf(*代表)n);printf(n);for(t=0;t連接，規(guī)則間用空格隔開); printf(n); for(int k=0;kr;k+)scanf(%s,Pk); printf(n);printf(即輸入的文法規(guī)則為:n); for(k=0;kr;k+) printf(%sn,Pk); if(direct(P)=1) directRemove(P);else if(i