LR0語法分析器

1、 西 安 郵 電 大 學(xué) （計(jì)算機(jī)學(xué)院）課內(nèi)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： LR(0)語法分析器 專業(yè)名稱： 計(jì)算機(jī)科學(xué)與技術(shù)班 級： 計(jì)科1304 學(xué)生姓名： 裴世宇學(xué)號（8位）： 04131132（12）指導(dǎo)教師： 陳燕實(shí)驗(yàn)日期： 2016年05月15日一、實(shí)驗(yàn)?zāi)康?1.鞏固對語法分析的基本功能和原理的認(rèn)識。2. 通過對語法分析表的自動(dòng)生成加深語法分析表的認(rèn)識。3.理解并處理語法分析中的異常和錯(cuò)誤。二、實(shí)驗(yàn)環(huán)境VC+6.0Windows 7三、實(shí)驗(yàn)內(nèi)容 大多數(shù)用上下文無關(guān)文法描述的程序語言都可用LR分析器予以識別。LR分析法比算符優(yōu)先分析法或其他的“移進(jìn)-規(guī)約”技術(shù)更加廣泛，而且分析效率并不比他們差。

2、規(guī)范規(guī)約的關(guān)鍵問題是尋找句柄。一個(gè)LR分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出的存儲(chǔ)器（棧）點(diǎn)確定有限狀態(tài)自動(dòng)機(jī)。1. 通過設(shè)計(jì)、編制、陶氏一個(gè)典型的語法分析程序，實(shí)現(xiàn)對詞法分析程序所提供的單詞序列進(jìn)行語法檢查和結(jié)構(gòu)分析，進(jìn)一步掌握常用的語法分析方法。2. 選擇對各種常見程序語言都用的語法結(jié)構(gòu)，如賦值語句（尤其是表達(dá)式）作為分析對象，并且與所選語法分析方法要比較貼切。四、實(shí)驗(yàn)功能LR分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出存儲(chǔ)器（棧）的確定有限狀態(tài)自動(dòng)機(jī)。我們將把“歷史”和“展望”材料綜合地抽象成某些“狀態(tài)”。我們把棧的結(jié)構(gòu)看成是：LR分析器模型LR分析器的核心部分是一張分析表。這張分析表包括兩部分，意識“動(dòng)作”（A

3、CTION）表，另一個(gè)是“狀態(tài)轉(zhuǎn)換”（GOTO）表。他們都是二維數(shù)組。ACTION s , a 規(guī)定了當(dāng)狀態(tài)s面臨符號a時(shí)應(yīng)采取什么動(dòng)作。GOTO s ,X 規(guī)定了狀態(tài)。面對文法符號X（終結(jié)符或非終結(jié)符）時(shí)下一個(gè)狀態(tài)是什么。顯然，GOTOs,X定義了一個(gè)以文法符號為字母表的DFA。 對于任一文法GS，若SA，若是的前綴，則稱是G的一個(gè)活前綴。    活前綴與句柄的關(guān)系： 活前綴已含有句柄的全部符號，表明產(chǎn)生式A的 右部已出現(xiàn)在棧頂。 活前綴只含句柄的一部分符號如1表明A12的右部子串1已出現(xiàn)在棧頂，當(dāng)前期待從輸入串中看到2推出的符號。 活前綴不

4、含有句柄的任何符號，此時(shí)期望產(chǎn)生式A的右部所推出的符號串。（1）ACTON表和GOTO表的構(gòu)建每一項(xiàng)ACTION s , a 所規(guī)定的動(dòng)作不外是下述四種可能之一： 移進(jìn)     把Sj=GOTOSi，a移入到狀態(tài)棧，把a(bǔ)移入到文法符號棧。其中i，j表示狀態(tài)號。 歸約     當(dāng)在棧頂形成句柄為時(shí)，則用歸約為相應(yīng)的非終結(jié)符A，即文法中有A的產(chǎn)生式，若的長度為r(即|=r)，則從狀態(tài)棧和文法符號棧中自棧頂向下去掉r個(gè)符號，即棧指針SP減去r。并把A移入文法符號棧內(nèi)，Sj=GOTOSi，A移進(jìn)狀態(tài)棧，其中Si為修改指針后

5、的棧頂狀態(tài)。 接受acc    當(dāng)歸約到文法符號棧中只剩文法的開始符號S時(shí)，并且輸入符號串已結(jié)束即當(dāng)前輸入符是'#'，則為分析成功。 報(bào)錯(cuò) 當(dāng)遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號時(shí)，則報(bào)錯(cuò)，說明輸入串不是該文法能接受的句子。 若項(xiàng)目A·a屬于Ik且轉(zhuǎn)換函數(shù)GO(Ik,a)= Ij，當(dāng)a為終結(jié)符時(shí)則置ACTIONk,a為Sj，其動(dòng)作含意為將終結(jié)符a移進(jìn)符號棧，狀態(tài)j進(jìn)入狀態(tài)棧，(相當(dāng)狀態(tài)k時(shí)遇a轉(zhuǎn)向狀態(tài)j)。 若項(xiàng)目A· 屬于Ik，則對任何終結(jié)符a 和'#'號置ACTIONk,a和ACTIONk

6、,#為"rj"，j為在文法G中某產(chǎn)生式A的序號。rj動(dòng)作的含義是把當(dāng)前文法符號棧頂?shù)姆柎畾w約為A，并狀態(tài)棧指針從棧頂向下移動(dòng)|的長度 , 文法符號棧從棧頂彈出|個(gè)符號，非終結(jié)符A變?yōu)楫?dāng)前面臨的符號。 若GO(Ik,A)Ij，則置GOTOk,A為"j"，其中A為非終結(jié)符，表示當(dāng)前狀態(tài)為"k"時(shí)，遇文法符號A時(shí)狀態(tài)應(yīng)轉(zhuǎn)向j，因此A移入文法符號棧，j移入狀態(tài)棧。 若項(xiàng)目SS·屬于Ik，則置ACTIONk,#為"acc"，表示接受。 凡不能用上述方法填入的分析表的元素，均應(yīng)填上"報(bào)錯(cuò)標(biāo)志"。

7、為了表的清晰我們僅用空白表示錯(cuò)誤標(biāo)志。 （2）LR(0)項(xiàng)目    在文法G中每個(gè)產(chǎn)生式的右部適當(dāng)位置添加一個(gè)圓點(diǎn)構(gòu)成LR(0)項(xiàng)目。我們也可以根據(jù)圓點(diǎn)所在的位置和圓點(diǎn)后是終結(jié)符還是非終結(jié)符把LR(0)項(xiàng)目分為以下幾種： 移進(jìn)項(xiàng)目    形如A·a,其中，V*，a VT，即圓點(diǎn)后面為終結(jié)符的項(xiàng)目為移進(jìn)項(xiàng)目，對應(yīng)狀態(tài)為移進(jìn)狀態(tài)。分析時(shí)把a(bǔ)移進(jìn)符號棧。 待約項(xiàng)目    形如A·B，其中,V* ，BVN，即圓點(diǎn)后面為非終結(jié)符的項(xiàng)目稱待約項(xiàng)目，它表明所對

8、應(yīng)的狀態(tài)等待著分析完非終結(jié)符B所能推出的串歸約成B，才能繼續(xù)分析A右部的B后面部分。 歸約項(xiàng)目    形如A·其中V* ，即圓點(diǎn)在最右端的項(xiàng)目，稱歸約項(xiàng)目，它表明一個(gè)產(chǎn)生式的右部已分析完，句柄已形成可以歸約。 接受項(xiàng)目    形如SS·，其中SVN ，SS為拓廣文法的產(chǎn)生式，S為左部的產(chǎn)生式只有一個(gè)，因而它是歸約項(xiàng)目的特殊情況，對應(yīng)狀態(tài)稱為接受狀態(tài)，表明已分析成功。我們規(guī)定S·S 為初態(tài)。（3）LR(0)項(xiàng)目集規(guī)范族的構(gòu)造    對于構(gòu)成識別一個(gè)

9、文法活前綴的DFA項(xiàng)目集(狀態(tài))的全體我們稱之為這個(gè)文法的LR(0)項(xiàng)目集規(guī)范族。為此，在這里須引入LR(0)項(xiàng)目集的閉包函數(shù)CLOSURE和狀態(tài)轉(zhuǎn)換函數(shù)GO兩個(gè)概念。 閉包函數(shù)CLOSURE(I)的定義如下： a）I的項(xiàng)目均在CLOSURE(I)中。b）若A·B屬于CLOSURE(I)，則每一形如B·的項(xiàng)目也屬于CLOSURE(I)。c）重復(fù)b)直到不出現(xiàn)新的項(xiàng)目為止。即CLOSURE(I)不再擴(kuò)大。 轉(zhuǎn)換函數(shù)GO(I，X)的定義：     GO(I，X)CLOSURE(J)    其中：I為

10、包含某一項(xiàng)目集的狀態(tài)，X為一文法符號，X(VNVT)，J任何形如AX·的項(xiàng)目| A·X屬于I。     這樣就可以使用閉包函數(shù)和轉(zhuǎn)換函數(shù)構(gòu)造文法G的LR(0)項(xiàng)目集規(guī)范族，其步驟如下： a）置項(xiàng)目S·S為初態(tài)集的核，然后對核求閉包，CLOSURE(S·S）得到初態(tài)的項(xiàng)目集。 b）對初態(tài)集或其它所構(gòu)造的項(xiàng)目集應(yīng)用轉(zhuǎn)換函數(shù)GO(I，X)=CLOSURE(J)，求出新狀態(tài)J的項(xiàng)目集。c）重復(fù)b）直到不出現(xiàn)新的項(xiàng)目為止。5、 算法描述核心算法為構(gòu)建ACTION表和GOTO表，構(gòu)造文法的所有項(xiàng)目。全局變量的定義以及注釋cha

11、r AnalyzedArrayMAXSIZE; /字符串char VtArrayMAXSIZE; /終結(jié)符號數(shù)組int NumVt; /終結(jié)符號個(gè)數(shù)char VnArrayMAXSIZE; /非終結(jié)符號數(shù)組int NumVn; /非終結(jié)符號個(gè)數(shù)char GrammarMAXARRAYMAXARRAY;/文法 數(shù)組int NumGrammar;/文法 條數(shù)char GeneralizationMAXARRAYMAXARRAY;/拓廣所有文法,eg E->.aA E->a.A E->aA.int NumGeneralization;/拓廣文法 條數(shù)int ACTIONMAXSIZ

12、EMAXSIZE; /ACTION表 正數(shù)=移進(jìn) 負(fù)數(shù)=規(guī)約 100=接受 0 = 報(bào)錯(cuò)int GOTOMAXSIZEMAXSIZE; /GOTO表 存放規(guī)約后的狀態(tài)int INum; /項(xiàng)目集規(guī)范族 個(gè)數(shù)利用二維數(shù)組Grammar來存儲(chǔ)所有的文法，利用 二維數(shù)組Generalization來存儲(chǔ)拓廣之后的所有文法。void getDFAGeneralization()/獲得文法的所有拓展 即.在文法在文法終點(diǎn)所有位置利用這個(gè)函數(shù)可以獲得所有文法的拓廣文法。在實(shí)現(xiàn)這個(gè)函數(shù)的同時(shí)需要調(diào)用另一個(gè)函數(shù)：void Insert_ponitosP(int num , char *s , char *G)

13、 ， 將.插入到制定字符串的指定位置i 并存儲(chǔ)到 擴(kuò)展文法n位置這樣只需要進(jìn)行下標(biāo)的定位就可以實(shí)現(xiàn).的加入。之后，要進(jìn)行項(xiàng)目規(guī)范族的劃分，同一族的項(xiàng)目可以通過到達(dá)，所以利用遞歸算法可以很快實(shí)現(xiàn)項(xiàng)目集的劃分，在同一族中被選中的項(xiàng)目原本的下標(biāo)會(huì)出現(xiàn)靠后的情況，這時(shí)需要引入另一數(shù)組Used記錄使用情況，如果被選中過，則不可以被再次選中，反之可以進(jìn)入新的族。void CLOSURE_DFA(DFA *I , int num , char c , int n ,int *U) ，這個(gè)函數(shù)就是用來實(shí)現(xiàn)識別活前綴的DFA 項(xiàng)目集規(guī)范族的構(gòu)建。并且它是遞歸的函數(shù)。獲得了每個(gè)獨(dú)立的識別活前綴的DFA 項(xiàng)目集規(guī)范

14、族后，下一步，就是要將他們連接起來，連接的弧我們通過終結(jié)符號或非終結(jié)符號來實(shí)現(xiàn)。通過函數(shù)void Line_DFA(DFA *I)我們實(shí)現(xiàn)了連接項(xiàng)目集規(guī)范族。在實(shí)現(xiàn)過程中我們調(diào)用了int ArcX(char *pro1 , char *pro2) 函數(shù)，獲得該字符串的弧c后的結(jié)果 , 比較pro1和pro2是否只是.的位置不同來確定兩個(gè)字符串是否只是.的位置不同，因?yàn)槊總€(gè)項(xiàng)目都是不同的，當(dāng)只有.的位置不同時(shí)可以確定他們是可以通過某個(gè)字符弧連接到的，也可以延伸到規(guī)范族可以連接到。前期工作完成后接下來就是置表了。首先完成ACTION表。函數(shù)void Action(DFA *I)置Action表 縱

15、坐標(biāo)是 規(guī)范族個(gè)數(shù)=INum，橫坐標(biāo)是 終結(jié)符號 = VtNum。實(shí)現(xiàn)過程也如圖上述實(shí)驗(yàn)功能所述，在此不再贅述。值得一提的是，按實(shí)驗(yàn)功能所述，移進(jìn)時(shí)應(yīng)移進(jìn)“si”表示狀態(tài)i進(jìn)棧，規(guī)約“rj”表示按照第j個(gè)文法進(jìn)行規(guī)約，我在這里小小的動(dòng)一下腦筋，因?yàn)榇嫒搿皊i”相當(dāng)于字符串，存儲(chǔ)和讀取都非常的麻煩，所以我利用數(shù)字的“+”“-”區(qū)分存儲(chǔ)和讀取，“+”為移進(jìn)，“-”為規(guī)約。當(dāng)然第一步是要初始化ACTION表全部賦值為“錯(cuò)誤”的值，之后進(jìn)行表的構(gòu)建會(huì)將“錯(cuò)誤”值替換。GOTO表的構(gòu)建如同ACTION表的過程，細(xì)心就好。萬事俱備，只欠分析。最后一步也是最重要的一步就是分析函數(shù)void Analysis(

16、seq *L , char *S , DFA *I)，這是用來傳入待分析串并且返回結(jié)果是否符合LR0文法。函數(shù)的實(shí)現(xiàn)方法也如同實(shí)驗(yàn)功能所述，但是在結(jié)構(gòu)體的創(chuàng)建時(shí)要想好需要什么標(biāo)識符來標(biāo)識需要用到的信息，比如該規(guī)范族通過某字符連接到下一規(guī)范族的下標(biāo)需要存儲(chǔ)等等。6、 運(yùn)行結(jié)果第一組正常數(shù)據(jù)第二組正常數(shù)據(jù)不正常數(shù)據(jù)7、 調(diào)試情況初期設(shè)計(jì)思想比較迷茫，不知道LR0語法分析器的編寫從何開始，無從下手。所以只能從書上找到切入點(diǎn)。按照書上的要求和提示，我進(jìn)行了一步步的編寫，偶爾出現(xiàn)要尋找下標(biāo)的困難就要從存儲(chǔ)方式上找捷徑，就這樣程序逐漸豐滿起來。我為了保證每一個(gè)模塊的完整性，每次寫完一個(gè)函數(shù)就要測試一下測試用例，