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

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