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

1、 淮北師范大學(xué) 編譯原理課程設(shè)計(jì) 課題名稱： LR(0)分析過(guò)程的實(shí)現(xiàn) 班 級(jí)： 2014級(jí)非師2班 學(xué) 號(hào)： 20141202109 姓 名 : 夏濤 目錄1課程設(shè)計(jì)的目的12課程設(shè)計(jì)的內(nèi)容及要求13實(shí)現(xiàn)原理13.1 LR分析器結(jié)構(gòu)13.2 LR分析法尋找可歸約句柄的依據(jù)23.3 LR分析器的核心23.4 LR分析器的總控程序33.5 具體過(guò)程分析如下：33.6 LR(0)分析表構(gòu)造基本思想43.7 構(gòu)造LR(0)分析表的方法43.7.1生成文法G的LR(0)項(xiàng)目43.7.2 由項(xiàng)目構(gòu)成識(shí)別文法活前綴的DFA43.7.3將所得DFA確定化43.7.4 LR(0)項(xiàng)目集規(guī)范簇的自動(dòng)構(gòu)造53.7

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

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

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

5、頭下符號(hào)a所應(yīng)采取的動(dòng)作。 b)轉(zhuǎn)向表(GOTO)GOTOS，X：若XÎVT，表示在當(dāng)前狀態(tài)下，讀入a應(yīng)轉(zhuǎn)向什么狀態(tài)；若XÎVN，表示當(dāng)前棧頂句柄歸約成X后，應(yīng)轉(zhuǎn)向什么狀態(tài)。c)棧結(jié)構(gòu)圖 d)分析表格式 3.4 LR分析器的總控程序總控程序的動(dòng)作是根據(jù)當(dāng)前棧頂狀態(tài)Sm和讀頭下符號(hào)ai查表決定。1、移進(jìn) 把(Sm, ai)的下一狀態(tài)S=GOTOSm，ai連同讀頭下符號(hào)推進(jìn)棧內(nèi)，棧頂成(S, ai)，而讀頭前進(jìn)一格；2、歸約 指用產(chǎn)生式Aa®進(jìn)行歸約。若a的長(zhǎng)度為g，則彈出棧頂g項(xiàng)，使棧頂狀態(tài)變?yōu)镾m- g，然后將(Sm- g,A)的下一狀態(tài)S=GOTOSm- g,A

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

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

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

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

10、74;XYZ 預(yù)期要?dú)w約的句柄是XYZ，僅XY進(jìn)棧A®X YZ 已處于歸態(tài)活前綴，XYZ可進(jìn)行歸約，這個(gè)項(xiàng)目也稱為歸約項(xiàng)目。(2)產(chǎn)生式右部符號(hào)串的長(zhǎng)度為n，則可以分解為n+1個(gè)項(xiàng)目。(3)產(chǎn)生式Ae®只有一個(gè)項(xiàng)目A®。由項(xiàng)目構(gòu)成識(shí)別文法活前綴的NFA1、將文法進(jìn)行拓廣，保證文法開始符號(hào)不出現(xiàn)在任何產(chǎn)生式右部，即增加產(chǎn)生式S®S，并令S® S作為初態(tài)項(xiàng)目； 2、凡圓點(diǎn)在串的最右邊的項(xiàng)目稱終態(tài)項(xiàng)目或稱歸約項(xiàng)目，而S® S 稱為接受項(xiàng)目；3、設(shè)項(xiàng)目i為X ®X1Xi-1XiXn, 項(xiàng)目j為X ®X1 Xi Xi1 Xn

11、 ，則從項(xiàng)目i畫一弧線射向j，標(biāo)記為Xi ， Xi是終結(jié)符則稱為移進(jìn)， Xi是 非終結(jié)符則稱為待約；4、若項(xiàng)目i為Xa®Ab，其中A是非終結(jié)符，則從i項(xiàng)目畫e弧射向所有A® g的項(xiàng)目，ÎgV*1)構(gòu)造出的NFA是包含有e串的NFA，可以使用子集法使之確定化，使之成為一個(gè)以項(xiàng)目集為狀態(tài)的DFA，這個(gè)DFA就是建立LR分析算法的基礎(chǔ)。2)相應(yīng)DFA的每個(gè)狀態(tài)是一個(gè)項(xiàng)目集，稱作LR(0)項(xiàng)目集，整個(gè)狀態(tài)集稱為L(zhǎng)R(0)項(xiàng)目集規(guī)范簇。3)在DFA的一個(gè)狀態(tài)對(duì)應(yīng)的項(xiàng)目集內(nèi)，每個(gè)項(xiàng)目是“等價(jià)”的，即從期待歸約的角度看相同。4)有一個(gè)唯一的初態(tài)和一個(gè)唯一的接受態(tài)，但有若干個(gè)歸約

12、態(tài)，表示有若干種活前綴的識(shí)別狀態(tài)。5)狀態(tài)反映了識(shí)別句柄的情況，即句柄的多大部分已進(jìn)棧，即知道了歷史情況。6)手工構(gòu)造文法的項(xiàng)目集規(guī)范3.7.4 LR(0)項(xiàng)目集規(guī)范簇的自動(dòng)構(gòu)造1、拓廣文法增加S ®S 產(chǎn)生式，使文法的開始符號(hào)不出現(xiàn)在任何產(chǎn)生式右部，從而保證有唯一的接受項(xiàng)目。2、定義和構(gòu)造項(xiàng)目集的閉包設(shè)I是拓廣文法G的一個(gè)項(xiàng)目集，如下定義和構(gòu)造I的閉包CLOSURE(I)：a) I的任何項(xiàng)目都屬于CLOSURE(I)；b) 若Aa®Bb屬于CLOSURE(I),B是非終結(jié)符，則對(duì)任何關(guān)于B的產(chǎn)生式Bg®，項(xiàng)目B®g也屬于CLOSURE(I);c) 重復(fù)

13、執(zhí)行步驟b)直到CLOSURE(I)不再擴(kuò)大為止。3、定義狀態(tài)轉(zhuǎn)換函數(shù)GO GO(I,X)定義為CLOSURE(J)，其中I,J都是項(xiàng)目集，X Î( VNÈ VT),J=任何形如Aa®Xb的項(xiàng)目| Aa®XÎbI。4、構(gòu)造LR(0)項(xiàng)目集規(guī)范族的算法PROC ITEMSETS-LR0 C:=CLOSURE(S ®S) /*初態(tài)項(xiàng)目集*/ DO FOR (對(duì)C中每個(gè)項(xiàng)目集I和G中每個(gè)文法符號(hào)X) IF (GO(I,X)非空且不屬于C) 把GO(I,X)加入C中 WHILE C仍然在擴(kuò)大3.7.5 LR(0)分析表的構(gòu)造算法設(shè)C=I0,I

14、1,In,以各項(xiàng)目集Ik(k0，,n)的k作為狀態(tài)序號(hào)，并以包含S ®S的項(xiàng)目集作為初始狀態(tài)，同時(shí)將G文法的產(chǎn)生式進(jìn)行編號(hào)。然后按下列步驟填寫ACTION表和GOTO表：1、若項(xiàng)目Aa®ab屬于Ik狀態(tài)且GO(Ik,a)= Ij,a為終結(jié)符，則置ACTIONk,a=Sj; 即：移進(jìn)a，并轉(zhuǎn)向Ij狀態(tài)。2、若項(xiàng)目Aa® ÎIk,則對(duì)任何終結(jié)符a(包括語(yǔ)句結(jié)束符),置ACTIONk,a=rj;即根據(jù)j號(hào)產(chǎn)生式進(jìn)行歸約，其中，j為產(chǎn)生式Aa® 的編號(hào)。3、若項(xiàng)目S ® S屬于Ik, 則置ACTIONk,=accept,簡(jiǎn)記為acc;4、若G

15、O(Ik ，A)= Ij,A是非終結(jié)符，則置GOTOk,A=j;5、分析表中凡不能用步驟1至4填入信息的空白項(xiàng)，均置上“出錯(cuò)標(biāo)志”。4算法實(shí)現(xiàn)流程圖5測(cè)試數(shù)據(jù)終結(jié)符abcd非終結(jié)符EAB開始符E產(chǎn)生式E->aAE->bBA->cAA->dB->cBB->d6結(jié)果輸出及分析下面是你輸入的文法G：非終結(jié)符號(hào)集合為： E, A, B 終結(jié)符符號(hào)集合為： a, b, c, d GE:(1) E->aA(2) E->bB(3) A->cA(4) A->d(5) B->cB(6) 

16、B->d下面是生成的拓廣文法G'：非終結(jié)符號(hào)集合為： $, E, A, B 終結(jié)符符號(hào)集合為： a, b, c, d G'E:(0) $->E(1) E->aA(2) E->bB(3) A->cA(4) A->d(5) B->cB(6) B->d該文法的項(xiàng)目如下：(1) $->.E(2) $->E.(3) E->.aA(4) E->a.A(5) E->aA.(6) E-&g

17、t;.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(0)項(xiàng)目規(guī)范族如下：I0 = 1, 3, 6 I1 = 2 I2 = 4, 9, 12 I3 = 7, 14, 17 I4 = 5 I5 =

18、10, 9, 12 I6 = 13 I7 = 8 I8 = 15, 14, 17 I9 = 18 I10 = 11 I11 = 16 文法的LR(0)分析表 狀態(tài) ACTIONGOTO a  b  c  d  #  E  A  B   0 S2  S3          

19、;1         1             acc            2       S5  S6     &

20、#160; 4      3       S8  S9          7   4 R1  R1  R1  R1  R1        &

21、#160;   5       S5  S6       10      6 R4  R4  R4  R4  R4            7

22、 R2  R2  R2  R2  R2            8       S8  S9          11   9 R6  R6  R6  R6  R6&