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

编译原理实验报告

实验名称:消除文法的左递归

实验时间 ：2015/5/28

院系：管理与信息工程学院

班级 ：12级计算机科学与技术

学号：0124

姓名 ：刘杨凡

1.实验目的：

输入：任意的上下文无关文法。 输出：消除了左递归的等价文法。

2.实验原理：

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→β1 P’ / β2 P’ /…/βm P’ P’ →α1P’ / α2 P’ /…/ αn P’ /ε 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'/ ε

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

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语言）：

#include \"\" #include<> #include<> #define N 20

char P[N][N]; //规则集

char Q[N]; //规则集,存放间接左递归消除后的部分规则 char R[N][N]; //用来存放规则的初始值 int r; //实际输入的规则的个数

int direct(char P[N][N]); //直接左递归函数 int indirect(char P[N][N]); //间接左递归函数

void directRemove(char P[N][N]); //消除直接左递归函数 void indirectRemove(char P[N][N]); //消除间接左递归函数

int direct(char P[N][N]) //定义直接左递归函数 {

int flag=0;

for(int i=0;iif(flag>0)

{ printf(\"经判断该文法含有直接左递归!\\n\"); return 1; //属于直接接左递归 }

else

return 0; //不属于直接左递归 }

int indirect(char P[N][N]) //定义间接左递归函数 {

int flag=0; for(int i=0;iflag++; break; } }

if(flag>0) break; } if(flag>0) { printf(\"经判断该文法含有间接左递归!\\n\"); return 2; //属于间接左递归 }

else

return 0; //不属于间接左递归 }

void directRemove(char P[N][N]) //定义消除直接左递归的函数 { int j=4; for(int i=0;iwhile(P[i][j]!=0)

j++; P[i][j]=P[i][0]; P[i][j+1]='\\''; for(int k=0;k<4;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(int t=0;tvoid indirectRemove(char P[N][N]) //定义消除间接左递归的函数 {

int flag,flag1=0,copy=r; int e=0;

Q[e]=P[e][0]; //统计规则中不同的左部 for(int i=1;iint g=0; for(int j=0;jint number=0; for(int z=0;z1) copy++; //如果有相同左部则规则总数加一 for(i=0;iif((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-1-2 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[copy-1][y]=R[g][y]; int m=3; while(P[i][m]!=0) //统计替换字符的个数为m-1-2 m++; int t=m-3; int n=4; while(P[copy-1][n]!=0) //统计被替换规则中非终结符的个数 n++; for(int s=n-1;s>=4;s--) P[copy-1][s+t-1]=P[copy-1][s];

for(int u=3;u<3+t;u++) P[copy-1][u]=P[i][u]; break; } } } flag1=0; g++; } printf(\"首次消除间接左递归后的直接左递归文法为:\\n\"); for(int t=0;tfor(i=0;iprintf(\"再次消除直接左递归后的文法为:\\n\"); printf(\"\\n\"); printf(\"(*代表ε)\\n\");

printf(\"\\n\"); for(t=0;t<=copy;t++) printf(\"%s\\n\ }

void main() { printf(\"请输入上下文无关的文法规则P的个数: \"); scanf(\"%d/n\ printf(\"\\n\");

printf(\"请输入各条规则，规则的左部跟右部用->连接，规则间用空格隔开\"); printf(\"\\n\");

for(int k=0;kdirectRemove(P); else if(indirect(P)==2) indirectRemove(P); else printf(\"经判断该文法不含有左递归!\\n\"); }

消除文法直接左递归实例见下页：

消除文法直接左递归实例如下：

消除文法间接左递归实例1如下：

消除文法间接左递归实例2如下：