城市學(xué)院《編譯原理》實(shí)驗(yàn)指導(dǎo)書

1、編譯原理實(shí)驗(yàn)指導(dǎo)書適用實(shí)驗(yàn)課時(shí)：30適用對(duì)象：城市學(xué)院計(jì)算機(jī)系實(shí)驗(yàn)?zāi)康暮蛢?nèi)容編譯原理實(shí)驗(yàn)的目的是使學(xué)生將編譯理論運(yùn)用到實(shí)際當(dāng)中，實(shí)現(xiàn)一個(gè)簡單語言集的詞法分析程序、語法分析程序和簡單語義處理程序，驗(yàn)證實(shí)際編譯系統(tǒng)的實(shí)現(xiàn)方法，并加深對(duì)編譯理論的認(rèn)識(shí).基本實(shí)驗(yàn)分為三個(gè)部分，實(shí)驗(yàn)一識(shí)別無符號(hào)數(shù)的詞法分析器設(shè)計(jì)實(shí)現(xiàn)、實(shí)驗(yàn)二無符號(hào)數(shù)的算術(shù)四則運(yùn)算LR語法分析器設(shè)計(jì)實(shí)現(xiàn)，實(shí)驗(yàn)三是無符號(hào)數(shù)的算術(shù)四則運(yùn)算語義處理程序?qū)崿F(xiàn)，總的實(shí)驗(yàn)學(xué)時(shí)為30課時(shí)。要求每個(gè)學(xué)生獨(dú)立完成所有實(shí)驗(yàn)要求。每部分基本實(shí)驗(yàn)還包括若干擴(kuò)展實(shí)驗(yàn)，供編程能力較強(qiáng)的學(xué)生自愿進(jìn)行。實(shí)驗(yàn)一 詞法分析程序?qū)崿F(xiàn)一、實(shí)驗(yàn)?zāi)康呐c要求通過編寫和調(diào)試一個(gè)詞法分析程

2、序，掌握在對(duì)程序設(shè)計(jì)語言的源程序進(jìn)行掃描的過程中，將字符形式的源程序流轉(zhuǎn)化為一個(gè)由各類單詞符號(hào)組成的流的詞法分析方法。二、實(shí)驗(yàn)內(nèi)容選取無符號(hào)數(shù)的算術(shù)四則運(yùn)算中的各類單詞為識(shí)別對(duì)象,要求將其中的各個(gè)單詞識(shí)別出來。輸入：由無符號(hào)數(shù)和+，/， ( , ) 構(gòu)成的算術(shù)表達(dá)式,如1.5E+2100。輸出：對(duì)識(shí)別出的每一單詞均單行輸出其類別碼（無符號(hào)數(shù)的值暫不要求計(jì)算）。三、實(shí)現(xiàn)方法與環(huán)境1、首先設(shè)計(jì)識(shí)別各類單詞的狀態(tài)轉(zhuǎn)換圖.描述無符號(hào)常數(shù)的確定、最小化狀態(tài)轉(zhuǎn)換圖如圖1所示。其中編號(hào)0，1，2，,6代表非終結(jié)符號(hào)<無符號(hào)數(shù)、<余留無符號(hào)數(shù)>、<十進(jìn)小數(shù)>、小數(shù)部分、<指

3、數(shù)部分、整指數(shù)>及<余留整指數(shù)， 1，2和6為終態(tài)，分別代表整數(shù)、小數(shù)和科學(xué)計(jì)數(shù)的識(shí)別結(jié)束狀態(tài)。圖1 文法G<無符號(hào)數(shù)>的狀態(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ù)>， 1,2和6為終態(tài),分別代表整數(shù)、小數(shù)和科學(xué)計(jì)數(shù)的識(shí)別結(jié)束狀態(tài)。在一個(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ù)最小化處理，最后據(jù)此構(gòu)造詞法分析程序。四則運(yùn)算算

4、術(shù)符號(hào)的識(shí)別很簡單，直接在狀態(tài)圖的0狀態(tài)分別引出相應(yīng)標(biāo)記的矢線至一個(gè)新的終態(tài)即可。根據(jù)自己的習(xí)慣，也可以將其轉(zhuǎn)換為狀態(tài)矩陣形式。2、詞法分析程序編寫根據(jù)描述語言中各類單詞的文法狀態(tài)轉(zhuǎn)換圖或狀態(tài)矩陣，利用某種語言（C語言或JAVA語言）直接編寫詞法分析程序.3、詞法分析程序測試用于測試掃描器的實(shí)例源文件中應(yīng)有詞法正確的，也應(yīng)有錯(cuò)誤的字符串，對(duì)于輸入的測試用例的源程序文件，以對(duì)照的形式將掃描器的分析結(jié)果信息在輸出文件中表示出來。四、參考資料實(shí)現(xiàn)無符號(hào)數(shù)識(shí)別的參考方法:將設(shè)計(jì)的狀態(tài)轉(zhuǎn)換圖直接轉(zhuǎn)化為一張程序流程圖，并在外層再增加一個(gè)以EOF為循環(huán)終止條件的while循環(huán)，即形成能連續(xù)識(shí)別各類單詞的詞法

5、分析程序.各類單詞的編碼建議如表1。表1 單詞的內(nèi)部編碼單詞符號(hào)類別碼(CLASS）單詞值（VALUE）無符號(hào)數(shù)1數(shù)字值+2無值3無值*4無值/5無值（6無值）7無值五、擴(kuò)展實(shí)驗(yàn)1、試對(duì)基礎(chǔ)實(shí)驗(yàn)識(shí)別的單詞種類進(jìn)行擴(kuò)充，構(gòu)造識(shí)別以下單詞的詞法分析程序.語言中具有的單詞包括五個(gè)有代表性的關(guān)鍵字begin、end、if、then、else;標(biāo)識(shí)符；整型常數(shù)；六種關(guān)系運(yùn)算符；一個(gè)賦值符和四個(gè)算術(shù)運(yùn)算符.參考實(shí)現(xiàn)方法簡述如下。表2 擴(kuò)展單詞分類碼表單詞符號(hào)類別編碼類別碼的助記符單詞值begin1BEGINend2ENDif3IFthen4THENelse5ELSE標(biāo)識(shí)符6ID字母打頭的字母數(shù)字串整常數(shù)7

6、INT數(shù)字串<8LT<=9LE=10EQ<>11NE>12GT=13GE：=14IS+15PL16MI*17MU/18DI處理過程：在此為了使詞法分析程序結(jié)構(gòu)比較清晰，且盡量避免某些枝節(jié)問題的糾纏，假定要編譯的語言中，全部關(guān)鍵字都是保留字，程序員不得將它們作為源程序中的標(biāo)識(shí)符；在源程序的輸入文本中，關(guān)鍵字、標(biāo)識(shí)符、整常數(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)行拼接,直至掃視到非字母、

7、數(shù)字字符為止，以期獲得一個(gè)盡可能長的字母數(shù)字字符串，然后以此字符串查所謂保留字表（此保留字表已事先造好),若查到此字符串，則取出相應(yīng)的類別碼；反之，則表明該字符串應(yīng)為一標(biāo)識(shí)符.采用上述策略后，針對(duì)表2中部分單詞可以構(gòu)造一個(gè)如圖2所示的有限自動(dòng)機(jī)(以狀態(tài)轉(zhuǎn)換圖表示）。在圖2中添加了當(dāng)進(jìn)行狀態(tài)轉(zhuǎn)移時(shí)，詞法分析程序應(yīng)執(zhí)行的語義動(dòng)作。根據(jù)圖2，可用C語言編寫出符合以上幾項(xiàng)要求的一個(gè)相應(yīng)的掃描器程序，如程序一所示。圖2 識(shí)別表I所列語言中的部分單詞的DFA及相關(guān)函數(shù)圖2所出現(xiàn)的變量及函數(shù)的含義和功能說明如下：函數(shù)GETCHAR：每調(diào)用一次，就把掃描指示器當(dāng)前所指示的源程序字符送入字符變量ch，然后把掃描

8、指示器前推一個(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)單詞的類別碼或其助記符；當(dāng)所識(shí)別的單詞為標(biāo)識(shí)符和整數(shù)時(shí)，實(shí)參VAL為TOKEN（即詞文分別為字母數(shù)字串和數(shù)字串），對(duì)于其余種類的

9、單詞,VAL均為空串。函數(shù)OUT的功能是,在送出一個(gè)單詞的內(nèi)部表示之后，返回到調(diào)用該詞法分析程序的那個(gè)程序.參考程序： include <stdio.h># include <ctype。h include string.h define ID 6 define INT 7 define LT 8# define LE 9 define EQ 10# define NE 11# define GT 12# define GE 13char TOKEN20;extern int lookup （char)；extern void out （int, char）；extern r

10、eport_error （void);void scanner_example （FILE *fp)char ch; int i， c;ch=fgetc （fp）；if (isalpha (ch)） /it must be a identifer!/TOKEN0=ch； ch=fgetc (fp)； i=1；while （isalnum （ch）TOKENi=ch; i+;ch=fgetc （fp);TOKENi= 0fseek(fp，-1,1); / retract*/c=lookup （TOKEN）；if (c=0) out (ID，TOKEN); else out （c，" &

11、quot;）;elseif（isdigit（ch）)TOKEN0=ch； 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，” ")；else if(ch=) out （NE," ”）;elsefseek (fp，1,1);out (LT，” ”);break；case =: out（EQ, ” "）; break;c

12、ase ： ch=fgetc(fp）;if（ch=）out（GE，" ");elsefseek(fp,1,1）；out(GT,” ”)；break;default: report_error( ）； break;return；提示：掃描器所用的若干函數(shù)以及主程序有待于具體編寫，并需事先建立好保留字表，以備查詢。例如：/ 建立保留字表 /#define MAX_KEY_NUMBER 20 /*關(guān)鍵字的數(shù)量/define KEY_WORD_END “waiting for your expanding” /*關(guān)鍵字結(jié)束標(biāo)記*/char *KeyWordTableMAX_KEY_

13、NUMBER=“begin”, “end"， “if”, “then"， “else”, KEY_WORD_END;/* 查保留字表,判斷是否為關(guān)鍵字 /int lookup (char *token）int i=0；while (strcmp（KeyWordTablen, KEY_WORD_END） /*strcmp比較兩串是否相同，若相同返回0/if （！strcmp（KeyWordTablen, token)） /*比較token所指向的關(guān)鍵字和保留字表中哪個(gè)關(guān)鍵字相符*/return n+1; /*設(shè)置正確的關(guān)鍵字類別碼,并返回此類別碼的值/break；n+；ret

14、urn 0； /*單詞不是關(guān)鍵字，而是標(biāo)識(shí)符/另外，在掃描源程序字符串時(shí)，一旦識(shí)別出關(guān)鍵字、標(biāo)識(shí)符、整常數(shù)以及運(yùn)算符中之一，即以二元式形式（類別編碼，值）輸出單詞到指定文件中。每次調(diào)用詞法分析程序，它均能自動(dòng)繼續(xù)掃描下去，形成下一個(gè)單詞，直至整個(gè)源程序全部掃描完畢,并形成相應(yīng)的單詞串形式的源程序。2、在詞法分析過程中建立變量名表和常數(shù)表，以備以后的編譯過程(如語法分析）查詢；擴(kuò)充關(guān)鍵字的數(shù)目、增加單詞類別（如邏輯運(yùn)算符等）、將常數(shù)分成字符串常量、整型常量和實(shí)型常量等；添加詞法分析中單詞出錯(cuò)的位置、錯(cuò)誤類型檢查,以及刪除注釋部分等。實(shí)驗(yàn)二 語法分析程序?qū)崿F(xiàn)一、實(shí)驗(yàn)?zāi)康呐c要求通過設(shè)計(jì)、編制、調(diào)試典

15、型的SLR（1）語法分析程序，實(shí)現(xiàn)對(duì)實(shí)驗(yàn)一所得詞法分析程序所提供的單詞序列進(jìn)行語法檢查和結(jié)構(gòu)分析，進(jìn)一步掌握常用的語法分析方法。二、實(shí)驗(yàn)內(nèi)容選擇對(duì)各種常見高級(jí)程序設(shè)計(jì)語言都較為通用的語法結(jié)構(gòu)無符號(hào)數(shù)的算術(shù)四則運(yùn)算作為分析對(duì)象，給出其文法描述(注意應(yīng)與所采用的語法分析方法比較貼近），設(shè)計(jì)并實(shí)現(xiàn)一個(gè)完整的語法分析程序.輸入：由實(shí)驗(yàn)一輸出的單詞類別串,如1，3,1。輸出:對(duì)于所輸入的源程序，如果輸入符號(hào)串是給定文法定義的合法句子，則輸出“RIGHT",并且給出每一步歸約的過程;如果不是句子,即輸入串有錯(cuò)誤，則輸出“ERROR"，并且顯示已經(jīng)歸約出的各個(gè)文法符號(hào)，以及必要的出錯(cuò)說明

16、信息。三、實(shí)現(xiàn)方法與環(huán)境1、 首先根據(jù)算術(shù)四則運(yùn)算的語法定義，構(gòu)造SLR（1）分析表.無符號(hào)數(shù)的算術(shù)四則運(yùn)算的語法可表示為：EE+T E-T|TT-T*F| T/FFF>(E）i2、語法分析程序編寫設(shè)置輸入緩沖區(qū)、狀態(tài)棧、符號(hào)棧，并根據(jù)SLR（1）分析表利用某種語言(C語言或JAVA語言）直接編寫移進(jìn)、歸約、接受子程序，編寫語法分析程序。3、語法分析程序測試用于測試的實(shí)例源文件中應(yīng)有語法正確的，也應(yīng)有語法錯(cuò)誤的符號(hào)串,以對(duì)照的形式將分析結(jié)果信息在輸出文件中表示出來。四、擴(kuò)展實(shí)驗(yàn)1、對(duì)以下復(fù)合語句進(jìn)行語法分析器的設(shè)計(jì)與實(shí)現(xiàn).G<復(fù)合語句:復(fù)合語句> begin語句表end<

17、;語句表 <語句|<語句;<語句表><語句 賦值語句><賦值語句> <變量>：=算術(shù)表達(dá)式>算術(shù)表達(dá)式 <項(xiàng)> 算術(shù)表達(dá)式+項(xiàng) 算術(shù)表達(dá)式項(xiàng)><項(xiàng) 因式 項(xiàng)*<因式> | 項(xiàng)/<因式因式 <變量> <常數(shù) | (算術(shù)表達(dá)式>)變量 <標(biāo)識(shí)符<標(biāo)識(shí)符 標(biāo)識(shí)符 字母 <標(biāo)識(shí)符 數(shù)字> | 字母<常數(shù)> <整數(shù)> | 浮點(diǎn)數(shù)><整數(shù)> <數(shù)字> <數(shù)字> 整數(shù)<浮點(diǎn)數(shù)>

18、 <整數(shù) | 整數(shù)> <整數(shù)><字母 ABC|X|Y|Zabcx|y|z<數(shù)字> 012|92、增強(qiáng)語法檢查功能，對(duì)出錯(cuò)位置、錯(cuò)誤類型給予提示。實(shí)驗(yàn)三 語義分析程序?qū)崿F(xiàn)一、實(shí)驗(yàn)?zāi)康呐c要求通過設(shè)計(jì)、編制、調(diào)試一個(gè)簡單的語義處理分析程序，實(shí)現(xiàn)對(duì)實(shí)驗(yàn)一和實(shí)驗(yàn)二所得單詞和語句的語義信息簡單處里，進(jìn)一步掌握語義處理的內(nèi)容和簡單方法.二、實(shí)驗(yàn)內(nèi)容對(duì)實(shí)驗(yàn)一進(jìn)行擴(kuò)展，對(duì)識(shí)別的無符號(hào)數(shù)進(jìn)行計(jì)值，并將輸出形式改為（類別碼，值)的二元式形式。對(duì)實(shí)驗(yàn)二進(jìn)行擴(kuò)展，在語法分析的基礎(chǔ)上，增加語義操作來實(shí)現(xiàn)語法制導(dǎo)翻譯。對(duì)于給定文法中的每一產(chǎn)生式，編寫相應(yīng)的語義子程序。在語法分析過程

19、中，每當(dāng)用一產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，語法分析程序除執(zhí)行相應(yīng)的語法分析動(dòng)作之外，還要調(diào)用相應(yīng)的語義子程序，計(jì)算并輸出算術(shù)表達(dá)式的值.將實(shí)驗(yàn)一與實(shí)驗(yàn)二的程序合并，以能對(duì)完整的輸入源文件進(jìn)行詞法分析生成中間文件，然后進(jìn)行語法制導(dǎo)翻譯，輸出最終翻譯結(jié)果。輸入：由無符號(hào)數(shù)和+，-，/， ( , ） 構(gòu)成的算術(shù)表達(dá)式。輸出：如果輸入單詞串是合法的無符號(hào)數(shù)的算術(shù)四則運(yùn)算，輸出運(yùn)算結(jié)果,并且給出每一步的分析過程；如果不是無符號(hào)數(shù)的算術(shù)四則運(yùn)算,輸出“非法四則運(yùn)算表達(dá)式”.三、基本實(shí)驗(yàn)題目對(duì)實(shí)驗(yàn)一中每個(gè)無符號(hào)數(shù)識(shí)別狀態(tài)插入計(jì)值處理，最終獲得無符號(hào)數(shù)的取值。對(duì)實(shí)驗(yàn)二進(jìn)行擴(kuò)展，在歸約(分析表中的歸約動(dòng)作已經(jīng)反應(yīng)了運(yùn)

20、算優(yōu)先級(jí))處理子程序中加入計(jì)值處理，接受子程序中加入輸出算數(shù)表達(dá)式值的處理。四、參考資料與無符號(hào)數(shù)狀態(tài)轉(zhuǎn)換圖對(duì)應(yīng)的包含語義處理過程(據(jù)此可計(jì)算求得無符號(hào)數(shù)的數(shù)字值）的狀態(tài)矩陣和參考程序如下所示。表3包含語義處理過程的識(shí)別無符號(hào)數(shù)的狀態(tài)矩陣根據(jù)加入語義過程說明的狀態(tài)轉(zhuǎn)換圖直接編寫詞法分析程序,部分實(shí)現(xiàn)代碼如下：1 #include stdio。h2 #include ctype。h>3 include math.h4 define LETTER 05 define DIGIT 16 #define POINT 27 define OTHER 38 define POWER 49 #defi

21、ne PLUS 510 #define MINUS 611 #define UCON 7 /Suppose the class number of unsigned constant is 712 #define ClassOther 20013 #define EndState -114 int w，n，p，e,d；15 int Class; /Used to indicate class of the word16 int ICON；17 float FCON；18 static int CurrentState; /Used to present current state， the i

22、nitial value:01920 int GetChar (void)；21 int EXCUTE （int，int）；22 int LEX (void)；23 int HandleOtherWord (void）24 return ClassOther；25 26 int HandleError (void)27 printf （"Error！n”）; return 0；2829 int GetChar (void)30 31 int c；32 c=getchar （ )；33 if（isdigit(c) d=c0;return DIGIT；34 if (c=.） return

23、 POINT;35 if (c=Ec=e) return POWER;36 if （c=+) return PLUS;37 if （c=) return MINUS;38 return OTHER;39 40 int EXCUTE （int state, int symbol)41 42 switch （state）43 44 case 0：switch （symbol)45 46 case DIGIT: n=0；p=0；e=1；w=d；CurrentState=1；Class=UCON；break；47 case POINT: w=0；n=0;p=0；e=1；CurrentState=3;C

24、lass=UCON;break;48 default: HandleOtherWord( ）；Class=ClassOther;49 CurrentState=EndState;50 51 break;52 case 1：switch （symbol)53 54 case DIGIT： w=w*10+d;break； /CurrentState=155 case POINT: CurrentState=2；break；56 case POWER： CurrentState=4;break；57 default： ICON=w；CurrentState=EndState;58 59 break；

25、60 case 2:switch （symbol)61 62 case DIGIT： n+；w=w*10+d；break；63 case POWER: CurrentState=4;break；64 default： FCON=w*pow（10，e*p-n）;CurrentState=EndState;65 66 break;67 case 3：switch （symbol）68 69 case DIGIT: n+;w=w*10+d;CurrentState=2；break;70 default： HandleError( )；CurrentState=EndState;71 72 break

26、；73 case 4：switch （symbol)74 75 case DIGIT： p=p*10+d；CurrentState=6；break；76 case MINUS: e=-1;CurrentState=5;break；77 case PLUS： CurrentState=5;break;78 default： HandleError( );CurrentState=EndState；79 80 break；81 case 5:switch (symbol）82 83 case DIGIT： p=p10+d；CurrentState=6;break；84 default: Handl

27、eError( )；CurrentState=EndState;85 86 break；87 case 6:switch （symbol)88 89 case： DIGIT：p=p10+d；break;90 default： FCON=wpow（10，e*pn）;CurrentState=EndState;91 92 break；93 94 return CurrentState；95 96 int LEX (void)97 98 int ch；99 CurrentState=0；100 while （CurrentState!=EndState）101 102 ch=GetChar( );103 EXCUTE （CurrentState，ch）;104 105 return Class;106 五、擴(kuò)展實(shí)驗(yàn)對(duì)以下復(fù)合語句進(jìn)行語法制導(dǎo)