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

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

2、現(xiàn)流程圖75測(cè)試數(shù)據(jù)86結(jié)果輸出及分析97軟件運(yùn)行環(huán)境及限制128心得體會(huì)139參考文獻(xiàn)131課程設(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)行描述，例如：S-aA。3. 以文件方式讀取文法。4. 求出項(xiàng)目集規(guī)范族(即所有的狀態(tài))。5. 給出狀態(tài)間的關(guān)系。6. 給出LR(O)分析表。7. 給定的任意符號(hào)串判定是否是文

3、法中的句子，將分析過(guò)程用計(jì)算機(jī)打印出來(lái)。3實(shí)現(xiàn)原理3.1LR分析器結(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)后出棧。32LR分析法尋找可歸約句柄的依據(jù)1）規(guī)范歸約的關(guān)鍵問(wèn)題是找句柄。2）問(wèn)題不在于“歷史”與“現(xiàn)實(shí)”，而是如何基于“歷史”對(duì)未來(lái)“展望”，“展望”可能存在相當(dāng)多的可能性。3）

4、一般只是使用簡(jiǎn)化了的“展望”信息，以便能構(gòu)造一個(gè)可行的分析算法。4）一個(gè)LR分析器實(shí)際上是一個(gè)帶有下推棧的確定的有限狀態(tài)自動(dòng)機(jī)?？蓪⒁粋€(gè)“歷史”與這個(gè)“歷史”下的展望信息綜合為抽象的一個(gè)狀態(tài)5）下推棧可用于存放由“歷史”及相應(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.3LR分析器的核心1、核心分析表2、分析表構(gòu)成a）動(dòng)作表（ACTION）ACTIONS,a表示在當(dāng)前狀態(tài)S下，面臨讀頭下符號(hào)a所應(yīng)采取的動(dòng)作。b）轉(zhuǎn)向表（GOTO）GO

5、TOS,X：若XeVT，表示在當(dāng)前狀態(tài)下，讀入a應(yīng)轉(zhuǎn)向什么狀態(tài)；若XeVN，表示當(dāng)前棧頂句柄歸約成X后，應(yīng)轉(zhuǎn)向什么狀態(tài)。c）棧結(jié)構(gòu)圖SoI頂指針狀態(tài)棧符號(hào)棧d）分析表格式動(dòng)作GOTOala2-%AlA2.Am5051Sk3.4LR分析器的總控程序總控程序的動(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)生式Aut進(jìn)行歸約。若a的長(zhǎng)度為丫，則彈出棧頂y項(xiàng)，使棧頂狀態(tài)變?yōu)镾m-y,然后將(Sm-y,A)的下一狀態(tài)S'=GOTOSm-y,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)串。36LR(0)分析表構(gòu)造基本思想只根據(jù)

8、“歷史”信息識(shí)別呈現(xiàn)于棧頂?shù)木浔豢紤]“展望”信息的狀態(tài)。活前綴1、定義在規(guī)范歸約的句型中，不含有句柄以后任何符號(hào)的前綴稱為活前綴。它有兩種情況：歸態(tài)活前綴和非歸態(tài)活前綴。2、歸態(tài)活前綴活前綴的尾部正好是句柄之尾，這時(shí)可以進(jìn)行歸約。歸約之后又會(huì)成為另一句型的活前綴。3、非歸態(tài)活前綴句柄尚未形成，需要繼續(xù)移進(jìn)若干符號(hào)之后才能形成句柄。37構(gòu)造LR(0)分析表的方法3.7.1生成文法G的LR(0)項(xiàng)目對(duì)文法G的每個(gè)產(chǎn)生式右部添加一個(gè)圓點(diǎn)，稱為G的一個(gè)LR(O)項(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的所有活前綴。2)

9、 由于產(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)生式ATXYZ對(duì)應(yīng)四個(gè)項(xiàng)目AtXYZ預(yù)期要?dú)w約的句柄是XYZ，但都未進(jìn)棧AtXYZ預(yù)期要?dú)w約的句柄是XYZ，僅X進(jìn)棧AtXYZ預(yù)期要?dú)w約的句柄是XYZ，僅XY進(jìn)棧At

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

11、符，則從i項(xiàng)目畫s弧射向所有Aty的項(xiàng)目，wyV*1) 構(gòu)造出的NFA是包含有s串的NFA,可以使用子集法使之確定化，使之成為一個(gè)以項(xiàng)目集為狀態(tài)的DFA,這個(gè)DFA就是建立LR分析算法的基礎(chǔ)。2) 相應(yīng)DFA的每個(gè)狀態(tài)是一個(gè)項(xiàng)目集，稱作LR(O)項(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è)歸約態(tài)，表示有若干種活前綴的識(shí)別狀態(tài)。5) 狀態(tài)反映了識(shí)別句柄的情況，即句柄的多大部分已進(jìn)棧，即知道了歷史情況。6) 手工構(gòu)造文法的項(xiàng)目集規(guī)范3.7.4LR(O)項(xiàng)目集

12、規(guī)范簇的自動(dòng)構(gòu)造1、拓廣文法增加S'tS產(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) 若AqtBB屬于CLOSURE(I),B是非終結(jié)符，則對(duì)任何關(guān)于B的產(chǎn)生式ByT,項(xiàng)目BTy也屬于CLOSURE(I);c) 重復(fù)執(zhí)行步驟b)直到CLOSURE(I)不再擴(kuò)大為止。3、定義狀態(tài)轉(zhuǎn)換函數(shù)GOGO(I,X)定義為CLOSURE(J),其中I,J都是項(xiàng)目集，Xe(VNuVT),J=任何形如AutXB的項(xiàng)目

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

14、ACTIONk,a=Sj;即：移進(jìn)a,并轉(zhuǎn)向Ij狀態(tài)。2、若項(xiàng)目Agtelk,則對(duì)任何終結(jié)符a(包括語(yǔ)句結(jié)束符#),置ACTIONk,a=rj;即根據(jù)j號(hào)產(chǎn)生式進(jìn)行歸約，其中，j為產(chǎn)生式Aut的編號(hào)。3、若項(xiàng)目S'tS屬于Ik,則置ACTIONk,#=accept,簡(jiǎn)記為acc;4、若GO(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é)果輸出及分析下面是

15、你輸入的文法G：非終結(jié)符號(hào)集合為：E,A,B終結(jié)符符號(hào)集合為：a,b,c,dGE:(1) E->aA(2) E->bB(3) A->cA(4) A->d(5) B->cB(6) B->d下面是生成的拓廣文法G'：非終結(jié)符號(hào)集合為：$,E,A,B終結(jié)符符號(hào)集合為：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該文法的項(xiàng)目如下：(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)項(xiàng)目規(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é)符集合|添加|刪除|兇文法開始符號(hào)導(dǎo)入文法“1IJ產(chǎn)生式集合|添加|刪除|E->aAE->bBA->cAA->dB->cBB->d生成分析表(0清除文法(保存文法(S)關(guān)閉|圖一:讀入文法圖二：分析文法圖三：分析句子：ad圖四：生成樹7軟件運(yùn)行環(huán)境及限制系統(tǒng)平臺(tái)：WindowsXP/2000軟件平臺(tái)：VC+6.08心得體會(huì)歸約的時(shí)候應(yīng)該從狀態(tài)棧和文法符號(hào)棧中自頂向下去掉R個(gè)符號(hào)，即棧指針SP減去R,并把A移入文法符號(hào)棧內(nèi)，j=G