編譯原理實(shí)驗(yàn)八：非ll文法到ll文法的轉(zhuǎn)換

《編譯原理實(shí)驗(yàn)八：非ll文法到ll文法的轉(zhuǎn)換》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、實(shí)驗(yàn)八：非LL(1)文法到LL(1)文法的轉(zhuǎn)換一：要求輸入：非LL(1)文法輸出：LL(1)文法二：實(shí)驗(yàn)?zāi)康?．掌握LL(1)文法2．熟悉運(yùn)用C++語言對消除左遞歸的使用三：實(shí)驗(yàn)原理直接左遞歸的消除消除產(chǎn)生式中的直接左遞歸是比較容易的。例如假設(shè)非終結(jié)符P的規(guī)則為P→Pα/β其中，β是不以P開頭的符號串。那么，我們可以把P的規(guī)則改寫為如下的非直接左遞歸形式：P→βP’P’→αP’/ε這兩條規(guī)則和原來的規(guī)則是等價(jià)的，即兩種形式從P推出的符號串是相同的。設(shè)有簡單表達(dá)式文法G[E]：E→E+T/TT→T*F/FF→（E）/I經(jīng)消除直接左遞

2、歸后得到如下文法：E→TE’E’→+TE’/εT→FT’T’→*FT’/εF→（E）/I考慮更一般的情況，假定關(guān)于非終結(jié)符P的規(guī)則為P→Pα1/Pα2/…/Pαn/β1/β2/…/βm其中，αi（I＝1，2，…，n）都不為ε，而每個(gè)βj（j＝1，2，…，m）都不以P開頭，將上述規(guī)則改寫為如下形式即可消除P的直接左遞歸：P→β1P’/β2P’/…/βmP’P’→α1P’/α2P’/…/αnP’/ε間接左遞歸的消除直接左遞歸見諸于表面，利用以上的方法可以很容易將其消除，即把直接左遞歸改寫成直接右遞歸。然而文法表面上不存在左遞歸并不意味

3、著該文法就不存在左遞歸了。有些文法雖然表面上不存在左遞歸，但卻隱藏著左遞歸。例如，設(shè)有文法G[S]：S→Qc/cQ→Rb/bR→Sa/a11雖不具有左遞歸，但S、Q、R都是左遞歸的，因?yàn)榻?jīng)過若干次推導(dǎo)有SQcRbcSabcQRbSabQcabRSaQcaRbca就顯現(xiàn)出其左遞歸性了，這就是間接左遞歸文法。消除間接左遞歸的方法是，把間接左遞歸文法改寫為直接左遞歸文法，然后用消除直接左遞歸的方法改寫文法。如果一個(gè)文法不含有回路，即形如PP的推導(dǎo)，也不含有以ε為右部的產(chǎn)生式，那么就可以采用下述算法消除文法的所有左遞歸。消除左遞歸算法：（

4、1）把文法G的所有非終結(jié)符按任一順序排列，例如，A1，A2，…，An。（2）for（i＝1；i<=n；i++）for（j＝1；j<=i－1；j++）{把形如Ai→Ajγ的產(chǎn)生式改寫成Ai→δ1γ/δ2γ/…/δkγ其中Aj→δ1/δ2/…/δk是關(guān)于的Aj全部規(guī)則；消除Ai規(guī)則中的直接左遞歸；}（3）化簡由（2）所得到的文法，即去掉多余的規(guī)則。利用此算法可以將上述文法進(jìn)行改寫，來消除左遞歸。首先，令非終結(jié)符的排序?yàn)镽、Q、S。對于R，不存在直接左遞歸。把R代入到Q中的相關(guān)規(guī)則中，則Q的規(guī)則變?yōu)镼→Sab/ab/b。代換后的Q不含有

5、直接左遞歸，將其代入S，S的規(guī)則變?yōu)镾→Sabc/abc/bc/c。此時(shí)，S存在直接左遞歸。在消除了S的直接左遞歸后，得到整個(gè)文法為：S→abcS’/bcS'/cS'S’→abcS'/εQ→Sab/ab/bR→Sa/a可以看到從文法開始符號S出發(fā)，永遠(yuǎn)無法達(dá)到Q和R，所以關(guān)于Q和R的規(guī)則是多余的，將其刪除并化簡，最后得到文法G[S]為：S→abcS'/bcS’/cS'S'→abcS'/ε當(dāng)然如果對文法非終結(jié)符排序的不同，最后得到的文法在形式上可能不一樣，但它們都是等價(jià)的。例如，如果對上述非終結(jié)符排序選為S、Q、R，那么最后得到的文

6、法G[R]為：R→bcaR'/caR'/aR’R'→bcaR'/ε容易證明上述兩個(gè)文法是等價(jià)的。11四：數(shù)據(jù)結(jié)構(gòu)與算法typedefstructChomsky//定義一個(gè)產(chǎn)生式結(jié)構(gòu)體{stringleft;//定義產(chǎn)生式的左部stringright;//定義產(chǎn)生式的右部}Chomsky;voidapart(Chomsky*p,inti)//分開產(chǎn)生式左右部，i代表產(chǎn)生式的編號intzero(Chomsky*p)//0型文法intone(Chomsky*p)//1型文法inttwo(Chomsky*p)//2型文法intremove

7、(Chomsky*p,intn)//消除左遞歸五：出錯(cuò)分析1：空符號表示錯(cuò)誤，前后不一致2：文法判斷參數(shù)傳遞錯(cuò)誤11六：實(shí)驗(yàn)結(jié)果與分析不是二型文法的：是二型文法的：11七：源代碼#include#includeusingnamespacestd;11typedefstructChomsky//定義一個(gè)產(chǎn)生式結(jié)構(gòu)體{stringleft;//定義產(chǎn)生式的左部stringright;//定義產(chǎn)生式的右部}Chomsky;intn;//產(chǎn)生式總數(shù)stringstrings;//存儲(chǔ)產(chǎn)生式charq[2

8、0];voidapart(Chomsky*p,inti)//分開產(chǎn)生式左右部，i代表產(chǎn)生式的編號{intj;for(j=0;j