编译原理实验报告
实验名称：消除左递归______________实验时间：20150527________________
院班学姓
系：管理信息工程学院______________级：12级计算机科学技术____________号：201104080112___________________名：王博一__________________
1、实验目的：理解LL1文法中消除左递归的原理2、实验原理：
1．直接左递归的消除消除产生式中的直接左递归是比较容易的。例如假设非终结符P的规则为：P→Pαβ其中，β是不以P开头的符号串。那么，我们可以把P的规则改写为如下的非直接左递归形式：P→βP’P’→αP’ε这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。设有简单表达式文法GE：
fE→ETTT→TFFF→（E）I经消除直接左递归后得到如下文法：E→TE’E’→TE’εT→FT’T’→FT’εF→（E）I考虑更一般的情况，假定关于非终结符P的规则为P→Pα1Pα2…Pα
β1β2…βm其中，αi（I＝1，2，…，
）都不为ε，而每个βj（j＝1，2，…，m）都不以P开头，将上述规则改写为如下形式即可消除P的直接左递归：P→β1P’β2P’…βmP’P’→α1P’α2P’…α
P’ε2．间接左递归的消除直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递归，但却隐藏着左递归。例如，设有文法GS：S→QccQ→RbbR→Saa虽不具有左递归，但S、Q、R都是左递归的，因为经过若干次推导有SQcRbcSabcQRbSabQcabRSaQcaRbca就显现出其左递归性了，这就是间接左递归文法。消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。如果一个文法不含有回路，即形如PP的推导，也不含有以ε为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。消除左递归算法：（1）把文法G的所有非终结符按任一顺序排列，例如，A1，A2，…，A
。（2）for（i＝1；i
；i）for（j＝1；ji－1；j）把形如Ai→Ajγ的产生式改写成Ai→δ1γδ2γ…δkγ其中Aj→δ1δ2…δk是关于的Aj全部规则；消除Ai规则中的直接左递归；
f（3）化简由（2）所得到的文法，即去掉多余的规则。利用此算法可以将上述文法进行改写，来消除左递归。首先，令非终结符的排序为R、Q、S。对于R，不存在直接左递归。把R代入到Q中的相关规则中，则Qr