《編譯原理》實(shí)驗(yàn)指導(dǎo)書

1、編譯原理實(shí)驗(yàn)指導(dǎo)書實(shí)驗(yàn)?zāi)康暮蛢?nèi)容編譯原理實(shí)驗(yàn)的目的是使學(xué)生將編譯理論運(yùn)用到實(shí)際當(dāng)中，實(shí)現(xiàn)一個(gè)簡(jiǎn)單語言集的詞法、語法和語義分析程序，驗(yàn)證實(shí)際編譯系統(tǒng)的實(shí)現(xiàn)方法，并加深對(duì)編譯技術(shù)的認(rèn)識(shí)。實(shí)驗(yàn)內(nèi)容共需實(shí)現(xiàn)編譯器的詞法、語法和語義分析程序三個(gè)組成部分。要求學(xué)生必須完成每個(gè)實(shí)驗(yàn)的基本題目要求，有余力的同學(xué)可嘗試實(shí)驗(yàn)的擴(kuò)展要求部分。實(shí)驗(yàn)報(bào)告要求每人針對(duì)所完成的實(shí)驗(yàn)內(nèi)容上交一份實(shí)驗(yàn)報(bào)告，其中主要包括三方面內(nèi)容：1 、實(shí)驗(yàn)設(shè)計(jì)：實(shí)驗(yàn)采用的實(shí)現(xiàn)方法和依據(jù)（如描述語言的文法及其機(jī)內(nèi)表示，詞分析的單詞分類碼表、狀態(tài)轉(zhuǎn)換圖或狀態(tài)矩陣等，語法分析中用到的分析表或優(yōu)先矩陣等，語法制導(dǎo)翻譯中文法的拆分和語義動(dòng)作的設(shè)計(jì)編寫等

2、）；具體的設(shè)計(jì)結(jié)果（應(yīng)包括整體設(shè)計(jì)思想和實(shí)現(xiàn)算法，程序結(jié)構(gòu)的描述，各部分主要功能的說明，法以及所用數(shù)據(jù)結(jié)構(gòu)的介紹等）。2 、程序代碼：實(shí)驗(yàn)實(shí)現(xiàn)的源程序清單，要求符合一般的程序書寫風(fēng)格，有詳細(xì)的注釋。3 、實(shí)驗(yàn)結(jié)果分析：自行編寫若干源程序作為測(cè)試用例，對(duì)所生成的編譯程序進(jìn)行測(cè)試（編譯程序的輸入與輸出以文件的形式給出）；運(yùn)行結(jié)果分析（至少包括一個(gè)正確和一個(gè)錯(cuò)誤單詞或語句的運(yùn)行結(jié)果）；以及改進(jìn)設(shè)想等。注意事項(xiàng)1 、電子版實(shí)驗(yàn)報(bào)告和源程序在最后一次機(jī)時(shí)后的一周內(nèi)上交。（每個(gè)同學(xué)上交一個(gè)壓縮文件，其命名格式為“學(xué)號(hào)_姓名.rar”，內(nèi)含實(shí)驗(yàn)報(bào)告和一個(gè)命名為“源程序”的文件夾。注意提交的源程序應(yīng)是經(jīng)過調(diào)試

3、、測(cè)試成功的較為通用的程序，并應(yīng)有相應(yīng)的注釋、運(yùn)行環(huán)境和使用方法簡(jiǎn)介。）2 、不接受不完整的實(shí)驗(yàn)報(bào)告和沒有說明注釋的源程序，或者說明與程序、運(yùn)行結(jié)果不符合的作業(yè)。特別鼓勵(lì)：擴(kuò)展題目1 、為親身經(jīng)歷一個(gè)小型編譯器的開發(fā)全過程，觸摸一下與實(shí)際編譯器開發(fā)相關(guān)的工作，大家可以自由組成3人左右的小組，推舉組長(zhǎng)，模擬一個(gè)團(tuán)隊(duì)分工協(xié)作開發(fā)大型軟件的實(shí)戰(zhàn)環(huán)境，融入軟件工程的思想規(guī)范和一般理論方法，初步體驗(yàn)從系統(tǒng)分析設(shè)計(jì)、編碼測(cè)試到交付維護(hù)的一個(gè)完整編譯器軟件的開發(fā)過程。要求組長(zhǎng)為每個(gè)小組成員分配主要負(fù)責(zé)的任務(wù)，完成相應(yīng)的分析設(shè)計(jì)員、程序員和測(cè)試員等角色的工作，并以小組為單位提交一份實(shí)驗(yàn)報(bào)告和源程序，在報(bào)告封面

4、上寫明每個(gè)同學(xué)主要完成和負(fù)責(zé)的部分。2 、以組為單位完成的實(shí)驗(yàn)內(nèi)容至少必須整合詞法、語法和語義三個(gè)部分的實(shí)驗(yàn)，對(duì)于選定的適當(dāng)規(guī)模的文法（如C語言的一個(gè)大小適宜的子集），進(jìn)行系統(tǒng)的總體設(shè)計(jì)、功能分析、編碼測(cè)試等工作。完成一個(gè)從對(duì)源程序的詞法分析開始，到中間代碼生成的完整的編譯器前端的開發(fā)，使所涉及到的編譯系統(tǒng)的各個(gè)組成模塊有機(jī)地銜接在一起，提交一份完整的實(shí)驗(yàn)報(bào)告和源程序，并將以下幾個(gè)方面描述清楚：1）任務(wù)概述2）系統(tǒng)的設(shè)計(jì)3）系統(tǒng)實(shí)現(xiàn)（包括必要的框圖，各.h和.c文件說明，所有函數(shù)功能的說明，數(shù)據(jù)結(jié)構(gòu)、各種表格、變量等的說明，以及函數(shù)調(diào)用關(guān)系圖等）4）系統(tǒng)工作過程及運(yùn)行說明（使用操作指南）5）源

5、程序清單（要求有詳細(xì)注釋）和實(shí)例程序運(yùn)行結(jié)果6）體會(huì)和討論3、實(shí)驗(yàn)題目1）參考題目：在詞法、語法和語義三個(gè)基本實(shí)驗(yàn)題目的基礎(chǔ)上，完成以下擴(kuò)展部分的要求：實(shí)驗(yàn)一：（1）擴(kuò)充關(guān)鍵字的數(shù)目、增加單詞類別（如分界符、邏輯運(yùn)算符等）、將常數(shù)分成字符串常量、整型常量和實(shí)型常量等；添加詞法分析中單詞出錯(cuò)的位置、加細(xì)錯(cuò)誤類型的檢查以及刪除注釋部分等；并考慮如何在詞法分析階段建立變量名表和常數(shù)表，以備后續(xù)的編譯過程查詢。（2）選作：識(shí)別一個(gè)程序設(shè)計(jì)語言（如C語言）所有單詞的詞法分析程序設(shè)計(jì)。建議自學(xué)LEX系統(tǒng)。實(shí)驗(yàn)二：（1）完成以下文法G復(fù)合語句刁的兩種典型的語法分析程序的設(shè)計(jì)與實(shí)現(xiàn)。G復(fù)合語句:復(fù)合語句beg

6、in語句表end語句表語句|語句;語句表語句賦值語句賦值語句-變量:=算術(shù)表達(dá)式算術(shù)表達(dá)式f項(xiàng)|算術(shù)表達(dá)式+項(xiàng)|算術(shù)表達(dá)式-項(xiàng)項(xiàng)f因式|項(xiàng)*因式|項(xiàng)/因式因式f變量|常數(shù)|（算術(shù)表達(dá)式）變量f標(biāo)識(shí)符標(biāo)識(shí)符f標(biāo)識(shí)符字母|標(biāo)識(shí)符數(shù)字|字母常數(shù)-整數(shù)|浮點(diǎn)數(shù)整數(shù)f數(shù)字|數(shù)字整數(shù)浮點(diǎn)數(shù)f?整數(shù)|整數(shù)?整數(shù)字母'A|B|C|X|Y|Z|a|b|c|x|y|z數(shù)字-0|1|2|9（2）在所給文法G復(fù)合語句的基礎(chǔ)上，適當(dāng)擴(kuò)大分析對(duì)象，增加功能。如賦值語句的左部不再只局限于簡(jiǎn)單變量，還可以是下標(biāo)變量等；右部的算術(shù)表達(dá)式中可以包括函數(shù)調(diào)用、數(shù)組元素等。除賦值語句外，還可進(jìn)一步選擇高級(jí)語言的其它語法結(jié)構(gòu)類

7、型，如流程控制語句、子程序結(jié)構(gòu)語句、說明語句等。語法分析的結(jié)果以語法樹的形式輸出，并顯示分析過程的信息（如分析棧、符號(hào)棧、當(dāng)前應(yīng)被歸約的最左子串、歸約后所得的符號(hào)等）。（3）增強(qiáng)錯(cuò)誤檢查和處理能力。例如，當(dāng)輸入的源程序存在錯(cuò)誤時(shí)，把所發(fā)現(xiàn)的每一處錯(cuò)誤的性質(zhì)（錯(cuò)誤編碼）和位置填入一張表中，以備以后輸出之用；同時(shí)再跳過錯(cuò)誤所在的語法范疇（如單詞、表達(dá)式、語句等），繼續(xù)對(duì)輸入串的后續(xù)部分進(jìn)行編譯。至于對(duì)錯(cuò)誤的具體處理措施應(yīng)結(jié)合所采用的語法分析方法，以LR分析為例，可對(duì)LR分析表中的空白單元進(jìn)行出錯(cuò)原因分析，填入一個(gè)指向出錯(cuò)處理子程序的指示字。（4）選作：學(xué)習(xí)編譯器的自動(dòng)生成工具LEX、YACC（或其

8、它類似工具）的使用方法，運(yùn)用LEX和YACC編寫并生成以下文法G程序刁所定義語言的詞法和語法分析程序。G程序:程序fPROGRAM標(biāo)識(shí)符;分程序分程序-變量說明BEGIN語句表END.變量說明-VAR變量說明表;變量說明表f變量表:類型|變量表:類型；變量說明表類型fINTEGER|REAL變量表-變量|變量,變量表語句表語句|語句;語句表語句賦值語句|條件語句|WHILE語句|復(fù)合語句賦值語句-變量:=算術(shù)表達(dá)式條件語句fIF關(guān)系表達(dá)式THEN語句ELSE語句WHILE語句fWHILE關(guān)系表達(dá)式DO語句復(fù)合語句fBEGIN語句表END算術(shù)表達(dá)式f項(xiàng)|算術(shù)表達(dá)式+項(xiàng)|算術(shù)表達(dá)式-項(xiàng)項(xiàng)f因式|項(xiàng)

9、*因式|項(xiàng)/因式因式f變量|常數(shù)|（算術(shù)表達(dá)式）關(guān)系表達(dá)式f算術(shù)表達(dá)式關(guān)系符算術(shù)表達(dá)式變量f標(biāo)識(shí)符標(biāo)識(shí)符f標(biāo)識(shí)符字母|標(biāo)識(shí)符數(shù)字|字母常數(shù)-整數(shù)|浮點(diǎn)數(shù)整數(shù)f數(shù)字|數(shù)字整數(shù)浮點(diǎn)數(shù)f?整數(shù)|整數(shù)?整數(shù)關(guān)系符-|=|=|=|字母'A|B|C|X|Y|Z|a|b|c|x|y|z數(shù)字-0|1|2|9實(shí)驗(yàn)三：（1）增加語義分析的范圍，如進(jìn)一步完成布爾表達(dá)式（參見教材P200）、常見程序流程控制語句（參見教材P205）等的翻譯。（2）語法制導(dǎo)翻譯過程的可視化處理，選擇編譯各階段用到的典型算法實(shí)現(xiàn)其動(dòng)態(tài)演示。（3）選作：完成實(shí)驗(yàn)二中文法G程序所定義的語言的語法制導(dǎo)翻譯程序。2）自擬題目：根據(jù)小組成員

10、的興趣自主選擇或自定實(shí)驗(yàn)題目。要求先提交一份申請(qǐng)文檔，說明所選題目、實(shí)現(xiàn)方案和技術(shù)路線；然后小組成員再與教師就題目的難易程度和工作量具體討論調(diào)整，細(xì)化課程設(shè)計(jì)內(nèi)容，最終確定要完成的主要工作；在得到老師的認(rèn)可之后方可繼續(xù)進(jìn)行。實(shí)驗(yàn)一詞法分析程序?qū)崿F(xiàn)一、實(shí)驗(yàn)?zāi)康呐c要求通過編寫和調(diào)試一個(gè)詞法分析程序，掌握在對(duì)程序設(shè)計(jì)語言的源程序進(jìn)行掃描的過程中，將字符流形式的源程序轉(zhuǎn)化為一個(gè)由各類單詞符號(hào)組成的流的詞法分析方法。二、實(shí)現(xiàn)方法與環(huán)境詞法分析是編譯程序的第一個(gè)處理階段，可以通過兩種途徑來構(gòu)造詞法分析程序。其一是根據(jù)對(duì)語言中各類單詞的某種描述或定義（如BNF），用手工的方式（例如可用C語言）構(gòu)造詞法分析程

11、序。一般地，可以根據(jù)文法或狀態(tài)轉(zhuǎn)換圖構(gòu)造相應(yīng)的狀態(tài)矩陣，該狀態(tài)矩陣連同控制程序一起便組成了編譯器的詞法分析程序；也可以根據(jù)文法或狀態(tài)轉(zhuǎn)換圖直接編寫詞法分析程序。構(gòu)造詞法分析程序的另外一種途徑是所謂的詞法分析程序的自動(dòng)生成，即首先用正規(guī)式對(duì)語言中的各類單詞符號(hào)進(jìn)行詞型描述，并分別指出在識(shí)別單詞時(shí)，詞法分析程序所應(yīng)進(jìn)行的語義處理工作，然后由一個(gè)所謂詞法分析程序的構(gòu)造程序?qū)ι鲜鲂畔⑦M(jìn)行加工。如美國(guó)BELL實(shí)驗(yàn)室研制的LEX就是一個(gè)被廣泛使用的詞法分析程序的自動(dòng)生成工具。總的來說，開發(fā)一種新語言時(shí)，由于它的單詞符號(hào)在不停地修改，采用LEX等工具生成的詞法分析程序比較易于修改和維護(hù)。一旦一種語言確定了，

12、則采用手工編寫詞法分析程序效率更高。三、實(shí)驗(yàn)內(nèi)容基本實(shí)驗(yàn)題目：若某一程序設(shè)計(jì)語言中的單詞包括五個(gè)關(guān)鍵字begin、end、if、then、else;標(biāo)識(shí)符；無符號(hào)常數(shù)；六種關(guān)系運(yùn)算符；一個(gè)賦值符和四個(gè)算術(shù)運(yùn)算符，試構(gòu)造能識(shí)別這些單詞的詞法分析程序（各類單詞的分類碼參見表I）。輸入：由符合和不符合所規(guī)定的單詞類別結(jié)構(gòu)的各類單詞組成的源程序文件。輸出：把所識(shí)別出的每一單詞均按形如（CLASS，VALUE）的二元式形式輸出，并將結(jié)果放到某個(gè)文件中。對(duì)于標(biāo)識(shí)符和無符號(hào)常數(shù)，CLASS字段為相應(yīng)的類別碼的助記符；VALUE字段則是該標(biāo)識(shí)符、常數(shù)的具體值；對(duì)于關(guān)鍵字和運(yùn)算符，采用一詞一類的編碼形式，僅需在

13、二元式的CLASS字段上放置相應(yīng)單詞的類別碼的助記符，VALUE字段則為“空”。擴(kuò)展實(shí)驗(yàn)：試對(duì)基本實(shí)驗(yàn)內(nèi)容進(jìn)行擴(kuò)充，例如：在詞法分析過程中建立變量名表,以備后續(xù)的編譯過程查詢；擴(kuò)充關(guān)鍵字的數(shù)目、增加邏輯運(yùn)算符等單詞類別、將常數(shù)再細(xì)分成字符串常量、整型常量和實(shí)型常量等；添加詞法分析中單詞出錯(cuò)的位置和錯(cuò)誤類型，以及刪除注釋部分等。表I語言中的各類單詞符號(hào)及其分類碼表單詞符號(hào)類別編碼類別碼的助記符單詞值begin1BEGINend2ENDif3IFthen4THENelse5ELSE標(biāo)識(shí)符6ID字母打頭的字母數(shù)字串無符號(hào)常數(shù)7UCON機(jī)內(nèi)二進(jìn)制表小<8LT<二9LE=10EQ<&g

14、t;11NE>12GT>=13GE:=14IS+15PL-16MI*17MU/18DI四、要求1、上機(jī)前的準(zhǔn)備：完成詞法分析程序的程序流圖，并選擇好相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。2、編程：用C語言或你熟悉的其它高級(jí)程序設(shè)計(jì)語言編寫掃描器程序。3、調(diào)試：將各個(gè)模塊連接成一個(gè)完整程序，并整體調(diào)試成功。4、測(cè)試：用于測(cè)試掃描器的實(shí)例源文件中應(yīng)有詞法正確的，也應(yīng)有錯(cuò)誤的字符串,并至少應(yīng)包含兩行以上的源代碼。5、輸出結(jié)果：對(duì)于輸入的測(cè)試用例的源程序文件，以對(duì)照的形式將掃描器的分析結(jié)果在輸出文件中表示出來，必要時(shí)給出錯(cuò)誤提示信息。例如，若輸入文件中的內(nèi)容為：“ifmyid>=1.5E-2+100the

15、nx:=y”,則輸出文件中的內(nèi)容應(yīng)為：(IF,)對(duì)應(yīng)“if”(ID,'myid)'對(duì)應(yīng)"myid"GE，）對(duì)應(yīng)“>=”UCON，0.015)對(duì)應(yīng)“1.5E-2”PL，）對(duì)應(yīng)“+”UCON，100）對(duì)應(yīng)“100”THEN）對(duì)應(yīng)“then”ID，x)對(duì)應(yīng)“x”IS，）對(duì)應(yīng)“:=”ID，y)對(duì)應(yīng)“y”五、參考實(shí)現(xiàn)方法1、處理過程簡(jiǎn)述：在一個(gè)程序設(shè)計(jì)語言中，一般都含有若干類單詞符號(hào)，為此可首先為每類單詞建立一張狀態(tài)轉(zhuǎn)換圖，然后將這些狀態(tài)轉(zhuǎn)換圖合并成一張統(tǒng)一的狀態(tài)圖，即得到了一個(gè)有限自動(dòng)機(jī)，再進(jìn)行必要的確定化和狀態(tài)數(shù)最小化處理，最后添加當(dāng)進(jìn)行狀態(tài)轉(zhuǎn)移時(shí)所需執(zhí)行的

16、語義動(dòng)作，就可以據(jù)此構(gòu)造詞法分析程序了。為了使詞法分析程序結(jié)構(gòu)比較清晰，且盡量避免某些枝節(jié)問題的糾纏，我們假定要編譯的語言中，全部關(guān)鍵字都是保留字，程序員不得將它們作為源程序中的標(biāo)識(shí)符；在源程序的輸入文本中，關(guān)鍵字、標(biāo)識(shí)符、無符號(hào)常數(shù)之間，若未出現(xiàn)關(guān)系和算術(shù)運(yùn)算符以及賦值符，則至少須用一個(gè)空白字符加以分隔。作了這些限制以后，就可以把關(guān)鍵字和標(biāo)識(shí)符的識(shí)別統(tǒng)一進(jìn)行處理。即每當(dāng)開始識(shí)別一個(gè)單詞時(shí)，若掃視到的第一個(gè)字符為字母，則把后續(xù)輸入的字母或數(shù)字字符依次進(jìn)行拼接，直至掃視到非字母、數(shù)字字符為止，以期獲得一個(gè)盡可能長(zhǎng)的字母數(shù)字字符串，然后以此字符串查所謂保留字表（此保留字表要事先造好），若查到此字符

17、串，則取出相應(yīng)的類別碼；反之，則表明該字符串應(yīng)為一標(biāo)識(shí)符。采用上述策略后，針對(duì)表I中的部分單詞可以參考教材P80的圖3-22（見圖1）和P81的程序3-4（見程序一），用C語言編寫出符合以上幾項(xiàng)要求的一個(gè)掃描器程序。注意還需要按照實(shí)驗(yàn)題目的具體要求將其中的整常數(shù)改為無符號(hào)常數(shù)。關(guān)于無符號(hào)數(shù)的文法可參見教材P49，其識(shí)別方法參考P51的圖3-3（見圖2）、P55的表3-1（見表II）和P57的程序3-3（見程序二）。hd其它errorGETCHARGOTOSTART圖1識(shí)別表I所列語言中的部分單詞的DFA及相關(guān)的語義過程圖1中所出現(xiàn)的語義變量及語義函數(shù)的含義和功能說明如下：函數(shù)GETCHAR:每

18、調(diào)用一次，就把掃描指示器當(dāng)前所指示的源程序字符送入字符變量ch,然后把掃描指示器前推一個(gè)字符位置。字符數(shù)組TOKEN:用來依次存放一個(gè)單詞詞文中的各個(gè)字符。函數(shù)CAT:每調(diào)用一次，就把當(dāng)前ch中的字符拼接于TOKEN中所存字符串的右邊。函數(shù)LOOKUP:每調(diào)用一次，就以TOKEN中的字符串查保留字表，若查到，就將相應(yīng)關(guān)鍵字的類別碼賦給整型變量c；否則將c置為零。函數(shù)RETRACT:每調(diào)用一次，就把掃描指示器回退一個(gè)字符位置（即退回多讀的那個(gè)字符）。函數(shù)OUT:一般僅在進(jìn)入終態(tài)時(shí)調(diào)用此函數(shù)，調(diào)用的形式為OUT（c,VAL）。其中，實(shí)參c為相應(yīng)單詞的類別碼助記符；實(shí)參VAL為TOKEN（即詞文）或

19、為空串。函數(shù)OUT的功能是，在送出一個(gè)單詞的內(nèi)部表示之后，返回到調(diào)用該詞法分析程序的那個(gè)程序。程序一根據(jù)圖1編寫的掃描器# include<stdio.h># include<ctype.h># include<string.h># defineID6# defineINT7# defineLT8# defineLE9# defineEQ10# defineNE11# defineGT12#defineGE13charTOKEN20；externintlookup(char*);externvoidout(int,char*);externreport_er

20、ror(void);voidscanner_example(FILE*fp)charch;inti,c;ch=fgetc(fp);if(isalpha(ch)/*itmustbeaidentifer!*/TOKEN0=ch;ch=fgetc(fp);i=1;while(isalnum(ch)TOKENi=ch;i+；ch=fgetc(fp);TOKENi=0'fseek(fp,-1,1);/*retract*/c=lookup(TOKEN);if(c=0)out(ID,TOKEN);elseout(c,"")；elseif(isdigit(ch)TOKEN0=ch;

21、ch=fgetc(fp);i=1;while(isdigit(ch)TOKENi=ch;i+;ch=fgetc(fp);TOKENi='0'fseek(fp,-1,1);out(INT,TOKEN);elseswitch(ch)case之'ch=fgetc(fp);if(ch='=')out(LE,"");elseif(ch=>")out(NE,"");elsefseek(fp,-1,1);out(LT,"");break;case'=Ut(EQ,""

22、);break;case%'ch=fgetc(fp);if(ch='=')out(GE,"");elsefseek(fp,-1,1);out(GT,"");break;default:report_error();break;return;2、兩點(diǎn)提示：程序一中所用的若干函數(shù)以及主程序有待于具體編寫，并需事先建立好保留字表，以備查詢。例如：/*建立保留字表*/#defineMAX_KEY_NUMBER20/*關(guān)鍵字的數(shù)量*/#defineKEY_WORD_END“waitingforyourexpanding”/*關(guān)鍵字結(jié)束標(biāo)記*

23、/char*KeyWordTableMAX_KEY_NUMBER=“begin”,“end”,“if”,“then”,“else”,KEY_WORD_END;/*查保留字表，判斷是否為關(guān)鍵字*/intlookup(char*token)intn=0;while(strcmp(KeyWordTablen,KEY_WORD_END)/*strcmp比較兩串是否相同，若相同返回0*/if(!strcmp(KeyWordTablen,token)/*比較token所指向的關(guān)鍵字和保留字表中哪個(gè)關(guān)鍵字相符*/returnn+1;/*根據(jù)單詞分類碼表I，設(shè)置正確的關(guān)鍵字類別碼，并返回此類別碼的值*/bre

24、ak;n+;return0;/*單詞不是關(guān)鍵字，而是標(biāo)識(shí)符*/另外，在掃描源程序字符串時(shí)，一旦識(shí)別出關(guān)鍵字、標(biāo)識(shí)符、無符號(hào)常數(shù)以及運(yùn)算符中之一，即以二元式形式(類別編碼的助記符，值)輸出單詞到指定文件中。每次調(diào)用該詞法分析程序，它均能自動(dòng)繼續(xù)掃描下去，形成下一個(gè)單詞，直至整個(gè)源程序全部掃描完畢，并形成相應(yīng)的單詞串形式的源程序文件。需要將程序一中的整常數(shù)擴(kuò)展為無符號(hào)常數(shù)，以滿足題目的要求。描述無符號(hào)數(shù)的右線性文法G1<無符號(hào)數(shù)>如下：無符號(hào)數(shù)-d余留無符號(hào)數(shù)無符號(hào)數(shù)f小數(shù)部分無符號(hào)數(shù)-d余留無符號(hào)數(shù)-d余留無符號(hào)數(shù)余留無符號(hào)數(shù)-十進(jìn)小數(shù)余留無符號(hào)數(shù)-E指數(shù)部分余留無符號(hào)數(shù)-d余留無符

25、號(hào)數(shù)f-十進(jìn)小數(shù)-E指數(shù)部分十進(jìn)小數(shù)fd十進(jìn)小數(shù)十進(jìn)小數(shù)-d小數(shù)部分fd十進(jìn)小數(shù)小數(shù)部分d指數(shù)部分fd余留整指數(shù)指數(shù)部分7+整指數(shù)指數(shù)部分-整指數(shù)指數(shù)部分d整指數(shù)-d余留整指數(shù)整指數(shù)-d余留整指數(shù)-d余留整指數(shù)余留整指數(shù)-d圖2所示為上述文法的狀態(tài)轉(zhuǎn)換圖，其中編號(hào)0、1、2、6分別代表非終結(jié)符號(hào)無符號(hào)數(shù)、余留無符號(hào)數(shù)、十進(jìn)小數(shù)、小數(shù)部分、指數(shù)部分、整指數(shù)及余留整指數(shù)。圖2文法G1卜無符號(hào)數(shù)的狀態(tài)轉(zhuǎn)換圖無符號(hào)數(shù)識(shí)別中的語義處理方法詳見教材P56。表II即為嵌入了語義動(dòng)作的狀態(tài)矩陣，其功能是在掃描源程序字符串的過程中，把識(shí)別出的字符串形式的無符號(hào)數(shù)的值，逐步轉(zhuǎn)換為相應(yīng)的二進(jìn)制整數(shù)（ICON）或二進(jìn)

26、制浮點(diǎn)數(shù)（FCON）的內(nèi)部形式。（注：考慮能否采用C語言的庫函數(shù)實(shí)現(xiàn)此語義處理工作；是否可將無符號(hào)常數(shù)這一類單詞進(jìn)一步細(xì)分成整型常數(shù)和浮點(diǎn)型常數(shù)兩類單詞。）根據(jù)表II所示的加入了語義過程說明的識(shí)別無符號(hào)數(shù)的狀態(tài)矩陣，編寫詞法分析程序，部分實(shí)現(xiàn)代碼如程序二所示。123456789101112131415161718192021222324252627表II包含語義處理過程的識(shí)別無符號(hào)數(shù)的狀態(tài)矩陣當(dāng)前班態(tài)目接字符語丈處理操作或接受動(dòng)作后*狀奇0d<n=0ip=聊1*=0n=Ojp=Oie=1a)-3other織別去MNULL1d如lO+dpI2E4Other回送整敷ICON=wi)砧丸2d(

27、11+Iw»w10+di：)2£4other(送客常教FCON-w*后*p-nJJ婚束3d(n+jw»w«2otherNULL4d(p«»pIQ+d*)fi+5忸一】i)5other跟別失敗NULL&dpr*)6otherift別失«NULL6d(p=p*+56othtr回送實(shí)常低FCOM=k-pow(10,e-p-rd/堇邕程序二單詞分類碼為UCON的無符號(hào)數(shù)的識(shí)別程序#include<stdio.h>#include<ctype.h>#include<math.h># defi

28、neDIGIT1# definePOINT2# defineOTHER3# definePOWER4# definePLUS5# defineMINUS6#defineUCON7/Supposetheclassnumberofunsignedconstantis7#defineClassOther200#defineEndState-1intw,n,p,e,d;intClass;/UsedtoindicateclassofthewordintICON;floatFCON;staticintCurrentState;/Usedtopresentcurrentstate,theinitialval

29、ue:0intGetChar(void);intEXCUTE(int,int);intLEX(void);intHandleOtherWord(void)returnClassOther;intHandleError(void)printf("Error!n");return0;28293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485intGetChar(void)intc;c=getchar();i

30、f(isdigit(c)d=c-'0'returnDIGIT;if(c='.')returnPOINT;if(c='E'|c='e')returnPOWER;if(c='+')returnPLUS;if(c=-'')returnMINUS;returnOTHER;intEXCUTE(intstate,intsymbol)switch(state)case0:switch(symbol)caseDIGIT:n=0;p=0;e=1;w=d;CurrentState=1;Class=UCON;break;

31、casePOINT:w=0;n=0;p=0;e=1;CurrentState=3;Class=UCON;break;default:HandleOtherWord();Class=ClassOther;CurrentState=EndState;break;case1:switch(symbol)caseDIGIT:w=w*10+d;break;/CurrentState=1casePOINT:CurrentState=2;break;casePOWER:CurrentState=4;break;default:ICON=w;CurrentState=EndState;break；case2:

32、switch(symbol)caseDIGIT:n+;w=w*10+d;break;casePOWER:CurrentState=4;break;default:FCON=w*pow(10,e*p-n);CurrentState=EndState;break;case3:switch(symbol)caseDIGIT:n+;w=w*10+d;CurrentState=2;break;default:HandleError()；CurrentState=EndState;break；case4:switch(symbol)caseDIGIT:p=p*10+d;CurrentState=6;bre

33、ak;caseMINUS:e=-1;CurrentState=5;break;casePLUS:CurrentState=5;break;default:HandleError();CurrentState=EndState;break；case5:switch(symbol)caseDIGIT:p=p*10+d;CurrentState=6;break;default:HandleError();CurrentState=EndState;break;case6:switch(symbol)case:DIGIT:p=p*10+d;break;default:FCON=w*pow(10,e*p

34、-n);CurrentState=EndState;break;returnCurrentState;intLEX(void)intch;CurrentState=0;while(CurrentState!=EndState)ch=GetChar();EXCUTE(CurrentState,ch);returnClass;8687888990919293949596979899100101102103104105106實(shí)驗(yàn)二語法分析程序?qū)崿F(xiàn)一、實(shí)驗(yàn)?zāi)康呐c要求通過設(shè)計(jì)、編制、調(diào)試一個(gè)典型的語法分析程序(任選一種有代表性的語法分析方法，如算符優(yōu)先法、遞歸下降法、LL(1)、SLR(1)、LR(1)

35、等，作為編制語法分析程序的依據(jù))，對(duì)實(shí)驗(yàn)一所得掃描器提供的單詞序列進(jìn)行語法檢查和結(jié)構(gòu)分析，實(shí)現(xiàn)并進(jìn)一步掌握常用的語法分析方法。二、一般實(shí)現(xiàn)方法說明為了在對(duì)源程序的一遍掃描過程中，同時(shí)完成詞法和語法分析任務(wù)，應(yīng)注意修改實(shí)驗(yàn)一中的詞法分析程序，將它編寫為子程序的形式，以便供語法分析程序調(diào)用。另外，應(yīng)加強(qiáng)錯(cuò)誤檢查，對(duì)輸入符號(hào)串中的詞法、語法錯(cuò)誤，給出必要的說明信息，盡可能多地、確切地指出錯(cuò)誤的位置、原因和性質(zhì)。例如，在詞法分析階段，對(duì)當(dāng)前正在處理白字符ch,可進(jìn)一步定義一些與該字符相關(guān)的信息row和col,分別表示該字符所在的行和列，這些內(nèi)容在出錯(cuò)處理時(shí)用來提供和源程序位置相關(guān)的信息。即定義：cha

36、rch;/*Thecurrentcharacter*/introw;/*Thelinenumberpositionofthecurrentcharacter*/intcol;/*Thecolumnnumberpositionofthecurrentcharacter*/三、實(shí)驗(yàn)內(nèi)容基本實(shí)驗(yàn)題目：選擇對(duì)各種常見高級(jí)程序設(shè)計(jì)語言都較為通用的語法結(jié)構(gòu)算術(shù)表達(dá)式的一個(gè)簡(jiǎn)化子集作為分析對(duì)象，根據(jù)如下描述其語法結(jié)構(gòu)的BNF定義G2算術(shù)表達(dá)式，任選一種學(xué)過的語法分析方法，針對(duì)運(yùn)算對(duì)象為無符號(hào)常數(shù)和變量的四則運(yùn)算，設(shè)計(jì)并實(shí)現(xiàn)一個(gè)語法分析程序。G2算術(shù)表達(dá)式：算術(shù)表達(dá)式項(xiàng)|算術(shù)表達(dá)式+項(xiàng)|算術(shù)表達(dá)式-項(xiàng)項(xiàng)f因式

37、|項(xiàng)*因式|項(xiàng)/因式因式f運(yùn)算對(duì)象|(算術(shù)表達(dá)式)若將語法范疇算術(shù)表達(dá)式、項(xiàng)、因式和運(yùn)算對(duì)象分別用E、T、F和i代表，則G2可寫成：G2E:E-T|E+T|E-TTfF|T*F|T/FFfi|(E)輸入：由實(shí)驗(yàn)一輸出的單詞串，例如：UCON,PL,UCON,MU,ID輸出：若輸入源程序中的符號(hào)串是給定文法的句子，則輸出“RIGHT”，并且給出每一步分析過程；若不是句子，即輸入串有錯(cuò)誤，則輸出“ERROR”，并且顯示分析至此所得的中間結(jié)果，如分析棧、符號(hào)棧中的信息等，以及必要的出錯(cuò)說明信息。擴(kuò)展實(shí)驗(yàn)：對(duì)所給算術(shù)表達(dá)式的文法G2，完成兩種以上不同的語法分析程序的設(shè)計(jì)與實(shí)現(xiàn)；或在G2的基礎(chǔ)上，適當(dāng)增

38、加功能，如進(jìn)一步選擇高級(jí)語言中的賦值語句、復(fù)合語句、流程控制語句等其它類型的語法結(jié)構(gòu)作為分析對(duì)象。四、要求1 、上機(jī)前的準(zhǔn)備：結(jié)合題目的要求，確定語法分析程序的流程圖，同時(shí)考慮相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用C或其它高級(jí)語言初步編寫一個(gè)語法分析源程序。2、調(diào)試：將詞法、語法分析合在一起構(gòu)成一個(gè)完整的程序，并調(diào)試成功。3、測(cè)試：供測(cè)試的例子應(yīng)包括符合語法規(guī)則的語句，及分析程序能判別的若干錯(cuò)例。4、結(jié)果輸出：對(duì)于所輸入的字符串，不論對(duì)錯(cuò)，都應(yīng)有明確的信息告訴外界。5、編寫的源程序中應(yīng)有較為詳細(xì)的說明和注釋。例如，對(duì)文法機(jī)內(nèi)表示的解釋、數(shù)據(jù)結(jié)構(gòu)的說明、函數(shù)的作用、全局變量的含義等等。五、參考實(shí)現(xiàn)方法下面分別簡(jiǎn)要給

39、出基于遞歸下降法、預(yù)測(cè)分析法、算符優(yōu)先法、SLR(1)四種語法分析程序的開發(fā)方法示例說明，僅供參考。1、示例一：采用具有遞歸功能的高級(jí)語言編制遞歸下降法的語法分析程序。運(yùn)算對(duì)象i可以進(jìn)一步定義為變量、常數(shù)等，例如，此處將i定義為：if變量變量f標(biāo)識(shí)符標(biāo)識(shí)符f字母字母.I|B|C|-|X|Y|Z利用擴(kuò)充的BNF消除G2E中E和T的直接左遞歸后，采用遞歸下降法分析上述算術(shù)表達(dá)式的框圖見圖3。其中ZC過程為總控程序，被設(shè)計(jì)成可以分析無窮多個(gè)算術(shù)表達(dá)式，主要完成：通知外界鍵入算術(shù)表達(dá)式?？刂艵過程分析算術(shù)表達(dá)式。根據(jù)分析結(jié)果之正誤，分別輸出不同的信息。E、T和F三個(gè)過程分別對(duì)應(yīng)算術(shù)表達(dá)式、項(xiàng)和因式三個(gè)

40、產(chǎn)生式的處理。它們都利用到一個(gè)公共過程ADVANCE。ADVANCE過程負(fù)責(zé)從輸入字符串ST中取出下一個(gè)字符，并存入SYM中等待分析；然后再剔除ST中的首字符，這可通過挪動(dòng)字符串指針的辦法來實(shí)現(xiàn)(而實(shí)際上是通過調(diào)用詞法分析程序來實(shí)現(xiàn)ADVANCE功能的)。變量TZ之值標(biāo)志分析的結(jié)果，表明表達(dá)式是否有錯(cuò)。(a)(d)圖3遞歸下降法分析算術(shù)表達(dá)式的框圖（a）ZC過程（b）E過程T過程（d）F過程（e）ADVANCE過程2 、示例二：基于預(yù)測(cè)分析法的語法分析程序。參考教材P121例4.3，首先編寫無二義性的簡(jiǎn)單算術(shù)表達(dá)式的文法(4.1)，并通過消除左遞歸對(duì)其進(jìn)行改寫得到文法(4.1)。然后求出如表4

41、-1所示的各個(gè)FIRST集和FOLLOW集。再檢查是不是LL(1)文法，并按照LL(1)文法構(gòu)造如表4-2所示的預(yù)測(cè)分析表。最后根據(jù)預(yù)測(cè)分析器的工作流程，實(shí)現(xiàn)預(yù)測(cè)分析器的控制程序。3 、示例三：用C語言編制算符優(yōu)先分析法的語法分析程序如程序三所示。其中使用了分析棧stack，用來在分析過程中存放當(dāng)前句型的某一前綴，一旦句型的最左素短語在棧頂形成，便立即進(jìn)行歸約。程序三算符優(yōu)先分析算法#defineRIGHT1#defineERROR0#defineMAXINPUT300#defineMAXSTACK100#defineSTARTSYMBOL'S'intstackMAXSTACK

42、，aMAXINPUT;/*aisinputline*/intIsHigherThan(int,int);/*prioritydetection*/intIsLowerThan(int,int);/*prioritydetection*/intIsEqualTo(int,int);/*prioritydetection*/intReduce(intbegin,intend,intlen);intIsVt(int);/*determineifstacksymbolisinVt*/intparser(void)inti,k,r,NewVn;/*NewVnholdsleftsideofaproduct

43、ion*/i=0;k=0;/*i,kisindexofaandstackseparately*/stack0='#'；dointj;r=ai+;if(IsVt(stackk)j=k;elsej=k-1;while(IsHigherThan(stackj,r)intq;doq=stackj;if(IsVt(stackj-1)j-;elsej-=2;while(!IsLowerThan(stackj,q);NewVn=Reduce(stackj+1,stackk,k-j);k=j+1;/*reducetheleftmostprimephrase*/stackk=NewVn;/*it

44、isstackj+1stackj+2stackk*/*endofwhile*/if(IsLowerThan(stackj,r)|IsEqualTo(stackj,r)stack+k=r;elsereturnERROR;while(r!='#');returnRIGHT;程序三給出的僅是采用算符優(yōu)先分析方法的示意性識(shí)別算法，還有許多工作要做。如：首先要確定一種合適的數(shù)據(jù)結(jié)構(gòu)，以便構(gòu)造所給文法G2卜算術(shù)表達(dá)式刁的機(jī)內(nèi)表示。然后，構(gòu)造該文法的算符優(yōu)先關(guān)系矩陣，在此可以根據(jù)算術(shù)表達(dá)式中各算符的優(yōu)先級(jí)和結(jié)合性，直接手工構(gòu)造算符優(yōu)先關(guān)系。最后，編寫程序三中所用到的各個(gè)函數(shù)，完成整個(gè)算符優(yōu)先

45、語法分析器的開發(fā)。4、示例四：SLR(1)分析器的開發(fā)。首先，對(duì)于分析對(duì)象，即算術(shù)表達(dá)式的文法G2E,引入一個(gè)新的開始符號(hào)E',得到G2E的拓廣文法G2'E'0.E'fE1.EfE+T2.E-E-T3.EfT4.TfT*F5.T-T/F6.TfF7.Ff(E)8.FT求出文法中各個(gè)非終結(jié)符號(hào)的FOLLOW集如下：Follow(E)=#,),+,-Follow(T)=#,),+,-,*,/Follow(F)=#,),+,-,*,/然后，根據(jù)文法G2'E構(gòu)造識(shí)別其全部活前綴的DFA,以便據(jù)此構(gòu)造SLR(1)分析表，參見表III。表IIIG2'E

46、9;的SLR(1)分析表狀態(tài)ACTIONGOTO1()+-*/i#ETF0S4S51231S6S7Acc2R3R3R3S8S9R33R6R6R6R6R6R64S4S510235R8R8R8R8R8R86S4S51137S4S51238S4S5139S4S51410S15S6S711R1R1R1S8S9R112R2R2R2S8S9R213R4R4R4R4R4R414R5R5R5R5R5R515R7R7R7R7R7R7最后，編程實(shí)現(xiàn)SLR(1)分析表的驅(qū)動(dòng)程序，即開發(fā)LR分析器的總控程序，完成對(duì)算術(shù)表達(dá)式的識(shí)別。實(shí)驗(yàn)三語義分析程序?qū)崿F(xiàn)一、實(shí)驗(yàn)?zāi)康呐c要求在實(shí)現(xiàn)詞法、語法分析程序的基礎(chǔ)上，編寫相應(yīng)的語

47、義子程序，進(jìn)行語義處理，加深對(duì)語法制導(dǎo)翻譯原理的理解，進(jìn)一步掌握將語法分析所識(shí)別的語法范疇變換為某種中間代碼（四元式）的語義分析方法，并完成相關(guān)語義分析器的代碼開發(fā)。二、一般實(shí)現(xiàn)方法語法制導(dǎo)翻譯模式是在語法分析的基礎(chǔ)上，增加語義操作來實(shí)現(xiàn)的，實(shí)際上是對(duì)前后文無關(guān)文法的一種擴(kuò)展。一般而言，首先需要根據(jù)進(jìn)行的語義分析工作，完成對(duì)給定文法的必要拆分和語義動(dòng)作的編寫，從而為每一個(gè)產(chǎn)生式都配備相應(yīng)的語義子程序，以便在進(jìn)行語法分析的同時(shí)進(jìn)行語義解釋。即在語法分析過程中，每當(dāng)用一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，語法分析程序除執(zhí)行相應(yīng)的語法分析動(dòng)作之外，還要調(diào)用相應(yīng)的語義子程序，以便完成生成中間代碼、查填有關(guān)表格、

48、檢查并報(bào)告源程序中的語義錯(cuò)誤等工作。每個(gè)語義子程序需指明相應(yīng)產(chǎn)生式中各個(gè)符號(hào)的具體含義，并規(guī)定使用該產(chǎn)生式進(jìn)行分析時(shí)所應(yīng)采取的語義動(dòng)作。這樣，語法制導(dǎo)翻譯程序在對(duì)源程序從左到右進(jìn)行的一遍掃描中，既完成語法分析任務(wù)，又完成語義分析和中間代碼生成方面的工作。本實(shí)驗(yàn)要求從編譯器的整體設(shè)計(jì)出發(fā)，重點(diǎn)通過對(duì)實(shí)驗(yàn)二中語法分析程序的擴(kuò)展，完成一個(gè)編譯器前端程序的編寫、調(diào)試和測(cè)試工作，形成一個(gè)將源程序翻譯為中間代碼序列的編譯系統(tǒng)。三、實(shí)驗(yàn)內(nèi)容基本實(shí)驗(yàn)題目：對(duì)文法G2<算術(shù)表達(dá)式>中的產(chǎn)生式添加語義處理子程序，完成無符號(hào)數(shù)的四則運(yùn)算的計(jì)值處理，將輸入的四則運(yùn)算轉(zhuǎn)換為四元式形式的中間代碼。輸入：包含測(cè)

49、試用例（如由無符號(hào)數(shù)和+、-、*、/、（、）構(gòu)成的算術(shù)表達(dá)式）的源程序文件。輸出：將源程序轉(zhuǎn)換為中間代碼形式表示，并將中間代碼序列輸出到文件中。若源程序中有錯(cuò)誤，應(yīng)指出錯(cuò)誤信息。擴(kuò)展實(shí)驗(yàn)：在所給文法G2的基礎(chǔ)上，增加語義分析的范圍，如運(yùn)算對(duì)象不再只局限于常量（和簡(jiǎn)單變量），還可以是函數(shù)調(diào)用、數(shù)組元素等。另外，可進(jìn)一步選擇賦值語句、流程控制語句等其它語法結(jié)構(gòu)類型進(jìn)行語義分析。四、要求1、上機(jī)前的準(zhǔn)備：完成語法制導(dǎo)翻譯系統(tǒng)的程序流圖設(shè)計(jì)，并編寫語義動(dòng)作。2、調(diào)試：結(jié)合實(shí)驗(yàn)一和實(shí)驗(yàn)二中的相關(guān)內(nèi)容，完成編譯器前端程序的調(diào)試工作。3、測(cè)試：對(duì)完成的編譯系統(tǒng)要進(jìn)行全面測(cè)試，供測(cè)試的例子應(yīng)包括符合語義規(guī)則的

50、語句，以及分析程序能夠判別的若干錯(cuò)例，并給出執(zhí)行結(jié)果。4、結(jié)果輸出：將所涉及到的分析過程中的信息，即詞法、語法、語義分析的結(jié)果輸出到文件中。對(duì)于有錯(cuò)誤的輸入字符串，應(yīng)有較為明確的信息告訴外界。五、參考實(shí)現(xiàn)方法示例：對(duì)文法G2卜算術(shù)表達(dá)式在利用遞歸下降法進(jìn)行語法分析的同時(shí)，生成四元式形式的中間代碼序列。其語法制導(dǎo)翻譯程序的核心部分(指表達(dá)式E、項(xiàng)T和因式F的處理)的算法思想，可用程序四所示的框架描述。程序四利用遞歸下降法生成簡(jiǎn)單算術(shù)表達(dá)式的四元式序列E()/*識(shí)別算術(shù)表達(dá)式*/E1_PLACE=T();/*調(diào)用T()分析產(chǎn)生算術(shù)表達(dá)式計(jì)算的第一項(xiàng)E1*/while(SYM=+|SYM=-)ADV

51、ANCE;/*使輸入串指針指向下一個(gè)輸入符號(hào)，即調(diào)用掃描器讀入下一個(gè)單詞符號(hào)*/E2_PLACE=T();/*調(diào)用T()分析產(chǎn)生算術(shù)表達(dá)式計(jì)算的第二項(xiàng)*/T1=NewTemp();/*分配一個(gè)新的臨時(shí)變量，以便存儲(chǔ)計(jì)算結(jié)果*/GEN(±,E1_PLACE,E2_PLACE,T1);/*根據(jù)所給實(shí)參產(chǎn)生一個(gè)四元式，送入四元式表*/E1_PLACE=T1;/*將計(jì)算結(jié)果作為下一次表達(dá)式計(jì)算的第一項(xiàng)*/returnE1_PLACE;T()/*識(shí)別項(xiàng)*/T1_PLACE=F();while(SYM=*|SYM=/)ADVANCE;T2_PLACE=F();T1=NewTemp();GEN(*/,T1_PLACE,T2_PLACE,T1);T1_PLACE=T1;returnT1_PLACE;F()/*識(shí)別<因式>*/if(SYM=標(biāo)識(shí)符)/*在此設(shè)運(yùn)算對(duì)象i為標(biāo)識(shí)符，即簡(jiǎn)單變量*/ADVANCE;returnEntry(i.詞文);/*以標(biāo)識(shí)