编译原理实验八：非ll(1)文法到ll(1)文法的转换

《编译原理实验八：非ll(1)文法到ll(1)文法的转换》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验八：非LL(1)文法到LL(1)文法的转换一：要求输入：非LL(1)文法输出：LL(1)文法二：实验目的1．掌握LL(1)文法2．熟悉运用C++语言对消除左递归的使用三：实验原理直接左递归的消除消除产生式中的直接左递归是比较容易的。例如假设非终结符P的规则为P→Pα/β其中，β是不以P开头的符号串。那么，我们可以把P的规则改写为如下的非直接左递归形式：P→βP’P’→αP’/ε这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。设有简单表达式文法G[E]：E→E+T/TT→T*F/FF→（E）/I经消除直接左递归后得到如下文法：E→

2、TE’E’→+TE’/εT→FT’T’→*FT’/εF→（E）/I考虑更一般的情况，假定关于非终结符P的规则为P→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[S]：S→Qc/cQ→Rb/bR→Sa/a11虽不具有左递归，但S、Q、R都是左递归的，因为经过若干次推导有SQcRbcSabcQRbSabQcabRSaQcaRbca就显现出其左递归性了，这就是间接左递归文法。消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。如果一个文法不含有回路，即形如PP的推导，也不含有以ε为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。消除左递归算法：（1）把文法G的所有非终结符按任一顺序排列，例如，A1，A2，…，A

4、n。（2）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规则中的直接左递归；}（3）化简由（2）所得到的文法，即去掉多余的规则。利用此算法可以将上述文法进行改写，来消除左递归。首先，令非终结符的排序为R、Q、S。对于R，不存在直接左递归。把R代入到Q中的相关规则中，则Q的规则变为Q→Sab/ab/b。代换后的Q不含有直接左递归，将其代入S，S的规则变为S→Sabc/abc/bc/c。此时，S存在直接左递

5、归。在消除了S的直接左递归后，得到整个文法为：S→abcS’/bcS'/cS'S’→abcS'/εQ→Sab/ab/bR→Sa/a可以看到从文法开始符号S出发，永远无法达到Q和R，所以关于Q和R的规则是多余的，将其删除并化简，最后得到文法G[S]为：S→abcS'/bcS’/cS'S'→abcS'/ε当然如果对文法非终结符排序的不同，最后得到的文法在形式上可能不一样，但它们都是等价的。例如，如果对上述非终结符排序选为S、Q、R，那么最后得到的文法G[R]为：R→bcaR'/caR'/aR’R'→bcaR'/ε容易证明上述两个文法是等价的。11四：数据结

6、构与算法typedefstructChomsky//定义一个产生式结构体{stringleft;//定义产生式的左部stringright;//定义产生式的右部}Chomsky;voidapart(Chomsky*p,inti)//分开产生式左右部，i代表产生式的编号intzero(Chomsky*p)//0型文法intone(Chomsky*p)//1型文法inttwo(Chomsky*p)//2型文法intremove(Chomsky*p,intn)//消除左递归五：出错分析1：空符号表示错误，前后不一致2：文法判断参数传递错误11六：实验结果与分

7、析不是二型文法的：是二型文法的：11七：源代码#include#includeusingnamespacestd;11typedefstructChomsky//定义一个产生式结构体{stringleft;//定义产生式的左部stringright;//定义产生式的右部}Chomsky;intn;//产生式总数stringstrings;//存储产生式charq[20];voidapart(Chomsky*p,inti)//分开产生式左右部，i代表产生式的编号{intj;for(j=0;j

8、h();j++)if(strings[j]=='-'){p[i].left=strings.s