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

【精品文档】如有侵权，请联系网站删除，仅供学习与交流编译原理实验：消除文法的左递归.精品文档.编译原理实验报告实验名称:消除文法的左递归实验时间 ：2015/5/28院系：管理与信息工程学院班级 ：12级计算机科学与技术学号：201201020124姓名 ：刘杨凡1.实验目的：输入：任意的上下文无关文法。输出：消除了左递归的等价文法。2.实验原理：1直接左递归的消除假设非终结符P的规则为：PP / 其中，是不以P开头的符号串。那么，我们可以把P的规则改写为如下的非直接左递归形式： PP PP / 这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。 设有简单表达式文法GE： EE+T/ T TT*F/ F F（E）/ I经消除直接左递归后得到如下文法： ETE E +TE/ TFTT *FT/ F（E）/ I考虑更一般的情况，假定关于非终结符P的规则为PP1 / P2 / Pn / 1 / 2 /m其中，i（I1，2，n）都不为，而每个j（j1，2，m）都不以P开头，将上述规则改写为如下形式即可消除P的直接左递归：P1 P / 2 P /m PP 1P / 2 P / n P /2间接左递归的消除直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递归，但却隐藏着左递归。例如，设有文法GS：SQc/ cQRb/ bRSa/ a虽不具有左递归，但S、Q、R都是左递归的，因为经过若干次推导有SQcRbcSabcQRbSabQcabRSaQcaRbca就显现出其左递归性了，这就是间接左递归文法。消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。如果一个文法不含有回路，即形如PP的推导，也不含有以为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。消除左递归算法：（1） 把文法G的所有非终结符按任一顺序排列，例如，A1，A2，An。（2） for （i1；i<=n；i+）for （j1；j<=i1；j+）把形如AiAj的产生式改写成Ai1 /2 /k 其中Aj1 /2 /k是关于的Aj全部规则； 消除Ai规则中的直接左递归；（3） 化简由（2）所得到的文法，即去掉多余的规则。利用此算法可以将上述文法进行改写，来消除左递归。首先，令非终结符的排序为R、Q、S。对于R，不存在直接左递归。把R代入到Q中的相关规则中，则Q的规则变为QSab/ ab/ b。代换后的Q不含有直接左递归，将其代入S，S的规则变为SSabc/ abc/ bc/ c。此时，S存在直接左递归。在消除了S的直接左递归后，得到整个文法为：SabcS/ bcS'/ cS'S abcS'/ QSab/ ab/ bRSa/ a可以看到从文法开始符号S出发，永远无法达到Q和R，所以关于Q和R的规则是多余的，将其删除并化简，最后得到文法GS为：SabcS'/ bcS/ cS'S' abcS'/ 当然如果对文法非终结符排序的不同，最后得到的文法在形式上可能不一样，但它们都是等价的。例如，如果对上述非终结符排序选为S、Q、R，那么最后得到的文法GR为： RbcaR'/ caR'/ aRR' bcaR'/ 容易证明上述两个文法是等价的。3.实验内容：消除左递归算法：（4） 把文法G的所有非终结符按任一顺序排列，例如，A1，A2，An。（5） for （i1；i<=n；i+）for （j1；j<=i1；j+）把形如AiAj的产生式改写成Ai1 /2 /k其中Aj1 /2 /k是关于的Aj全部规则；消除Ai规则中的直接左递归；（6） 化简由（2）所得到的文法，即去掉多余的规则。利用此算法可以将上述文法进行改写，来消除左递归。注意事项：指明是否存在左递归，以及左递归的类型。对于直接左递归，可将其改为直接右递归；对于间接左递归（也称文法左递归），则应按照算法给出非终结符不同排列的等价的消除左递归后的文法。（应该有n！种）4.代码实现（C语言）：#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 indirectRemove(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; /属于直接接左递归 else return 0; /不属于直接左递归int indirect(char PNN) /定义间接左递归函数 int flag=0; for(int i=0;i<r;i+)for(int k=1;k<r;k+)if(Pi+k0=Pi3) flag+; break; if(flag>0) break;if(flag>0)printf("经判断该文法含有间接左递归!n");return 2; /属于间接左递归 else return 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='''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 indirectRemove(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+; /如果有相同左部则规则总数加一 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-2m+;int t=m-3;int n=4;while(Pi+kn!=0) /统计被替换规则中非终结符的个数为n-4n+;for(int s=n-1;s>=4;s-)Pi+ks+t-1=Pi+ks;for(int u=3;u<3+t;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-2m+;int t=m-3;int n=4;while(Pcopy-1n!=0) /统计被替换规则中非终结符的个数为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;break;flag1=0;g+;printf("首次消除间接左递归后的直接左递归文法为: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='*'elsej=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); printf("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)indirectRemove(P); elseprintf("经判断该文法不含有左递归!n");消除文法直接左递归实例见下页：消除文法直接左递归实例如下：消除文法间接左递归实例1如下：消除文法间接左递归实例2如下：