編譯原理課程設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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