c实现消除文法左递归doc.docx
《c实现消除文法左递归doc.docx》由会员分享，可在线阅读，更多相关《c实现消除文法左递归doc.docx（19页珍藏版）》请在冰点文库上搜索。
c实现消除文法左递归doc
编译原理实验报告
实验名称消除文法的左递归
实验时间
院系计算机科学与技术
班级2008
学号JB084193
姓名潘亚飞
1.试验目的
输入：
任意的上下文无关文法。
输出：
消除了左递归的等价文法。
2.实验原理
1．直接左递归的消除
消除产生式中的直接左递归是比较容易的。
例如假设非终结符P的规则为
P→Pα/β
其中，β是不以P开头的符号串。
那么，我们可以把P的规则改写为如下的非
直接左递归形式：
P→βP’
P’→αP’/ε
这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。
设有简单表达式文法G[E]：
E→E+T/T
T→T*F/FF→（E）/I
经消除直接左递归后得到如下文法：
E→TE’
E’→+TE’/ε
T→FT’
T’→*FT’/ε
F→（E）/I
考虑更一般的情况，假定关于非终结符P的规则为
P→Pα1/Pα2//Pαn/β1/β2//βm
其中，αi（I＝1，2，，n）都不为ε，而每个βj（j＝1，2，，m）都不以
P开头，将上述规则改写为如下形式即可消除P的直接左递归：
P→β1P’/β2P’//βmP’
P’→α1P’/α2P’//αnP’/ε
2．间接左递归的消除
直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。
然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。
有些文法虽然表面上不存在左递归，但却隐藏着左递归。
例如，设有文法G[S]：
S→Qc/c
Q→Rb/b
R→Sa/a
虽不具有左递归，但S、Q、R都是左递归的，因为经过若干次推导有
SQcRbcSabc
QRbSabQcab
RSaQcaRbca
就显现出其左递归性了，这就是间接左递归文法。
消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。
如果一个文法不含有回路，即形如PP的推导，也不含有以ε为右部的
产生式，那么就可以采用下述算法消除文法的所有左递归。
消除左递归算法：
（1）把文法G的所有非终结符按任一顺序排列，例如，
（2）for（i＝1；i<=n；i++）
A1，A2，，An。
for
（j
＝1；j<=i
－1；j++）
{把形如Ai→Ajγ的产生式改写成Ai→δ1γ/δ2γ//δkγ其中Aj→δ1/δ2//δk是关于的Aj全部规则；
消除Ai规则中的直接左递归；
}
（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'/ε
容易证明上述两个文法是等价的。
3..实验内容
消除左递归算法：
（1）把文法G的所有非终结符按任一顺序排列，例如，A1，A2，，An。
（2）for（i＝1；i<=n；i++）
for（j＝1；j<=i－1；j++）
{把形如Ai→Ajγ的产生式改写成Ai→δ1γ/δ2γ//δkγ其中Aj→δ1/δ2//δk是关于的Aj全部规则；
消除Ai规则中的直接左递归；
}
（3）化简由
（2）所得到的文法，即去掉多余的规则。
利用此算法可以将上述文法进行改写，来消除左递归。
4.实验代码
eft[0]==q[0]）
if（p[i].left[0]==p[i].right[0]）
flag++;
if（flag!
=0）eft[0]==q[0]）
if（p[i].left[0]==p[i].right[0]）
{
stringstr;
str=p[i].（1,int（p[i].（）））;
stringtemp=p[i].left;
stringtemp1="'";
p[i].left=temp+temp1;
p[i].right=str+p[i].left;
}
else
{
stringtemp=p[i].left;
stringtemp1="'";
temp=temp+temp1;
p[i].right=p[i].right+temp;
}
stringstr="'";
p[count1].left=p[0].left[0]+str;
p[count1].right="ε";
}
for（i=0;i<=count;i++）
{
for（intj=0;j
{
for（intg=0;g
if（q[i]==p[g].left[0]）
if（p[g].right[0]==q[j]）
{
for（inth=0;h
if（p[h].left[0]==q[j]&&int（p[h].（））==1）
{
stringstr;
str=p[g].（1,int（p[g].（）））;
p[++count1].left=p[g].left;
p[count1].right=p[h].right+str;
}
p[g].left="";
p[g].right="";
}
}
}
for（i=0;i<=count;i++）
{
flag=0;
for（intj=0;j
if（p[j].left[0]==q[i]）
if（p[j].left[0]==p[j].right[0]）
flag++;
if（flag!
=0）
{
for（intj=0;j<=n*n;j++）
if（p[j].left[0]==q[i]）
if（p[j].left[0]==p[j].right[0]）
{
stringstr;
str=p[j].（1,int（p[j].（）））;
stringtemp=p[j].left;
stringtemp1="'";
p[j].left=temp+temp1;
p[j].right=str+p[j].left;
}
else
{
stringtemp=p[j].left;
stringtemp1="'";
temp=temp+temp1;
p[j].right=p[j].right+temp;
}
stringstr="'";
p[++count1].left=q[i]+str;
p[count1].right="ε";
}
}
}
intDelete（WF*p,intn）
{
return0;
}
intmain（）
{
inti,j,flag=0,count=1,n;
cout<<"请输入文法产生式个数n：
"<
cin>>n;
WF*p=newWF[50];
cout<<"请输入文法的个产生式：
"<
for（i=0;i
cout<<"->"<
cin>>p[i].right;
cout<
}
cout<
cout<<"即输入的文法产生式为：
"<
for（i=0;i
cout<"<
cout<<"*********************"<
charq[20];eft[0];eft==p[j].left）
flag++;
if（flag==0）
q[count++]=p[i].left[0];
}
count--;
Removing（p,q,n,count）;eft[0]==q[i]）&&int（p[j].（））==1）
cout<"<
elsecontinue;
for（j=0;j<=n*n;j++）
if（（p[j].left[0]==q[i]）&&int（p[j].（））==2）
cout<"<
elsecontinue;
}
return0;
}
5.实验结果
消除直接左递归：
消除间接左递归：
6.实验心得
一个文法是含有左递归的，如果存在非终结符P，PPα
含有左递归的文法将使上述的自上而下的分析过程陷入无限循环，
即当试图
用P去匹配输入串时，就会出现在没有吃进任何输入符号的情况下，又得重新要
求P去进行新的匹配。
因此，使用自上而下分析法必须消除文法的左递归性。
对文法中一切左递归的消除要求文法中不含回路即无AA的推导。
满足这个要
求的充分条件是：
文法中不包含形如A→A和A→ε的空产生式。
根据消除左递归的算法步骤我们可以得出整个程序思路。
对于产生式的存储问
题，采用定义产生式的结构体，再用表的形式来存储所有的产生式。
再输入存储时就将产生式的左部和右部分开存储于产生式结构体中，方便后面的操作。
在消除左递归的过程中，对于直接左递归，可将其改为直接右递归；对于间接左递归（也称文法左递归），则应按照算法给出非终结符不同排列的等价的消除左递归后的文法。
升级会员 