编译原理实验二：消除文法的左递归说课讲解

1、编译原理实验报告实验名称消除文法的左递归实验时间2013年11月12日院系 计算机科学与电子技术系班级 11计算机软件学号JV114001 JV114095 JP114065姓名唐茹韩强强 徐思维1.试验目的：输入：任意的上下文无关文法。 输出：消除了左递归的等价文法。2.实验原理：1直接左递归的消除消除产生式中的直接左递归是比较容易的。例如假设非终结符P 的规则为：P Pa / B其中，B是不以P开头的符号串。那么，我们可以把 P的规则改写为如下的非 直接左递归形式：PB P'P'a P' /&这两条规则和原来的规则是等价的，即两种形式从 P推出的符号串是相同

2、的。设有简单表达式文法 GE ：E E+T/ TT T*F/ FF （E）/ I经消除直接左递归后得到如下文法：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

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

4、间接左递归的方法是， 把间接左递归文法改写为直接左递归文法， 然后 用消除直接左递归的方法改写文法。如果一个文法不含有回路，即形如 P P的推导，也不含有以&为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。消除左递归算法：(1) 把文法G的所有非终结符按任一顺序排列，例如，Ai,，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 其中AfS 1 / S 2 / S k是关于的A全部规则； 消除 Ai 规则中的

5、直接左递归;(3) 化简由( 2)所得到的文法，即去掉多余的规则。 利用此算法可以将上述文法进行改写，来消除左递归。首先，令非终结符的排序为 R、Q S。对于R,不存在直接左递归。把 R代 入到Q中的相关规则中，贝U Q的规则变为Sab/ ab/ b。代换后的Q不含有直接左递归，将其代入S,S的规则变为Sf Sabc/ abc/ be/ c。此时，S存在直接左递归。在消除了 S的直接左递归后，得到整个文法为：SfabcS'/ bcS'/ cS'S' f abeS'/ &QfSab/ ab/ bRfSa/ a可以看到从文法开始符号 S出发，永远无法

6、达到Q和R,所以关于Q和R的 规则是多余的，将其删除并化简，最后得到文法GS为：SfabeS'/ beS ' / eS'S' f abcS'/ £ 当然如果对文法非终结符排序的不同，最后得到的文法在形式上可能不一 样，但它们都是等价的。例如，如果对上述非终结符排序选为S、Q R,那么最后得到的文法 GR为： R f bcaR'/ caR'/ aR 'R' fbeaR'/ £容易证明上述两个文法是等价的。3.实验内容：消除左递归算法：(4) 把文法G的所有非终结符按任一顺序排列，例如，A, A,，

7、A。(5) for (i = 1 ； i<=n ； i+ )for (j = 1; j<=i 1; j+ )把形如A f A 丫的产生式改写成Ai fS 1 y / S 2 丫 / S k y其中A S 1 / S 2 / S k是关于的A全部规则；消除 Ai 规则中的直接左递归；（6）化简由（ 2）所得到的文法，即去掉多余的规则。利用此算法可以将上述文法进行改写，来消除左递归。注意事项：指明是否存在左递归， 以及左递归的类型。 对于直接左递归， 可将其改为直 接右递归；对于间接左递归（也称文法左递归） ，则应按照算法给出非终结符不 同排列的等价的消除左递归后的文法。（应该有n种）

8、/直接左递归函数/间接左递归函数/消除直接左递归函数/消除间接左递归函数4.实验代码与结果： #include "stdafx.h" #include<stdio.h> #include<string.h> #define N 20char PNN;char QN;char RNN; int r;/规则集/规则集 ,存放间接左递归消除后的部分规则 /用来存放规则的初始值 /实际输入的规则的个数int direct(char PNN);int indirect(char PNN); void directRemove(char PNN); void i

9、ndirectRemove(char PNN);int direct(char PNN)/定义直接左递归函数int flag=0;for(int i=0;i<r;i+)if(Pi3=Pi0)/右部字符中有与左部相同的符号flag+; break;if(flag>0)printf(" 经判断该文法含有直接左递归 !n");return 1;/ 属于直接接左递归elsereturn 0;/不属于直接左递归int indirect(char PNN)/ 定义间接左递归函数int flag=0;for(int i=0;i<r;i+)for(int k=1;k<

10、;r;k+)if(Pi+k0=Pi3)flag+; break;if(flag>0) break; if(flag>0) printf(" 经判断该文法含有间接左递归 !n"); return 2; / 属于间接左递归elsereturn 0;/不属于间接左递归void directRemove(char PNN) / 定义消除直接左递归的函数 int j=4;for(int i=0;i<r;i+) if(Pi3=Pi0) Pi3=Pi2;Pi2=Pi1;Pi1=''' while(Pij!=0) j+;Pij=Pi0;Pij+1=

11、'''for(int k=0;k<4;k+) /包含空的一条规则 Prk=Pik;Prk='*'elsej=3;while(Pij!=0)j+;Pij=Pi0;Pij+1='''printf("n 消除直接左递归后的文法为 :n");printf("n");printf("(* 代表& )n");printf("n");for(int t=0;t<r+1;t+) printf("%sn",Pt);void ind

12、irectRemove(char PNN)/定义消除间接左递归的函数int flag,flag1=0,copy=r;int e=0;Qe=Pe0;/统计规则中不同的左部for(int i=1;i<r;i+)flag=0;for(int k=0;k<=e;k+)if(Pi0!=Qk) flag+;if(flag=(e+1)e+;Qe=Pi0;int g=0;for(int j=0;j<e;j+)int number=0; for(int z=0;z<r;z+)if(Pz0=Qj) number+; if(number>1) copy+;/统计相同左部的规则个数/如果

13、有相同左部则规则总数加一for(i=0;i<r;i+)for(int k=1;k<r;k+) if(Pi0=Pi+k3)&&(flag1=0)for(int y=0;Pi+ky!=0;y+)Rgy=Pi+ky;/把原值保留flag1=1; int m=3;while(Pim!=0) /统计替换字符的个数为 m-1-2 m+;int t=m-3;int n=4;为 n-4while(Pi+kn!=0)/ 统计被替换规则中非终结符的个数n+; for(int s=n-1;s>=4;s-) Pi+ks+t-1=Pi+ks; for(int u=3;u<3+t;

14、u+) Pi+ku=Piu; break;else if(Pi0=Rg3)&&(flag1=1)for(int y=0;Rgy!=0;y+)Pcopy-1y=Rgy;int m=3;while(Pim!=0) /统计替换字符的个数为 m-1-2 m+;int t=m-3;int n=4;为 n-4n+;for(int s=n-1;s>=4;s-)Pcopy-1s+t-1=Pcopy-1s;for(int u=3;u<3+t;u+)Pcopy-1u=Piu;while(Pcopy-1n!=0) / 统计被替换规则中非终结符的个数 break;flag1=0;g+;pr

15、intf(" 首次消除间接左递归后的直接左递归文法为 :n");for(int t=0;t<copy;t+)printf("%sn",Pt);printf("n");for(i=0;i<copy;i+)if(Pi0=Qe)if(Pi3=Pi0)Pi3=Pi2;Pi2=Pi1;Pi1='''while(Pij!=0)j+;Pij=Pi0;Pij+1='''for(int k=0;k<4;k+)/包含空的一条规则Pcopyk=Pik;Pcopyk='*'el

16、sej=3;while(Pij!=0)j+;Pij=Pi0;Pij+1='''printf(" 再次消除直接左递归后的文法为 :n");printf("n");printf("(* 代表& )n");printf("n");for(t=0;t<=copy;t+)printf("%sn",Pt);void main()printf("请输入上下文无关的文法规则P的个数：")；scanf("%d/n",&r);pr

17、intf("n")；printf(" 请输入各条规则， 规则的左部跟右部用 ->连接，规则间用空格隔开 ")；printf("n")；for(int k=0；k<r；k+)scanf("%s",Pk)；printf("n")；printf(" 即输入的文法规则为 ：n")；for(k=0；k<r；k+)printf("%sn",Pk)；if(direct(P)=1)directRemove(P)；else if(indirect(P)=2

18、)indirectRemove(P)；elseprintf(" 经判断该文法不含有左递归 !n")；消除文法直接左递归实例见下页：消除文法直接左递归实例如下:扁入各条规则，规则的左部跟右部用-楚规 规则问用主格隔汗 S->Sa S>b即输入的文法规则为=S->£aK->b经判胖该文法含有亘妾左递归甲消除直接左递归后的文法知”-鮒S->bS-rrc53 w# key tu coni inuc消除文法间接左递归实例1如下:-|qM予输入上下文无关的文法规则f&； i数4谨输入各条规P虬规则的左部跟右部用T连按，规则间用空恪腌开 fi->aB fi->Bb B->Ad 3->A即输入的