共享知识分享快乐编译原理实验报告实验名称消除文法左递归实验时间2014年12月12日院系软件工程 ______________班级软件工程（2）班学号E01214215 __________姓名刘翼________________实验目的：输入：任意的上下文无关文法。
输出：消除了左递归的等价文法。
实验原理：1．直接左递归的消除消除产生式中的直接左递归是比较容易的。
例如假设非终结符P 的规则为P—P a / B其中，B是不以P开头的符号串。
那么，我们可以把P的规则改写为如下的非直接左递归形式：P —B P'P'—a 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 a 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的直接左递归：P—B 1 P' / B 2 P' / …/ B m P'P' —a 1P' / a 2 P' / …/ a n P' / £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的所有非终结符按任一顺序排列，例如，A i, A,…，A。
(2)for (i = 1 ；i<=n ；i++ )for (j = 1; j<=i —1; j++ ){ 把形如A f A丫的产生式改写成A i 1丫/ S' 2丫/…/ S' kY其中A fS 1 / S 2 /…/ S k是关于的A全部规则；消除A i 规则中的直接左递归;}(3)化简由( 2)所得到的文法，即去掉多余的规则。
利用此算法可以将上述文法进行改写，来消除左递归。
首先，令非终结符的排序为R、Q S。
对于R,不存在直接左递归。
把R代入到Q中的相关规则中，贝U Q的规则变为Sab/ ab/ b。
代换后的Q不含有直接左递归，将其代入S,S的规则变为S f Sabc/ abc/ be/ c。
此时，S存在直接左递归。
在消除了S的直接左递归后，得到整个文法为：S f abcS'/ bcS'/ cS'S' f abeS'/ &Q f Sab/ ab/ bR f Sa/ a可以看到从文法开始符号S出发，永远无法达到Q和R,所以关于Q和R的规则是多余的，将其删除并化简，最后得到文法G[S]为：S f abeS'/ beS ' / eS'S' f abeS'/ £当然如果对文法非终结符排序的不同，最后得到的文法在形式上可能不一样，但它们都是等价的。
例如，如果对上述非终结符排序选为S、Q R,那么最后得到的文法G[R]为：R f beaR'/ eaR'/ aR 'R' f beaR'/ £容易证明上述两个文法是等价的。
实验内容：指明是否存在左递归，以及左递归的类型。
对于直接左递归，可将其改为直接右递归;对于间接左递归(也称文法左递归)，则应按照算法给出非终结符不同排列的等价的消除左递归后的文法。
(应该有n!种) 实验代码与结果：#include<stdio.h>#include<stdlib.h> #include<string.h> #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;k<r;k++){scanf("%s",P[k]); if(strlen(P[k])==4) strcpy(str1[count1++],P[k]); else strcpy(str[count++],P[k]);}if(direct(P)==1) directRemove(P);else if(indirect(P)==2) perm(str , 0, count-1); elseprintf(" 经判断该文法不含有左递归 !\n"); return 0;}int direct(char P[N][N]){int flag=0;// 判断直接左递归// 判断间接左递归 // 消除直接左递归 // 消除间接左递归 // 实现全排列{{if(P[i][3]==P[i][0]){flag++; break;}}if(flag>0){printf(" 经判断该文法含有直接左递归 return 1;}elsereturn 0;}int indirect(char P[N][N]){int flag=0;for(int i=0;i<r;i++){for(int k=1;k<r;k++){if(P[i+k][0]==P[i][3]){flag++; break;}}if(flag>0)break;}if(flag>0){printf(" 经判断该文法含有间接左递归 return 2;}elsereturn 0;}void directRemove(char P[N][N])int k,j=4;memset(sp,0,sizeof(sp)); for(int i=0;i<r;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]='\'';sp[i]=1; for(k=0;k<4;k++) P[r][k]=P[i][k];!\n");!\n");sp[r]=1;}else{j=3;while(P[i][j]!=0)j++;P[i][j]=P[i][0];P[i][j+1]='\'';sp[i]=1;}}printf("\n 消除直接左递归后的文法为:\n");for(int t=0;t<r+1;t++){if(sp[t]==1)printf("%s\n",P[t]);}}void indirectRemove(char P[N][N]){int flag,flag1=0,r1=r;int i,j,k,t,e=0,g=0;Q[e]=P[e][0];for(i=1;i<r;i++)int flag=0;for(int k=0;k<=e;k++)if(P[i][0]!=Q[k])flag++;if(flag==(e+1)){e++;Q[e]=P[i][0];}}printf("\n 非终结符序列为：%s\n", Q);for(j=0;j<e;j++){int number=0;for(int z=0;z<r;z++)if(P[z][0]==Q[j])number++;if(number>1)r1++;for(i=0;i<r;i++){for(k=1;k<r;k++){if((P[i][0]==P[i+k][3])&&(flag1==0)){for(int y=0;P[i+k][y]!=0;y++) {共享知识分享快乐{R[g][y]=P[i+k][y]; flag1=1; int m=3; while(P[i][m]!=0) m++;int t=m-3;int n=4;while(P[i+k][n]!=0)n++;for(int s=n-1;s>=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<r1;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]='\'';sp[i]=1;for(k=0;k<4;k++)P[r1][k]=P[i][k];P[r1][k]='$';sp[r1]=1;}elsej=3;共享知识分享快乐while(P[i][j]!=0)j++;P[i][j]=P[i][0];P[i][j+1]='\''; sp[i]=1;}}}printf(" 消除间接左递归后的文法为:\n"); for(t=0;t<=r1;t++){if(sp[t]==1) printf("%s\n",P[t]);}}void perm(char str[N][N], int i, int n){int k=0,j=0;char temp[N];if(i == n){memset(P , 0, sizeof(P));while(k<count){ strcpy(P[k], str[k]); k++;}while(k<r){ strcpy(P[k], str1[k-count]); k++;}indirectRemove(P);}else{for(j=i;j<=n;j++){ strcpy(temp, str[j]); strcpy(str[j], str[i]); strcpy(str[i], temp); perm(str , i+1, n); strcpy(temp, str[j]);共享知识分享快乐strcpy(str[j], str[i]); strcpy(str[i], temp);}}}输出结果:。