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

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

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

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

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

5、構與模塊說明（功能與流程圖）、詳細的算法設計、軟件調試、軟件的測試方法和結果、有關技術的討論、收獲與體會等。</p><p><b>　?、芙Y束語。</b></p><p><b>　?、輩⒖嘉墨I。</b></p><p>　　⑥附錄：軟件清單（或者附盤）。</p><p><b>　　時

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

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 設計任務2</p>

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

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

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

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

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

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

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

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

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

17、3.1 設計原理</b></p><p>　　總的來說，分析表構造的主要問題如下：</p><p>　　識別文法活前綴的及的狀態(tài)圖</p><p>　　項目集規(guī)范族的構造；</p><p><b>　　分析表的構造；</b></p><p>　　它們的主要設計原理如下：</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>　　為了構造活前綴的，我們首先需要構造文法的項目級。在文法的每個文法的右部適當位置添加一個圓點構成項目。對于文法中的每個產生式的項目集的大小是由其產生式的長度決定的，長度是其右部符號的長度加1。例如產生式：A→aBC，有4個LR(0)項目：</p><p

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

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

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

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

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

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

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

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

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

29、范族的構造，找出所有產生式的項目集。在這個設計中，與原理中的不同之處是使用數(shù)字來代表點的位置，而沒有真實的點存在。如文法O>S S>AB A>a B>b的項目集的構造結果如下：</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>　　經過上述的一系列的處理之后就可以使用LR0類生成活前綴的DFA了。然后使用類LR0Table來生成LR(0)分析表。</p><p>　　除此之外，此程序使用了F

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

48、<p>　　[3]《Java程序設計》 辛運緯 饒一梅 張鈞 清華大學出版社</p><p>　　[4]《精通Eclipse》 張大治 應群 清華大學出版社</p><p>　　[5]《編譯原理》（第二版） 呂映芝、張素琴、蔣維杜 清華大學出版社</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]《編譯原理與技術》（第二版）陳

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

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