编译原理实验报告
实验名称消除文法的左递归
实验时间
院系
班级
学号
姓名
1.试验目的
♦掌握和理解消除左递归(包括直接左递归和间接左递归)在构建
LL(1)文法的作用和目的
♦掌握消除左递归(包括直接左递归和间接左递归)的方法和步骤。
♦写出对于输入任意的上下文无关文法可以输出消除了左递归的等
价文法。
2.实验原理
♦直接左递归的消除
{
strcpy(ch,P[j].right); strcpy(P[cou nt].left,P[i].left); Replace(ch,P[i].right); strcpy(P[co un t].right,ch); P[cou nt].flags=0;
flags=1;
coun t++;
}
} if(flags==1)P[i].flags=1;
{
if(P[i].left[0]==P[i].right[0])flags1=1;
}
if(flags1==1)
{
chx[O]=P[i].left[O];
strcpy(P[co unt].l eft,chx);
strcpy(ch,P[i].right);
Sort(ch,chx);
strcpy(P[co un t].right,ch);
strcat(ch1,ch2);
}
void Analysis()//消除间接左递归
{
int i,j,flags=0;
char ch[50];
int num=co unt;
for(i=0;i< nu m;i++)
{
flags=0;
for(j=0;j<i;j++)
{
if(P[i].right[O]==P[j]」eft[O])
gets(P[i].left);
flushall();
prin tf("\n”);
printf("输入第%d条产生式的右部:",i+1);
gets(P[i].right);
flushall();
prin tf("\n”);
P[i].flags=0;
}
printf(" *******************************************************\n");
法，然后用消除直接左递归的方法改写文法。
♦消除左递归算法：
把文法G的所有非终结符按任一顺序排列，例如，A1,A2，…,
An。
for
(i=1；
iv=n;
i++)
for
(j=1；
j<=i-
1；j++)
{把形如AifAj丫的产生式改写成Aif81y/<2丫/…/ck丫
其中Ajf81 / 32/…/8是关于的Aj全部规则；
int flags;
}P[30]；
int count=O;〃产生式数量
void creat()
{
int i;
printf("输入产生式数量：”)；
scan f("%d",&count);
for(i=0;i<co un t;i++)
{
flushall();
printf("输入第%d条产生式的左部:",i+1);
for(i=0;i<(i nt)strle n( ch3);i++)
ch3[i]=ch3[i+1]; strcat(ch1,ch3);
}
void Sort(char *ch1,char ch2[2])
{
int i;
for(i=0;i<(i nt)strle n(ch1);i++) ch1[i]=ch1[i+1];
消除Ai规则中的直接左递归；
}
化简由(2)所得到的文法，即去掉多余的规则。
3..实验内容
♦利用消除左递归算法上机了实现对于输入任意的上下文无关文法
可以输出消除了左递归的等价文法。
4.实验心得
♦通过本次试验更加清晰的理解了消除左递归在构建LL(1)文法的重
要作用，以及如何的消除文法中的左递归。在本次试验中原本想用
PfPal |Pa2|…|Pa|B1 |超|…|师这种相同左部的产生式右部用或连
5.实验代码与结果
源代码(
#in clude<stdio.h>
#in clude<stri ng.h>
struct Node//定义产生式结构
{
char left[20];〃产生式左部
char right[50];〃产生式右部
P
P'—01P'/aP'/…/an P'/£
♦间接左递归的消除
直接左递归见诸于表面，利用以上的方法可以很容易将其消除, 即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并 不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递 归，但却隐藏着左递归。
消除间接左递归的方法是，把间接左递归文法改写为直接左递归文
printf("你输入的产生式是:\n");
for(i=0;i<co un t;i++)
{
prin tf("%s->%s\n",P[i].left,P[i].right);
}
}
void Replace(char *ch1,char ch2[20])
{
int i;
char ch3[20]; strcpy(ch3,ch2);
}
}
void Analysis1()〃消除直接左递归
{
int i,j;
char ch[50];
char chx[2];
int num=co unt;
int flagsl;
strcpy(chx,"*1");
for(i=0;i<num;i++)〃消除直接左递归
{
flags 1=0;
if(P[i].flags==0)
消除产生式中的直接左递归是比较容易的。例如假设非终结符
P的规则为
P
其中，B是不以P开头的符号串。那么，我们可以把P的规则改写为
如下的非直接左递归形式：P—尸’
P'—P'£
考虑更一般的情况Pan/[31/[32/…/pm
其中，a(I=1,2,…，n)都不为£而每个pj(j=1,2,…，m)都不以P开头，将上述规则改写为如下形式即可消除P的直接左递归：