消除左遞歸-編譯原理實(shí)驗(yàn)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：消除左遞歸_實(shí)驗(yàn)時(shí)間：2015-05-27_院 系：管理信息工程學(xué)院_班 級(jí)：12級(jí)計(jì)算機(jī)科學(xué)技術(shù)_學(xué) 號(hào)：2_姓 名：王博一_1、 實(shí)驗(yàn)?zāi)康模豪斫釲L(1)文法中消除左遞歸的原理2、 實(shí)驗(yàn)原理：1直接左遞歸的消除消除產(chǎn)生式中的直接左遞歸是比較容易的。例如假設(shè)非終結(jié)符P的規(guī)則為：PP / 其中，是不以P開頭的符號(hào)串。那么，我們可以把P的規(guī)則改寫為如下的非直接左遞歸形式： PP PP / 這兩條規(guī)則和原來的規(guī)則是等價(jià)的，即兩種形式從P推出的符號(hào)串是相同的。 設(shè)有簡(jiǎn)單表達(dá)式文法GE： EE+T/ T TT*F/ F F（E）/ I經(jīng)消除直接左遞歸

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

3、Rb/ bRSa/ a雖不具有左遞歸，但S、Q、R都是左遞歸的，因?yàn)榻?jīng)過若干次推導(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)生式改寫成A

4、i1 /2 /k 其中Aj1 /2 /k是關(guān)于的Aj全部規(guī)則； 消除Ai規(guī)則中的直接左遞歸； （3） 化簡(jiǎn)由（2）所得到的文法，即去掉多余的規(guī)則。利用此算法可以將上述文法進(jìn)行改寫，來消除左遞歸。首先，令非終結(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'/ cS'S abcS'/ QSab/ ab/ bRSa/ a可以看到從文法開

5、始符號(hào)S出發(fā)，永遠(yuǎn)無法達(dá)到Q和R，所以關(guān)于Q和R的規(guī)則是多余的，將其刪除并化簡(jiǎn)，最后得到文法GS為：SabcS'/ bcS/ cS'S' abcS'/ 當(dāng)然如果對(duì)文法非終結(jié)符排序的不同，最后得到的文法在形式上可能不一樣，但它們都是等價(jià)的。例如，如果對(duì)上述非終結(jié)符排序選為S、Q、R，那么最后得到的文法GR為： RbcaR'/ caR'/ aRR' bcaR'/ 容易證明上述兩個(gè)文法是等價(jià)的。3、 實(shí)驗(yàn)內(nèi)容：分析見下圖圖（a）變量說明圖（b）直接左遞歸分析圖圖（c）間接左遞歸分析圖用C語言實(shí)現(xiàn)定義四個(gè)函數(shù)int direct(char

6、 PNN); /直接左遞歸函數(shù)int indirect(char PNN); /間接左遞歸函數(shù)void directRemove(char PNN); /消除直接左遞歸函數(shù)void indirectRemove(char PNN); /消除間接左遞歸函數(shù)并在main函數(shù)中依次調(diào)用4、 代碼實(shí)現(xiàn)#include "stdafx.h"#include<stdio.h>#include<string.h>#define N 20char PNN; /規(guī)則集char QN; /規(guī)則集,存放間接左遞歸消除后的部分規(guī)則char RNN; /用來存放規(guī)則的初始值i

7、nt r; /實(shí)際輸入的規(guī)則的個(gè)數(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;i<r;i+) if(Pi3=Pi0) /右部字符中有與左部相同的符號(hào) flag+; break; if(flag>0)printf("經(jīng)判斷該文法

8、含有直接左遞歸!n");return 1; /屬于直接接左遞歸 else return 0; /不屬于直接左遞歸int indirect(char PNN) /定義間接左遞歸函數(shù) int flag=0; for(int i=0;i<r;i+)for(int k=1;k<r;k+)if(Pi+k0=Pi3) flag+; break; if(flag>0) break; if(flag>0) printf("經(jīng)判斷該文法含有間接左遞歸!n");return 2; /屬于間接左遞歸 else return 0; /不屬于間接左遞歸void di

9、rectRemove(char PNN) /定義消除直接左遞歸的函數(shù)int j=4;for(int i=0;i<r;i+)if(Pi3=Pi0) Pi3=Pi2; Pi2=Pi1; Pi1=''' while(Pij!=0) j+;Pij=Pi0;Pij+1='''for(int k=0;k<4;k+) /包含空的一條規(guī)則 Prk=Pik;Prk='*'elsej=3;while(Pij!=0) j+;Pij=Pi0;Pij+1=''' printf("n消除直接左遞歸后的文法為:n&

10、quot;);printf("n");printf("(*代表)n");printf("n");for(int t=0;t<r+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;i<r;i+)flag=0;for(int k=0;k<=e;k+)if(Pi0!=Qk)flag+;if(f

11、lag=(e+1)e+;Qe=Pi0; int g=0;for(int j=0;j<e;j+)int number=0;for(int z=0;z<r;z+)if(Pz0=Qj)number+; /統(tǒng)計(jì)相同左部的規(guī)則個(gè)數(shù) if(number>1) copy+; /如果有相同左部則規(guī)則總數(shù)加一 for(i=0;i<r;i+) for(int k=1;k<r;k+) if(Pi0=Pi+k3)&&(flag1=0) for(int y=0;Pi+ky!=0;y+)Rgy=Pi+ky; /把原值保留flag1=1; int m=3;while(Pim!=

12、0) /統(tǒng)計(jì)替換字符的個(gè)數(shù)為m-1-2m+;int t=m-3;int n=4;while(Pi+kn!=0) /統(tǒng)計(jì)被替換規(guī)則中非終結(jié)符的個(gè)數(shù)為n-4n+;for(int s=n-1;s>=4;s-)Pi+ks+t-1=Pi+ks;for(int u=3;u<3+t;u+)Pi+ku=Piu;break;else if(Pi0=Rg3)&&(flag1=1) for(int y=0;Rgy!=0;y+) Pcopy-1y=Rgy;int m=3;while(Pim!=0) /統(tǒng)計(jì)替換字符的個(gè)數(shù)為m-1-2m+;int t=m-3;int n=4;while(Pco

13、py-1n!=0) /統(tǒng)計(jì)被替換規(guī)則中非終結(jié)符的個(gè)數(shù)為n-4n+;for(int s=n-1;s>=4;s-)Pcopy-1s+t-1=Pcopy-1s;for(int u=3;u<3+t;u+)Pcopy-1u=Piu;break; flag1=0;g+;printf("首次消除間接左遞歸后的直接左遞歸文法為:n");for(int t=0;t<copy;t+) printf("%sn",Pt);printf("n"); for(i=0;i<copy;i+)if(Pi0=Qe)if(Pi3=Pi0) Pi3=

14、Pi2;Pi2=Pi1;Pi1='''while(Pij!=0)j+;Pij=Pi0;Pij+1='''for(int k=0;k<4;k+) /包含空的一條規(guī)則Pcopyk=Pik;Pcopyk='*'elsej=3;while(Pij!=0) j+;Pij=Pi0;Pij+1=''' printf("再次消除直接左遞歸后的文法為:n");printf("n");printf("(*代表)n");printf("n");

15、for(t=0;t<=copy;t+) printf("%sn",Pt);void main() printf("請(qǐng)輸入上下文無關(guān)的文法規(guī)則P的個(gè)數(shù): "); scanf("%d/n",&r); printf("n"); printf("請(qǐng)輸入各條規(guī)則，規(guī)則的左部跟右部用->連接，規(guī)則間用空格隔開"); printf("n"); for(int k=0;k<r;k+)scanf("%s",Pk); printf("n");printf("即輸入的文法規(guī)則為:n&qu