实验2+消除文法左递归.docx

实验2+消除文法左递归.docx

《实验2+消除文法左递归.docx》由会员分享，可在线阅读，更多相关《实验2+消除文法左递归.docx（16页珍藏版）》请在冰点文库上搜索。

实验2+消除文法左递归

安徽大学编译原理实验

Author：

idiot10

实验二

名称

消除文法的左递归（Removingtheleftrecursionofthegrammar）

一、背景资料

一个文法是含有左递归的，如果存在非终结符P

P

Pα

含有左递归的文法将使上述的自上而下的分析过程陷入无限循环，即当试图用P去匹配输入串时，就会出现在没有吃进任何输入符号的情况下，又得重新要求P去进行新的匹配。

因此，使用自上而下分析法必须消除文法的左递归性。

二、实验目的要求

输入：

任意的上下文无关文法。

输出：

消除了左递归的等价文法。

三、实验原理

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’

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都是左递归的，因为经过若干次推导有

S

Qc

Rbc

Sabc

Q

Rb

Sab

Qcab

R

Sa

Qca

Rbca

就显现出其左递归性了，这就是间接左递归文法。

消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。

如果一个文法不含有回路，即形如P

P的推导，也不含有以ε为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。

消除左递归算法：

（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）所得到的文法，即去掉多余的规则。

利用此算法可以将上述文法进行改写，来消除左递归。

首先，令非终结符的排序为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'/ε

容易证明上述两个文法是等价的。

四、材料、试剂及仪器

微机

五、实验步骤（包括操作方法、数据处理）

消除左递归算法：

（4）把文法G的所有非终结符按任一顺序排列，例如，A1，A2，…，An。

（5）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规则中的直接左递归；

}

（6）化简由

（2）所得到的文法，即去掉多余的规则。

利用此算法可以将上述文法进行改写，来消除左递归。

六、注意事项

指明是否存在左递归，以及左递归的类型。

对于直接左递归，可将其改为直接右递归；对于间接左递归（也称文法左递归），则应按照算法给出非终结符不同排列的等价的消除左递归后的文法。

（应该有n！

种）

七、思考题

Code：

#include

#include

usingnamespacestd;

stringss[20]={"",""};

stringss1[20]={"",""};

stringsa="",sd="";

intl;

voidkill（charc）

{

stringtemp="";

temp+=c;

inti=0;

for（intj=0;j

{

for（i=0;i

if（temp.find（ss[i].at（0））!

=-1）

temp+=ss[i];

}

for（i=0;i

{

if（temp.find（ss[i].at（0））==-1）

ss[i]="";

}

i=0;

for（j=0;j

{

if（ss[j]!

=""）

{

ss[i]=ss[j];

if（i!

=j）

ss[j]="";

i++;

}

}

l=i;

}

voidverdict（）

{

stringsx="";

for（intj=0;j

{

stringsw[10]={"",""};

intf=0;

for（inth=3;h

{

if（ss[j].at（h）=='|'）

f++;

else

sw[f]+=ss[j].at（h）;

}

boolflag=false;

boolrepeflag=false;

while（!

repeflag）

{

repeflag=true;

for（h=0;h<=f;h++）

{

if（!

flag&&sw[h].at（0）==sa.at（j））

flag=true;

if（sx.find（sw[h].at（0））!

=-1）

{

repeflag=false;

stringspil="";

for（intjj=1;jj

spil+=sw[h].at（jj）;

intkk=sx.find（sw[h].at（0））;

stringtemp="";

if（ss[kk].find（'|'）!

=-1）

{

boolappflag=false;

for（jj=3;jj

{

if（ss[kk].at（3）==sa.at（j））

flag=true;

if（ss[kk].at（jj）=='|'）

{

if（ss[kk].at（jj+1）==sa.at（j））

flag=true;

if（!

appflag）

{

sw[h].replace（0,1,temp）;

appflag=true;

}

else

{

f++;

sw[f]=temp;

sw[f]+=spil;

}

temp="";

jj++;

}

temp+=ss[kk].at（jj）;

}

f++;

sw[f]=temp;

sw[f]+=spil;

}

else

{

temp=ss[kk].substr（3,ss[kk].length（）-3）;

sw[h].replace（0,1,temp）;

temp="";

}

}

}

}

if（flag）

{

boolflag1=false;

boolflag2=false;

boolflag3=false;

for（h=0;h<=f;h++）

{

chart=sa.at（j）+8;

if（!

flag3）

{

sa+=t;

flag3=true;

}

if（sw[h].at（0）==sa.at（j））

{

stringsr="->";

stringse="";

for（inty=1;y

se+=sw[h].at（y）;

if（!

flag1）

{

ss[l]+=t;

ss[l]+=sr;

ss[l]+=se;

ss[l]+=t;

flag1=true;

}

else

{

ss[l]+='|';

ss[l]+=se;

ss[l]+=t;

}

}

else

{

stringsr="->";

stringse="";

for（inty=0;y

se+=sw[h].at（y）;

se+=t;

if（!

flag2）

{

sr+=se;

ss[j]=ss[j].at（0）;

ss[j]+=sr;

flag2=true;

}

else

{

sr="";

sr='|';

sr+=se;

ss[j]+=sr;

}

}

}

if（flag1）

{

ss[l]+='|';

ss[l]+='*';

l++;

}

}

sx+=sa.at（j）;

}

}

voidshow（）

{

inti=0;

while（i

{

cout<

ss[i]="";

i++;

}

cout<

}

voidswap（char*a,char*b）

{

intm;

m=*a;

*a=*b;

*b=m;

}

voidperm（string&df,intk,intm,int&sum,string*s）

{

inti;

if（k>m）

{

for（i=0;i<=m;i++）

s[sum]+=df.at（i）;

sum++;

}

else

{

for（i=k;i<=m;i++）

{

swap（&df.at（k）,&df.at（i））;

perm（df,k+1,m,sum,s）;

swap（&df.at（k）,&df.at（i））;

}

}

}

voidchange（string*st,intp）

{

for（inti=0;i

{

intj=0;

if（st[p].at（i）!

=ss1[i].at（0））

{

for（;j

{

if（st[p].at（i）==ss1[j].at（0））

break;

}

ss[i]=ss1[j];

}

else

ss[i]=ss1[i];

}

}

intmain（）

{

intk=0;

cout<<"输入非终结符:

"<

cin>>sa;

charc=sa.at（0）;

k=sa.length（）;

cout<<"输入终结符:

"<

cin>>sd;

sd+='*';

cout<<"输入文法,#号结束"<

strings="";

inti=0;

while（true）

{

cin>>s;

if（s=="#"）

break;

ss[i]=s;

ss1[i]=s;

i++;

}

l=i;

intsum=1;

for（intii=1;ii<=sa.length（）;ii++）

sum*=ii;

string*st=newstring[sum];

stringdf=sa;

intp=0;

perm（df,0,df.length（）-1,p,st）;

cout<

for（p=0;p

{

cout<

sa=st[p];

change（st,p）;

l=sa.length（）;

cout<<"以"<

"<

verdict（）;

kill（c）;

show（）;

}

delete[]st;

return0;

}

测试数据：

S→Qc|c

Q→Rb|b

R→Sa|a