《消除左递归实验报告材料》由会员分享，可在线阅读，更多相关《消除左递归实验报告材料（12页珍藏版）》请在金锄头文库上搜索。
1、编译原理实验报告实验名称 消除文法左递归实验时间2014年12月12日院系软件工程班级软件工程（2）班学号E01214215翼实验目的：输入：任意的上下文无关文法。输出：消除了左递归的等价文法。实验原理：1直接左递归的消除消除产生式中的直接左递归是比较容易的。例如假设非终结符P的规则为P Pa / B其中，B是不以P开头的符号串。那么，我们可以把 P的规则改写为如下的非 直接左递归形式：PB PPa P /这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。设有简单表达式文法GE:E E+T/ TT T*F/ FF ( E) / I经消除直接左递归后得到如下文法：E TEE +
2、TE / T FTT *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 P P a 1P/ a 2 P / a n P / 2 间接左递归的消除直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左 递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存 在左递归了
3、。有些文法虽然表面上不存在左递归，但却隐藏着左递归。例如，设 有文法GS:S Qc/ cC Rb/ bR Sa/ a虽不具有左递归，但S、Q R都是左递归的，因为经过若干次推导有SQcRbcSabcQRbSabQcabRSaQcaRbca就显现出其左递归性了，这就是间接左递归文法消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法， 然后 用消除直接左递归的方法改写文法。如果一个文法不含有回路，即形如 P P的推导，也不含有以&为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。消除左递归算法：(1) 把文法G的所有非终结符按任一顺序排列，例如，Ai, A,，A。(2) for
4、 (i = 1 ； i=n ； i+ )for(j = 1; j=i 1; j+ ) 把形如A f A 丫的产生式改写成 A 1丫 / S 2丫 / S k y 其中A fS 1 / S 2 / S k是关于的A全部规则； 消除A规则中的直接左递归；(3) 化简由(2)所得到的文法，即去掉多余的规则。利用此算法可以将上述文法进行改写，来消除左递归。首先，令非终结符的排序为 R、Q S。对于R,不存在直接左递归。把 R代 入到Q中的相关规则中，贝U Q的规则变为Sab/ ab/ b。代换后的Q不含有直接左递归，将其代入S,S的规则变为Sf Sabc/ abc/ be/c。此时，S存在直接左递归。
5、在消除了 S的直接左递归后，得到整个文法为：Sf abeS / bcS/ cSS f abcS/ &Cf Sab/ ab/ bRf Sa/ a可以看到从文法开始符号 S出发，永远无法达到Q和R,所以关于Q和R的 规则是多余的，将其删除并化简，最后得到文法GS为：Sf abcS/ bcS / cSS f abcS/ 当然如果对文法非终结符排序的不同，最后得到的文法在形式上可能不一 样，但它们都是等价的。例如，如果对上述非终结符排序选为S、Q R,那么最后得到的文法 GR为： R f bcaR/ caR/ aR R f bcaR/ 容易证明上述两个文法是等价的。实验容：指明是否存在左递归，以及左递
6、归的类型。对于直接左递归，可将其改为直 接右递归；对于间接左递归(也称文法左递归)，则应按照算法给出非终结符不 同排列的等价的消除左递归后的文法。(应该有 n!种)实验代码与结果：#i nclude #in clude #i nclude #defi ne N 20char PNN;/ 存放文法char QN;/存放非终结符char RNN;/存放含有间接左递归的产生式char strNN, str1NN;int spN; /标记无用的产生式int r , count=0,count1=0;int direct(char PNN);/ 判断直接左递归int indirect(char PNN)
7、;/ 判断间接左递归void directRemove(char PNN); void in directRemove(char PNN); void perm(char strNN, i nt i, i nt n);/消除直接左递归/消除间接左递归/实现全排列int main()printf(请输入文法P产生式的个数:);sca nf(%d/n,&r);printf(请输入各条产生式，产生式的左部跟右部用- 连接:n);for(int k=O;kr;k+)sca nf(%s,Pk);if(strle n(Pk)=4) strcpy(str1cou nt1+,Pk);elsestrcpy(st
8、rcou nt+,Pk);if(direct(P)=1)directRemove(P);else if(in direct(P)=2)perm(str , 0, count-1);elseprintf(经判断该文法不含有左递归!n);return 0; int direct(char PNN) int flag=0;for(i nt i=O;i0)printf(经判断该文法含有直接左递归 return 1;elsereturn 0;int indirect(char PNN)int flag=0;for(i nt i=0;ir;i+)for(i nt k=1;k0) break;if(flag
9、0)printf(经判断该文法含有间接左递归 return 2;elsereturn 0;!n);!n);void directRemove(char PNN)int k,j=4;memset(sp,0,sizeof(sp);for(i nt i=0;ir;i+)if(Pi3=Pi0)Pi3=Pi2;Pi2=Pi1; Pi1=; while(Pij!=0) j+;Pij=Pi0;Pij+1=;spi=1; for(k=0;k4;k+) Prk=Pik;Prk=$; spr=1;elsej=3; while(Pij!=0)j+;Pij=Pi0;Pij+1=; spi=1;prin tf(n消除直
10、接左递归后的文法为:n);for(i nt t=0;t r+1;t+)if(spt=1)prin tf(%sn,Pt);void indirectRemove(char PNN)int flag,flag1=0,r仁r;int i,j,k,t,e=0,g=0;Qe=Pe0;for(i=1;ir;i+)int flag=O;for(i nt k=O;k=e;k+)if(PiO!=Qk) flag+;if(flag=(e+1)e+;Qe=PiO;prin tf(n非终结符序列为：sn, Q);for(j=0;je;j+)int nu mber=0;for(i nt z=0;z1)r1+;for(i
11、=0;ir;i+)for(k=1;k=4;s-) Pi+ks+t-1=Pi+ks;for(i nt u=3;u=4;s-) Pr1-1s+t-1=Pr1-1s;for(i nt u=3;u3+t;u+)Pr1-1u=Piu; break;flag 仁0;g+;memset(sp,0,sizeof(sp);for(i=0;ir1;i+)if(Pi0=Qe)if(Pi3=Pi0)Pi3=Pi2;Pi2=Pi1; Pi1=; while(Pij!=0) j+;Pij=Pi0;Pij+1=; spi=1; for(k=0;k4;k+)Pr1k=Pik;Pr1k=$; spr1=1;elsej=3;while(Pij!=O)j+；Pij=PiO； Pij+1=； spi=1;
