編譯基本知識實驗-消除文法的左遞歸

1、編譯原理實驗報告實驗名稱:消除文法的左遞歸實驗時間:2015/5/28院系：管理與信息工程學院班級:12級計算機科學與技術學號：201201020124姓名：劉楊凡1.實驗目的:輸入：任意的上下文無關文法。輸出：消除了左遞歸的等價文法。2.實驗原理:1 .直接左遞歸的消除假設非終結符P的規(guī)則為:其中，P是不以P開頭的符號串。那么，我們可以把 P的規(guī)則改寫為如下的非直PBP接左遞歸形式:Pa P/ 這兩條規(guī)則和原來的規(guī)則是等價的，即兩種形式從P推出的符號串是相同的。設有簡單表達式文法GE:E E+T/ TTT*F/ FFt( E) / I經消除直接左遞歸后得到如下文法：E+TE / TFTT*F

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

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

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

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

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

7、clude #define N 20int r;/ 實際輸入的規(guī)則的個數char PNN;/ 規(guī)則集char QN;/ 規(guī)則集 ,存放間接左遞歸消除后的部分規(guī)則char RNN;/ 用來存放規(guī)則的初始值int direct(char PNN);/ 直接左遞歸函數int indirect(char PNN);/ 間接左遞歸函數void directRemove(char PNN);/ 消除直接左遞歸函數void indirectRemove(char PNN);/ 消除間接左遞歸函數int direct(char PNN)/ 定義直接左遞歸函數int flag=0;for(int i=0;i0)

8、printf（ 經判斷該文法含有直接左遞歸 !n）;return 1;/ 屬于直接接左遞歸elsereturn 0;/ 不屬于直接左遞歸int indirect(char PNN)/ 定義間接左遞歸函數int flag=0;for(int i=0;ir;i+)for(int k=1;k0)break;if(flag0)printf（ 經判斷該文法含有間接左遞歸 !n）;return 2;/ 屬于間接左遞歸elsereturn 0;/ 不屬于間接左遞歸void directRemove(char PNN)/ 定義消除直接左遞歸的函數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)/ 定義消除間接左遞歸的函數int flag,flag1=0,copy=

10、r;int e=0;Qe=Pe0;/ 統(tǒng)計規(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ī)則總數加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ī)則間用空格隔開);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經判斷該文法含有直番左遞歸.悄除S接左遞歸后的文注為:骨-朋AMS-s一*PrcsH diy hey tv vviH inue消除文法間接左遞歸實例1如下:謔輸入上T文無關的文法規(guī)則F的T就:4謹輸入&雜規(guī)則h規(guī)則的左部跟占部