消除左递归实验报告材料

1、编译原理实验报告实验名称 消除文法左递归实验时间2014年12月12日院系软件工程班级软件工程（2）班学号E01214215翼实验目的：输入：任意的上下文无关文法。输出：消除了左递归的等价文法。实验原理：1直接左递归的消除消除产生式中的直接左递归是比较容易的。例如假设非终结符P的规则为P Pa / B其中，B是不以P开头的符号串。那么，我们可以把 P的规则改写为如下的非 直接左递归形式：PB P'P'a P' /£这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。设有简单表达式文法GE:E E+T/ TT T*F/ FF ( E) / I经消

2、除直接左递归后得到如下文法：E TE'E ' +TE' / £T FT'T' *FT' / £F ( E) / I考虑更一般的情况，假定关于非终结符 P的规则为P Pa 1 / P a 2 / / P a n / B 1 / B 2 / / B m 其中，a i (I = 1，2，n)都不为£，而每个B j (j = 1，2，m都不以 P开头，将上述规则改写为如下形式即可消除P的直接左递归：PB 1 P ' / B 2 P ' / / B m P ' P' a 1P'/ a 2

3、 P '/ a n P '/ £2 间接左递归的消除直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左 递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存 在左递归了。有些文法虽然表面上不存在左递归，但却隐藏着左递归。例如，设 有文法GS:S Qc/ cC Rb/ bR Sa/ a虽不具有左递归，但S、Q R都是左递归的，因为经过若干次推导有SQcRbcSabcQRbSabQcabRSaQcaRbca就显现出其左递归性了，这就是间接左递归文法消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法， 然后 用消除直接左递归的方法

4、改写文法。如果一个文法不含有回路，即形如 P P的推导，也不含有以&为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。消除左递归算法：(1) 把文法G的所有非终结符按任一顺序排列，例如，Ai, A,，A。(2) for (i = 1 ； i<=n ； i+ )for(j = 1; j<=i 1; j+ ) 把形如A f A 丫的产生式改写成 A 1丫 / S' 2丫 / S' k y 其中A fS 1 / S 2 / S k是关于的A全部规则； 消除A规则中的直接左递归；(3) 化简由(2)所得到的文法，即去掉多余的规则。利用此算法可以将上述文法进

5、行改写，来消除左递归。首先，令非终结符的排序为 R、Q S。对于R,不存在直接左递归。把 R代 入到Q中的相关规则中，贝U Q的规则变为Sab/ ab/ b。代换后的Q不含有直接左递归，将其代入S,S的规则变为Sf Sabc/ abc/ be/c。此时，S存在直接左递归。在消除了 S的直接左递归后，得到整个文法为：Sf abeS' / bcS'/ cS'S' f abcS'/ &Cf Sab/ ab/ bRf Sa/ a可以看到从文法开始符号 S出发，永远无法达到Q和R,所以关于Q和R的 规则是多余的，将其删除并化简，最后得到文法GS为：Sf a

6、bcS'/ bcS ' / cS'S' f abcS'/ £当然如果对文法非终结符排序的不同，最后得到的文法在形式上可能不一 样，但它们都是等价的。例如，如果对上述非终结符排序选为S、Q R,那么最后得到的文法 GR为： R f bcaR'/ caR'/ aR 'R' f bcaR'/ £容易证明上述两个文法是等价的。实验容：指明是否存在左递归，以及左递归的类型。对于直接左递归，可将其改为直 接右递归；对于间接左递归(也称文法左递归)，则应按照算法给出非终结符不 同排列的等价的消除左递归后的文法

7、。(应该有 n!种)实验代码与结果：#i nclude<stdio.h> #in clude<stdlib.h> #i nclude<stri ng.h> #defi ne N 20char PNN;/ 存放文法char QN;/存放非终结符char RNN;/存放含有间接左递归的产生式char strNN, str1NN;int spN; /标记无用的产生式int r , count=0,count1=0;int direct(char PNN);/ 判断直接左递归int indirect(char PNN);/ 判断间接左递归void directRem

8、ove(char PNN); void in directRemove(char PNN); void perm(char strNN, i nt i, i nt n);/消除直接左递归/消除间接左递归/实现全排列int main()printf("请输入文法P产生式的个数:");sca nf("%d/n",&r);printf("请输入各条产生式，产生式的左部跟右部用-> 连接:n");for(int k=O;k<r;k+)sca nf("%s",Pk);if(strle n(Pk)=4) s

9、trcpy(str1cou nt1+,Pk);elsestrcpy(strcou nt+,Pk);if(direct(P)=1)directRemove(P);else if(in direct(P)=2)perm(str , 0, count-1);elseprintf("经判断该文法不含有左递归!n");return 0; int direct(char PNN) int flag=0;for(i nt i=O;i<r;i+)if(Pi3=Pi0)flag+; break;if(flag>0)printf("经判断该文法含有直接左递归 return

10、 1;elsereturn 0;int indirect(char PNN)int flag=0;for(i nt i=0;i<r;i+)for(i nt k=1;k<r;k+)if(Pi+k0=Pi3)flag+; break;if(flag>0) break;if(flag>0)printf("经判断该文法含有间接左递归 return 2;elsereturn 0;!n");!n");void directRemove(char PNN)int k,j=4;memset(sp,0,sizeof(sp);for(i nt i=0;i<

11、;r;i+)if(Pi3=Pi0)Pi3=Pi2;Pi2=Pi1; Pi1=''' while(Pij!=0) j+;Pij=Pi0;Pij+1='''spi=1; for(k=0;k<4;k+) Prk=Pik;Prk='$' spr=1;elsej=3; while(Pij!=0)j+;Pij=Pi0;Pij+1=''' spi=1;prin tf("n消除直接左递归后的文法为:n");for(i nt t=0;t< r+1;t+)if(spt=1)prin tf(&qu

12、ot;%sn",Pt);void indirectRemove(char PNN)int flag,flag1=0,r仁r;int i,j,k,t,e=0,g=0;Qe=Pe0;for(i=1;i<r;i+)int flag=O;for(i nt k=O;k<=e;k+)if(PiO!=Qk) flag+;if(flag=(e+1)e+;Qe=PiO;prin tf("n非终结符序列为：sn", Q);for(j=0;j<e;j+)int nu mber=0;for(i nt z=0;z<r;z+)if(Pz0=Qj)nu mber+;if

13、(nu mber>1)r1+;for(i=0;i<r;i+)for(k=1;k<r;k+)if(Pi0=Pi+k3)&&(flag 仁=0)for(i nt y=0;Pi+ky!=0;y+)Rg y=Pi+ky;flag仁1;int m=3;while(Pim!=0)m+;int t=m-3;int n=4;while(Pi+k n!=0)n+;for(i nt s=n-1;s>=4;s-) Pi+ks+t-1=Pi+ks;for(i nt u=3;u<3+t;u+)Pi+ku=Piu;break;else if(Pi0=R g 3)&&a

14、mp;(flag1=1) for(i nt y=O;R gy!=O;y+) P-iy=R g y; int m=3;while(Pim!=O) m+;int t=m-3;int n=4;while(Pr1-1 n!=0) n+;for(i nt s=n-1;s>=4;s-) Pr1-1s+t-1=Pr1-1s;for(i nt u=3;u<3+t;u+)Pr1-1u=Piu; break;flag 仁0;g+;memset(sp,0,sizeof(sp);for(i=0;i<r1;i+)if(Pi0=Qe)if(Pi3=Pi0)Pi3=Pi2;Pi2=Pi1; Pi1=

15、9;'' while(Pij!=0) j+;Pij=Pi0;Pij+1=''' spi=1; for(k=0;k<4;k+)Pr1k=Pik;Pr1k='$' spr1=1;elsej=3;while(Pij!=O)j+；Pij=PiO； Pij+1='''； spi=1;printf("消除间接左递归后的文法为:n");for(t=0;t<=r1;t+)if(spt=1)prin tf("%sn",Pt);void perm(char strNN, i nt i, i nt n)int k=0,j=0;char tempN;if(i = n)memset(P , 0, sizeof(P); while(k<co unt)strcpy(Pk, strk); k+;while(kvr)strcpy(Pk, str1k-cou nt); k+;in directRemove(P);elsefor(j=i;j<=n ;j+)strcpy(temp, strj); strcpy(strj, stri); strcpy(stri, temp); perm(str , i+1, n); strcpy(temp, strj);strcpy