LR(0)分析法的實現(xiàn)編譯原理課程設(shè)計

0課程設(shè)計成績總成績教師簽名：《編譯原理》課程設(shè)計報告LR(0)分析法的實現(xiàn)學(xué)院(系):從2007年12月17日到2007年12月29日1 4 4 2通過課程設(shè)計進(jìn)一步理解高級語言在計算機(jī)中的執(zhí)行過程，加深對編譯原理中重點(diǎn)算法和編譯技術(shù)的理解，提高自己的編程能力，培養(yǎng)好的程序設(shè)計風(fēng)格。同時通過某種可視化編程語言的應(yīng)用，具備初步的Windows環(huán)境下2.課程設(shè)計的內(nèi)容及要求4.求出項目集規(guī)范族(即所有的狀態(tài))。6.給出LR(0)分析表。(1)總控程序，也可稱驅(qū)動程序。對所有的LR分析器總控程序都是相同的。(2)分析表或分析函數(shù)，不同的文法分析表將不同，同一個文法采用的LR分析器不同時，分析表將不同，分析表又可以分為動作表(ACTION)和狀(3)分析棧，包括文法符號棧和相應(yīng)的狀態(tài)棧，它們均是先進(jìn)后出棧。輸出帶總控程序分析表#3下推棧下推棧2)問題不在于"歷史"與“現(xiàn)實",而是如何基于"歷史"對未來“展3)一般只是使用簡化了的"展望"信息，以便能構(gòu)造一個可行的分析算6)下推棧內(nèi)的每個狀態(tài)都概括了從分析開始到歸約階段的全部“歷史”#狀態(tài)棧棧頂指針符號棧43.4LR分析器的總控程序總控程序的動作是根據(jù)當(dāng)前棧頂狀態(tài)Sm和讀頭下符號ai查表決定。分析器的動作就是由棧頂狀態(tài)和當(dāng)前輸入符號所決定。(2)歸約：action[i，a]=r：當(dāng)在棧頂形成句柄時，則歸約為相應(yīng)的非k棧和文法符號棧中自頂向下去掉R個符號，即棧指針SP減去R，并把A移入3.6LR(0)分析表構(gòu)造基本思想活前綴5在規(guī)范歸約的句型中，不含有句柄以后任何符號的前綴稱為活前綴。它有兩種情況：歸態(tài)活前綴和非歸態(tài)活前綴?；钋熬Y的尾部正好是句柄之尾，這時可以進(jìn)行歸約。歸約之后又會成為句柄尚未形成，需要繼續(xù)移進(jìn)若干符號之后才能形成句柄。3.7構(gòu)造LR(0)分析表的方法2)由于產(chǎn)生式右部的符號串就是句柄，若這些符號串都已進(jìn)棧，則表示它已處于歸態(tài)活前綴，若只有部分進(jìn)棧，則表示它處于非歸態(tài)活前綴。要想知道活前綴有多大部分進(jìn)棧了，可以為每個產(chǎn)生式構(gòu)造一個自動機(jī)，由它的狀態(tài)來記住當(dāng)前情況，這時，我們把“狀態(tài)”稱為“項目”。這些自動機(jī)的全體就是能識別所有活前綴的有限自動機(jī)。預(yù)期要?dú)w約的句柄是XYZ，但都未進(jìn)棧預(yù)期要?dú)w約的句柄是XYZ，僅X進(jìn)棧預(yù)期要?dú)w約的句柄是XYZ，僅XY進(jìn)棧64)有一個唯一的初態(tài)和一個唯一的接受態(tài)，但有若干個歸約態(tài)，表示有5)狀態(tài)反映了識別句柄的情況，即句柄的多大部分已進(jìn)棧，即知道了歷6)手工構(gòu)造文法的項目集規(guī)范3.7.4LR(0)項目集規(guī)范簇的自動構(gòu)造2、定義和構(gòu)造項目集的閉包}73.7.5LR(0)分析表的構(gòu)造算法ACTION[k,a]=Sj;即：移進(jìn)a,并轉(zhuǎn)向Ij狀態(tài)。2、若項目Aα→·∈Ik,則對任何終結(jié)符a(包括語句結(jié)束符#),置5、分析表中凡不能用步驟1至4填入信息的空白項，均置上“出錯標(biāo)彈出2*符號s'是現(xiàn)在的符號產(chǎn)生式非終結(jié)符號入棧輸出產(chǎn)生式彈出2*符號s'是現(xiàn)在的符號產(chǎn)生式非終結(jié)符號入棧輸出產(chǎn)生式輸入容號t足當(dāng)前輸人符號)ip指向下二個輸入符號8中的每個項中的每個項XY)非空有LRO項目集的構(gòu)造否到項自集中abCdEABE9A->cAA->dB->cBB->d下面是你輸入的文法G：G[E]:下面是生成的拓廣文法G'：G'[E]:LR(0)項目規(guī)范族如下：I?={8}文法的LR(0)分析表狀態(tài)abCd#EAB0S?S11243S74RR5bl6R?R7R?RR?RR?RR?RR?R89R?RR?R0XX文法開始符號Eab導(dǎo)入文法(I)保存文法(S)添加刪除關(guān)閉添加刪除EAB添加刪除Q出非終結(jié)符號集合為：{E,A,B}終結(jié)符符號集合為：{a,b,c,d}X關(guān)閉1步驟棧輸入串10#2#a3#ad#44#15并aco圖四：生成樹2歸約的時候應(yīng)該從狀態(tài)棧和