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

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

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

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

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

6、,#為"rj"，j為在文法G中某產生式A的序號。rj動作的含義是把當前文法符號棧頂的符號串歸約為A，并狀態棧指針從棧頂向下移動|的長度 , 文法符號棧從棧頂彈出|個符號，非終結符A變為當前面臨的符號。 若GO(Ik,A)Ij，則置GOTOk,A為"j"，其中A為非終結符，表示當前狀態為"k"時，遇文法符號A時狀態應轉向j，因此A移入文法符號棧，j移入狀態棧。 若項目SS·屬于Ik，則置ACTIONk,#為"acc"，表示接受。 凡不能用上述方法填入的分析表的元素，均應填上"報錯標志"。

7、為了表的清晰我們僅用空白表示錯誤標志。 （2）LR(0)項目    在文法G中每個產生式的右部適當位置添加一個圓點構成LR(0)項目。我們也可以根據圓點所在的位置和圓點后是終結符還是非終結符把LR(0)項目分為以下幾種： 移進項目    形如A·a,其中，V*，a VT，即圓點后面為終結符的項目為移進項目，對應狀態為移進狀態。分析時把a移進符號棧。 待約項目    形如A·B，其中,V* ，BVN，即圓點后面為非終結符的項目稱待約項目，它表明所對

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

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

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

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

12、EMAXSIZE; /ACTION表 正數=移進 負數=規約 100=接受 0 = 報錯int GOTOMAXSIZEMAXSIZE; /GOTO表 存放規約后的狀態int INum; /項目集規范族 個數利用二維數組Grammar來存儲所有的文法，利用 二維數組Generalization來存儲拓廣之后的所有文法。void getDFAGeneralization()/獲得文法的所有拓展 即.在文法在文法終點所有位置利用這個函數可以獲得所有文法的拓廣文法。在實現這個函數的同時需要調用另一個函數：void Insert_ponitosP(int num , char *s , char *G)

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

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

15、坐標是 規范族個數=INum，橫坐標是 終結符號 = VtNum。實現過程也如圖上述實驗功能所述，在此不再贅述。值得一提的是，按實驗功能所述，移進時應移進“si”表示狀態i進棧，規約“rj”表示按照第j個文法進行規約，我在這里小小的動一下腦筋，因為存入“si”相當于字符串，存儲和讀取都非常的麻煩，所以我利用數字的“+”“-”區分存儲和讀取，“+”為移進，“-”為規約。當然第一步是要初始化ACTION表全部賦值為“錯誤”的值，之后進行表的構建會將“錯誤”值替換。GOTO表的構建如同ACTION表的過程，細心就好。萬事俱備，只欠分析。最后一步也是最重要的一步就是分析函數void Analysis(

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