課程設(shè)計---生成lr分析表的算法實現(xiàn)

1、<p><b>　　課 程 設(shè) 計</b></p><p><b>　　課程設(shè)計任務(wù)書</b></p><p>　　題 目: 生成LR分析表的算法實現(xiàn) </p><p><b>　　初始條件：</b></p><p>　　程序設(shè)計語言:主要使用C語言的開發(fā)工具

2、，或者采用LEX、YACC等工具，也可利用其他熟悉的開發(fā)工具。算法：可以根據(jù)《編譯原理》課程所講授的算法進(jìn)行設(shè)計。</p><p>　　要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求，說明書撰寫等具體要求）</p><p>　　明確課程設(shè)計的目的和重要性，認(rèn)真領(lǐng)會課程設(shè)計的題目，讀懂課程設(shè)計指導(dǎo)書的要求，學(xué)會設(shè)計的基本方法與步驟，學(xué)會如何運(yùn)用前修知識與收集、歸納相關(guān)資料解決具體問題

3、的方法。嚴(yán)格要求自己，要獨(dú)立思考，按時、獨(dú)立完成課程設(shè)計任務(wù)。</p><p>　　主要功能包括：利用語法分析中LR分析法的原理和思想對給定的文法進(jìn)行分析，識別出文法活前綴的，構(gòu)造項目集規(guī)范族，最后輸出文法的分析表。</p><p>　　進(jìn)行總體設(shè)計，詳細(xì)設(shè)計：包括算法的設(shè)計和數(shù)據(jù)結(jié)構(gòu)設(shè)計。系統(tǒng)實施、調(diào)試，合理使用出錯處理程序。</p><p>　　設(shè)計報告：要求層

4、次清楚、整潔規(guī)范、不得相互抄襲。正文字?jǐn)?shù)不少于0.3萬字。包含內(nèi)容：</p><p><b>　　①課程設(shè)計的題目。</b></p><p><b>　　②目錄。</b></p><p>　?、壅模喊ㄒ?、需求分析、總體設(shè)計及開發(fā)工具的選擇，設(shè)計原則（給出語法分析方法及中間代碼形式的描述、文法和屬性文法的設(shè)計），數(shù)據(jù)結(jié)

5、構(gòu)與模塊說明（功能與流程圖）、詳細(xì)的算法設(shè)計、軟件調(diào)試、軟件的測試方法和結(jié)果、有關(guān)技術(shù)的討論、收獲與體會等。</p><p><b>　　④結(jié)束語。</b></p><p><b>　　⑤參考文獻(xiàn)。</b></p><p>　　⑥附錄：軟件清單（或者附盤）。</p><p><b>　　時

6、間安排：</b></p><p>　　消化資料、系統(tǒng)調(diào)查、形式描述1天</p><p>　　系統(tǒng)分析、總體設(shè)計、實施計劃3天</p><p>　　撰寫課程設(shè)計報告書1天</p><p>　　指導(dǎo)教師簽名： 2011年 12月 30日</p><p>　　系主任（或責(zé)任教

7、師）簽名： 2011年 12月 30日 </p><p><b>　　1、 引言1</b></p><p><b>　　2、 系統(tǒng)概述2</b></p><p><b>　　2.1 目的2</b></p><p>　　2.2 設(shè)計任務(wù)2</p>

8、<p>　　2.3 設(shè)計環(huán)境與工具2</p><p><b>　　3、總體設(shè)計3</b></p><p>　　3.1 設(shè)計原理3</p><p>　　3.1.1 識別文法活前綴的及的狀態(tài)圖3</p><p>　　3.1.2 項目集規(guī)范族的構(gòu)造4</p><p>　　3.1.2

9、分析表的構(gòu)造4</p><p>　　3.2 簡要的分析與概要設(shè)計5</p><p>　　4、詳細(xì)的算法描述7</p><p><b>　　4.1模塊說明7</b></p><p>　　4.2 程序具體設(shè)計8</p><p>　　5、測試方法和測試結(jié)果9</p><p

10、><b>　　6 個人總結(jié)12</b></p><p>　　生成LR分析表的算法實現(xiàn)</p><p><b>　　引言</b></p><p>　　作為計算機(jī)專業(yè)的一門重要的專業(yè)課程，《編譯原理》旨在介紹編譯程序構(gòu)造的一般原理和基本方法 。課程內(nèi)容主要包括語言和文法、詞法分析、語法分析、語法制導(dǎo)翻譯、中間代碼生成、

11、存儲管理、代碼優(yōu)化和目標(biāo)代碼生成等。 </p><p>　　語法分析是程序編譯過程的第二階段，是編譯器前端的核心組成部分，在編譯系統(tǒng)中起到了至關(guān)重要的作用。語法分析程序從掃描程序中獲取記號形式的源代碼，并完成定義程序結(jié)構(gòu)的語法分析，這與自然語言中句子的語法分析類似。語法分析定義了程序的結(jié)構(gòu)元素及其關(guān)系。一般來說，常用的語法分析方法包括自底向上的語法分析與自頂向下的語法分析。相比于自頂向下的語法分析方法，自底向上的

12、語法分析方法對將要分析的源程序有著更大的分析空間，從而受到了廣泛的運(yùn)用。</p><p>　　自底向上語法分析方法是一種移進(jìn)-規(guī)約過程，它的主要思想是正規(guī)規(guī)約，及最右推導(dǎo)的逆過程，在當(dāng)前分析的棧頂符號串形成句柄時就采取規(guī)約動作，因此最終目標(biāo)是如何在分析過程中確定句柄。LR分析法是給出一種能根據(jù)當(dāng)前分析棧中的符號串和向右順序查看k個符號串就可以唯一地確定分析器動作：是移進(jìn)還是規(guī)約，采用哪條產(chǎn)生式。LR(0)分析是自

13、底向上LR類語法分析的基礎(chǔ)，LR(0)分析器是在分析過程中，不需要向后查看輸入串符號，因此它對文法的限制較大。</p><p>　　LR(0)最終存在的問題和需要解決的問題是在構(gòu)造LR(0)分析表的時候，在LR(0)項目集規(guī)范族中，有移進(jìn)項目和規(guī)約項目、規(guī)約項目和規(guī)約項目同時存在的現(xiàn)象，形成移進(jìn)-規(guī)約沖突和規(guī)約-規(guī)約沖突，直接導(dǎo)致語法分析器無法在某一狀態(tài)進(jìn)行移進(jìn)還是規(guī)約。為了能夠解決這一問題，我們需要再向后查看一

14、個輸入字符（也就是當(dāng)前字符的FOLLOW集）以確定下一步操作是否能夠進(jìn)行。這就產(chǎn)生了我們說的LR（1）分析方法。但是由于難度的問題，本文只考慮LR（0）分析方法。</p><p><b>　　系統(tǒng)概述</b></p><p><b>　　2.1 目的</b></p><p>　　對任意給定的上下文無關(guān)文法G，構(gòu)造其項目集族

15、，并且在此基礎(chǔ)上進(jìn)一步構(gòu)造其分析表。希望通過設(shè)計、編制、調(diào)試一個 語法分析程序，加深對語法及語義分析程序的理解，加深對編譯原理的理解，培養(yǎng)自己動手能力。 通過實現(xiàn)輸入一個給定的文法生成分析表，從而實現(xiàn)語言的語法分析，也為后面的語義分析做基礎(chǔ)。</p><p><b>　　2.2 設(shè)計任務(wù)</b></p><p>　　利用語法分析中LR分析法的原理和思想對給定的文法進(jìn)行

16、分析，識別出文法活前綴的，構(gòu)造項目集規(guī)范族，最后輸出文法的分析表。</p><p>　　2.3 設(shè)計環(huán)境與工具</p><p>　　程序開發(fā)環(huán)境：Eclipse </p><p>　　程序設(shè)計語言：java </p><p><b>　　3、總體設(shè)計</b></p><p><b>　　

17、3.1 設(shè)計原理</b></p><p>　　總的來說，分析表構(gòu)造的主要問題如下：</p><p>　　識別文法活前綴的及的狀態(tài)圖</p><p>　　項目集規(guī)范族的構(gòu)造；</p><p><b>　　分析表的構(gòu)造；</b></p><p>　　它們的主要設(shè)計原理如下：</p&g

18、t;<p>　　3.1.1 識別文法活前綴的及的狀態(tài)圖</p><p><b>　　活前綴</b></p><p>　　如果一個規(guī)范句型的前綴中不含句柄后的任何符號，則稱它是該規(guī)范句型的一個活前綴。換句話說，活前綴是一個或若干個規(guī)范句型的前綴，在規(guī)范歸約過程中的任何時刻只要已分析過的部分即在符號棧中的符號串均為規(guī)范句型的活前綴，則表明輸入串已被分析過的部

19、分是該文法某規(guī)范句型的一個正確部分。</p><p><b>　　項目</b></p><p>　　為了構(gòu)造活前綴的，我們首先需要構(gòu)造文法的項目級。在文法的每個文法的右部適當(dāng)位置添加一個圓點(diǎn)構(gòu)成項目。對于文法中的每個產(chǎn)生式的項目集的大小是由其產(chǎn)生式的長度決定的，長度是其右部符號的長度加1。例如產(chǎn)生式：A→aBC，有4個LR(0)項目：</p><p

20、><b>　　活前綴的DFA</b></p><p>　　一般構(gòu)造識別活前綴的NFA的兩種方法：</p><p>　　第一種方法是求出文法的所有產(chǎn)生式的LR(0)項目，每個項目都為NFA的一個狀態(tài)，按一定規(guī)則構(gòu)造識別活前綴的NFA，再確定化為DFA。</p><p>　　第二種方法是把拓廣文法的第一個項目{S′→ ? S}作為初態(tài)集的核，

21、通過求核的閉包和轉(zhuǎn)換函數(shù)，求出LR(0)項目集規(guī)范族，再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系得到識別活前綴的DFA。</p><p>　　在此，我采用的是第二種方式求的狀態(tài)圖。</p><p>　　3.1.2 項目集規(guī)范族的構(gòu)造</p><p>　　此處，我采用構(gòu)造項目集I的閉包來構(gòu)造一個文法的項目規(guī)范簇。假定</p><p>　　是文法的任一項

22、目集，定義和構(gòu)造的閉包的算法：</p><p>　?。?）的任何項目都屬于；</p><p>　?。?）若屬于，那么，對任何關(guān)于的產(chǎn)生式，項目也屬于；</p><p>　?。?）重復(fù)執(zhí)行上述兩個步驟直至不再增大。</p><p>　　其中初始 ，為對文法進(jìn)行拓廣構(gòu)造而引進(jìn)的不出現(xiàn)在中的非終結(jié)符。</p><p>　　然

23、后，定義狀態(tài)轉(zhuǎn)換函數(shù)，函數(shù)是通過DFA的一個狀態(tài)和下一輸入求其他狀態(tài)通過狀態(tài)轉(zhuǎn)換函數(shù)，其中的第一個變元是一個項目集，第二個變元是一個文法符號。函數(shù)值定義為。</p><p>　?。ㄆ渲?= {任何形如的項目| 屬于}）</p><p>　　3.1.2 分析表的構(gòu)造 </p><p><b>　　分析表的組成：</b></p>

24、<p>　　動作表(ACTION) ：表示當(dāng)前狀態(tài)下面臨輸入符應(yīng)做的動作是移進(jìn)、歸約、接受或出錯，面臨的輸入符只包含終結(jié)符和‘?！?lt;/p><p>　　轉(zhuǎn)換表(GOTO)：表示在當(dāng)前狀態(tài)下面臨文法符號時應(yīng)轉(zhuǎn)向的下一個狀態(tài)</p><p><b>　　分析表的構(gòu)造算法</b></p><p>　　設(shè)已構(gòu)造出項目集規(guī)范族為，令項目集對

25、應(yīng)的狀態(tài)為，含項目的項目集對應(yīng)的狀態(tài)為初始狀態(tài)分析表的表和表構(gòu)造步驟為：</p><p>　?。?）若項目屬于且，為終結(jié)符，則置為“把移近棧”，簡記為“”。</p><p>　?。?）若項目屬于，那么對于任何終結(jié)符（或結(jié)束符#），置為“用產(chǎn)生式進(jìn)行規(guī)約”，簡記為“”（假定產(chǎn)生式是文法的第j個產(chǎn)生式）</p><p>　?。?）若項目屬于，則置為“接受”，簡記為“ac

26、c”。</p><p><b>　?。?）若，則置。</b></p><p>　?。?）分析表中凡不能用規(guī)則1~4填入信息的空白處均置上“報錯標(biāo)志”。如果分析表中任何一項被重復(fù)填入，則說明分析表的入口不是唯一的，項目集中存在沖突項目，該文法不是文法。</p><p>　　3.2 簡要的分析與概要設(shè)計</p><p>　　

27、本次課程設(shè)計中的程序主要有以下問題需要解決。</p><p>　　對于給定的文法G，如何提取它的產(chǎn)生式。</p><p>　　在提取產(chǎn)生式后，如何識別它的終結(jié)符和非終結(jié)符。</p><p>　　文法產(chǎn)生式項目集的構(gòu)造。</p><p>　　識別文法活前綴的及的狀態(tài)圖</p><p>　　C分析表的構(gòu)造 </p

28、><p>　　首先在文件中輸入 LR0文法。然后使用 Transform 類找出文法中的所有產(chǎn)生式，放在相應(yīng)的數(shù)據(jù)結(jié)構(gòu)中。同時，對文法進(jìn)行拓廣，消除一些中間的換行符號，空格等。然后，在此基礎(chǔ)上，使用類 TerminalAndNon識別文法中得終結(jié)符和終結(jié)符，將終結(jié)符和非終結(jié)符分別存儲。除此之外，還通過類TerminalAndNon實現(xiàn)了終結(jié)符與非終結(jié)符的判斷。之后，利用Addpoint 類中進(jìn)行進(jìn)行 LR0 項目集規(guī)

29、范族的構(gòu)造，找出所有產(chǎn)生式的項目集。在這個設(shè)計中，與原理中的不同之處是使用數(shù)字來代表點(diǎn)的位置，而沒有真實的點(diǎn)存在。如文法O>S S>AB A>a B>b的項目集的構(gòu)造結(jié)果如下：</p><p><b>　　1O>S</b></p><p><b>　　2O>S</b></p><p>&

30、lt;b>　　1S>AB</b></p><p><b>　　2S>AB</b></p><p><b>　　3S>AB</b></p><p><b>　　1A>a</b></p><p><b>　　2A>a<

31、/b></p><p><b>　　1B>b</b></p><p><b>　　2B>b</b></p><p>　　經(jīng)過上述的一系列的處理之后就可以使用LR0類生成活前綴的DFA了。然后使用類LR0Table來生成LR(0)分析表。</p><p>　　除此之外，此程序使用了F

32、ileIO類來從文件中輸入文法。</p><p><b>　　4、詳細(xì)的算法描述</b></p><p><b>　　4.1模塊說明</b></p><p>　　FileIO類：這個類的主要作用是供用戶輸入要用的文法。這個類主要調(diào)用系統(tǒng)類的對象實現(xiàn)功能。</p><p>　　Transform類：這

33、個類的功能是從文法中把產(chǎn)生式分離出來，放到一個字符串?dāng)?shù)組之中一邊后來調(diào)用。</p><p>　　TerminalAndNon類：這個類的功能是提取文法中的終結(jié)符和非終結(jié)符并放到字符數(shù)組里，方便以后調(diào)用。除此之外，該類也編寫了判斷是否為終結(jié)符的方法，是否為非終結(jié)符的方法。</p><p>　　AddPoint類：這個類的功能是構(gòu)造文法產(chǎn)生式的項目集。</p><p>

34、　　LR0類：這個類的功能是生成自動機(jī)，及所有活前綴的，并存在一個二維數(shù)組里。</p><p>　　LR0Table類：這個類就是生成LR0的分析表。</p><p>　　4.2 程序具體設(shè)計</p><p><b>　　FileIO 類</b></p><p>　　這個類供用戶從文件中輸入文法。其中包含readFile

35、ByLines(String fileName)方法，用來讀取文件。在該方法體中，使用while循環(huán)判斷是否讀完的文法，每讀入一個產(chǎn)生式，就將其連接到字符串的尾部，這樣就將文法轉(zhuǎn)換成一個字符串。</p><p>　　Transform 類 </p><p>　　該類主要是用來提取文法中的所有產(chǎn)生式，其中包含方法transfer（String S），該方法中將文法中所有的符號分為3中，“&g

36、t;”，“終結(jié)符和非終結(jié)符”，“換行和空格”。每遇到“>”時，便知道有一個產(chǎn)生式，而忽略所有的的空格和換行。然后將文法的產(chǎn)生式存在一個字符串?dāng)?shù)組中。</p><p>　　TerminalAndNon 類 </p><p>　　這個類主要是從文法中分離出終結(jié)符和非終結(jié)符。其中包括三個方法：</p><p>　　getNonTerminal(String s)方法

37、用于文法提取出來非終結(jié)符，該方法將那些產(chǎn)生式的第一個字母視為該文發(fā)的非終結(jié)符。直接從 Tranform 類的結(jié)果中讀取即可。</p><p>　　getTerminal(String s)則提取出終結(jié)符，主要思想是掃描所有的字符串，除去</p><p>　　查找出來的非終結(jié)符和“>”，其他的則全部是終結(jié)符了。</p><p>　　isNonTerminal(c

38、har c,char[] vn)則是判斷某個字符串是不是非終結(jié)符。 </p><p>　　AddPoint 類 </p><p>　　這個類是用來構(gòu)造文法的LR0項目集。例如 S>O，它的LR0 項目則是：S>.O和S>O.則在在這里就表示為 1S>O,2S>O。這是因為在程序中難以表示·這個實體，就是用數(shù)字來表示其所在的位置。在這個類中，主要是有方

39、法add(String)，先利用類Transform的對象來找出文法的所有產(chǎn)生式，然后構(gòu)造所有產(chǎn)生式的項目集。</p><p><b>　　LR0 類 </b></p><p>　　這個類是用來生成文法活前綴的DFA，是這個程序的核心類之一。主要的算法（求項目集規(guī)范族）就包括在這個類中，通過不斷的遞歸來將文法加入。但是這個求的只是將每個文法都加入進(jìn)去了，會有很多的重復(fù)

40、需要篩選。這就增加了一個方法來進(jìn)行篩選工作，反復(fù)查看是否還有重復(fù)的項目有就刪除，沒有就繼續(xù)下去，知道最后沒有重復(fù)的項目為止。 </p><p>　　5. LR0Table類 </p><p>　　這個類就是生成LR0分析表，由生成的活前綴DFA來構(gòu)造，構(gòu)造出ACTION表和GOTO</p><p>　　表，根據(jù)上述給定的算法來構(gòu)造。 </p>&

41、lt;p><b>　　測試方法和測試結(jié)果</b></p><p>　　這里選取了兩個文法來進(jìn)行測試。</p><p>　　為了驗證算法的正確性，這里先列出人工計算的結(jié)果，然后與程序輸出的結(jié)果進(jìn)行對比。</p><p>　　文法 的DFA，以及人工計算的狀態(tài)轉(zhuǎn)化表如下：</p><p>　　文法

42、的實際輸出結(jié)果如下：</p><p>　　結(jié)果中的S并無實際意義，作為一個分割，其左邊為ACTION表，右邊為GOTO表。</p><p>　　文法 的人工計算的狀態(tài)轉(zhuǎn)化表如下：</p><p><b>　　實際輸出結(jié)果為：</b></p><p><b>　　6 個人總結(jié)</b><

43、/p><p>　　在這次編譯原理的課程設(shè)計中，我體會頗深。剛看到自己的題目時，我并未認(rèn)識到這個題目的難度有多大。只是想著人工實現(xiàn)比較簡單，但是當(dāng)自己真正著手去寫程序時，問題才開始浮出水面，也在這時我才發(fā)現(xiàn)原來需要解決的問題實在很多。首先我考慮的是如何提取輸入的文法的產(chǎn)生式，如何找出所有的終結(jié)符和非終結(jié)符；其次是對于提取出來的每個產(chǎn)生式，我又該怎么樣構(gòu)造它的 LR0 項目集；最后就是怎么樣構(gòu)造活前綴 的DFA并在此基礎(chǔ)

44、上生成 LR0分析表。對于上面的問題，通過查找資料并向同學(xué)請教，最終都得到了解決。除了解決上面所說的問題以外，整個課程設(shè)計還用到了許多小技巧。比如，利用數(shù)字來表示每個項目中“.”的位置，為了簡化判斷，使用“>”來代替箭頭等。</p><p>　　在解決了算法中的問題之后，我面臨的就是語言的選擇?？紤]到，我們不僅僅希望構(gòu)造出一個文法的狀態(tài)轉(zhuǎn)換表，有時還希望能夠輸出中間結(jié)果。如果利用C語言的話，勢必會使用到多個

45、文件，所以我采用具有面向?qū)ο蟮乃枷氲腏ava語言。另外一個原因是，Java語言是我這學(xué)期剛剛學(xué)習(xí)的，我想利用此次機(jī)會加以實踐和鍛煉。這些工作都完成以后，我就開始著手書寫代碼。最終，功夫不負(fù)有心人，我終于完成了任務(wù)。</p><p>　　當(dāng)然，這個程序依然存在很多的不足之處。首先，在輸入的時候必須輸入LR(0)文法的拓廣文法。其次，如果給出的文法不是LR0文法時，不能解決沖突問題。由于時間問題，這些問題都還沒有解決

46、，但是在以后，我會將它逐步完善，畢竟這是我第一次使用Java寫的相對較大的程序。</p><p>　　雖然本次課程設(shè)計時間并不是很長，但是在這個過程中，我還是學(xué)到了很多。對于書本上所講的自底向上的語法分析有了更加深入的了解，也更深刻的理解了LR(0)分析方法。除此之外，對于一些問題的處理的思想我也有了新的認(rèn)識，我相信這些對于以后將會很有幫助的。 最后，再次對給過我?guī)椭乃型瑢W(xué)和指導(dǎo)老師表示忠心的感謝！沒有你們的

47、幫助我想我是不能這么好的完成這項工作的。</p><p><b>　　參考文獻(xiàn) </b></p><p>　　[1]《編譯原理》 胡倫俊、徐蘭芳、駱婷 電子工業(yè)出版社 </p><p>　　[2]《Java程序設(shè)計與實踐教程》 王薇 董迎紅 清華大學(xué)出版社 </p>

48、<p>　　[3]《Java程序設(shè)計》 辛運(yùn)緯 饒一梅 張鈞 清華大學(xué)出版社</p><p>　　[4]《精通Eclipse》 張大治 應(yīng)群 清華大學(xué)出版社</p><p>　　[5]《編譯原理》（第二版） 呂映芝、張素琴、蔣維杜 清華大學(xué)出版社</p><p

49、>　　出版時間：2004年11月</p><p>　　[6]《Compilers:Principles,Techniques,and Tools》 Alfred V A Ravi S Ullman J D 人民郵電出版社 出版時間：2002年2月</p><p>　　[7]《編譯原理與技術(shù)》（第二版）陳

50、意云 中國科學(xué)技術(shù)大學(xué)出版社 出版時間：2002年1月</p><p>　　[8]《編譯原理課程設(shè)計》 王雷、劉志成、周晶 機(jī)械工業(yè)出版社 出版時間：2005年3月</p><p>　　本科生課程設(shè)計成績評定表</p><p>　　班級：軟件0903班　　　姓名：

51、彭懷梁　　 學(xué)號：0120910680320</p><p>　　注：最終成績以五級分制記。優(yōu)（90-100分）、良（80-89分）、中（70-79分）、</p><p>　　及格（60-69分）、60分以下為不及格</p><p><b>　　指導(dǎo)教師簽名：</b></p><p><b>　　201 年