编译原理实验：消除文法的左递归

编译原理实验报告实验名称:消除文法的左递归实验时间：2015/5/28院系：管理与信息工程学院班级：12级计算机科学与技术学号：201201020124姓名：刘杨凡1.实验目的：输入：任意的上下文无关文法。输出：消除了左递归的等价文法。2.实验原理：1．直接左递归的消除假设非终结符P的规则为：P→Pα/β其中，β是不以P开头的符号串。那么，我们可以把P的规则改写为如下的非直接左递归形式：P→βP’P’→αP’/ε这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。设有简单表达式文法G[E]：E→E+T/TT→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/cQ→Rb/bR→Sa/a虽不具有左递归，但S、Q、R都是左递归的，因为经过若干次推导有SQcRbcSabcQRbSabQcabR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/bR→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..实验内容：消除左递归算法：（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！种）4.代码实现（C语言）：#includestdafx.h#includestdio.h#includestring.h#defineN20charP[N][N];//规则集charQ[N];//规则集,存放间接左递归消除后的部分规则charR[N][N];//用来存放规则的初始值intr;//实际输入的规则的个数intdirect(charP[N][N]);//直接左递归函数intindirect(charP[N][N]);//间接左递归函数voiddirectRemove(charP[N][N]);//消除直接左递归函数voidindirectRemove(charP[N][N]);//消除间接左递归函数intdirect(charP[N][N])//定义直接左递归函数{intflag=0;for(inti=0;ir;i++){if(P[i][3]==P[i][0])//右部字符中有与左部相同的符号{flag++;break;}}if(flag0){printf(经判断该文法含有直接左递归!\n);return1;//属于直接接左递归}elsereturn0;//不属于直接左递归}intindirect(charP[N][N])//定义间接左递归函数{intflag=0;for(inti=0;ir;i++){for(intk=1;kr;k++){if(P[i+k][0]==P[i][3]){flag++;break;}}if(flag0)break;}if(flag0){printf(经判断该文法含有间接左递归!\n);return2;//属于间接左递归}elsereturn0;//不属于间接左递归}voiddirectRemove(charP[N][N])//定义消除直接左递归的函数{intj=4;for(inti=0;ir;i++){if(P[i][3]==P[i][0]){P[i][3]=P[i][2];P[i][2]=P[i][1];P[i][1]='\'';while(P[i][j]!=0)j++;P[i][j]=P[i][0];P[i][j+1]='\'';for(intk=0;k4;k++)//包含空的一条规则P[r][k]=P[i][k];P[r][k]='*';}else{j=3;while(P[i][j]!=0)j++;P[i][j]=P[i][0];P[i][j+1]='\'';}}printf(\n消除直接左递归后的文法为:\n);printf(\n);printf((*代表ε)\n);printf(\n);for(intt=0;tr+1;t++)printf(%s\n,P[t]);}voidindirectRemove(charP[N][N])//定义消除间接左递归的函数{intflag,flag1=0,copy=r;inte=0;Q[e]=P[e][0];//统计规则中不同的左部for(inti=1;ir;i++){flag=0;for(intk=0;k=e;k++)if(P[i][0]!=Q[k])flag++;if(flag==(e+1)){e++;Q[e]=P[i][0];}}intg=0;for(intj=0;je;j++){intnumber=0;for(intz=0;zr;z++)if(P[z][0]==Q[j])number++;//统计相同左部的规则个数if(number1)copy++;//如果有相同左部则规则总数加一for(i=0;ir;i++){for(intk=1;kr;k++){if((P[i][0]==P[i+k][3])&&(flag1==0)){for(inty=0;P[i+k][y]!=0;y++)R[g][y]=P[i+k][y];//把原值保留flag1=1;intm=3;while(P[i][m]!=0)//统计替换字符的个数为m-1-2m++;intt=m-3;intn=4;while(P[i+k][n]!=0)//统计被替换规则中非终结符的个数为n-4n++;for(ints=n-1;s=4;s--)P[i+k][s+t-1]=P[i+k][s];for(intu=3;u3+t;u++)P[i+k][u]=P[i][u];break;}elseif((P[i][0]==R[g][3])&&(flag1==1)){for(inty=0;R[g][y]!=0;y++)P[copy-1][y]=R[g][y];intm=3;while(P[i][m]!=0)//统计替换字符的个数为m-1-2m++;intt=m-3;intn=4;while(P[copy-1][n]!=0)//统计被替换规则中非终结符的个数为n-4n++;for(ints=n-1;s=4;s--)P[copy-1][s+t-1]=P[copy-1][s];for(intu=3;u3+t;u++)P[copy-1][u]=P[i][u];break;}}}flag1=0;g++;}printf(首次消除间接左递归后的直接左递归文法为:\n);for(intt=0;tcopy;t++)printf(%s\n,P[t]);printf(\n);for(i=0;icopy;i++){if(P[i][0]==Q[e]){if(P[i][3]==P[i][0]){P[i][3]=P[i][2];P[i][2]=P[i][1];P[i][1]='\'';while(P[i][j]!=0)j++;P[i][j]=P[i][0];P[i][j+1]='\'';for(intk=0;k4;k++)//包含空的一条规则P[copy][k]=P[i][k];P[copy][k]='*';}else{j=3;while(P[i][j]!=0)j++;P[i][j]=P[i][0];P[i][j+1]='\'';}}}printf(再次消除直接左递归后的文法为:\n);printf(\n);printf((*代表ε)\n);printf(\n);for(t=0;t=copy;t++)printf(%s\n,P[t]);}voidmain(){printf(请输入上下文无关的文法规则P的个数:);scanf(%d/n,&r);printf(\n);printf(请输入各条规则，规则的左部跟右部用-连接，规则间用空格隔开);printf(\n);for(intk=0;kr;k++)scanf(%s,P[k]);printf(\n);printf(即输入的文法规则为:\n);for(k=0;kr;k++)printf(%s\n,P[k]);if(direct(P)==1)directRemove(P);elseif(indirect(P)==2)indirectRemove(P);elseprintf(经判断该文法不含有左递归!\n);}消除文法直接左递归实例见下页：消除文法直接左递归实例如下：消除文法间接左递归实例1如下：消除文法间接左递归实例2如下：