《c实现消除文法左递归》由会员分享，可在线阅读，更多相关《c实现消除文法左递归（6页珍藏版）》请在金锄头文库上搜索。
1、精品文档，仅供学习与交流，如有侵权请联系网站删除编译原理实验报告实验名称 消除文法的左递归 实验时间 2010.11.1 院系 计算机科学与技术 班级 2008 学号 JB084193 姓名 潘亚飞 1.试验目的输入：任意的上下文无关文法。输出：消除了左递归的等价文法。2.实验原理1直接左递归的消除消除产生式中的直接左递归是比较容易的。例如假设非终结符P的规则为PP / 其中，是不以P开头的符号串。那么，我们可以把P的规则改写为如下的非直接左递归形式： PP PP / 这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。 设有简单表达式文法GE： EE+T/ T TT*F/ F
2、 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间接左递归的消除直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递归，但却隐藏着左递归。例
3、如，设有文法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
4、的产生式改写成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/ cSS abcS/ QSab/ ab/ bRSa/ a可以看到从文法开始符号S出发，永
5、远无法达到Q和R，所以关于Q和R的规则是多余的，将其删除并化简，最后得到文法GS为：SabcS/ bcS/ cSS abcS/ 当然如果对文法非终结符排序的不同，最后得到的文法在形式上可能不一样，但它们都是等价的。例如，如果对上述非终结符排序选为S、Q、R，那么最后得到的文法GR为： RbcaR/ caR/ aRR bcaR/ 容易证明上述两个文法是等价的。3.实验内容 消除左递归算法：(1)把文法G的所有非终结符按任一顺序排列，例如，A1，A2，An。(2)for （i1；i=n；i+）for （j1；j=i1；j+）把形如AiAj的产生式改写成Ai1 /2 /k 其中Aj1 /2 /k是关
6、于的Aj全部规则； 消除Ai规则中的直接左递归；(3)化简由（2）所得到的文法，即去掉多余的规则。利用此算法可以将上述文法进行改写，来消除左递归。4.实验代码/#include stdafx.h#include#includeusing namespace std;struct WF /定义一个产生式结构体string left; /定义产生式的左部string right; /定义产生式的右部void Removing(WF *p,char *q,int n,int count)int count1=n;int flag=0;for(int i=0;i n;i+)/判断第一个非终结符是否存在
7、直接左递归 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(); string temp=pi.left; string temp1=; pi.left=temp+temp1; pi.right=str+pi.left; else string temp=pi.left
8、; 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+) 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.subs
9、tr(1,int (pg.right.length(); p+count1.left=pg.left; pcount1.right=ph.right+str; pg.left=; pg.right=;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.s
10、ubstr(1,int (pj.right.length(); string temp=pj.left; string temp1=; 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,c
11、ount=1,n;cout请输入文法产生式个数n：n;WF *p=new WF50;cout请输入文法的个产生式：endl;for(i=0;ipi.left; coutpi.right; coutendl;coutendl;cout即输入的文法产生式为：endl;for(i=0;i n;i+) coutpi.leftpi.rightendl;cout*endl;char q20;/对产生式的非终结符排序并存取在字符数组q q0=p0.left0;/把产生式的第一个非终结符存入q中for(i=1;in;i+)/对非终结符排序并存取 flag=0; for(j=0;ji;j+) if(pi.left=pj.left) flag+; if(flag=0) qcount+=pi.left0; count-; Removing(p,q,n,count);/调用消除递归子函数 Delete(p,n)
