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