城市學院《編譯原理》實驗指導書

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

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

3、數(shù)部分、整指數(shù)>及<余留整指數(shù)， 1，2和6為終態(tài)，分別代表整數(shù)、小數(shù)和科學計數(shù)的識別結(jié)束狀態(tài)。圖1 文法G<無符號數(shù)>的狀態(tài)轉(zhuǎn)換圖其中編號0，1，2，6代表非終結(jié)符號<無符號數(shù)、余留無符號數(shù)、十進小數(shù)、小數(shù)部分、<指數(shù)部分、<整指數(shù)及<余留整指數(shù)>， 1,2和6為終態(tài),分別代表整數(shù)、小數(shù)和科學計數(shù)的識別結(jié)束狀態(tài)。在一個程序設(shè)計語言中，一般都含有若干類單詞符號，為此可首先為每類單詞建立一張狀態(tài)轉(zhuǎn)換圖，然后將這些狀態(tài)轉(zhuǎn)換圖合并成一張統(tǒng)一的狀態(tài)圖,即得到了一個有限自動機，再進行必要的確定化和狀態(tài)數(shù)最小化處理，最后據(jù)此構(gòu)造詞法分析程序。四則運算算

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

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

6、INT數(shù)字串<8LT<=9LE=10EQ<>11NE>12GT=13GE：=14IS+15PL16MI*17MU/18DI處理過程：在此為了使詞法分析程序結(jié)構(gòu)比較清晰，且盡量避免某些枝節(jié)問題的糾纏，假定要編譯的語言中，全部關(guān)鍵字都是保留字，程序員不得將它們作為源程序中的標識符；在源程序的輸入文本中，關(guān)鍵字、標識符、整常數(shù)之間，若未出現(xiàn)關(guān)系和算術(shù)運算符以及賦值符，則至少須用一個空白字符加以分隔。作了這些限制以后，就可以把關(guān)鍵字和標識符的識別統(tǒng)一進行處理。即每當開始識別一個單詞時，若掃視到的第一個字符為字母，則把后續(xù)輸入的字母或數(shù)字字符依次進行拼接,直至掃視到非字母、

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

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

9、單詞,VAL均為空串。函數(shù)OUT的功能是,在送出一個單詞的內(nèi)部表示之后，返回到調(diào)用該詞法分析程序的那個程序.參考程序： 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é)束標記*/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)鍵字和保留字表中哪個關(guān)鍵字相符*/return n+1; /*設(shè)置正確的關(guān)鍵字類別碼,并返回此類別碼的值/break；n+；ret

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

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

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

17、;語句表 <語句|<語句;<語句表><語句 賦值語句><賦值語句> <變量>：=算術(shù)表達式>算術(shù)表達式 <項> 算術(shù)表達式+項 算術(shù)表達式項><項 因式 項*<因式> | 項/<因式因式 <變量> <常數(shù) | (算術(shù)表達式>)變量 <標識符<標識符 標識符 字母 <標識符 數(shù)字> | 字母<常數(shù)> <整數(shù)> | 浮點數(shù)><整數(shù)> <數(shù)字> <數(shù)字> 整數(shù)<浮點數(shù)>

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

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

20、算優(yōu)先級)處理子程序中加入計值處理，接受子程序中加入輸出算數(shù)表達式值的處理。四、參考資料與無符號數(shù)狀態(tài)轉(zhuǎn)換圖對應的包含語義處理過程(據(jù)此可計算求得無符號數(shù)的數(shù)字值）的狀態(tài)矩陣和參考程序如下所示。表3包含語義處理過程的識別無符號數(shù)的狀態(tài)矩陣根據(jù)加入語義過程說明的狀態(tài)轉(zhuǎn)換圖直接編寫詞法分析程序,部分實現(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 五、擴展實驗對以下復合語句進行語法制導