編譯原理課程設計LR分析張小蒙

1、編譯原理課程設計LR分析張小蒙課程設計課程名稱編譯技術課程設計根據(jù)LR分析表構造LR分析 題目名稱器專業(yè)班級2013級軟件工程張小蒙吳松琴李偉學生姓名孫萌程起楊偉平張紅偉學 號指導教師鄒青青二O六年五月二十八日蚌埠學院計算機科學及技術系課程設計任務書課程編譯技術課程設計班級2013級軟件工程指導教師鄒青青題目根據(jù)LR分析表構造LR分析器完成時間2016年5月23日至2015年6月17日主 要 內 容1. LR方法的基本思想過程。2. LR分析器實質上是一個帶先進后出存儲器（棧）的確 定有限狀態(tài)自動機。3. LR分析器的每一步工作是由棧頂狀態(tài)和現(xiàn)行輸入符號 所唯一決定的。4. 為清晰說明LR分析

2、器實現(xiàn)原理和模型：5 / 36設計報告要求版面要求1. 封面2 課程設計任務書3. 分工協(xié)作說明4. 成績評定表5 課程設計報告(1) 系統(tǒng)總體方案(2) 設計思路和主要步驟(3) 各功能模塊和流程圖(4) 設計代碼(5) 心得體會和參考資料說明：學生完成課程設計后，提交軟件及課程設計電子和 紙質版，要求報告文字通暢、字跡工整，文字不少于3000 字，并按要求裝訂成冊。1題目用黑體三號，段后距18磅(或1行)，居中對齊;2. 標題用黑體四號，段前、段后距6磅(或0.3行)；3. 正文用小四號宋體，行距為1.25倍行距；4. 標題按“一”、“”、“1”、“”順序編號。周次第14周至第17周5-6

3、 節(jié)1-2節(jié)指導時間上機時間，多媒體技術實驗室（A503）地點分工協(xié)作說明課題名稱學生姓名學號所做的工作根 據(jù) LR 分 析 表 構 造 LR張小蒙總體架構，模塊指導吳松琴總體設計方案，綜合文檔修改李偉模塊測試孫萌模塊測試分析器程起模塊測試張紅偉模塊測試楊偉平資料整理、打印蚌埠學院計算機科學及技術系課程設計成績評定表項目權重分值具體要求得分文獻閱讀及調查論證0.20100能獨立杳閱文獻和從事其它調研活動； 有收集、加工各種信息的能力設計質量0.30100設計合理、功能齊備，程序運行正常， 實驗數(shù)據(jù)準確可靠；有較強的實際動手 能力論文撰寫質量0.20100設計說明書完全符合規(guī)范化要求，用A4 復

4、印紙打印成文學習態(tài)度0.20100學習態(tài)度認真，科學作風嚴謹，嚴格按 要求開展各項工作，按期完成任務學術水平及創(chuàng)新0.10100設計有創(chuàng)意，有一定的學術水平或實用 價值總分評語：等級：指導教師：年月日編譯原理課程設計LR分析張小蒙目錄1設計題目及內容11.1設計題目11.2內容11.3設計環(huán)境22設計的基本原理32.1基本原理32.2 LR分析器工作過程算法描述43程序設計63.1總體設計方案63.1.1建模63.1.2程序設計關鍵注意環(huán)節(jié)63.1.3 LR分析器的組成73.1.4分析器結構圖73.2各模塊設計83.2.1棧設計83.2.2 LR分析器工作過程算法設計93.3流程圖104測試運

5、行114.1測試一 114.2測試二114.3測試三121 / 36編譯原理課程設計LR分析張小蒙5心得體會136參考文獻14附錄153 / 36編譯原理課程設計LR分析張小蒙1設計題目及內容1.1設計題目根據(jù)LR分析表構造LR分析器1.2內容已知文法G: (1)E-E+T(2) ET(3) TT*F(4) TF F-(E)(6) FILR分析表：狀態(tài)ACTION(動作)GOTO (轉換)I+*()#ETF0S5S41231S6Acc2R2S7R2R23R4R4R4R44S5S48235R6R6R6R66S5S4937S5S4108S6SU9R1S7R1R110R3R3R3R311R5R5R5

6、R5注：sj表示把下一狀態(tài)j和現(xiàn)行輸入符號a移進棧巧表示按第j個產(chǎn)生式進行規(guī)約acc表示接受空格表示出錯標志，報錯根據(jù)以上文法和LR分析表，構造LR分析器，并要求輸出LR 工作過程。1.3設計環(huán)境硬件設備：一臺PC機軟件設備：Windows 2000/XP OS , VC+6.0實現(xiàn)語言：C語言2設計的基本原理2.1基本原理1. LR方法的基本思想在規(guī)范規(guī)約的過程中，一方面記住已移進和規(guī)約出的整個符號串，即 記住“歷史”，另一方面根據(jù)所用的產(chǎn)生式推測未來可能碰到的輸入 符號，即對未來進行“展望”。當一串貌似句柄的符號串呈現(xiàn)于分析 棧的頂端時，我們希望能夠根據(jù)記載的“歷史”和“展望”以及“現(xiàn) 實

7、”的輸入符號等三個方面的材料，來確定棧頂?shù)姆柎欠駱嫵上?對某一產(chǎn)生式的句柄。2. LR分析器實質上是一個帶先進后出存儲器(棧)的確定有限狀 態(tài)自動機。3. LR分析器的每一步工作是由棧頂狀態(tài)和現(xiàn)行輸入符號所唯一決 定的。4. 為清晰說明LR分析器實現(xiàn)原理和模型：LR分析器的核心部分是一張分析表。這張分析表包括兩個部分, 一是“動作”(ACTION)表，另一是“狀態(tài)轉換”(GOTO)表。他 們都是二維數(shù)組oACTION(s,a)規(guī)定了當狀態(tài)s面臨輸入符號a時應 采取什么動作。GOTO (s, X)規(guī)定了狀態(tài)s面對文法符號X (終 結符或非終結符)時下一狀態(tài)是什么。顯然，GOTO(s, X)定

8、義了一 個以文法符號為字母表的DFAo每一項ACTION(s, a)所規(guī)定的動作不外是下述四種可能之一:(1) 移進：把(s, a)的下一個轉態(tài)s = GOTO(s, X)和輸 入符號a推進棧，下一輸入符號變成現(xiàn)行輸入符號。(2) 規(guī)約：指用某一產(chǎn)生式A-p進行規(guī)約。假若卩的長度為r,規(guī)約的動作是A,去除棧頂?shù)腎個項，使狀態(tài)Sm-r變成棧頂狀態(tài), 然后把(Sm-r, A)的下一狀態(tài)s = GOTO(Sm-r,A)和文法符號 A推進棧。規(guī)約動作不改變現(xiàn)行輸入符號。執(zhí)行規(guī)約動作意味著P (= Xm-r+1-Xm)已呈現(xiàn)于棧頂而且是一個相對于A的句柄。(3) 接受：宣布分析成功，停止分析器的工作。(

9、4) 報錯：發(fā)現(xiàn)源程序含有錯誤，調用出錯處理程序。2.2 LR分析器工作過程算法描述一個LR分析器的工作過程可看成是棧里的狀態(tài)序列，已規(guī)約串 和輸入串所構成的三元式的變化過程。分析開始時的初始三元式為(sO,#,ala2an#)其中，sO為分析器的初態(tài)；#為句子的左括號；ala2an為 輸入串；其后的#為結束符(句子右括號)。分析過程每步的結果可 表示為(sOslsm, #X1X2Xmai, ai+1an#)分析器的下一步動作是由棧頂狀態(tài)sm和現(xiàn)行輸入符號ai所唯一 決定的。即，執(zhí)行ACTION (sm, ai)所規(guī)定的動作。經(jīng)執(zhí)行每種可能的動作之后，三元式的變化情形是：若 ACTION (s

10、m, ai)為移進，且 s = GOTO (sm, ai),則 三元式變成：(sOsl sm s , #X1X2Xmai,ai+1an#)若ACTION (sm, ai) = A-|3,則按照產(chǎn)生式A-p進行規(guī)約。 此時三元式變?yōu)?sOslsm s ,#X1X2Xm A,aiai+1an#)此處 s = GOTO (Sm-r, A), r 為 p 的長度，p =Xm-r+1Xmo若ACTION (sm, ai)為“接受”，則三元式不再變化，變化 過程終止，宣布分析成功。若ACTION (sm, ai)為“報錯”，則三元式的變化過程終止， 報告錯誤。一個LR分析器的工作過程就是一步一步的變換三元

11、式，直至執(zhí) 行“接受”或“報錯”為止。5 / 36編譯原理課程設計LR分析張小蒙3程序設計3.1總體設計方案3.1.1建模(1) 分析表建模：構造一個int型二維數(shù)組table 13，用于存放LR分析表。并初始 化。作者這樣規(guī)定：011表示狀態(tài)sj,其中0對應sO, 1對應si2126表示規(guī)約rj,其中21對應rl, 22對應r212表示“接受”-1表示規(guī)約出錯，報錯(2) 棧建模：建立一個int型狀態(tài)棧，該棧為順序棧。建立一個char型符號棧和一個char型輸入串棧，該棧為順序棧。(3) 規(guī)約表達式建模：建立一個rule型結構，成員變量為char型非終結符和int型表示規(guī) 約第幾條表達式。3

12、.1.2程序設計關鍵注意環(huán)節(jié)在輸入串(句子)輸入的過程中，涉及到一個壓棧的問題。但是輸 入串壓入的字符順序剛好及原理中的字符串模型剛好相反，這樣需要 先彈出的反而在棧底。為了既要保證字符串輸入，又要讓輸入的字符 串存儲順序及輸入的字符串相反。采取以下措施：先將輸入的字符串壓入符號棧symbol中，然后符號棧彈出的 字符再壓入輸入串棧instr中，這樣實現(xiàn)了輸入串的倒序存儲。狀態(tài)棧 status_stack(status_p)和符號棧 symbol_instr(symbol_p)出(遍歷)過程均采取自棧底到棧頂?shù)?順序，而輸入串棧symbol_instr(instr_p)lj1i是采取自棧頂?shù)綏?/p>

13、底的 順序輸出。3.1.3 LR分析器的組成(1) 總控程序，也可以稱為驅動程序。對所有的LR分析器總控程 序都是相同的。(2) 分析表或分析函數(shù)，不同的文法分析表將不同，同一個文法采 用的LR分析器不同時，分析表將不同，分析表又可以分為動作表(ACTION)和狀態(tài)轉換(GOTO)表兩個部分，它們都可用二維數(shù) 組表示。(3) 分析棧，包括文法符號棧和相應的狀態(tài)棧，它們均是先進后出 棧。分析器的動作就是由棧頂狀態(tài)和當前輸入符號所決定。3.1.4分析器結構圖(1) 在總控程序的控制下，從左到右掃描輸入串根據(jù)分析棧和輸入 符號的情況，查分析表確定分析動作；(2) 分析表是LR分析器的核心，它跟文法有

14、關，它包括動作表(Action)和狀態(tài)轉換表(Goto)兩部分，總控程序據(jù)分析表確定分析動作；(3) 分析棧包括文法符號棧Xi和相應的狀態(tài)棧Si兩部分(狀態(tài) 是指能識別活前綴的自動機狀態(tài))，LR分析器通過判斷棧頂元素和輸 入符號查分析表確定下步分析動作。圖3-1分析器結構圖3.2各模塊設計3.2.1棧設計構造一個int型“狀態(tài)棧” status和一個char型“符號一輸入串?！?symbol_instro該棧包括初始化該棧init_status(),壓棧push(),彈棧pop(), 取棧頂元素get_top(),自棧底到棧頂遍歷元素out_stackl()和自棧 頂?shù)綏５妆闅v元素out_st

15、ack2 () o3.2.2 LR分析器工作過程算法設計構造一個狀態(tài)轉換函數(shù)實現(xiàn)狀態(tài)轉換intgoto_char(status *status_p,symbol_instr *instr_p)構造一個移進一一規(guī)約函數(shù)實現(xiàn)移進規(guī)約動作voidaction(status*status_p,symbol_instr*symbol_p,symbol_instr *instr_p)構造一個打印LR分析器的工作過程函數(shù)實現(xiàn)輸出voidprint(status*status_p, symbol_instr*symbol_p,symbol_instr *instr_p)9 / 36編譯原理課程設計LR分析張小

16、蒙33流程圖規(guī)約成功!退出亠求下一狀態(tài)符號2i = goicuto規(guī)約岀錯!異常中止！卩移進動作；a1. 將現(xiàn)狀態(tài)1壓找42. 將當前輸入串 字符壓入符號初貽化探態(tài)枝待虧復，輸 入串將輸入串各寶符壓揃規(guī)約動作；Q1 .求出i對應規(guī)約規(guī)則右部 字符串長度x = ri.21.y2在符號Ji和狀態(tài)棧中彈出 x個字符。燃后將該規(guī)約 規(guī)則左部壓入輸入串找圖3-2 LR分析器設計流程圖4測試運行4.1測試一輸入表達式i*i+i并且個符號之間不能有空格，以#字符結束,結果如下：c *D : 2GDelu62G. e*c*請輸入要規(guī)絢的輸入申，之間不能有空格.以葉字符貉束?=Expi*oss ion =ii*

17、ittttbp + 瑋i 入i* 輸02 M2?02 7502016Ml 650163Ml 6701itttt tt ttttPressanykeyto continue圖4-1測試圖一4.2測試二輸入表達式i+i叫并且個符號之間不能有空格，以#字符結束，結果如下D:26Euby26. cmc*請輸入要規(guī)釣的輸A申，各字符之間不能有空恪，字符結車? =Expess ion = UkI H伏態(tài)棧=符號棧=乂工二“輸入串ItiG 63 2 1110 n n 0 uUFUF+T*ttH *1u tt tt*i*U *i*lUii#Mitt*ittUUF*TF #E*T #Ett #二規(guī)釣咸功to c

18、ontinuePi*eee anykey圖4-2測試圖二4.3測試三輸入表達式i+(i+i)*i+i*i并且個符號之間不能有空格，以#字符結束，測試結果如下：11/36編譯原理課程設計LR分析張小蒙CVeze*|請輸入要規(guī)約的輸入串，各字符之間不能有空格，以,字符結束？ =Expres ion =i+( i+i*i+i*itt狀態(tài)棧=符號棧_=輸入串0tt05tti03ttF02ttT01ttE016itE*0164HEX0164501643#EXF01642#EYT01648ttEYE016486ttEYE*0164865ttEYET0164863井EYE+F0164869#E+E+T016

19、48UEXE0164811#E+-0163ttE+F0169ttE+T01697ttE+T*016975ttE+-T*i+i*i0169710ttE*T*F+i*i0169ttE*T01ttEi*i016ttE*i*i0165ttE+i*iit0163ttE+F0169ttE+T01697ttE+T*016975ttE4-T*ift0169710#E4-T*F#0169ttE+Ttt01ttEttPress any=規(guī)約成歲=key to continue=圖4-3測試圖三5心得體會經(jīng)過這個實驗的練習，通過對程序的分析，讓我進一步了解LR 算法的思想以及它的進一步程序實現(xiàn)，讓我對它的了解從簡單

20、的理論 上升到程序實現(xiàn)的級別，有理論上升到實際，讓我更清楚它的用途。在對實驗的分析的時候，也遇到很多的問題，剛開始根本想不到 用程序怎么實現(xiàn)這么繁雜的LR文法，后來看了程序才知道，才轉過 來彎，通過對這個程序的分析及揣摩，讓自己對這方面文法的實現(xiàn)有 了一定的頭緒，對以后的的一些文法的程序實現(xiàn)會有很大的幫助，通 過練習我也感到理論僅留在理論是遠遠不行的，用通過一定方式實現(xiàn) 才有實用價值。通過本次課程設計，我加深了對預測分析LR分析法的理解，同時體驗到了編譯原理中一些算法的巧妙。由于LR分析法程序是一個 相當復雜的程序，它需要利用到大量的編譯原理，編程技巧和數(shù)據(jù)結 構。由于先前掌握的知識不夠牢固深

21、刻使之在實驗過程中出現(xiàn)了大量 的問題。由于課前的充分準備，加上同學和老師的幫助，最后順利完 成了實驗。編譯原理的在整個計算機體系課程中有著重要的地位，我現(xiàn)在才剛剛入門，所以，我會在以后的課程和實驗中繼續(xù)努力，學好編譯原 理課程，為以后的學習打下基礎。6參考文獻1張素琴呂映芝等編譯原理M.清華大學出版.2004年王宏李玉東.李罡.Visual C+實戰(zhàn)演練M.人民郵電出版.2003 年3月胡元義等編譯原理實踐教程M.西安電子科技大學出版社.2005年7月4胡倫駿.編譯原理M.電子工業(yè)出版社，2002高仲儀編譯原理及編譯程序構造M.北京航空航天大學出版 社.19906 陳火旺，劉春林，譚慶平，趙克

22、佳，劉越程序設計語言編譯原理（第三版）。北京，國防工業(yè)出版社，2000: 44-46, 221-2367 薛聯(lián)鳳.秦振松.編譯原理及編譯程序構造（第2版）東南大學出 版社附錄程序源代碼一:頭文件lr.h/LR分析表#include#include/0-11表示狀態(tài)結點，21-一26表示規(guī)約標號，/-I表示error （出錯），12表示acc （接受）int table 139 = 5,-1,-1, 4,-1,-1, 1, 2, 3,-1, 6,-1,-1,-1,12,-1,-1,-1,-1,22, 7,-1,22,22,-1,-1,-1,-1,24,24,-1,24,24,5,-1,-1,4,

23、-1,-1,8, 2, 3,-1,26,26,-1,26,26,-1,-1,-1, 5,-1,-1, 4,-1,-1,-1, 9, 3, 5,-1,-1, 4,-1,-1,-1,-1,10,-1, 6,-1,-1,11,-1,-1,-1,-1,M,21, 7,-1,21,21,-1,-1,-1,-1,23,23,-1,23,23,-1,25,25,-1,25,25,-1,-1,-1;/規(guī)約規(guī)則struct rulechar x;int y;旳6=E,3,E,1,T,3,T,1,F,3,F,1;輸入字符charindex_char 9=丫,屮,/獲取index_char中元素的位置intget_

24、index_char(char i)forfint j=0;j9;j+)if (index_charj = i)return j;return -1;二：頭文件 status_stack.h#i nclude#include#define MAX 20 typedefstruct int stackMAX;int top;status;初始化棧voidinit_stack(status *p)iff !p)printfC*n初始化狀態(tài)棧出錯!n“);p-top = -1;壓棧void pushfstatus *p,int x)辻(p-top top+;p-stackp-top = x;else

25、 printf(n 狀態(tài)棧溢出!nH)；彈棧int pop (status *p)int x;if(p-top != 0)x = p-stackp-top;p-top;return x;elseprintf(nn 狀態(tài)棧 1 空!n”); return 0;/取棧頂元素intget_top (status *p)int x;辻(p-top != -1)x = p-stackp-top;return x;elseprintf(n 狀態(tài)棧 2 空!n”);return 0;/遍歷棧元素voidout_stack(status *p)inti;if(p-top top;i+)printf(%d,p-

26、stacki);三： 頭文件 symbol_instr_stack. .h#include#include#define MAX 20 typedefstruct char stackMAX;int top;symbol_instr;初始化棧 voidinit_stack(symbol_instr *p) if( !p)printffn初始化符號棧出錯!n“);p-top = -1;壓棧void push(symbol_instr *p,char x)if(p-top v MAX-1)p-top+;p-stackp-top = x;else printf(Hn 符號棧溢出!nu)；彈棧char pop(symbol_instr *p)char x;辻(p-top !=