




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
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)在通過自己動手
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 公司房租收取管理辦法
- 供水企業(yè)薪酬管理辦法
- 華僑職稱管理暫行辦法
- 公益宣傳印章管理辦法
- 保健原料采購管理辦法
- 辦公用房管理制度優(yōu)化與實施
- 新學(xué)制背景下哲學(xué)話語與教育權(quán)力的博弈
- 景區(qū)建筑維修管理辦法
- 租賃業(yè)務(wù)風(fēng)險管理與防控策略探討
- 云計算管理平臺系統(tǒng)建設(shè)的策略與實踐
- 中國醫(yī)院質(zhì)量安全管理第2-13部分:患者服務(wù)臨床用血
- 《籃球原地運球》教案 (共三篇)
- 思維模型之六頂思考帽
- DB34T 1708-2020 電站堵閥檢驗規(guī)程
- 2025年高考化學(xué)復(fù)習(xí)備考策略講座
- 《網(wǎng)絡(luò)系統(tǒng)建設(shè)與運維》課件-第3章 路由技術(shù)
- 常用建筑類型疏散寬度計算表格
- 電氣設(shè)備經(jīng)典故障案例分析與處理
- QB/T 2660-2024 化妝水(正式版)
- GB/T 4074.1-2024繞組線試驗方法第1部分:一般規(guī)定
- 《中國旅游地理》模塊一 項目一解讀中國旅游地理(教案) -《中國旅游地理》(高教版第一版)
評論
0/150
提交評論