消除文法的左递归实验.doc

《消除文法的左递归实验.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理实验报告实验名称消除文法的左递归实验时间院系班级学号姓名1.试验目的◆掌握和理解消除左递归（包括直接左递归和间接左递归）在构建LL(1)文法的作用和目的◆掌握消除左递归（包括直接左递归和间接左递归）的方法和步骤。◆写出对于输入任意的上下文无关文法可以输出消除了左递归的等价文法。2.实验原理◆直接左递归的消除消除产生式中的直接左递归是比较容易的。例如假设非终结符P的规则为P→Pα/β其中，β是不以P开头的符号串。那么，我们可以把P的规则改写为如下的非直接左递归形式：P→βP’P’→αP’/ε考虑更一般的情况，假定关于非终结符P的规则为P

2、→Pα1/Pα2/…/Pαn/β1/β2/…/βm其中，αi（I＝1，2，…，n）都不为ε，而每个βj（j＝1，2，…，m）都不以P开头，将上述规则改写为如下形式即可消除P的直接左递归：P→β1P’/β2P’/…/βmP’P’→α1P’/α2P’/…/αnP’/ε◆间接左递归的消除直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递归，但却隐藏着左递归。消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后用

3、消除直接左递归的方法改写文法。◆消除左递归算法：把文法G的所有非终结符按任一顺序排列，例如，A1，A2，…，An。for（i＝1；i<=n；i++）for（j＝1；j<=i－1；j++）{把形如Ai→Ajγ的产生式改写成Ai→δ1γ/δ2γ/…/δkγ其中Aj→δ1/δ2/…/δk是关于的Aj全部规则；消除Ai规则中的直接左递归；}化简由（2）所得到的文法，即去掉多余的规则。3..实验内容◆利用消除左递归算法上机了实现对于输入任意的上下文无关文法可以输出消除了左递归的等价文法。4.实验心得◆通过本次试验更加清晰的理解了消除左递归在构建LL(1

4、)文法的重要作用，以及如何的消除文法中的左递归。在本次试验中原本想用P→Pα1

5、Pα2

6、…

7、Pαn

8、β1

9、β2

10、…

11、βm这种相同左部的产生式右部用或连接起来形式来消除左递归但是在实现上不是很容易，所以只有分开书写利用消除左递归的算法来实现.5.实验代码与结果源代码（C）#include#includestructNode//定义产生式结构{charleft[20];//产生式左部charright[50];//产生式右部intflags;}P[30];intcount=0;//产生式数量voidcreat

12、(){inti;printf("输入产生式数量:");scanf("%d",&count);for(i=0;i

13、******************");printf("你输入的产生式是:");for(i=0;i%s",P[i].left,P[i].right);}}voidReplace(char*ch1,charch2[20]){inti;charch3[20];strcpy(ch3,ch2);for(i=0;i<(int)strlen(ch3);i++)ch3[i]=ch3[i+1];strcat(ch1,ch3);}voidSort(char*ch1,charch2[2]){inti;

14、for(i=0;i<(int)strlen(ch1);i++)ch1[i]=ch1[i+1];strcat(ch1,ch2);}voidAnalysis()//消除间接左递归{inti,j,flags=0;charch[50];intnum=count;for(i=0;i

15、ight);strcpy(P[count].right,ch);P[count].flags=0;flags=1;count++;}}if(flags==1)P[i