消除文法的左递归实验

1、编译原理实验报告实验名称消除文法的左递归实验时间院系 班级 学号 姓名叮叮小文库1. 试验目的掌握和理解消除左递归(包括直接左递归和间接左递归)在构建LL(1)文法的作用和目的掌握消除左递归(包括直接左递归和间接左递归)的方法和步骤。写出对于输入任意的上下文无关文法可以输出消除了左递归的等价文法。2. 实验原理直接左递归的消除消除产生式中的直接左递归是比较容易的。例如假设非终结符P的规则为P Pa/ B其中，B是不以P开头的符号串。那么，我们可以把 P的规则改写为如下的非直接左递归形式：P尸P P 考虑更一般的情况，假定关于非终结符 P的规则为P P a / P o2 / / P an / 3

2、1 / 32 / / pm其中，a (I = 1, 2,，n)都不为而每个pj (j = 1, 2,，m) 都不以P开头，将上述规则改写为如下形式即可消除 P的直接左递归：P pl P/ 32 P/pm PP 01P / a P/ an P/间接左递归的消除直接左递归见诸于表面，利用以上的方法可以很容易将其消除, 即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并 不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递 归，但却隐藏着左递归。消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。消除左递归算法：把文法G的所有非终结符按

3、任一顺序排列，例如，A1 , A2，,An。for(i = 1；iv=n;i+)for(j = 1；j=i -1； j+) 把形如Ai f Aj 丫的产生式改写成 Ai f 81 y/ 2 丫/ ck 丫其中Aj f 81 / 32 /8是关于的Aj全部规则；消除Ai规则中的直接左递归；化简由(2)所得到的文法，即去掉多余的规则。3.实验内容利用消除左递归算法上机了实现对于输入任意的上下文无关文法可以输出消除了左递归的等价文法。4.实验心得通过本次试验更加清晰的理解了消除左递归在构建LL(1)文法的重要作用，以及如何的消除文法中的左递归。在本次试验中原本想用Pf Pal |Pa2 |Pa |B

4、1 |超|师这种相同左部的产生式右部用或连所以只有分开书接起来形式来消除左递归但是在实现上不是很容易， 写利用消除左递归的算法来实现.5.实验代码与结果源代码(C)#in clude#in cludestruct Node/定义产生式结构char left20;产生式左部char right50;产生式右部int flags;P30；int count=O;产生式数量void creat()int i;printf(输入产生式数量：”)；scan f(%d,&count);for(i=0;ico un t;i+)flushall();printf(输入第%d条产生式的左部:,i+1);gets

5、(Pi.left);flushall();prin tf(n ”);printf(输入第%d条产生式的右部:,i+1);gets(Pi.right);flushall();prin tf(n ”);Pi.flags=0;printf( *n);printf(你输入的产生式是:n);for(i=0;i%sn,Pi.left,Pi.right);void Replace(char *ch1,char ch220)int i;char ch320; strcpy(ch3,ch2);for(i=0;i(i nt)strle n( ch3);i+)ch3i=ch3i+1; strcat(ch1,ch3)

6、;void Sort(char *ch1,char ch22)int i;for(i=0;i(i nt)strle n(ch1);i+) ch1i=ch1i+1;strcat(ch1,ch2);void Analysis()/消除间接左递归int i,j,flags=0;char ch50;int num=co unt;for(i=0;i nu m;i+)flags=0;for(j=0;ji;j+)if(Pi.rightO=PjeftO)strcpy(ch,Pj.right); strcpy(Pcou nt.left,Pi.left); Replace(ch,Pi.right); strcpy

7、(Pco un t.right,ch); Pcou nt.flags=0;flags=1;coun t+; if(flags=1)Pi.flags=1;void Analysis1()消除直接左递归int i,j;char ch50;char chx2;int num=co unt;int flagsl;strcpy(chx,*1);for(i=0;inum;i+)消除直接左递归flags 1=0;if(Pi.flags=0)if(Pi.left0=Pi.right0)flags1=1;if(flags1=1)chxO=Pi.leftO;strcpy(Pco unt.l eft,chx);st

8、rcpy(ch,Pi.right);Sort(ch,chx);strcpy(Pco un t.right,ch);Pcou nt.flags=0;Pi.flags=1;coun t+;for(j=0;j nu m;j+)if(j!=i&Pj.leftO!=Pj.rightO&Pj.flags=0&Pj.leftO=Pi.leftO)Pcou nt.leftO=Pi.leftO;strcpy(Pco un t.right,strcat(Pj.right,chx);Pcou nt.flags=0;Pj.flags=1;coun t+;strcpy(Pco unt.l eft,chx);strcpy(Pcount.right,e );Pcou nt.flags=0;coun t+;voi