編譯原理課程設(shè)計(jì)報(bào)告LR分析----張小蒙

1、-. z.課程設(shè)計(jì)課程名稱編譯技術(shù)課程設(shè)計(jì)題目名稱根據(jù)LR分析表構(gòu)造LR分析器專業(yè)班級(jí)2013級(jí)軟件工程學(xué)生*小蒙吳松琴李偉孫萌程起楊偉平*紅偉*指導(dǎo)教師鄒青青二一六年五月二十八日*學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)任務(wù)書(shū)課程編譯技術(shù)課程設(shè)計(jì)班級(jí)2013級(jí)軟件工程指導(dǎo)教師鄒青青題目根據(jù)LR分析表構(gòu)造LR分析器完成時(shí)間2016年5月23日至2015年6月17日主要內(nèi)容1LR方法的根本思想過(guò)程。2LR分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出存儲(chǔ)器棧確實(shí)定有限狀態(tài)自動(dòng)機(jī)。3LR分析器的每一步工作是由棧頂狀態(tài)和現(xiàn)行輸入符號(hào)所唯一決定的。4為清晰說(shuō)明LR分析器實(shí)現(xiàn)原理和模型：設(shè)計(jì)報(bào)告要求1封面2課程設(shè)計(jì)任務(wù)書(shū)3. 分工

2、協(xié)作說(shuō)明4. 成績(jī)?cè)u(píng)定表5課程設(shè)計(jì)報(bào)告系統(tǒng)總體方案設(shè)計(jì)思路和主要步驟各功能模塊和流程圖設(shè)計(jì)代碼心得體會(huì)和參考資料說(shuō)明：學(xué)生完成課程設(shè)計(jì)后，提交軟件及課程設(shè)計(jì)電子和紙質(zhì)版，要求報(bào)告文字通暢、字跡工整，文字不少于3000字，并按要求裝訂成冊(cè)。版面要求1.題目用黑體三號(hào)，段后距18磅或1行，居中對(duì)齊；2.標(biāo)題用黑體四號(hào)，段前、段后距6磅或0.3行；3.正文用小四號(hào)宋體，行距為1.25倍行距；4.標(biāo)題按一、1、順序編號(hào)。上機(jī)時(shí)間安排星期周次一二三四五六日第14周至第17周5-6節(jié)1-2節(jié)指導(dǎo)時(shí)間地點(diǎn)上機(jī)時(shí)間，多媒體技術(shù)實(shí)驗(yàn)室A503分工協(xié)作說(shuō)明課題名稱學(xué)生*所做的工作根據(jù)LR分析表構(gòu)造LR分析器*小蒙

3、總體架構(gòu)，模塊指導(dǎo)吳松琴總體設(shè)計(jì)方案，綜合文檔修改李偉模塊測(cè)試孫萌模塊測(cè)試程起模塊測(cè)試*紅偉模塊測(cè)試楊偉平資料整理、打印*學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)成績(jī)?cè)u(píng)定表工程權(quán)重分值具體要求得分文獻(xiàn)閱讀與調(diào)查論證0.20100能獨(dú)立查閱文獻(xiàn)和從事其它調(diào)研活動(dòng)；有收集、加工各種信息的能力設(shè)計(jì)質(zhì)量0.30100設(shè)計(jì)合理、功能齊備，程序運(yùn)行正常，實(shí)驗(yàn)數(shù)據(jù)準(zhǔn)確可靠；有較強(qiáng)的實(shí)際動(dòng)手能力論文撰寫(xiě)質(zhì)量0.20100設(shè)計(jì)說(shuō)明書(shū)完全符合規(guī)*化要求，用A4復(fù)印紙打印成文學(xué)習(xí)態(tài)度0.20100學(xué)習(xí)態(tài)度認(rèn)真，科學(xué)作風(fēng)嚴(yán)謹(jǐn)，嚴(yán)格按要求開(kāi)展各項(xiàng)工作，按期完成任務(wù)學(xué)術(shù)水平與創(chuàng)新0.10100設(shè)計(jì)有創(chuàng)意，有一定的學(xué)術(shù)水平或?qū)嵱脙r(jià)值

4、總分評(píng)語(yǔ)：等級(jí)：指導(dǎo)教師：年月日-. z.目錄TOC o 1-3 h u HYPERLINK l _Toc109021 設(shè)計(jì)題目及內(nèi)容 PAGEREF _Toc10902 3HYPERLINK l _Toc59391.1 設(shè)計(jì)題目 PAGEREF _Toc5939 3HYPERLINK l _Toc182921.2 內(nèi)容 PAGEREF _Toc18292 3HYPERLINK l _Toc294651.3 設(shè)計(jì)環(huán)境 PAGEREF _Toc29465 3HYPERLINK l _Toc79052設(shè)計(jì)的根本原理 PAGEREF _Toc7905 3HYPERLINK l _Toc91052.1

5、 根本原理 PAGEREF _Toc9105 3HYPERLINK l _Toc2122.2 LR分析器工作過(guò)程算法描述 PAGEREF _Toc212 3HYPERLINK l _Toc237493程序設(shè)計(jì) PAGEREF _Toc23749 3HYPERLINK l _Toc32493.1 總體設(shè)計(jì)方案 PAGEREF _Toc3249 3HYPERLINK l _Toc5344建模 PAGEREF _Toc5344 3HYPERLINK l _Toc191813.1.2 程序設(shè)計(jì)關(guān)鍵注意環(huán)節(jié) PAGEREF _Toc19181 3HYPERLINK l _Toc147673.1.3 LR

6、分析器的組成 PAGEREF _Toc14767 3HYPERLINK l _Toc1180分析器構(gòu)造圖 PAGEREF _Toc1180 3HYPERLINK l _Toc164913.2各模塊設(shè)計(jì) PAGEREF _Toc16491 3HYPERLINK l _Toc20648棧設(shè)計(jì) PAGEREF _Toc20648 3HYPERLINK l _Toc185973.2.2 LR分析器工作過(guò)程算法設(shè)計(jì) PAGEREF _Toc18597 3HYPERLINK l _Toc193293.3流程圖 PAGEREF _Toc19329 3HYPERLINK l _Toc50284測(cè)試運(yùn)行 PAG

7、EREF _Toc5028 3HYPERLINK l _Toc218924.1測(cè)試一 PAGEREF _Toc21892 3HYPERLINK l _Toc234864.2測(cè)試二 PAGEREF _Toc23486 3HYPERLINK l _Toc218704.3測(cè)試三 PAGEREF _Toc21870 3HYPERLINK l _Toc131715心得體會(huì) PAGEREF _Toc13171 3HYPERLINK l _Toc101346參考文獻(xiàn) PAGEREF _Toc10134 3HYPERLINK l _Toc4683附錄 PAGEREF _Toc4683 3-. z.1 設(shè)計(jì)題目

8、及內(nèi)容1.1 設(shè)計(jì)題目根據(jù)LR分析表構(gòu)造LR分析器1.2 內(nèi)容文法G：(1)EE+T (2) ET (3) TT*F (4) TF (5) F(E) (6) FILR分析表：狀態(tài) ACTION(動(dòng)作)GOTO(轉(zhuǎn)換) I + * ( ) # E T F0S5S41231S6Acc2R2S7R2R23R4R4R4R44S5S48235R6R6R6R66S5S4937S5S4108S6S119R1S7R1R110R3R3R3R311R5R5R5R5注：sj表示把下一狀態(tài)j和現(xiàn)行輸入符號(hào)a移進(jìn)棧rj表示按第j個(gè)產(chǎn)生式進(jìn)展規(guī)約acc表示承受空格表示出錯(cuò)標(biāo)志，報(bào)錯(cuò)根據(jù)以上文法和LR分析表，構(gòu)造LR分析器

9、，并要求輸出LR工作過(guò)程。1.3 設(shè)計(jì)環(huán)境硬件設(shè)備：一臺(tái)PC機(jī)軟件設(shè)備：Windows 2000/*P OS ，VC+6.0 實(shí)現(xiàn)語(yǔ)言：C語(yǔ)言2設(shè)計(jì)的根本原理2.1 根本原理1.LR方法的根本思想在規(guī)*規(guī)約的過(guò)程中，一方面記住已移進(jìn)和規(guī)約出的整個(gè)符號(hào)串，即記住歷史，另一方面根據(jù)所用的產(chǎn)生式推測(cè)未來(lái)可能碰到的輸入符號(hào)，即對(duì)未來(lái)進(jìn)展展望。當(dāng)一串貌似句柄的符號(hào)串呈現(xiàn)于分析棧的頂端時(shí)，我們希望能夠根據(jù)記載的歷史和展望以及現(xiàn)實(shí)的輸入符號(hào)等三個(gè)方面的材料，來(lái)確定棧頂?shù)姆?hào)串是否構(gòu)成相對(duì)*一產(chǎn)生式的句柄。2LR分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出存儲(chǔ)器棧確實(shí)定有限狀態(tài)自動(dòng)機(jī)。3LR分析器的每一步工作是由棧頂狀態(tài)和現(xiàn)

10、行輸入符號(hào)所唯一決定的。4為清晰說(shuō)明LR分析器實(shí)現(xiàn)原理和模型： LR分析器的核心局部是一*分析表。這*分析表包括兩個(gè)局部，一是動(dòng)作ACTION表，另一是狀態(tài)轉(zhuǎn)換GOTO表。他們都是二維數(shù)組。ACTION(s,a)規(guī)定了當(dāng)狀態(tài)s面臨輸入符號(hào)a時(shí)應(yīng)采取什么動(dòng)作。GOTOs，*規(guī)定了狀態(tài)s面對(duì)文法符號(hào)*終結(jié)符或非終結(jié)符時(shí)下一狀態(tài)是什么。顯然，GOTO(s，*)定義了一個(gè)以文法符號(hào)為字母表的DFA。每一項(xiàng)ACTION(s，a)所規(guī)定的動(dòng)作不外是下述四種可能之一：1移進(jìn)：把s，a的下一個(gè)轉(zhuǎn)態(tài)s = GOTO(s，*)和輸入符號(hào)a推進(jìn)棧，下一輸入符號(hào)變成現(xiàn)行輸入符號(hào)。2規(guī)約：指用*一產(chǎn)生式A進(jìn)展規(guī)約。假假

11、設(shè)的長(zhǎng)度為r，規(guī)約的動(dòng)作是A，去除棧頂?shù)膔個(gè)項(xiàng)，使?fàn)顟B(tài)Sm-r 變成棧頂狀態(tài)，然后把Sm-r，A的下一狀態(tài)s = GOTO(Sm-r,A)和文法符號(hào)A推進(jìn)棧。規(guī)約動(dòng)作不改變現(xiàn)行輸入符號(hào)。執(zhí)行規(guī)約動(dòng)作意味著= *m-r+1*m已呈現(xiàn)于棧頂而且是一個(gè)相對(duì)于A的句柄。3承受：宣布分析成功，停頓分析器的工作。4報(bào)錯(cuò)：發(fā)現(xiàn)源程序含有錯(cuò)誤，調(diào)用出錯(cuò)處理程序。2.2 LR分析器工作過(guò)程算法描述一個(gè)LR分析器的工作過(guò)程可看成是棧里的狀態(tài)序列，已規(guī)約串和輸入串所構(gòu)成的三元式的變化過(guò)程。分析開(kāi)場(chǎng)時(shí)的初始三元式為s0, #, a1a2an#其中，s0為分析器的初態(tài)；為句子的左括號(hào)；a1a2an為輸入串；其后的為完畢

12、符句子右括號(hào)。分析過(guò)程每步的結(jié)果可表示為s0s1sm， #*1*2*m ai, ai+1an#分析器的下一步動(dòng)作是由棧頂狀態(tài)sm和現(xiàn)行輸入符號(hào)ai所唯一決定的。即，執(zhí)行ACTIONsm，ai所規(guī)定的動(dòng)作。經(jīng)執(zhí)行每種可能的動(dòng)作之后，三元式的變化情形是：假設(shè)ACTIONsm，ai為移進(jìn)，且s = GOTOsm，ai，則三元式變成：s0s1sm s， #*1*2*m ai, ai+1an#假設(shè)ACTIONsm，ai= A,則按照產(chǎn)生式A進(jìn)展規(guī)約。此時(shí)三元式變?yōu)閟0s1sm s， #*1*2*m A, ai ai+1an#此處s = GOTOSm-r，A，r為的長(zhǎng)度， = *m-r+1*m。假設(shè)ACT

13、IONsm，ai為承受，則三元式不再變化，變化過(guò)程終止，宣布分析成功。假設(shè)ACTIONsm，ai為報(bào)錯(cuò)，則三元式的變化過(guò)程終止，報(bào)告錯(cuò)誤。一個(gè)LR分析器的工作過(guò)程就是一步一步的變換三元式，直至執(zhí)行承受或報(bào)錯(cuò)為止。3程序設(shè)計(jì)3.1 總體設(shè)計(jì)方案建模1分析表建模：構(gòu)造一個(gè)int 型二維數(shù)組table139,用于存放LR分析表。并初始化。作者這樣規(guī)定：011 表示狀態(tài)sj，其中0對(duì)應(yīng)s0，1對(duì)應(yīng)s12126表示規(guī)約rj，其中21對(duì)應(yīng)r1，22對(duì)應(yīng)r212表示承受-1表示規(guī)約出錯(cuò)，報(bào)錯(cuò)2棧建模：建立一個(gè)int 型狀態(tài)棧，該棧為順序棧。建立一個(gè)char型符號(hào)棧和一個(gè)char型輸入串棧，該棧為順序棧。3規(guī)

14、約表達(dá)式建模：建立一個(gè)rule型構(gòu)造，成員變量為char型非終結(jié)符和int型表示規(guī)約第幾條表達(dá)式。3.1.2 程序設(shè)計(jì)關(guān)鍵注意環(huán)節(jié)在輸入串(句子)輸入的過(guò)程中，涉及到一個(gè)壓棧的問(wèn)題。但是輸入串壓入的字符順序剛好與原理中的字符串模型剛好相反，這樣需要先彈出的反而在棧底。為了既要保證字符串輸入，又要讓輸入的字符串存儲(chǔ)順序與輸入的字符串相反。采取以下措施：先將輸入的字符串壓入符號(hào)棧symbol中，然后符號(hào)棧彈出的字符再壓入輸入串棧instr中，這樣實(shí)現(xiàn)了輸入串的倒序存儲(chǔ)。狀態(tài)棧status_stack(status_p)和符號(hào)棧symbol_instr(symbol_p)輸出遍歷過(guò)程均采取自棧底到棧

15、頂?shù)捻樞?，而輸入串?symbol_instr(instr_p)則是采取自棧頂?shù)綏５椎捻樞蜉敵觥?.1.3 LR分析器的組成(1)總控程序，也可以稱為驅(qū)動(dòng)程序。對(duì)所有的LR分析器總控程序都是一樣的。(2)分析表或分析函數(shù)，不同的文法分析表將不同，同一個(gè)文法采用的LR分析器不同時(shí)，分析表將不同，分析表又可以分為動(dòng)作表ACTION和狀態(tài)轉(zhuǎn)換GOTO表兩個(gè)局部，它們都可用二維數(shù)組表示。(3)分析棧，包括文法符號(hào)棧和相應(yīng)的狀態(tài)棧，它們均是先進(jìn)后出棧。分析器的動(dòng)作就是由棧頂狀態(tài)和當(dāng)前輸入符號(hào)所決定。分析器構(gòu)造圖(1)在總控程序的控制下，從左到右掃描輸入串根據(jù)分析棧和輸入符號(hào)的情況，查分析表確定分析動(dòng)作；

16、(2)分析表是LR分析器的核心，它跟文法有關(guān)，它包括動(dòng)作表(Action)和狀態(tài)轉(zhuǎn)換表(Goto)兩局部，總控程序據(jù)分析表確定分析動(dòng)作；(3)分析棧包括文法符號(hào)棧*i和相應(yīng)的狀態(tài)棧Si兩局部(狀態(tài)是指能識(shí)別活前綴的自動(dòng)機(jī)狀態(tài))，LR分析器通過(guò)判斷棧頂元素和輸入符號(hào)查分析表確定下步分析動(dòng)作。圖 3-1 分析器構(gòu)造圖3.2各模塊設(shè)計(jì)棧設(shè)計(jì)構(gòu)造一個(gè)int型狀態(tài)棧status和一個(gè)char型符號(hào)輸入串棧 symbol_instr。該棧包括初始化該棧init_status()，壓棧push()，彈棧pop()，取棧頂元素get_top()，自棧底到棧頂遍歷元素out_stack1()和自棧頂?shù)綏５妆闅v元

17、素out_stack2()。3.2.2 LR分析器工作過(guò)程算法設(shè)計(jì)構(gòu)造一個(gè)狀態(tài)轉(zhuǎn)換函數(shù)實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換int goto_char(status *status_p,symbol_instr *instr_p)構(gòu)造一個(gè)移進(jìn)規(guī)約函數(shù)實(shí)現(xiàn)移進(jìn)規(guī)約動(dòng)作voidaction(status *status_p,symbol_instr *symbol_p,symbol_instr *instr_p)構(gòu)造一個(gè)打印LR分析器的工作過(guò)程函數(shù)實(shí)現(xiàn)輸出void print(status *status_p,symbol_instr *symbol_p,symbol_instr *instr_p)3.3流程圖圖3-2 L

18、R分析器設(shè)計(jì)流程圖4測(cè)試運(yùn)行4.1測(cè)試一輸入表達(dá)式 i*i+i 并且個(gè)符號(hào)之間不能有空格，以#字符完畢，結(jié)果如下：圖4-1 測(cè)試圖一4.2測(cè)試二輸入表達(dá)式i+i*i并且個(gè)符號(hào)之間不能有空格，以#字符完畢，結(jié)果如下圖4-2 測(cè)試圖二4.3測(cè)試三輸入表達(dá)式 i+(i+i)*i+i*i 并且個(gè)符號(hào)之間不能有空格，以#字符完畢，測(cè)試結(jié)果如下：圖4-3 測(cè)試圖三5心得體會(huì)經(jīng)過(guò)這個(gè)實(shí)驗(yàn)的練習(xí)，通過(guò)對(duì)程序的分析，讓我進(jìn)一步了解LR算法的思想以及它的進(jìn)一步程序?qū)崿F(xiàn)，讓我對(duì)它的了解從簡(jiǎn)單的理論上升到程序?qū)崿F(xiàn)的級(jí)別，有理論上升到實(shí)際，讓我更清楚它的用途。在對(duì)實(shí)驗(yàn)的分析的時(shí)候，也遇到很多的問(wèn)題，剛開(kāi)場(chǎng)根本想不到用程

19、序怎么實(shí)現(xiàn)這么繁雜的LR文法，后來(lái)看了程序才知道，才轉(zhuǎn)過(guò)來(lái)彎，通過(guò)對(duì)這個(gè)程序的分析與揣摩，讓自己對(duì)這方面文法的實(shí)現(xiàn)有了一定的頭緒，對(duì)以后的的一些文法的程序?qū)崿F(xiàn)會(huì)有很大的幫助，通過(guò)練習(xí)我也感到理論僅留在理論是遠(yuǎn)遠(yuǎn)不行的，用通過(guò)一定方式實(shí)現(xiàn)才有實(shí)用價(jià)值。通過(guò)本次課程設(shè)計(jì)，我加深了對(duì)預(yù)測(cè)分析LR分析法的理解，同時(shí)體驗(yàn)到了編譯原理中一些算法的巧妙。由于LR分析法程序是一個(gè)相當(dāng)復(fù)雜的程序，它需要利用到大量的編譯原理，編程技巧和數(shù)據(jù)構(gòu)造。由于先前掌握的知識(shí)不夠結(jié)實(shí)深刻使之在實(shí)驗(yàn)過(guò)程中出現(xiàn)了大量的問(wèn)題。由于課前的充分準(zhǔn)備，加上同學(xué)和教師的幫助，最后順利完成了實(shí)驗(yàn)。編譯原理的在整個(gè)計(jì)算機(jī)體系課程中有著重要的地

20、位，我現(xiàn)在才剛剛?cè)腴T(mén)，所以，我會(huì)在以后的課程和實(shí)驗(yàn)中繼續(xù)努力，學(xué)好編譯原理課程，為以后的學(xué)習(xí)打下根底。6參考文獻(xiàn)1 *素琴.呂映芝等.編譯原理M.清華大學(xué)出版.2004年2王宏.李玉東.李罡. VisualC+實(shí)戰(zhàn)演練 M .人民郵電出版.2003年3月3胡元義等.編譯原理實(shí)踐教程M .*電子科技大學(xué).2005年7月4胡倫駿.編譯原理M .電子工業(yè)，20025高仲儀.編譯原理及編譯程序構(gòu)造.M .航空航天大學(xué).19906陳火旺，*春林，譚慶平，趙克佳，*越.程序設(shè)計(jì)語(yǔ)言編譯原理第三版。，國(guó)防工業(yè)，2000：44-46，221-2367薛聯(lián)鳳.秦振松.編譯原理及編譯程序構(gòu)造第2版.東南大學(xué)附錄程

21、序源代碼一：頭文件 lr.h/LR分析表#include#include/0-11表示狀態(tài)結(jié)點(diǎn)，2126表示規(guī)約標(biāo)號(hào)，/-1表示error出錯(cuò)，12表示acc承受int table139 = 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,-1,-1,-1, 5,-1,-1, 4,-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,-

22、1,-1,-1,10,-1, 6,-1,-1,11,-1,-1,-1,-1,-1,21, 7,-1,21,21,-1,-1,-1,-1,23,23,-1,23,23,-1,-1,-1,-1,25,25,-1,25,25,-1,-1,-1;/規(guī)約規(guī)則struct rulechar *;int y;r6=E,3,E,1,T,3,T,1,F,3,F,1;/輸入字符char inde*_char9=i,+,*,(,),#,E,T,F;/獲取inde*_char9中元素的位置int get_inde*_char(char i)for(int j=0;j9;j+)if(inde*_charj = i)re

23、turn j;return -1;二：頭文件 status_stack.h#include#include#define MA* 20typedef structint stackMA*;int top;status;/初始化棧void init_stack(status *p)if( !p)printf(n初始化狀態(tài)棧出錯(cuò)!n);p-top = -1;/壓棧void push(status *p,int *)if(p-top top+;p-stackp-top = *;else printf(n狀態(tài)棧溢出!n);/彈棧int pop(status *p)int *;if(p-top != 0

24、)* = p-stackp-top;p-top-;return *;else printf(n狀態(tài)棧1空!n);return 0;/取棧頂元素int get_top(status *p)int *;if(p-top != -1)* = p-stackp-top;return *;else printf(n狀態(tài)棧2空!n);return 0;/遍歷棧元素void out_stack(status *p)int i;if(p-top 0)printf(n狀態(tài)棧3空!n);for(i=0; itop;i+)printf(%d,p-stacki);三：頭文件 symbol_instr_stack.h#include#include#define MA* 20typedef structchar stackMA*;int top;symbol_instr;/初始化棧void init_stack(symbol_instr *p)if( !p)printf(n初始化符號(hào)棧出錯(cuò)!n);p-top = -1;/壓棧void push(symbol_instr *p,char *)if(p-top top+;p-stackp-top = *;else printf(n符號(hào)棧溢出!n);/彈棧char pop(symbol_instr *p)char *;if(p-top != -1)* = p-s