1、姓名：課程設計名稱課程設計(論文)任務書 軟 件 學 院 學院 專業 班 一、課程設計(論文)題目 二、課程設計(論文)工作自 2015 年 6 月 16 日起至 2013 年 6 月 19 日止。三、課程設計(論文) 地點: 軟 件 學 院 實 訓 中 心 四、課程設計(論文)內容要求：1本課程設計的目的進一步培養學生編譯器設計的思想，加深對編譯原理和應用程序的理解，針對編譯過程的重點和難點內容進行編程，獨立完成有一定工作量的程序設計任務，同時，強調好的程序設計風格，并綜合使用程序設計語言、數據結構和編譯原理的知識, 熟悉使用開發工具VC /JAVA/C#/.NET 。2課程設計的任務及要求

2、1）課程設計任務：根據自己所選擇的題目填寫內容2）創新要求：在基本要求達到后，可進行創新設計3）課程設計論文編寫要求（1）課程設計任務及要求（2）設計思路-工作原理、功能規劃（3）詳細設計-數據分析、算法思路、功能實現（含程序流程圖、主要代碼及注釋）、界面等。（4）運行調試與分析討論-給出運行屏幕截圖，分析運行結果，有何改進想法等。（5）設計體會與小結-設計遇到的問題及解決辦法，通過設計學到了哪些新知識，鞏固了哪些知識，有哪些提高。（6）報告按規定排版打印，要求裝訂平整，否則要求返工；（7）課設報告的裝訂順序如下：封面-任務書-中文摘要-目錄-正文-附錄(代碼及相關圖片)（8）嚴禁抄襲，如有發

3、現，按不及格處理。4）課程設計評分標準： （1）學習態度：20分；（2）系統設計：20分；（3）編程調試：20分；（4）回答問題：20分；（5）論文撰寫：20分。5）參考文獻：（1）張素琴，呂映芝. 編譯原理M., 清華大學出版社（2）蔣立源、康慕寧等，編譯原理（第2版）M，西安：西北工業大學出版社6）課程設計進度安排1準備階段（4學時）：選擇設計題目、了解設計目的要求、查閱相關資料2程序模塊設計分析階段（4學時）：程序總體設計、詳細設計3代碼編寫調試階段（8學時）：程序模塊代碼編寫、調試、測試4撰寫論文階段（4學時）：總結課程設計任務和設計內容，撰寫課程設計論文學生簽名： 2015 年 6

4、月 19 日課程設計(論文)評審意見（1）學習態度（20分）：優（）、良（）、中（）、一般（）、差（）； （2）系統設計（20分）：優（ ）、良（）、中（）、一般（）、差（）； （3）編程調試（20分）：優（）、良（）、中（）、一般（）、差（）；（4）回答問題（20分）：優（）、良（）、中（）、一般（）、差（）；（5）論文撰寫（20分）：優（）、良（）、中（）、一般（）、差（）； 評閱人： 職稱： 講師 2015 年 6 月 19 日中文摘要1965年，D.Knuth首先提出了LR(K)文法及LR(K)分析技術。所謂LR(K)分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根

5、據分析棧當前已移進和歸約出的全部文法符號，并至多再向前查看K個輸入符號，就能確定相對于某一產生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當前所應采取的分析動作 (是移進還是按某一產生式進行歸約等)。LR分析是當前最一般的分析方法。這是因為它對文法的限制最少，現今能用上下文無關文法描述的程序設計語言一般均可用LR方法進行有效的分析，而且在分析的效率上也不比諸如不帶回溯的自頂向下分析、一般的“移進歸約”以及算符優先等分析方法遜色。此外，LR分析器在工作過程中，還能準確及時地發現輸入符號串的語法錯誤。凡此種種，就使LR分析方法在國際上受到了廣泛的重視。顧名思義，LR(0)分析就是LR

6、(K)分析當K=0的情況，亦即在分析的每一步，只要根據當前的棧頂狀態 (或者說根據當前分析棧中已移進或歸約出的全部文法符號)就能確定應采取何種分析動作，而無須向前查看輸入符號。做這次課設采用的是C+語言進行編寫的LR(0)分析器，使用的編譯器是ClodeBlocks,電腦系統是win 8.1內存為4G目錄一、課程設計任務及要求1二、需求分析1三、設計思路13.1 識別文法的LR(0)項目集規范族的構造13.2 LR(0)分析表的構造23.3 LR(0)分析器總控程序構造3四、詳細設計44.1 程序總體構架44.2 程序存儲結構54.2.1 符號表存儲結構54.2.2 產生式表存儲結構54.2.

7、3 項目集規范族表存儲結構64.2.4 LR(0)分析表存儲結構74.3 程序算法74.3.1 項目集規范族的構造74.3.2 LR(0)分析表構造9五、運行調試與分析討論104.1 符號表測試104.2 產生式表測試114.3 項目集規范族表測試114.4 LR(0)分析表測試124.5 LR(0)分析器測試12六、設計體會與小結13七、參考文獻14-第 3 頁 -一、課程設計任務及要求. 本課程設計完成了以下內容：1. 實現了對任意給定的文法，識別文法活前綴的、的狀態轉化矩陣及項目集規范族的構造；2. 判斷該文法是否為文法，實現了分析表的構造，并輸出到指定文件中；3. 實現了分析器總控程序

8、，對輸入的表達式進行文法分析。二、需求分析本課程設計的核心算法Error! Reference source not found.主要有三點：1. 識別文法活前綴的、的狀態轉化矩陣及項目集規范族的構造；2. 分析表的構造；3. 分析器總控程序的構造。三、設計思路3.1 識別文法的LR(0)項目集規范族的構造采用（閉包）的構造一個文法的項目規范簇。假定是文法的任一項目集，定義和構造的閉包的算法：（1）的任何項目都屬于；（2）若屬于，那么，對任何關于的產生式，項目也屬于；（3）重復執行上述兩個步驟直至不再增大。其中初始 ，為對文法進行拓廣構造而引進的不出現在中的非終結符。定義狀態轉換函數，的第一個

9、變元是一個項目集，第二個變元是一個文法符號。函數值定義為。其中 = 任何形如的項目| 屬于3.2 LR(0)分析表的構造 假定。令每個項目集的下標作為分析器的狀態。特別是，令那個包含項目的集合的下標為分析器的初態。分析表的子表和子表可按如下方法構造： （1）若項目屬于且，為終結符，則置為“把移近棧”，簡記為“”。 （2）若項目屬于，那么對于任何終結符（或結束符#），置為“用產生式進行規約”，簡記為“”（假定產生式是文法的第j個產生式） （3）若項目屬于，則置為“接受”，簡記為“acc”。 （4）若，則置。 （5）分析表中凡不能用規則14填入信息的空白處均置上“報錯標志”。如果分析表中任何一項被

10、重復填入，則說明分析表的入口不是唯一的，項目集中存在沖突項目，該文法不是文法。3.3 LR(0)分析器總控程序構造分析表包括量部分，“動作”表和“狀態轉換”表。規定了當狀態面臨輸入符號時應采取什么動作。規定了狀態面對文法符號時下一狀態是什么。每一項所規定的動作不外乎是下述四種可能之一。（1）移進 把的下一狀態和輸入符號推進棧，下一輸入符號變成現行輸入符號。（2）歸約 指用某一產生式進行規約。假若的長度為,規約的動作是，去除棧頂的個項，使狀態變成棧頂狀態，然后把的下一狀態推進棧。規約動作不改變現行輸入符號。規約動作不改變現行輸入符號。（3）接受 宣布分析成功，停止分析器工作（4）報錯 發現源程序

11、含有錯誤，調用出錯處理程序。四、詳細設計4.1 程序總體構架本課程設計開發的程序主要由4張表組成，分別為：符號表、產生式表、表和項目集規范簇表。同時，項目集規范簇表包含一個分析棧作為分析器總控程序。產生式表包含符號表作為子表，項目集規范簇表包含產生式表、表作為子表。 程序工作流程：1. 讀取含有文法規則的文件，為該文法中的每一個不同的文法符號（終結符和非終結符分配一個編號），記錄文法符號的屬性（終結符/非終結符），存儲于一張符號表中；2. 再次讀取文件，將產生式存儲于產生式表中；3. 根據產生式構建項目集規范族，存儲于表中；4. 根據構建的項目集規范族構建分析表，填寫分析表同時檢查該文法是否為

12、文法；5. 對于輸入的表達式，分析器根據構建的分析表進行文法分析，給出分析結果。4.2 程序存儲結構4.2.1 符號表存儲結構動態數組下標，同時作為符號的編號標識符是否為非終結符4.2.2 產生式表存儲結構產生式標號非終結符標號 （與中的一致）指示當前非終結符的產生式當前非終結符產生式的長度，用于幫助區分一個產生式的不同項目，即項目個數等于指示下一個非終結符一個產生式中的標識符名（與中的一致）一個產生式中的下一個標識符4.2.3 項目集規范族表存儲結構 1）定義二元組 ： ：產生式標號，與 中的一致 ：一個產生式的第個項目，可由 中的幫助確定 如：產生式 ： ， 2）結構：當前狀態編號 指示下

13、一狀態 指示閉包中的項目 閉包中的項目名當前項目的產生的新狀態的編號，即狀態轉移的目的地狀態編號閉包中的下一個項目待構造的項目的閉包的待構造的項目的閉包待構造狀態的待構造狀態的項目4.2.4 LR(0)分析表存儲結構指示表頭的孩子結點指示表頭的后繼結點指示該表項的操作指示該表項的操作數指示該表項是否被填寫過,用于判斷文法是否為文法4.3 程序算法4.3.1 項目集規范族的構造1. （初始化）將初始條件作為該狀態頭結點的第一個孩子結點，并構造該孩子結點的閉包，連接其后，指向第一個狀態頭結點，指向第一個狀態頭結點的第一個孩子結點；2. 查看，若為空，停止；若不為空，轉3；3. 查看，若為空，轉4；

14、若不為空，構造的，檢查該狀態與之前構造的狀態有無重復，若重復，則停止構造，的填寫重復的已存在的狀態的編號；若不重復，則作為一個新狀態，連接于，并構造其閉包連接其后，指向。轉2；4. 指向下一狀態，若下一狀態為空，則結束，否則，指向下一狀態頭結點的第一個孩子結點，轉3。具體細節：設所指項目為，因為要對其構造閉包，該項目一定不是終態，所以區分項目的圓點符號位于第個標識符的左側。現在構造的閉包，分兩個步驟實現：1. 構造的 ： 查看中編號為的產生式，取得該產生式的長度屬性1） 若，則停止構造當前閉包（已是終態），此時 的項填；2） 否則，將作為該閉包的第一個項目，此時 的項填該新狀態的狀態編號。2.

15、 構造該孩子結點的閉包 ：查看中編號為的產生式的第個標識符，取得該標識符的，查看中該標識符的類別屬性3） 若為1（非終結符），則查看非終結符的所有產生式，記這些產生式的編號為，將所有的加入閉包4） 否則，結束3. 檢查該狀態與之前構造的狀態有無重復 :斷言：任意兩個狀態，只要不同，則即為不同狀態。4.3.2 LR(0)分析表構造對于編號為的狀態，現依據其項目填寫分析表：1. 如果該項目形如，查看該項目的屬性，1）若為終結符，則在表的狀態對應行，對應列，填寫，表示將把 移進棧2）若為非終結符，則在表的狀態對應行，對應列，填寫，表示狀態轉移至狀態2. 如果該項目形如1）若為起始符號，則置在表的狀態

16、對應行，對應列，填寫，表示接受。2）否則，對任何終結符或結束符，則在表的狀態對應行，對應列，填寫，表示用產生式進行規約。五、運行調試與分析討論以文法G為例：程序模塊輸入：含上述文法的文件，下面展示個模塊的輸出結果4.1 符號表測試圖6 符號表測試輸出結果為 <符號編號，符號，是否為終結符>與預期結果相同圖7 產生式表測試4.2 產生式表測試輸出結果與讀入的文件中的產生式相同，且產生式中符號的編號正確4.3 項目集規范族表測試圖8 產生式表測試輸出結果為 <狀態編號> ：<產生式編號，產生式項目編號，項目轉移的目標狀態>與預期結果相同4.4 LR(0)分析表測試圖9 分析表測試輸出結果為分析表，與預期結果相同4.5 LR(0)分析器測試以輸入字符串和為例圖10 分析器測試表達式的分析結果正確第 11 頁 六、設計體會與小結經過半年的編譯原理的學習，我漸漸明白編譯器的工作原理，通過這次實驗對該理論在實踐中的應用有深刻的理解， 通過把該算法的內容，算法的執行順序在計算機上實現，知道和理解了該理論在計算機中是怎樣執行的，對該理論在實踐中的應用有深刻的理解。 作系統的認識是模糊的，概念上的，現在通過自己動手