c实现消除文法左递归

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

2、 E) / I经消除直接左递归后得到如下文法：E - TE'E ' +TE' / £T -FT'T' -*FT' / £F - ( E) / I考虑更一般的情况，假定关于非终结符P 的规则为P-Pa 1 / P a2 / / P an/ 储/ 02 / 0 m其中，a i (I=1, 2,，n)都不为£ ,而每个0j (j=1, 2,，nm都不以P 开头，将上述规则改写为如下形式即可消除P 的直接左递归：4 B 1 P' / 02 P' / Bm P'P'-aiP' / a 2

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

4、接左递归的方法改写文法。如果一个文法不含有回路，即形如 P P的推导，也不含有以8为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。消除左递归算法：(1) 把文法G的所有非终结符按任一顺序排列，例如， A, 4,A(2) for (i = 1; i<=n ； i+ )for (j = 1; j<=i 1; j+ ) 把形如A-A y的广生式改写成 A-"丫 / S1 2 y / S' k y其中A-" / ” / 6 k是关于的A全部规则；消除Ai 规则中的直接左递归；( 3) 化简由(2)所得到的文法，即去掉多余的规则。利用此算法可以将上述文

5、法进行改写，来消除左递归。首先，令非终结符的排序为 R Q S。对于R,不存在直接左递归。把 R代 入到Q中的相关规则中，则Q的规则变为QHSab/ ab/ b。代换后的Q不含有直接左递归，将其代入S,S的规则变为S-Sabc/ abc/ bc/ c。此时，S存在直接左递归。在消除了 S的直接左递归后，得到整个文法为：Sf abcS' / bcS'/ cS'S' -abcS'/ £QH Sab/ ab/ bRH* Sa/ a可以看到从文法开始符号 S出发，永远无法达到Q和R,所以关于Q和R的 规则是多余的，将其删除并化简，最后得到文法GS为：S

6、f abcS'/ bcS ' / cS'S' -abcS'/ £当然如果对文法非终结符排序的不同，最后得到的文法在形式上可能不一样，但它们都是等价的。例如，如果对上述非终结符排序选为S、Q R,那么最后得到的文法 GR为： R-bcaR'/ caR'/ aR 'R' - bcaR'/ £容易证明上述两个文法是等价的。3.1. 实验内容消除左递归算法：(1)把文法G的所有非终结符按任一顺序排列，例如， A, 4,，A。(2)for(i = 1; i<=n ; i+ )for (j = 1;

7、j<=i 1; j+ ) 把形如A-A y的广生式改写成 Af占1丫 / S1 2 y / S' k y 其中A-" / ” / 6 k是关于的A全部规则； 消除Ai 规则中的直接左递归；(3) 化简由(2)所得到的文法，即去掉多余的规则。利用此算法可以将上述文法进行改写，来消除左递归。4. 实验代码eft0=q0)if(pi.left0=pi.right0)flag+;if(flag!=0)eft0=q0)if(pi.left0=pi.right0)string str;str=pi.(1,int (pi.();string temp=pi.left;string t

8、emp1="'"pi.left=temp+temp1;pi.right=str+pi.left;elsestring 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+)for(int j=0;j < i;j+)for(int

9、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.()=1)string str;str=pg.(1,int (pg.();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.lef

10、t0=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.(1,int (pj.();string temp=pj.left;string temp1="'"pj.left=temp+temp1;pj.right=str+pj.left;elsestring temp=pj.left;string temp1="'"temp=temp+temp

11、1;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 ij,flag=0,count=1,n;coutvv"请输入文法产生式个数n： "«endl;cin»n;WF *p=new WF50;coutvv”请输入文法的个产生式："«endl;for(i=0;i<n;i+)eft;cout«"-&g

12、t;"«endl;cin»pi.right;cout«endl;)cout«endl;coutvv”即输入的文法产生式为："«endl; for(i=0;i < n;i+)cout«pi.left«"->"«pi.right«endl;coutv v”*” v vend I .char q 2 0; eft 0; eft=p j. I eft)flag+;if(flag=O)qcount+=pi.left0;)count-;Removing(p,q,n,

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