c实现消除文法左递归

1、编译原理实验报告实验名称 消除文法的左递归 实验时间 2010.11.1 院系 计算机科学与技术 班级 2008 学号 JB084193 姓名 潘亚飞 1.试验目的输入：任意的上下文无关文法。输出：消除了左递归的等价文法。2.实验原理1直接左递归的消除消除产生式中的直接左递归是比较容易的。例如假设非终结符P的规则为PP / 其中，是不以P开头的符号串。那么，我们可以把P的规则改写为如下的非直接左递归形式： PP PP / 这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。 设有简单表达式文法GE： EE+T/ T TT*F/ F F（E）/ I经消除直接左递归后得到如下文法：

2、 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

3、/ 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

4、 其中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出发，永

5、远无法达到Q和R，所以关于Q和R的规则是多余的，将其删除并化简，最后得到文法GS为：SabcS'/ bcS/ cS'S' abcS'/ 当然如果对文法非终结符排序的不同，最后得到的文法在形式上可能不一样，但它们都是等价的。例如，如果对上述非终结符排序选为S、Q、R，那么最后得到的文法GR为： RbcaR'/ caR'/ aRR' bcaR'/ 容易证明上述两个文法是等价的。3.实验内容 消除左递归算法：(1)把文法G的所有非终结符按任一顺序排列，例如，A1，A2，An。(2)for （i1；i<=n；i+）for （j1；j

6、<=i1；j+）把形如AiAj的产生式改写成Ai1 /2 /k 其中Aj1 /2 /k是关于的Aj全部规则； 消除Ai规则中的直接左递归； (3)化简由（2）所得到的文法，即去掉多余的规则。利用此算法可以将上述文法进行改写，来消除左递归。4.实验代码/#include "stdafx.h"#include<iostream>#include<string>using namespace std;struct WF /定义一个产生式结构体string left; /定义产生式的左部string right; /定义产生式的右部;void Remo

7、ving(WF *p,char *q,int n,int count)int count1=n;int flag=0;for(int i=0;i < n;i+)/判断第一个非终结符是否存在直接左递归 if(pi.left0=q0) if(pi.left0=pi.right0) flag+;if(flag!=0)/如果存在直接左递归则消除直接左递归 for(int i=0;i < n;i+) if(pi.left0=q0) if(pi.left0=pi.right0) string str; str=pi.right.substr(1,int (pi.right.length();

8、string temp=pi.left; string temp1="'" pi.left=temp+temp1; pi.right=str+pi.left; else string temp=pi.left; string temp1="'" temp=temp+temp1; pi.right=pi.right+temp; string str="'" pcount1.left=p0.left0+str; pcount1.right=""for( i=0;i <= count;i+)

9、 for(int j=0;j < i;j+) for(int g=0;g < n;g+) if(qi=pg.left0) if(pg.right0=qj) for(int h=0;h < n*n;h+) if(ph.left0=qj&&int (ph.left.length()=1) string str; str=pg.right.substr(1,int (pg.right.length(); p+count1.left=pg.left; pcount1.right=ph.right+str; pg.left="" pg.right=&

10、quot;" for( i=0;i <= count;i+) flag=0; for(int j=0;j < n*n;j+) if(pj.left0=qi) if(pj.left0=pj.right0) flag+; if(flag!=0) for(int j=0;j <= n*n;j+) if(pj.left0=qi) if(pj.left0=pj.right0) string str; str=pj.right.substr(1,int (pj.right.length(); string temp=pj.left; string temp1="

11、9;" pj.left=temp+temp1; pj.right=str+pj.left; else string temp=pj.left; string temp1="'" temp=temp+temp1; pj.right=pj.right+temp; string str="'" p+count1.left=qi+str; pcount1.right="" int Delete(WF *p,int n)return 0;int main()int i,j,flag=0,count=1,n;cout&l

12、t;<"请输入文法产生式个数n："<<endl;cin>>n;WF *p=new WF50;cout<<"请输入文法的个产生式："<<endl;for(i=0;i<n;i+)/输入产生式 cin>>pi.left; cout<<"->"<<endl; cin>>pi.right; cout<<endl;cout<<endl;cout<<"即输入的文法产生式为："<

13、;<endl;for(i=0;i < n;i+) cout<<pi.left<<"->"<<pi.right<<endl;cout<<"*"<<endl;char q20;/对产生式的非终结符排序并存取在字符数组q q0=p0.left0;/把产生式的第一个非终结符存入q中for(i=1;i<n;i+)/对非终结符排序并存取 flag=0; for(j=0;j<i;j+) if(pi.left=pj.left) flag+; if(flag=0) qco

14、unt+=pi.left0; count-; Removing(p,q,n,count);/调用消除递归子函数 Delete(p,n);/删除无用产生式 cout<<"消除递归后的文法产生式为："<<endl; for(i=0;i <= count;i+) for(int j=0;j <= n*n;j+) if( (pj.left0=qi) && int (pj.left.length()=1 ) cout<<pj.left<<"->"<<pj.right<

15、;<endl; else continue; for( j=0;j <= n*n;j+) if( (pj.left0=qi) && int (pj.left.length()=2 ) cout<<pj.left<<"->"<<pj.right<<endl; else continue; return 0;5.实验结果消除直接左递归：消除间接左递归：6.实验心得一个文法是含有左递归的，如果存在非终结符P ，PP含有左递归的文法将使上述的自上而下的分析过程陷入无限循环，即当试图用P去匹配输入串时，就会出现在没有吃进任何输入符号的情况下，又得重新要求P去进行新的匹配。因此，使用自上而下分析法必须消除文法的左递归性。