編譯原理實(shí)驗(yàn)：消除文法的左遞歸

1、編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱:消除文法的左遞歸實(shí)驗(yàn)時(shí)間 ：2015/5/28院系：管理與信息工程學(xué)院班級(jí) ：12級(jí)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)號(hào)：4姓名 ：劉楊凡1.實(shí)驗(yàn)?zāi)康模狠斎耄喝我獾纳舷挛臒o(wú)關(guān)文法。輸出：消除了左遞歸的等價(jià)文法。2.實(shí)驗(yàn)原理：1直接左遞歸的消除假設(shè)非終結(jié)符P的規(guī)則為：PP / 其中，是不以P開(kāi)頭的符號(hào)串。那么，我們可以把P的規(guī)則改寫為如下的非直接左遞歸形式： PP PP / 這兩條規(guī)則和原來(lái)的規(guī)則是等價(jià)的，即兩種形式從P推出的符號(hào)串是相同的。 設(shè)有簡(jiǎn)單表達(dá)式文法GE： EE+T/ T TT*F/ F F（E）/ I經(jīng)消除直接左遞歸后得到如下文法： ETE E +TE/ TFTT *FT

2、/ F（E）/ I考慮更一般的情況，假定關(guān)于非終結(jié)符P的規(guī)則為PP1 / P2 / Pn / 1 / 2 /m其中，i（I1，2，n）都不為，而每個(gè)j（j1，2，m）都不以P開(kāi)頭，將上述規(guī)則改寫為如下形式即可消除P的直接左遞歸：P1 P / 2 P /m PP 1P / 2 P / n P /2間接左遞歸的消除直接左遞歸見(jiàn)諸于表面，利用以上的方法可以很容易將其消除，即把直接左遞歸改寫成直接右遞歸。然而文法表面上不存在左遞歸并不意味著該文法就不存在左遞歸了。有些文法雖然表面上不存在左遞歸，但卻隱藏著左遞歸。例如，設(shè)有文法GS：SQc/ cQRb/ bRSa/ a雖不具有左遞歸，但S、Q、R都是左

3、遞歸的，因?yàn)榻?jīng)過(guò)若干次推導(dǎo)有SQcRbcSabcQRbSabQcabRSaQcaRbca就顯現(xiàn)出其左遞歸性了，這就是間接左遞歸文法。消除間接左遞歸的方法是，把間接左遞歸文法改寫為直接左遞歸文法，然后用消除直接左遞歸的方法改寫文法。如果一個(gè)文法不含有回路，即形如PP的推導(dǎo)，也不含有以為右部的產(chǎn)生式，那么就可以采用下述算法消除文法的所有左遞歸。消除左遞歸算法：（1） 把文法G的所有非終結(jié)符按任一順序排列，例如，A1，A2，An。（2） for （i1；i=n；i+）for （j1；j=i1；j+）把形如AiAj的產(chǎn)生式改寫成Ai1 /2 /k 其中Aj1 /2 /k是關(guān)于的Aj全部規(guī)則； 消除Ai

4、規(guī)則中的直接左遞歸； （3） 化簡(jiǎn)由（2）所得到的文法，即去掉多余的規(guī)則。利用此算法可以將上述文法進(jìn)行改寫，來(lái)消除左遞歸。首先，令非終結(jié)符的排序?yàn)镽、Q、S。對(duì)于R，不存在直接左遞歸。把R代入到Q中的相關(guān)規(guī)則中，則Q的規(guī)則變?yōu)镼Sab/ ab/ b。代換后的Q不含有直接左遞歸，將其代入S，S的規(guī)則變?yōu)镾Sabc/ abc/ bc/ c。此時(shí)，S存在直接左遞歸。在消除了S的直接左遞歸后，得到整個(gè)文法為：SabcS/ bcS/ cSS abcS/ QSab/ ab/ bRSa/ a可以看到從文法開(kāi)始符號(hào)S出發(fā)，永遠(yuǎn)無(wú)法達(dá)到Q和R，所以關(guān)于Q和R的規(guī)則是多余的，將其刪除并化簡(jiǎn)，最后得到文法GS為：S

5、abcS/ bcS/ cSS abcS/ 當(dāng)然如果對(duì)文法非終結(jié)符排序的不同，最后得到的文法在形式上可能不一樣，但它們都是等價(jià)的。例如，如果對(duì)上述非終結(jié)符排序選為S、Q、R，那么最后得到的文法GR為： RbcaR/ caR/ aRR bcaR/ 容易證明上述兩個(gè)文法是等價(jià)的。3.實(shí)驗(yàn)內(nèi)容：消除左遞歸算法：（4） 把文法G的所有非終結(jié)符按任一順序排列，例如，A1，A2，An。（5） for （i1；i=n；i+）for （j1；j=i1；j+）把形如AiAj的產(chǎn)生式改寫成Ai1 /2 /k其中Aj1 /2 /k是關(guān)于的Aj全部規(guī)則；消除Ai規(guī)則中的直接左遞歸；（6） 化簡(jiǎn)由（2）所得到的文法，即去

6、掉多余的規(guī)則。利用此算法可以將上述文法進(jìn)行改寫，來(lái)消除左遞歸。注意事項(xiàng)：指明是否存在左遞歸，以及左遞歸的類型。對(duì)于直接左遞歸，可將其改為直接右遞歸；對(duì)于間接左遞歸（也稱文法左遞歸），則應(yīng)按照算法給出非終結(jié)符不同排列的等價(jià)的消除左遞歸后的文法。（應(yīng)該有n！種）4.代碼實(shí)現(xiàn)（C語(yǔ)言）：#include stdafx.h#include#include#define N 20char PNN; /規(guī)則集char QN; /規(guī)則集,存放間接左遞歸消除后的部分規(guī)則char RNN; /用來(lái)存放規(guī)則的初始值int r; /實(shí)際輸入的規(guī)則的個(gè)數(shù)int direct(char PNN); /直接左遞歸函數(shù)in

7、t 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 indirect(char PNN) /定義間接左遞歸函數(shù) int flag=0; for(int i=0;ir;i+

8、)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=0;k4;k+) /包含空的一條規(guī)則 Prk=Pik;Prk=*;elsej=3;while(Pij!=0)

9、 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)計(jì)規(guī)則中不同的左部 for(int i=1;ir;i+)flag=0;for(int k=0;k=e;k+)if(Pi0!=Qk)flag+;if(flag=(e+1)e+;Qe=Pi0; int

10、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);for(int t=0;tcopy;t+) printf(%sn,Pt);printf(n); for(i=

11、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ī)則間用空格隔開(kāi)); printf(n); for(int k=0;kr;k+)scanf(%s,Pk); printf(n);printf(即輸入的文法規(guī)則為:n); for(k=0;kr;k+)