消除左递归实验
编译原理实验报告
实验名称 消除文法左递归_____
___ 实验时间 2014年12月12日
院系 软件工程____________
班级 软件工程(2)班_____
学号 E01214215___________
姓名 刘翼______________
实验目的:
输入:任意的上下文无关文法。
输出:消除了左递归的等价文法。
实验原理:
1(直接左递归的消除
消除产生式中的直接左递归是比较容易的。例如假设非终结符P的规则为
P?Pα / β
其中,β是不以P开头的符号串。那么,我们可以把P的规则改写为如下的非直接左递归形式: P?βP’
P’?αP’ / ε
这两条规则和原来的规则是等价的,即两种形式从P推出的符号串是相同的。
设有简单表达式文法G[E]:
E?E+T/ T
T?T*F/ F
F?(E)/ I
经消除直接左递归后得到如下文法:
E?TE’
?+TE’/ ε E’
T?FT’
T’ ?*FT’/ ε
F?(E)/ I
考虑更一般的情况,假定关于非终结符P的规则为
P?Pα / Pα /…/ Pα / β/ β/…/β 12n1 2 m
其中,α(I,1,2,…,n)都不为ε,而每个β(j,1,2,…,m)都不以ij
P开头,将上述规则改写为如下形式即可消除P的直接左递归:
P?β P’/ β P’/…/β P’ 1 2 m
P’ ?αP’ / α P’ /…/ α P’ /ε 12n
2(间接左递归的消除
直接左递归见诸于表面,利用以上的方法可以很容易将其消除,即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递归,但却隐藏着左递归。例如,设有文法G[S]:
S?Qc/ c
Q?Rb/ b
R?Sa/ a
虽不具有左递归,但S、Q、R都是左递归的,因为经过若干次推导有
SQcRbcSabc ,,,
QRbSabQcab ,,,
RSaQcaRbca ,,,
就显现出其左递归性了,这就是间接左递归文法。
消除间接左递归的方法是,把间接左递归文法改写为直接左递归文法,然后用消除直接左递归的方法改写文法。
,
,如果一个文法不含有回路,即形如PP的推导,也不含有以ε为右部的产生式,那么就可以采用下述算法消除文法的所有左递归。
消除左递归算法:
(1) 把文法G的所有非终结符按任一顺序排列,例如,A,A,…,A。 12n
(2) for (i,1;i<=n;i++)
for (j,1;j<=i,1;j++)
{ 把形如A?Aγ的产生式改写成A?δγ /δγ /…/δγ iji12k
其中A?δ /δ /…/δ是关于的A全部规则; j12kj
消除A规则中的直接左递归; i
}
(3) 化简由(2)所得到的文法,即去掉多余的规则。
利用此算法可以将上述文法进行改写,来消除左递归。
首先,令非终结符的排序为R、Q、S。对于R,不存在直接左递归。把R代入到Q中的相关规则中,则Q的规则变为Q?Sab/ ab/ b。
代换后的Q不含有直接左递归,将其代入S,S的规则变为S?Sabc/ abc/ bc/
。 c
此时,S存在直接左递归。在消除了S的直接左递归后,得到整个文法为:
S?abcS’/ bcS'/ cS'
S’ ?abcS'/ ε
Q?Sab/ ab/ b
R?Sa/ a
可以看到从文法开始符号S出发,永远无法达到Q和R,所以关于Q和R的规则是多余的,将其删除并化简,最后得到文法G[S]为:
S?abcS'/ bcS’/ cS'
S' ?abcS'/ ε
当然如果对文法非终结符排序的不同,最后得到的文法在形式上可能不一样,但它们都是等价的。例如,如果对上述非终结符排序选为S、Q、R,那么最后得到的文法G[R]为: R?bcaR'/ caR'/ aR’
R' ?bcaR'/ ε
容易证明上述两个文法是等价的。
实验内容:
指明是否存在左递归,以及左递归的类型。对于直接左递归,可将其改为直接右递归;对于间接左递归(也称文法左递归),则应按照算法给出非终结符不同排列的等价的消除左递归后的文法。(应该有n~种)
实验代码与结果:
#include
#include
#include
#define N 20
char P[N][N]; //存放文法
char Q[N]; //存放非终结符
char R[N][N]; //存放含有间接左递归的产生式 char str[N][N], str1[N][N]; int sp[N]; //标记无用的产生式
int r, count=0,count1=0;
int direct(char P[N][N]); //判断直接左递归 int indirect(char P[N][N]); //判断间接左递归 void directRemove(char P[N][N]); //消除直接左递归 void indirectRemove(char P[N][N]); //消除间接左递归 void perm(char str[N][N], int i, int n); //实现全排列
int main()
{
printf("请输入文法P产生式的个数: ");
scanf("%d/n",&r);
printf("请输入各条产生式,产生式的左部跟右部用->连接:\n");
for(int k=0;k0)
{
printf("经判断该文法含有直接左递归!\n");
return 1;
}
else
return 0;
}
int indirect(char P[N][N]) {
int flag=0;
for(int i=0;i0)
break;
}
if(flag>0)
{
printf("经判断该文法含有间接左递归!\n");
return 2;
}
else
return 0;
}
void directRemove(char P[N][N])
{
int k,j=4;
memset(sp,0,sizeof(sp));
for(int i=0;i1)
r1++;
for(i=0;i=4;s--)
P[i+k][s+t-1]=P[i+k][s];
for(int u=3;u<3+t;u++)
P[i+k][u]=P[i][u];
break;
}
else if((P[i][0]==R[g][3])&&(flag1==1))
{
for(int y=0;R[g][y]!=0;y++)
P[r1-1][y]=R[g][y];
int m=3;
while(P[i][m]!=0)
m++;
int t=m-3;
int n=4;
while(P[r1-1][n]!=0)
n++;
for(int s=n-1;s>=4;s--)
P[r1-1][s+t-1]=P[r1-1][s];
for(int u=3;u<3+t;u++)
P[r1-1][u]=P[i][u];
break;
}
}
}
flag1=0;
g++;
}
memset(sp,0,sizeof(sp));
for(i=0;i