編譯原理 LR(0)分析過程的實現(xiàn)

1、淮北師范大學編譯原理課程設計課題名稱：LR(O)分析過程的實現(xiàn)班級：2014級非師2班學號：20141202109姓名：夏濤目錄1課程設計的目的22課程設計的內(nèi)容及要求23實現(xiàn)原理23.1LR分析器結(jié)構(gòu)23.2LR分析法尋找可歸約句柄的依據(jù)33.3LR分析器的核心33.4LR分析器的總控程序43.5具體過程分析如下：43.6LR(0)分析表構(gòu)造基本思想.43.7構(gòu)造LR(0)分析表的方法53.7.1生成文法G的LR(0)項目53.7.2由項目構(gòu)成識別文法活前綴的DFA53.7.3將所得DFA確定化53.7.4 LR(0)項目集規(guī)范簇的自動構(gòu)造63.7.5 LR(0)分析表的構(gòu)造算法.74算法實

2、現(xiàn)流程圖75測試數(shù)據(jù)86結(jié)果輸出及分析97軟件運行環(huán)境及限制128心得體會139參考文獻131課程設計的目的通過課程設計進一步理解高級語言在計算機中的執(zhí)行過程，加深對編譯原理中重點算法和編譯技術(shù)的理解，提高自己的編程能力，培養(yǎng)好的程序設計風格。同時通過某種可視化編程語言的應用，具備初步的Windows環(huán)境下的編程思想。2課程設計的內(nèi)容及要求1. 可以使用任何語言來完成，例如：Java、C、C+。2. 文法采用常用的方式進行描述，例如：S-aA。3. 以文件方式讀取文法。4. 求出項目集規(guī)范族(即所有的狀態(tài))。5. 給出狀態(tài)間的關(guān)系。6. 給出LR(O)分析表。7. 給定的任意符號串判定是否是文

3、法中的句子，將分析過程用計算機打印出來。3實現(xiàn)原理3.1LR分析器結(jié)構(gòu)LR分析器由三個部分組成：(1) 總控程序，也可稱驅(qū)動程序。對所有的LR分析器總控程序都是相同的。(2) 分析表或分析函數(shù)，不同的文法分析表將不同，同一個文法采用的LR分析器不同時，分析表將不同，分析表又可以分為動作表(ACTION)和狀態(tài)轉(zhuǎn)換(GOTO)表兩個部分，它們都可用二維數(shù)組表示。(3) 分析棧，包括文法符號棧和相應的狀態(tài)棧，它們均是先進后出棧。32LR分析法尋找可歸約句柄的依據(jù)1）規(guī)范歸約的關(guān)鍵問題是找句柄。2）問題不在于“歷史”與“現(xiàn)實”，而是如何基于“歷史”對未來“展望”，“展望”可能存在相當多的可能性。3）

4、一般只是使用簡化了的“展望”信息，以便能構(gòu)造一個可行的分析算法。4）一個LR分析器實際上是一個帶有下推棧的確定的有限狀態(tài)自動機?？蓪⒁粋€“歷史”與這個“歷史”下的展望信息綜合為抽象的一個狀態(tài)5）下推?？捎糜诖娣庞伞皻v史”及相應“展望”信息形成的抽象狀態(tài)。6）下推棧內(nèi)的每個狀態(tài)都概括了從分析開始到歸約階段的全部“歷史”和“展望”信息，因此。棧頂?shù)臓顟B(tài)可用于決定當前動作，即，LR分析器的每步動作可由棧頂狀態(tài)和讀頭下符號唯一確定。3.3LR分析器的核心1、核心分析表2、分析表構(gòu)成a）動作表（ACTION）ACTIONS,a表示在當前狀態(tài)S下，面臨讀頭下符號a所應采取的動作。b）轉(zhuǎn)向表（GOTO）GO

5、TOS,X：若XeVT，表示在當前狀態(tài)下，讀入a應轉(zhuǎn)向什么狀態(tài)；若XeVN，表示當前棧頂句柄歸約成X后，應轉(zhuǎn)向什么狀態(tài)。c）棧結(jié)構(gòu)圖SoI頂指針狀態(tài)棧符號棧d）分析表格式動作GOTOala2-%AlA2.Am5051Sk3.4LR分析器的總控程序總控程序的動作是根據(jù)當前棧頂狀態(tài)Sm和讀頭下符號ai查表決定。1、移進把(Sm,ai)的下一狀態(tài)S'二GOTOSm,ai連同讀頭下符號推進棧內(nèi)，棧頂成(S',ai)，而讀頭前進一格；2、歸約指用產(chǎn)生式Aut進行歸約。若a的長度為丫，則彈出棧頂y項，使棧頂狀態(tài)變?yōu)镾m-y,然后將(Sm-y,A)的下一狀態(tài)S'=GOTOSm-y,A

6、連同非終結(jié)符A一起推進棧內(nèi)，棧頂變?yōu)?S',A)。讀頭不動，即不改變現(xiàn)行輸入符號。3、接受宣布分析成功，退出總控程序。4、報錯報告輸入串含有錯誤，調(diào)用相應錯誤錯誤處理程序。3.5具體過程分析如下：分析器的動作就是由棧頂狀態(tài)和當前輸入符號所決定。LR分析器結(jié)構(gòu)：其中:SP為棧指針，Si為狀態(tài)棧，Xi為文法符號棧。狀態(tài)轉(zhuǎn)換表用GOTOi,X=j表示，規(guī)定當棧頂狀態(tài)為i,遇到當前文法符號為X時應轉(zhuǎn)向狀態(tài)j，X為終結(jié)符或非終結(jié)符。ACTIONi，a規(guī)定了棧頂狀態(tài)為i時遇到輸入符號a應執(zhí)行。動作有四種可能：(1) 移進：actioni，a=Sj:狀態(tài)j移入到狀態(tài)棧，把a移入到文法符號棧，其中i,

7、j表示狀態(tài)號。(2) 歸約：actioni，a=rk:當在棧頂形成句柄時，則歸約為相應的非終結(jié)符A,即文法中有A->B的產(chǎn)生式，若B的長度為R(即|B|=R)，則從狀態(tài)棧和文法符號棧中自頂向下去掉R個符號，即棧指針SP減去R,并把A移入文法符號棧內(nèi)，j=GOTOi,A移進狀態(tài)棧，其中i為修改指針后的棧頂狀態(tài)。(3) 接受acc:當歸約到文法符號棧中只剩文法的開始符號S時，并且輸入符號串已結(jié)束即當前輸入符是'#'，則為分析成功。(4) 報錯:當遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號時，則報錯，說明輸入端不是該文法能接受的符號串。36LR(0)分析表構(gòu)造基本思想只根據(jù)

8、“歷史”信息識別呈現(xiàn)于棧頂?shù)木浔?，而不考慮“展望”信息的狀態(tài)?；钋熬Y1、定義在規(guī)范歸約的句型中，不含有句柄以后任何符號的前綴稱為活前綴。它有兩種情況：歸態(tài)活前綴和非歸態(tài)活前綴。2、歸態(tài)活前綴活前綴的尾部正好是句柄之尾，這時可以進行歸約。歸約之后又會成為另一句型的活前綴。3、非歸態(tài)活前綴句柄尚未形成，需要繼續(xù)移進若干符號之后才能形成句柄。37構(gòu)造LR(0)分析表的方法3.7.1生成文法G的LR(0)項目對文法G的每個產(chǎn)生式右部添加一個圓點，稱為G的一個LR(O)項目(簡稱項目)3.7.2由項目構(gòu)成識別文法活前綴的DFA1) 對于一個文法G，我們可以構(gòu)造一個有限自動機，它能識別G的所有活前綴。2)

9、 由于產(chǎn)生式右部的符號串就是句柄，若這些符號串都已進棧，則表示它已處于歸態(tài)活前綴，若只有部分進棧，則表示它處于非歸態(tài)活前綴。要想知道活前綴有多大部分進棧了，可以為每個產(chǎn)生式構(gòu)造一個自動機，由它的狀態(tài)來記住當前情況，這時，我們把“狀態(tài)”稱為“項目”。這些自動機的全體就是能識別所有活前綴的有限自動機。3.7.3將所得DFA確定化(1) 文法G的LR(0)項目生成在文法的每個產(chǎn)生式右部添加一個圓點，就成為G的一個LR(0)項目。例如，產(chǎn)生式ATXYZ對應四個項目AtXYZ預期要歸約的句柄是XYZ，但都未進棧AtXYZ預期要歸約的句柄是XYZ，僅X進棧AtXYZ預期要歸約的句柄是XYZ，僅XY進棧At

10、XYZ已處于歸態(tài)活前綴，XYZ可進行歸約，這個項目也稱為歸約項目。(2) 產(chǎn)生式右部符號串的長度為n則可以分解為n+1個項目。產(chǎn)生式A£T只有一個項目At。由項目構(gòu)成識別文法活前綴的NFA1、將文法進行拓廣，保證文法開始符號不出現(xiàn)在任何產(chǎn)生式右部，即增加產(chǎn)生式S、tS,并令S'tS作為初態(tài)項目；2、凡圓點在串的最右邊的項目稱終態(tài)項目或稱歸約項目，而S'tS稱為接受項目；3、設項目i為XTXlXi1XiXn,項目j為XtXIXiXi+1 Xn,則從項目i畫一弧線射向j,標記為Xi,Xi是終結(jié)符則稱為移進,Xi是非終結(jié)符則稱為待約；4、若項目i為XaTAp,其中A是非終結(jié)

11、符，則從i項目畫s弧射向所有Aty的項目，wyV*1) 構(gòu)造出的NFA是包含有s串的NFA,可以使用子集法使之確定化，使之成為一個以項目集為狀態(tài)的DFA,這個DFA就是建立LR分析算法的基礎(chǔ)。2) 相應DFA的每個狀態(tài)是一個項目集，稱作LR(O)項目集，整個狀態(tài)集稱為LR(0)項目集規(guī)范簇。3) 在DFA的一個狀態(tài)對應的項目集內(nèi)，每個項目是“等價”的，即從期待歸約的角度看相同。4) 有一個唯一的初態(tài)和一個唯一的接受態(tài)，但有若干個歸約態(tài)，表示有若干種活前綴的識別狀態(tài)。5) 狀態(tài)反映了識別句柄的情況，即句柄的多大部分已進棧，即知道了歷史情況。6) 手工構(gòu)造文法的項目集規(guī)范3.7.4LR(O)項目集

12、規(guī)范簇的自動構(gòu)造1、拓廣文法增加S'tS產(chǎn)生式，使文法的開始符號不出現(xiàn)在任何產(chǎn)生式右部，從而保證有唯一的接受項目。2、定義和構(gòu)造項目集的閉包設I是拓廣文法G'的一個項目集，如下定義和構(gòu)造I的閉包CLOSURE(I):a) I的任何項目都屬于CLOSURE(I)；b) 若AqtBB屬于CLOSURE(I),B是非終結(jié)符，則對任何關(guān)于B的產(chǎn)生式ByT,項目BTy也屬于CLOSURE(I);c) 重復執(zhí)行步驟b)直到CLOSURE(I)不再擴大為止。3、定義狀態(tài)轉(zhuǎn)換函數(shù)GOGO(I,X)定義為CLOSURE(J),其中I,J都是項目集，Xe(VNuVT),J=任何形如AutXB的項目

13、|AaTXepI。4、構(gòu)造LR(0)項目集規(guī)范族的算法PROCITEMSETS-LR0C:=CLOSURE(S'TS)/*初態(tài)項目集*/DOFOR(對C中每個項目集I和G'中每個文法符號X)IF(GO(I,X)非空且不屬于C)把GO(I,X)加入C中WHILEC仍然在擴大3.7.5LR(O)分析表的構(gòu)造算法設C=IO,Il,In,以各項目集Ik(k=O,n)的k作為狀態(tài)序號，并以包含S'TS的項目集作為初始狀態(tài)，同時將G'文法的產(chǎn)生式進行編號。然后按下列步驟填寫ACTION表和GOTO表：1、若項目Agtap屬于Ik狀態(tài)且GO(Ik,a)=Ij,a為終結(jié)符，則置

14、ACTIONk,a=Sj;即：移進a,并轉(zhuǎn)向Ij狀態(tài)。2、若項目Agtelk,則對任何終結(jié)符a(包括語句結(jié)束符#),置ACTIONk,a=rj;即根據(jù)j號產(chǎn)生式進行歸約，其中，j為產(chǎn)生式Aut的編號。3、若項目S'tS屬于Ik,則置ACTIONk,#=accept,簡記為acc;4、若GO(Ik，A)=Ij,A是非終結(jié)符，則置GOTOk,A=j;5、分析表中凡不能用步驟1至4填入信息的空白項，均置上“出錯標4算法實現(xiàn)流程圖5測試數(shù)據(jù)終結(jié)符abcd非終結(jié)符EAB開始符E產(chǎn)生式E->aAE->bBA->cAA->dB->cBB->d6結(jié)果輸出及分析下面是

15、你輸入的文法G：非終結(jié)符號集合為：E,A,B終結(jié)符符號集合為：a,b,c,dGE:(1) E->aA(2) E->bB(3) A->cA(4) A->d(5) B->cB(6) B->d下面是生成的拓廣文法G'：非終結(jié)符號集合為：$,E,A,B終結(jié)符符號集合為：a,b,c,dG'E:(0)$->E(1)E->aA(2)E->bB(3) A->cA(4) A->d(5) B->cB(6) B->d該文法的項目如下：(1)$->.E(2)$->E.(3)E->.aA(4)E->a.

16、A(5)E->aA.(6)E->.bB(7)E->b.B(8)E->bB.(9)A->.cA(10)A->c.A(11) A->cA.(12) A->.d(13) A->d.(14) B->.cB(15) B->c.B(16) B->cB.(17) B->.d(18) B->d.LR(O)項目規(guī)范族如下:I0=1,3,6I1=2I2=4,9,12I3=7,14,17I4=5I5=10,9,12I6=13I7=8I8=15,14,17I9=18I10=11I11=16文法的LR(0)分析表狀態(tài)ACTIONGOTO

17、abcd#EAB0S2S311acc2S5S643S8S974片片片片片5S5S6106R4R4R4R4R47R2R2R2R2R28S8S9119R6R6R6R6R610R3R3R3R3R311R5R5R5R5R514民lr(o)5£分靳表生成程序乎終結(jié)符集合|添加|刪除|終結(jié)符集合|添加|刪除|兇文法開始符號導入文法“1IJ產(chǎn)生式集合|添加|刪除|E->aAE->bBA->cAA->dB->cBB->d生成分析表(0清除文法(保存文法(S)關(guān)閉|圖一:讀入文法圖二：分析文法圖三：分析句子：ad圖四：生成樹7軟件運行環(huán)境及限制系統(tǒng)平臺：WindowsXP/2000軟件平臺：VC+6.08心得體會歸約的時候應該從狀態(tài)棧和文法符號棧中自頂向下去掉R個符號，即棧指針SP減去R,并把A移入文法符號棧內(nèi)，j=G