1、編譯原理實驗1 實驗題目蘭州大學(xué)計算機(jī)科學(xué)與技術(shù)專業(yè)編譯原理實驗手冊(V1.4)第一節(jié)概述一、實驗?zāi)康木幾g原理是一門實踐性很強(qiáng)的課程，但由于課時所限，只能在課堂上講授一些通用的原理和方法。而為了真正學(xué)好這門課程，必須自己動手構(gòu)造出一個編譯器，才能對書里講到的原理、方法和技術(shù)有較全面的體會，才能對學(xué)生以后的程序設(shè)計和解決實際問題的能力有所幫助。實際的編譯程序是十分復(fù)雜的，有時由多達(dá)十幾萬條指令組成。為此，編譯原理的實踐教學(xué)，采用簡化編譯過程的辦法，選擇最關(guān)鍵的三個環(huán)節(jié)詞法分析、語法分析、語義分析和中間代碼產(chǎn)生，每個環(huán)節(jié)作為一個實踐課題，逐步深入，擴(kuò)展功能，直至得到一個簡單實用的編譯器。本實驗不涉

2、及到優(yōu)化。二、實驗內(nèi)容任何一個實用的高級語言，其語法都比較復(fù)雜，如選其作為源語言，很難實踐全過程。故本試驗將定義一個簡化的語言PASCAL語言的一個子集作為源語言，分三個課題、一步步地構(gòu)造出它的編譯程序。所有試驗項目前后貫穿這一條主線進(jìn)行。本實驗共進(jìn)行6周，每周3學(xué)時，共18學(xué)時。本實驗主要包括以下三個課題：1.詞法分析：以源程序為輸入，輸出單詞符號流；2.語法分析：以源語言的文法為依據(jù)，調(diào)用詞法分析器，使用遞歸下降分析法或算符優(yōu)先分析法或LR(1)分析法，構(gòu)造能識別源語言各種語法結(jié)構(gòu)的語法分析器；(語發(fā)單元，語法樹碑)3.語義分析和中間代碼產(chǎn)生：使用語法制導(dǎo)翻譯技術(shù)，對源語言程序進(jìn)行簡單的翻

3、譯，輸出四元式序列。在本節(jié)的第三部分給出了PASCAL語言兩個子集的文法，對這些文法稍加變換，即可獲得用于語法分析的LL(1)文法或LR(1)文法。學(xué)生可以直接選擇一個作為編譯器的源語言，也可以對這些文法進(jìn)行改造，以獲得能力更為強(qiáng)大的源語言。學(xué)生也可以自己設(shè)計源語言，來完成這些題目；唯一的要求是源語言必須包含三種基本的程序設(shè)計結(jié)構(gòu)(順序、選擇、循環(huán))和至少兩種不同的數(shù)據(jù)類型。本實驗要求：所有的輸入輸出均采用文件形式。獨(dú)立完成。語言不限，開發(fā)工具不限；但必須有可運(yùn)行的程序和規(guī)范的注釋。三、PASCAL語言子集的文法由于Pascal語言結(jié)構(gòu)嚴(yán)謹(jǐn)，層次清晰，語法與C語言接近，也便于理解，因此本實驗抽

4、取Pascal語言的一個子集，稍加改造，作為源語言，姑且命名為LittleP。一個LittleP程序由一系列全局?jǐn)?shù)據(jù)聲明和一個主程序體組成。所有數(shù)據(jù)采用靜態(tài)存儲分配，沒有I/O，只支持一種基本數(shù)據(jù)類型：無符號整數(shù)。1.LittleP的文法：程序程序首部程序體.程序首部program程序名；程序體變量聲明復(fù)合語句變量聲明var變量定義列表|空變量定義列表變量定義變量定義列表|變量定義；變量定義變量名列表：類型；變量名列表變量名|變量名,變量名列表類型integer復(fù)合語句begin語句塊end語句塊語句|語句；語句塊語句賦值語句|條件語句|循環(huán)語句|復(fù)合語句|空賦值語句左部：=右部左部變量名右部

5、算術(shù)表達(dá)式條件語句if關(guān)系表達(dá)式then語句else語句循環(huán)語句while關(guān)系表達(dá)式do語句關(guān)系表達(dá)式算術(shù)表達(dá)式關(guān)系運(yùn)算符算術(shù)表達(dá)式算術(shù)表達(dá)式項|算術(shù)表達(dá)式加運(yùn)算符項項因子|項乘運(yùn)算符因子因子變量名|(算術(shù)表達(dá)式)|整數(shù)程序名標(biāo)識符變量名標(biāo)識符標(biāo)識符字母|標(biāo)識符字母|標(biāo)識符數(shù)字整數(shù)數(shù)字|整數(shù)數(shù)字關(guān)系運(yùn)算符|=|=|=|加運(yùn)算符+|-乘運(yùn)算符*|/字母a|b|x|y|z數(shù)字1|2|3|4|5|6|7|8|9|0 2.在此基礎(chǔ)上加以擴(kuò)充，可得功能較強(qiáng)的一個LittleP語言的超集：LittleP+。該語言引入了實數(shù)、一維數(shù)組和過程、函數(shù)的定義，參數(shù)傳遞采用傳值方式。另外，加入了I/O支持，編譯器提

6、供兩個系統(tǒng)函數(shù)：read()和write()。程序程序首部程序體.程序首部program程序名；程序體變量聲明分程序聲明復(fù)合語句變量聲明var變量定義列表|空變量定義列表變量定義變量定義列表|變量定義；變量定義變量名列表：類型；變量名列表變量名|變量名,變量名列表類型基本類型|數(shù)組基本類型integer|real數(shù)組array下界.上界of基本類型下界整數(shù)上界整數(shù)分程序聲明分程序分程序聲明|空分程序分程序首部變量聲明復(fù)合語句分程序首部procedure過程名(形參列表)；|function函數(shù)名(形參列表)：基本類型；形參列表形參定義,形參列表|形參定義|空形參定義變量名列表：基本類型復(fù)合語句

7、begin語句塊end語句塊語句|語句；語句塊語句賦值語句|條件語句|循環(huán)語句|過程調(diào)用語句|復(fù)合語句|讀寫語句|空賦值語句左部：=右部左部變量名|變量名算術(shù)表達(dá)式右部算術(shù)表達(dá)式條件語句if關(guān)系表達(dá)式then語句else語句循環(huán)語句while關(guān)系表達(dá)式do語句過程調(diào)用語句過程名(實參列表)|函數(shù)名(實參列表)實參列表算術(shù)表達(dá)式|算術(shù)表達(dá)式,實參列表|空讀寫語句read(變量名列表)|write(實參列表)關(guān)系表達(dá)式算術(shù)表達(dá)式關(guān)系運(yùn)算符算術(shù)表達(dá)式算術(shù)表達(dá)式項|算術(shù)表達(dá)式加運(yùn)算符項項因子|項乘運(yùn)算符因子因子變量名|(算術(shù)表達(dá)式)|函數(shù)名(實參列表)|變量名算術(shù)表達(dá)式|整數(shù)|實數(shù)程序名標(biāo)識符變量名標(biāo)

8、識符過程名標(biāo)識符函數(shù)名標(biāo)識符標(biāo)識符字母|標(biāo)識符字母|標(biāo)識符數(shù)字整數(shù)數(shù)字|整數(shù)數(shù)字實數(shù)整數(shù).整數(shù)關(guān)系運(yùn)算符|=|=|=|加運(yùn)算符+|-乘運(yùn)算符*|div|mod字母a|b|x|y|z|A|B|X|Y|Z數(shù)字1|2|3|4|5|6|7|8|9|0 3.對源程序語法的其他說明：a)出現(xiàn)在里的所有字符作為注釋跳過。b)各單詞符號之間的空格可有可無，但關(guān)鍵字和標(biāo)識符必須分隔開來。c)過程沒有返回值，只能出現(xiàn)在過程調(diào)用語句中；函數(shù)有且只有1個返回值，只能出現(xiàn)在算術(shù)表達(dá)式中或作為賦值語句的右部。函數(shù)返回值通過函數(shù)名帶回，因此在函數(shù)體內(nèi)必須給函數(shù)名賦值。d)標(biāo)識符的長度不得超過8個字符。e)關(guān)鍵字保留，包括r

9、ead和write。四、實驗要求：每個課題完成后寫出實驗報告。實驗報告應(yīng)該包括：程序設(shè)計時考慮的算法和主要的數(shù)據(jù)結(jié)構(gòu)；可執(zhí)行的程序至少2個測試用例，包括：至少1個合法的源程序及其運(yùn)行結(jié)果；至少1個非法的源程序及其錯誤報告。第二節(jié)詞法分析一、目的與要求1.目的通過設(shè)計、調(diào)試詞法分析程序，實現(xiàn)從源程序中分離出各種單詞的方法；加深對課堂教學(xué)的理解，尤其是對正規(guī)式、有窮自動機(jī)的原理和用途的理解；為以后軟件開發(fā)過程中設(shè)計高效率的掃描器打下基礎(chǔ)。2.要求應(yīng)有適當(dāng)?shù)念A(yù)處理。輸入源程序，輸出定長單詞符號流，均采用文件形式。針對選定的源語言，構(gòu)造識別其合法單詞符號的詞法分析器。實現(xiàn)時可以借助LEX(如何使用請參

10、考教材并上網(wǎng)搜索資料)。應(yīng)考慮到后續(xù)階段的需要，合理設(shè)計詞法分析器的結(jié)構(gòu)。本實驗應(yīng)在一周內(nèi)完成。二、設(shè)計步驟(要求文檔)1.問題分析：l分析源語言的文法，找出各種詞法單位的構(gòu)詞規(guī)則。l工作流程：構(gòu)詞規(guī)則(正規(guī)式NFADFA)狀態(tài)轉(zhuǎn)換圖程序；(算法的一部分)構(gòu)詞規(guī)則狀態(tài)轉(zhuǎn)換圖程序。l預(yù)處理：有哪些預(yù)處理工作要做。2.總體設(shè)計：l輸入輸出緩沖區(qū)，輸出格式(等長二元式序列)；l表格設(shè)計(設(shè)計幾張表，每張表登記什么信息)：關(guān)鍵字表算符、分隔符表變量表：簡單變量、數(shù)組、過程與函數(shù)錯誤信息表(掃描一遍源程序，登記錯誤信息，最后再輸出到文件)l出錯處理：錯誤位置、錯誤消息格式、錯誤恢復(fù)等。3.程序流程設(shè)計：

11、明確程序所使用的主要算法，一般以偽代碼或程序流程圖表示。圖1給出了一個程序流程圖的例子，作為參考。4.編碼與測試：編寫程序并調(diào)試通過，然后自己設(shè)計至少3個測試用例。測試用例包括兩部分：輸入(源程序代碼)和預(yù)期結(jié)果(運(yùn)行結(jié)果或錯誤信息)。5.編寫實驗報告。圖1詞法分析程序流程圖三、擴(kuò)充有余力的同學(xué)，可適當(dāng)擴(kuò)大分析對象。譬如：1.加入更多的基本類型，如：考慮引入布爾型變量和邏輯運(yùn)算。2.加入復(fù)雜的數(shù)據(jù)類型，如：類似java中的String類型。3.加入二義性文法結(jié)構(gòu)，如：單分支和雙分支的選擇語句。第三節(jié)語法分析一、目的與要求1.目的通過設(shè)計、編寫、調(diào)試一個典型的語法分析程序，實現(xiàn)對詞法分析程序所提

12、供的單詞序列進(jìn)行語法分析和檢查，進(jìn)一步掌握常用的語法分析方法的實現(xiàn)技術(shù)。2.要求調(diào)用詞法分析器，分析源程序的語法結(jié)構(gòu)(區(qū)分出各種語法結(jié)構(gòu))，檢查語法錯誤。推薦使用算符優(yōu)先分析算術(shù)表達(dá)式，用遞歸子程序法分析其他各種語法結(jié)構(gòu)，如賦值語句、IF語句、WHILE語句等。也可以使用LR分析法完成這些工作，實現(xiàn)時可以借助YACC(如何使用請參考教材并上網(wǎng)搜索資料)。輸入文本文件形式的源程序；識別出程序中主要的語法結(jié)構(gòu)，以注釋的形式給出簡單的說明信息，如變量聲明語句、IF語句、循環(huán)開始、循環(huán)結(jié)束等。若有錯誤，則在相應(yīng)位置給出錯誤提示。本課題應(yīng)在兩周內(nèi)完成。因時間緊張，建議采用增量開發(fā)模式：從簡單到復(fù)雜、能力

13、逐漸增強(qiáng)。二、設(shè)計步驟1.問題分析：使用哪種語法分析方法?單獨(dú)使用遞歸下降分析法可以完成任務(wù)嗎?從文法中提煉出主要的語法結(jié)構(gòu)，如：程序、變量聲明、分程序聲明、復(fù)合語句、IF語句、算術(shù)表達(dá)式等，認(rèn)真分析他們的語法結(jié)構(gòu)。如何利用前面構(gòu)造的詞法分析器和相關(guān)表格?考慮錯誤處理的方法。2.總體設(shè)計：對文法進(jìn)行必要的等價變換，使之符合所選語法分析方法的要求。若有必要，對上次實驗后得到的詞法分析器及相關(guān)符號表進(jìn)行調(diào)整。針對產(chǎn)生算術(shù)表達(dá)式(關(guān)系表達(dá)式)的文法，構(gòu)造算符優(yōu)先關(guān)系表，在此基礎(chǔ)上，編寫一小段程序，分析這類語法結(jié)構(gòu)。(算法示例見附錄一)針對各種語法結(jié)構(gòu)，逐一產(chǎn)生其遞歸下降分析的狀態(tài)轉(zhuǎn)換圖，再一一翻譯為

14、程序段。(算法示例見附錄二)設(shè)計輸出的形式。將前面的工作組合起來，形成一個完整的語法分析器。3.程序流程設(shè)計。4.編碼和測試：編寫代碼，調(diào)試通過，并設(shè)計測試用例。5.編寫實驗報告。三、程序流程示例：題目：遞歸下降法分析表達(dá)式(此題目僅供參考，而且不完全準(zhǔn)確)1.分析對象的BNF定義如下：算術(shù)表達(dá)式項|算術(shù)表達(dá)式+項|算術(shù)表達(dá)式-項項因式|項*因式|項/因式因式變量(算術(shù)表達(dá)式)變量字母字母A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z用遞歸下降法分析上述算術(shù)表達(dá)式的框圖，如圖2所示。(a)(b)(c)(d)(e)(f)圖2遞歸下降法分析表

15、達(dá)式之框圖(a)ZC過程；(b)E過程；(c)T過程；(d)F過程；(e)函數(shù)過程SYM；(f)過程ADVANCE這里，ZC過程為總控程序，主要完成：通知外界鍵入算術(shù)表達(dá)式；控制E過程分析算術(shù)表達(dá)式；根據(jù)分析結(jié)果之正誤，分別通知外界不同的信息。ZC過程被設(shè)計成可以分析無窮多個算術(shù)表達(dá)式。E、T和F三個過程分別對應(yīng)算術(shù)表達(dá)式、項和因式三個產(chǎn)生式的處理。它們用到兩個公共過程。一個是函數(shù)過程SYM，它負(fù)責(zé)從輸入字符串ST中取出下一個字符，并存入SYM中等待分析。另一個過程ADVANCE負(fù)責(zé)剔除ST中的首字符。四、擴(kuò)充有余力的同學(xué)，可適當(dāng)擴(kuò)大分析對象。譬如：1.加入for循環(huán)語句：for i：=1 t

16、o 5do begin dosomething()end；2.引入二義性文法：stmtif cond then stmt else stmt|if cond then stmt 3.加強(qiáng)語法檢查，盡量多和確切地指出各種錯誤。第四節(jié)語義分析和中間代碼產(chǎn)生一、目的與要求1.目的通過上機(jī)實習(xí)，加深對語法制導(dǎo)翻譯和運(yùn)行時存儲空間分配的理解，掌握將語法分析所識別的語法范疇變換為某種中間代碼的語義翻譯方法。2.要求l采用語法制導(dǎo)翻譯技術(shù)。l可以考慮實現(xiàn)簡單的靜態(tài)語義檢查。l語義分析的對象重點考慮經(jīng)過語法分析后已是正確的語法范疇，程序設(shè)計的重點是語義子程序的設(shè)計。l中間代碼選用四元式。l以兩周內(nèi)完成為宜。3

17、.源語言的語法結(jié)構(gòu)大致可分為以下六類：n聲明語句：簡單類型、復(fù)雜類型及其數(shù)據(jù)空間特性(如全局?jǐn)?shù)據(jù)、局部數(shù)據(jù)等)，以及過程聲明。重點是符號表的操作。n順序結(jié)構(gòu)：典型代表是兩類表達(dá)式(算術(shù)表達(dá)式、布爾表達(dá)式)及相應(yīng)的賦值語句。重點是算術(shù)表達(dá)式的翻譯方法(各種屬性值的計算)。n控制結(jié)構(gòu)：if語句。重點是跳轉(zhuǎn)的地址問題(拉鏈返填)。n子程序結(jié)構(gòu)：過程和函數(shù)的調(diào)用。重點是參數(shù)傳遞和返回地址(活動記錄)。n循環(huán)結(jié)構(gòu)：while語句。重點是循環(huán)的優(yōu)化(本實驗暫不涉及)。n格式語句：主要指輸入輸出語句的格式加工。在LittleP+中,read(a,b,c)表示從鍵盤讀入三個無符號整數(shù)；write(x,Y+2)

18、表示向屏幕打印兩個表達(dá)式的值。二、設(shè)計步驟1.問題分析：如何把語法分析和語義分析結(jié)合起來(語義子程序的處理時機(jī))；如何設(shè)計語義子程序來產(chǎn)生四元式；有哪些靜態(tài)語義檢查工作?(應(yīng)著重考慮實現(xiàn)以下幾點：)i.標(biāo)識符必須先說明，再使用；ii.同一作用域內(nèi)不得重復(fù)定義(在符號表中記錄標(biāo)識符的作用域)；iii.操作數(shù)與操作符的類型匹配a)定義在integer上的運(yùn)算：+-*div mod和關(guān)系運(yùn)算符；b)定義在boolean上的運(yùn)算：not or and；c)賦值運(yùn)算符：=兩端的類型應(yīng)該相同。iv.對于不滿足上述規(guī)則的，應(yīng)給出錯誤提示。2.總體設(shè)計：對文法進(jìn)行必要的等價變換，并為每條產(chǎn)生式添加語義子程序。

19、針對表達(dá)式的產(chǎn)生式，自下而上地計算其綜合屬性。針對各種語句的產(chǎn)生式，自上而下地計算其繼承屬性。將各種語法結(jié)構(gòu)翻譯為四元式序列(四元式的格式見本節(jié)第四部分)。把四元式按順序編號，輸出到文件。3.程序流程設(shè)計：核心是語法制導(dǎo)翻譯的實現(xiàn)算法。4.編碼與測試。5.編寫實驗報告。三、算法示例題目：在對簡化的算術(shù)表達(dá)式進(jìn)行語法分析的同時生成四元式(僅作參考)。四元式生成程序的核心部分(指表達(dá)式、項和因式的處理)的算法，可描述如下：PROCEDURE E；BEGIN E1PLACE：=T；WHILE SYM=+OR-DO BEGIN ADVANCE；E2PLACE：=T；T1：=NEWTEMP；GEN(,E

20、1PLACE,E2PLACE,T1)；E1PLACE：=T1 END；RETURN(E1PLACE)END；PROCEDURE T；BEGIN T1PLACE：=F；WHILE SYM=*OR/DO BEGIN ADVANCE：T2PLACE：=F；T1：=NEWTEMP；GEN(*/,T1PLACE,T2PLACE,T1)；T1PLACE：=T1 END；RETURN(T1PLACE)END；PROCEDURE F：BEGIN IF SYM=標(biāo)識符THEN BEGIN ADVANCE；RETURN(ENTRY(i)END ELSE IF SYM=(THEN BEGIN ADVANCE；PLA

21、CE：=E；IF SYM=)THEN BEGIN ADVANCE；RETURN(PLACE)END ELSE ERROR END ELSE ERROR END.這里：E表達(dá)式；T項；F因子；ADVANCE將輸入串指針調(diào)整至指向下一個輸入字符；NEWTEMP分配一個新的工作單元；GEN將一個四元式填入四元式表；ENTRY查找變量名表，并獲得名字所在位置值。四、建議生成的四元式統(tǒng)一采用如下的形式：?形如x：=y op z的賦值語句，其中op是二元運(yùn)算符；或者形如x：=op z的賦值語句，其中op是not。?形如x：=y的復(fù)制語句，將y的值復(fù)制給x。?無條件跳轉(zhuǎn)goto L,L是接下來要執(zhí)行的四元式

22、的編號或地址。?條件跳轉(zhuǎn)jump xL，若x為真，則跳轉(zhuǎn)至L所指的四元式；否則順序執(zhí)行。?過程調(diào)用系列：n傳參數(shù)param x，有n個參數(shù)就生成n條傳參數(shù)四元式；n過程調(diào)用call p,n，其中：p是過程或函數(shù)名，n表示參數(shù)的個數(shù)；n返回值return y。?形如x：=yi和xi：=y的變址賦值語句。?讀寫語句：n傳參數(shù)param x，有n個參數(shù)就生成n條傳參數(shù)四元式；n過程調(diào)用call read/write,n，其中n表示參數(shù)的個數(shù)。附錄一算符優(yōu)先分析算法示例Tree term2Rest(Tree t,int minprec)/minprec is the lowest precedence

23、 of all binary operators.Tree odStack=newOdStack()；/stack of operands；int opStack=newOpStack()；/stack of top=0；/top pointer of stack.odStack0=t；int startPos=S.pos；/S is ascanner.It returns atoken and its position everytime./topOp is always the top element of opStack.Its initial value i

24、 topOp=ERROR；while(prec(S.token)=minprec)/移進(jìn)opStacktop=topOp；top+；topOp=S.token；int pos=S.pos；S.nextToken()；odStacktop=term()；/term()分析表達(dá)式中的項/規(guī)約while(top 0&prec(topOp)=prec(S.token)/You can do something here,such as creating asyntax tree or calculating the value.odStacktop-1=makeop(pos,topOp,odStacktop-1,odStacktop)；top-；topOp=opStacktop；.#附錄二遞歸下降分析算法示例SyntaxTree*Parser：Statement()SyntaxTree*tree=NULL；switch(currentToken.type).case ID：this-nextToken()；tree=Assign()；if(tree！=N