资源描述：
《编译原理实验八非ll文法到ll文法的转换》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、实验八：非LL(1)文法到LL(1)文法的转换要求输入：非LL(1)文法输出:LL(1)文法二：实验目的1.掌握LL⑴文法2.熟悉运用C++语言对消除左递归的使用三：实验原理直接左递归的消除消除产生式屮的直接左递归是比较容易的。例如假设非终结符P的规则为P-*Pa/P其中，P是不以P开头的符号串。那么，我们可以把P的规则改写为如下的非直接左递归形式：P—PP’P'->aP'/e这两条规则和原来的规则是等价的，即两种形式从P推出的符号申是相同的。设有简单表达式文法G[E]:E-*E+T/TT-*T*E/FF-*(E)/I经消除直接左递归后得到如下文法：E-
2、TE,E’->+TE,/eT-*ET,r―抓/e卜(E)/I考虑更一般的情况，假定关于非终结符P的规则为P->Pai/Pa2/…/Pan/0,/02/…/Pm其巾，(T=l,2,n)都不为e，而每个p」(j=l，2,…，m)都不以P开头，将上述规则改写为如下形式即可消除P的直接左递归：卜p,r/p2I)’/"./pmrP’->a,P,/a2P,/.../anPV8间接左递归的消除直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表而上不存在左递归
3、，但却隐藏着左递归。例如，设有文法G[S]:S-*Qc/cQ->Rb/bR-*Sa/a虽不具有左递归，但S、Q、R都是左递归的，因为经过若干次推导有S^>Qc^>Rbc=>SabcQ=>Rb=>Sab^>QcabR=>Sa=>Qca^>Rhea就显现出其左递归性了，这就是间接左递归文法。消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。+如果一个文法不含有回路，即形如P=P的推导，也不含有以e为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。消除左递归算法：(1)把文法G的所有非终结符按任一顺序排
4、列，例如，A,，A2,…，An。(2)for(i=l;i〈=n;i++)for(j=l；j<=i—1；j++){把形如Ai—A」丫的产生式改写成Ai~*S,y/62y/•••/5ky其中Ai—S：/S2/•••/§、是关于的Aj全部规则；消除A：规则中的直接左递归；}(3)化简巾(2)所得到的文法，即去掉多余的规则。利用此算法可以将上述文法进行改写，来消除左递归。首先，令非终结符的排序为K、Q、S。对于K,不存在直接左递归。把R代入到Q中的相关规则中，则Q的规则变为Q—Sab/ab/b。代换后的Q不含有直接左递归，将其代入S,S的规则变为S—Sabc/a
5、he/be/c0此时，S存在直接左递归。在消除了S的直接左递归后，得到整个文法为：S-abeS’/beS’/cS'S’->abcS，/£Q->Sab/ab/bR-*Sa/a可以看到从文法开始符号S出发，永远无法达到Q和R,所以关于Q和R的规则是多余的，将其删除并化简，最后得到文法G[S]为：S->abcS，/beS’/cS’S’-abeSVe当然如果对文法非终结符排序的不同，最后得到的文法在形式上可能不一样，但它们都是等价的。例如，如果对上述非终结符排序选为S、Q、R,那么最后得到的文法G[R]为：R—bcaR’/caR’/aR'->bcaR’/e容易证
6、明上述两个文法是等价的。:据结构与算法typedefstructChomsky//定义一个产生式结构体{stringleft;//定义产生式的左部stringright;//定义产生式的右部}Chomsky;voidapart(Chomsky*p,inti)//分幵产生式左右部，i代表产生式的编号intzero(Chomsky*p)//0型文法intone(Chomsky*p)//l型文法inttwo(Chomsky*p)//2型文法intremove(Chomsky*p,intn)//消除左递归五：出错分析1：空符号表示错误，前后不一致2：文法判断参数
7、传递错误六：实验结果与分析不是二型文法的：L^J3.EASTIA计算价编译^B^^788Debug8.e)«b格褪:t⑴文翻左右邰Z
8、S］用f袭示，全用表示a-a是二型文法的:55.EASTIA计算价编译願读验788Debug8.exe，
9、d『B
10、■E:STU计算机編泽原理该验实验788Debug8.exe"1—»l"°~l
11、工;，译^^里蹲八：非LIX1〉文法到LIX1〉文法的转换▲用，《，表示
12、A-aBI一BbB-AcB-d实验继续...fe鼸S霧織l->aB卜〉Bb
13、B->dB'K->aBcBJ->bcBJ一〉tt
14、清按任意键继续-.
15、七：源代码#include#includ
