消除文法的左递归实验

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

2、1，2，n）都不为，而每个j（j1，2，m）都不以P开头，将上述规则改写为如下形式即可消除P的直接左递归：P1 P / 2 P /m PP 1P / 2 P / n P /间接左递归的消除直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递归，但却隐藏着左递归。消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。消除左递归算法：把文法G的所有非终结符按任一顺序排列，例如，A1，A2，An。for （i1；i<=n；i+）

3、for （j1；j<=i1；j+）把形如AiAj的产生式改写成Ai1 /2 /k 其中Aj1 /2 /k是关于的Aj全部规则； 消除Ai规则中的直接左递归； 化简由（2）所得到的文法，即去掉多余的规则。3.实验内容利用消除左递归算法上机了实现对于输入任意的上下文无关文法可以输出消除了左递归的等价文法。4.实验心得通过本次试验更加清晰的理解了消除左递归在构建LL(1)文法的重要作用，以及如何的消除文法中的左递归。在本次试验中原本想用PP1 |P2 |Pn |1 | 2 |m这种相同左部的产生式右部用或连接起来形式来消除左递归但是在实现上不是很容易，所以只有分开书写利用消除左递归的算法来实现

4、.5.实验代码与结果源代码（C）#include<stdio.h>#include<string.h>struct Node/定义产生式结构char left20;/产生式左部char right50;/产生式右部int flags;P30;int count=0;/产生式数量void creat()int i;printf("输入产生式数量:");scanf("%d",&count);for(i=0;i<count;i+)flushall();printf("输入第%d条产生式的左部:",i+1

5、);gets(Pi.left);flushall();printf("n");printf("输入第%d条产生式的右部:",i+1);gets(Pi.right);flushall();printf("n");Pi.flags=0;printf("*n");printf("你输入的产生式是:n");for(i=0;i<count;i+)printf("%s->%sn",Pi.left,Pi.right);void Replace(char *ch1,char ch

6、220)int i;char ch320;strcpy(ch3,ch2);for(i=0;i<(int)strlen(ch3);i+)ch3i=ch3i+1;strcat(ch1,ch3);void Sort(char *ch1,char ch22)int i;for(i=0;i<(int)strlen(ch1);i+)ch1i=ch1i+1;strcat(ch1,ch2);void Analysis()/消除间接左递归int i,j,flags=0;char ch50;int num=count;for(i=0;i<num;i+)flags=0;for(j=0;j<i

7、;j+)if(Pi.right0=Pj.left0)strcpy(ch,Pj.right);strcpy(Pcount.left,Pi.left);Replace(ch,Pi.right);strcpy(Pcount.right,ch);Pcount.flags=0;flags=1;count+;if(flags=1)Pi.flags=1;void Analysis1()/消除直接左递归int i,j;char ch50;char chx2;int num=count;int flags1;strcpy(chx,"*1");for(i=0;i<num;i+)/消除直接

8、左递归flags1=0;if(Pi.flags=0)if(Pi.left0=Pi.right0)flags1=1;if(flags1=1)chx0=Pi.left0;strcpy(Pcount.left,chx);strcpy(ch,Pi.right);Sort(ch,chx);strcpy(Pcount.right,ch);Pcount.flags=0;Pi.flags=1;count+;for(j=0;j<num;j+)if(j!=i&&Pj.left0!=Pj.right0&&Pj.flags=0&&Pj.left0=Pi.left0)Pcount.left0=Pi.left0;strcpy(Pcount.right,strcat(Pj.right,chx);Pcount.flags=0;Pj.flags=1;count+;strcpy(Pcount.left,chx);strcpy(Pcount.right,"");Pcount.flags=0;count+;void Display()int i;printf("消除递归后产生式为:n");for