编译基本知识实验-消除文法的左递归

1、编译原理实验报告实验名称:消除文法的左递归实验时间:2015/5/28院系：管理与信息工程学院班级:12级计算机科学与技术学号：201201020124姓名：刘杨凡1.实验目的:输入：任意的上下文无关文法。输出：消除了左递归的等价文法。2.实验原理:1 .直接左递归的消除假设非终结符P的规则为:其中，P是不以P开头的符号串。那么，我们可以把 P的规则改写为如下的非直PBP接左递归形式:Pa P/ 这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。设有简单表达式文法GE:E E+T/ TTT*F/ FFt( E) / I经消除直接左递归后得到如下文法：E+TE / TFTT*F

2、T / F(E) / I考虑更一般的情况，假定关于非终结符 P 的规则为P P a / P a /I P an / Bi / B2 / / Bm其中，ai （1= 1 , 2，n）都不为，而每个Bj （j = 1, 2，m ）都不以P 开头，将上述规则改写为如下形式即可消除 P 的直接左递归：PBi P/B2 p/ Bm PPa1P/ a2 P/ an P/2间接左递归的消除直接左递归见诸于表面， 利用以上的方法可以很容易将其消除， 即把直接左 递归改写成直接右递归。 然而文法表面上不存在左递归并不意味着该文法就不存 在左递归了。有些文法虽然表面上不存在左递归，但却隐藏着左递归。例如，设 有文

3、法 GS ：SQc/ cQRb/ bRf Sa/ a虽不具有左递归，但 S、 Q 、 R 都是左递归的，因为经过若干次推导有Qc RbcSabcRb SabQcabSa QcaRbca就显现出其左递归性了，这就是间接左递归文法。消除间接左递归的方法是， 把间接左递归文法改写为直接左递归文法， 然后 用消除直接左递归的方法改写文法。如果一个文法不含有回路，即形如 P P的推导，也不含有以为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。消除左递归算法：把文法G的所有非终结符按任一顺序排列，例如， Ai, A2,An 。for(i = 1 ； iv=n ； i+ )for(j = 1;

4、j=i - 1; j+ )把形如Aif Aj 丫的产生式改写成AifSl 丫 /出丫 / Sk 丫其中Ajf/ 2 / Sk是关于的Aj全部规贝U;消除Ai规则中的直接左递归;化简由（ 2）所得到的文法，即去掉多余的规贝。利用此算法可以将上述文法进行改写，来消除左递归。首先，令非终结符的排序为 R、Q、S。对于R,不存在直接左递归。把 R代入到Q中的相关规则中，贝U Q的规则变为Qf Sab/ ab/ b 。代换后的Q不含有直接左递归，将其代入S, S的规则变为Sf Sabc/abc/ bc/ c 。此时，S存在直接左递归。在消除了 S的直接左递归后，得到整个文法为:SfabcS/ bcS/

5、cSS f abcS/ QfSab/ ab/ bRfSa/ a可以看到从文法开始符号 S出发，永远无法达到Q和R,所以关于Q和R的规则是多余的，将其删除并化简，最后得到文法GS为:SfabcS/ bcS / cSS f abcS/当然如果对文法非终结符排序的不同，最后得到的文法在形式上可能不一样，但它们都是等价的。例如，如果对上述非终结符排序选为S、Q、R,那么最后得到的文法GR为:RfbcaR/ caR/ aRR fbcaR/ 容易证明上述两个文法是等价的。3. 实验内容:消除左递归算法:把文法G的所有非终结符按任一顺序排列，例如， Ai, A2,An 。5)for (i = 1 ； iv=

6、n ； i+ )for(j = 1; j=i - 1; j+ )把形如Af Aj 丫的产生式改写成AiSl 丫 / 2 丫 / k 丫 其中Aj7i / 2 /k是关于的Aj全部规则;消除Ai规则中的直接左递归;化简由（ 2）所得到的文法，即去掉多余的规则。利用此算法可以将上述文法进行改写，来消除左递归。注意事项：指明是否存在左递归， 以及左递归的类型。 对于直接左递归， 可将其改为直接右递归;对于间接左递归（也称文法左递归） ，则应按照算法给出非终结符不 同排列的等价的消除左递归后的文法。（应该有n!种）4.代码实现（ C 语言）：#include stdafx.h #include #in

7、clude #define N 20int r;/ 实际输入的规则的个数char PNN;/ 规则集char QN;/ 规则集 ,存放间接左递归消除后的部分规则char RNN;/ 用来存放规则的初始值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;i0)

8、printf（ 经判断该文法含有直接左递归 !n）;return 1;/ 属于直接接左递归elsereturn 0;/ 不属于直接左递归int indirect(char PNN)/ 定义间接左递归函数int flag=0;for(int i=0;ir;i+)for(int k=1;k0)break;if(flag0)printf（ 经判断该文法含有间接左递归 !n）;return 2;/ 属于间接左递归elsereturn 0;/ 不属于间接左递归void directRemove(char PNN)/ 定义消除直接左递归的函数int j=4;for(int i=0;ir;i+)if(Pi3

9、=Pi0)Pi3=Pi2;Pi2=Pi1;Pi1=;while(Pij!=0)j+;Pij=Pi0;Pij+1=;for(int k=0;k4;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;tr+1;t+)printf(%sn,Pt);void indirectRemove(char PNN)/ 定义消除间接左递归的函数int flag,flag1=0,copy=

10、r;int e=0;Qe=Pe0;/ 统计规则中不同的左部for(int z=0;zr;z+)for(int i=1;ir;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;j1)copy+;/ 如果有相同左部则规则总数加for(i=0;ir;i+)for(int k=1;k=4;s-)Pi+ks+t-1=Pi+ks;for(int u=3;u3+t;u+)Pi+ku=Piu;break;else if(Pi0=Rg3)&(flag1=1)for(int y=0;Rg

11、y!=0;y+)Pcopy-1y=Rgy;int m=3;for(int u=3;u=4;s-)Pcopy-1s+t-1=Pcopy-1s;Pcopy-1u=Piu;break;flag1=0;g+;printf（ 首次消除间接左递归后的直接左递归文法为 :n）;for(int t=0;tcopy;t+)printf(%sn,Pt);printf(n);for(i=0;icopy;i+)if(Pi0=Qe)if(Pi3=Pi0)Pi3=Pi2;Pi2=Pi1;Pi1=;while(Pij!=0)j+;Pij=Pi0;Pij+1=;for(int k=0;k4;k+)/ 包含空的一条规则Pcop

12、yk=Pik;Pcopyk=*;elsej=3;while(Pij!=0)j+;Pij=Pi0;Pij+1=;printf（ 再次消除直接左递归后的文法为 :n）;printf(n);printf(* 代表 )n);printf(n);printf(%sn,Pt);for(t=0;t 连接，规则间用空格隔开);printf(n);for(int k=0;kr;k+)scanf(%s,Pk);printf(n);printf（ 即输入的文法规则为 :n）;for(k=0;kSa S-Jb即输入的文法规则为：S-EaK-b经判断该文法含有直番左递归.悄除S接左递归后的文注为:骨-朋AMS-s一*PrcsH diy hey tv vviH inue消除文法间接左递归实例1如下:谑輸入上T文无关的文法规则F的T就:4谨输入&杂规则h规则的左部跟占部