編譯基本知識(shí)實(shí)驗(yàn)-消除文法的左遞歸

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

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

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

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

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

6、n ； i+ )for(j = 1; j=i - 1; j+ )把形如Af Aj 丫的產(chǎn)生式改寫(xiě)成AiSl 丫 / 2 丫 / k 丫 其中Aj7i / 2 /k是關(guān)于的Aj全部規(guī)則;消除Ai規(guī)則中的直接左遞歸;化簡(jiǎn)由（ 2）所得到的文法，即去掉多余的規(guī)則。利用此算法可以將上述文法進(jìn)行改寫(xiě)，來(lái)消除左遞歸。注意事項(xiàng)：指明是否存在左遞歸， 以及左遞歸的類(lèi)型。 對(duì)于直接左遞歸， 可將其改為直接右遞歸;對(duì)于間接左遞歸（也稱(chēng)文法左遞歸） ，則應(yīng)按照算法給出非終結(jié)符不 同排列的等價(jià)的消除左遞歸后的文法。（應(yīng)該有n!種）4.代碼實(shí)現(xiàn)（ C 語(yǔ)言）：#include stdafx.h #include #in

7、clude #define N 20int r;/ 實(shí)際輸入的規(guī)則的個(gè)數(shù)char PNN;/ 規(guī)則集char QN;/ 規(guī)則集 ,存放間接左遞歸消除后的部分規(guī)則char RNN;/ 用來(lái)存放規(guī)則的初始值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)

8、printf（ 經(jīng)判斷該文法含有直接左遞歸 !n）;return 1;/ 屬于直接接左遞歸elsereturn 0;/ 不屬于直接左遞歸int indirect(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;/ 屬于間接左遞歸elsereturn 0;/ 不屬于間接左遞歸void directRemove(char PNN)/ 定義消除直接左遞歸的函數(shù)int j=4;for(int i=0;ir;i+)if(Pi3

9、=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)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=

10、r;int e=0;Qe=Pe0;/ 統(tǒng)計(jì)規(guī)則中不同的左部for(int z=0;zr;z+)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 g=0;for(int j=0;j1)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;u3+t;u+)Pi+ku=Piu;break;else if(Pi0=Rg3)&(flag1=1)for(int y=0;Rg

11、y!=0;y+)Pcopy-1y=Rgy;int m=3;for(int u=3;u=4;s-)Pcopy-1s+t-1=Pcopy-1s;Pcopy-1u=Piu;break;flag1=0;g+;printf（ 首次消除間接左遞歸后的直接左遞歸文法為 :n）;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ī)則Pcop

12、yk=Pik;Pcopyk=*;elsej=3;while(Pij!=0)j+;Pij=Pi0;Pij+1=;printf（ 再次消除直接左遞歸后的文法為 :n）;printf(n);printf(* 代表 )n);printf(n);printf(%sn,Pt);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;kSa S-Jb即輸入的文法規(guī)則為：S-EaK-b經(jīng)判斷該文法含有直番左遞歸.悄除S接左遞歸后的文注為:骨-朋AMS-s一*PrcsH diy hey tv vviH inue消除文法間接左遞歸實(shí)例1如下:謔輸入上T文無(wú)關(guān)的文法規(guī)則F的T就:4謹(jǐn)輸入&雜規(guī)則h規(guī)則的左部跟占部