消除左递归实验报告

消除左递归实验报告 编译原理实验报告 实验名称 消除文法左递归_____ ___ 实验时间 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