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

年4月19日城市學院編譯原理實驗指導書文檔僅供參考《編譯原理》實驗指導書適用實驗課時：30適用對象：城市學院計算機系

實驗目的和內容編譯原理實驗的目的是使學生將編譯理論運用到實際當中，實現一個簡單語言集的詞法分析程序、語法分析程序和簡單語義處理程序，驗證實際編譯系統的實現方法，并加深對編譯理論的認識。基本實驗分為三個部分，實驗一識別無符號數的詞法分析器設計實現、實驗二無符號數的算術四則運算LR語法分析器設計實現，實驗三是無符號數的算術四則運算語義處理程序實現，總的實驗學時為30課時。要求每個學生獨立完成所有實驗要求。每部分基本實驗還包括若干擴展實驗，供編程能力較強的學生自愿進行。

實驗一詞法分析程序實現一、實驗目的與要求經過編寫和調試一個詞法分析程序，掌握在對程序設計語言的源程序進行掃描的過程中，將字符形式的源程序流轉化為一個由各類單詞符號組成的流的詞法分析方法。二、實驗內容選取無符號數的算術四則運算中的各類單詞為識別對象，要求將其中的各個單詞識別出來。輸入：由無符號數和+，－，*，/,(,)構成的算術表示式，如1.5E+2－100。輸出：對識別出的每一單詞均單行輸出其類別碼（無符號數的值暫不要求計算）。三、實現方法與環境1、首先設計識別各類單詞的狀態轉換圖。描述無符號常數的確定、最小化狀態轉換圖如圖1所示。其中編號0，1，2，…，6代表非終結符號<無符號數>、<余留無符號數>、<十進小數>、<小數部分>、<指數部分>、<整指數>及<余留整指數>，1，2和6為終態，分別代表整數、小數和科學計數的識別結束狀態。圖1文法G[<無符號數>]的狀態轉換圖其中編號0，1，2，…，6代表非終結符號<無符號數>、<余留無符號數>、<十進小數>、<小數部分>、<指數部分>、<整指數>及<余留整指數>，1，2和6為終態，分別代表整數、小數和科學計數的識別結束狀態。在一個程序設計語言中，一般都含有若干類單詞符號，為此可首先為每類單詞建立一張狀態轉換圖，然后將這些狀態轉換圖合并成一張統一的狀態圖，即得到了一個有限自動機，再進行必要的確定化和狀態數最小化處理，最后據此構造詞法分析程序。四則運算算術符號的識別很簡單，直接在狀態圖的0狀態分別引出相應標記的矢線至一個新的終態即可。根據自己的習慣，也能夠將其轉換為狀態矩陣形式。2、詞法分析程序編寫根據描述語言中各類單詞的文法狀態轉換圖或狀態矩陣，利用某種語言（C語言或JAVA語言）直接編寫詞法分析程序。3、詞法分析程序測試用于測試掃描器的實例源文件中應有詞法正確的，也應有錯誤的字符串，對于輸入的測試用例的源程序文件，以對照的形式將掃描器的分析結果信息在輸出文件中表示出來。四、參考資料實現無符號數識別的參考方法：將設計的狀態轉換圖直接轉化為一張程序流程圖，并在外層再增加一個以EOF為循環終止條件的while循環，即形成能連續識別各類單詞的詞法分析程序。各類單詞的編碼建議如表1。表1單詞的內部編碼單詞符號類別碼（CLASS）單詞值（VALUE）無符號數1數字值+2無值－3無值*4無值/5無值(6無值)7無值五、擴展實驗1、試對基礎實驗識別的單詞種類進行擴充，構造識別以下單詞的詞法分析程序。語言中具有的單詞包括五個有代表性的關鍵字begin、end、if、then、else；標識符；整型常數；六種關系運算符；一個賦值符和四個算術運算符。參考實現方法簡述如下。表2擴展單詞分類碼表單詞符號類別編碼類別碼的助記符單詞值begin1BEGINend2ENDif3IFthen4THENelse5ELSE標識符6ID字母打頭的字母數字串整常數7INT數字串<8LT<=9LE=10EQ<>11NE>12GT>=13GE:=14IS+15PL-16MI*17MU/18DI處理過程：在此為了使詞法分析程序結構比較清晰，且盡量避免某些枝節問題的糾纏，假定要編譯的語言中，全部關鍵字都是保留字，程序員不得將它們作為源程序中的標識符；在源程序的輸入文本中，關鍵字、標識符、整常數之間，若未出現關系和算術運算符以及賦值符，則至少須用一個空白字符加以分隔。作了這些限制以后，就能夠把關鍵字和標識符的識別統一進行處理。即每當開始識別一個單詞時，若掃視到的第一個字符為字母，則把后續輸入的字母或數字字符依次進行拼接，直至掃視到非字母、數字字符為止，以期獲得一個盡可能長的字母數字字符串，然后以此字符串查所謂保留字表（此保留字表已事先造好），若查到此字符串，則取出相應的類別碼；反之，則表明該字符串應為一標識符。采用上述策略后，針對表2中部分單詞能夠構造一個如圖2所示的有限自動機（以狀態轉換圖表示）。在圖2中添加了當進行狀態轉移時，詞法分析程序應執行的語義動作。根據圖2，可用C語言編寫出符合以上幾項要求的一個相應的掃描器程序，如程序一所示。圖2識別表I所列語言中的部分單詞的DFA及相關函數圖2所出現的變量及函數的含義和功能說明如下：函數GETCHAR：每調用一次，就把掃描指示器當前所指示的源程序字符送入字符變量ch，然后把掃描指示器前推一個字符位置。字符數組TOKEN：用來依次存放一個單詞詞文中的各個字符。函數CAT：每調用一次，就把當前ch中的字符拼接于TOKEN中所存字符串的右邊。函數LOOKUP：每調用一次，就以TOKEN中的字符串查保留字表，若查到，就將相應關鍵字的類別碼賦給整型變量c；否則將c置為零。函數RETRACT：每調用一次，就把掃描指示器回退一個字符位置（即退回多讀的那個字符）。函數OUT：一般僅在進入終態時調用此函數，調用的形式為OUT(c，VAL)。其中，實參c為相應單詞的類別碼或其助記符；當所識別的單詞為標識符和整數時，實參VAL為TOKEN（即詞文分別為字母數字串和數字串），對于其余種類的單詞，VAL均為空串。函數OUT的功能是，在送出一個單詞的內部表示之后，返回到調用該詞法分析程序的那個程序。參考程序：#include<stdio.h>#include<ctype.h>#include<string.h>#defineID6#defineINT7#defineLT8#defineLE9#defineEQ10#defineNE11#defineGT12#defineGE13charTOKEN[20]；externintlookup(char*);externvoidout(int,char*);externreport_error(void);voidscanner_example(FILE*fp){charch;inti,c;ch=fgetc(fp);if(isalpha(ch))/*itmustbeaidentifer!*/{TOKEN[0]=ch;ch=fgetc(fp);i=1;while(isalnum(ch)){TOKEN[i]=ch;i++；ch=fgetc(fp);}TOKEN[i]=′＼0′fseek(fp,-1,1);/*retract*/c=lookup(TOKEN);if(c==0)out(ID,TOKEN);elseout(c,"")；}elseif(isdigit(ch)){TOKEN[0]=ch;ch=fgetc(fp);i=1;while(isdigit(ch)){TOKEN[i]=ch;i++;ch=fgetc(fp);}TOKEN[i]=′＼0′；fseek(fp,-1,1);out(INT,TOKEN);}elseswitch(ch){case′＜′:ch=fgetc(fp);if(ch==′=′)out(LE,"");elseif(ch==′＞′)out(NE,"");else{fseek(fp,-1,1);out(LT,"");}break;case′=′:out(EQ,"");break;case′＞′:ch=fgetc(fp);if(ch==′=′)out(GE,"");else{fseek(fp,-1,1);out(GT,"");}break;default:report_error();break;}return;}提示：掃描器所用的若干函數以及主程序有待于具體編寫，并需事先建立好保留字表，以備查詢。例如：/*建立保留字表*/#defineMAX_KEY_NUMBER20/*關鍵字的數量*/#defineKEY_WORD_END“waitingforyourexpanding”/*關鍵字結束標記*/char*KeyWordTable[MAX_KEY_NUMBER]={“begin”,“end”,“if”,“then”,“else”,KEY_WORD_END};/*查保留字表，判斷是否為關鍵字*/intlookup(char*token){inti=0;while(strcmp(KeyWordTable[n],KEY_WORD_END))/*strcmp比較兩串是否相同，若相同返回0*/{if(!strcmp(KeyWordTable[n],token))/*比較token所指向的關鍵字和保留字表中哪個關鍵字相符*/{returnn+1;/*設置正確的關鍵字類別碼，并返回此類別碼的值*/break;}n++;}return0;/*單詞不是關鍵字，而是標識符*/}另外，在掃描源程序字符串時，一旦識別出關鍵字、標識符、整常數以及運算符中之一，即以二元式形式（類別編碼，值）輸出單詞到指定文件中。每次調用詞法分析程序，它均能自動繼續掃描下去，形成下一個單詞，直至整個源程序全部掃描完畢，并形成相應的單詞串形式的源程序。2、在詞法分析過程中建立變量名表和常數表，以備以后的編譯過程（如語法分析）查詢；擴充關鍵字的數目、增加單詞類別（如邏輯運算符等）、將常數分成字符串常量、整型常量和實型常量等；添加詞法分析中單詞出錯的位置、錯誤類型檢查，以及刪除注釋部分等。

實驗二語法分析程序實現一、實驗目的與要求經過設計、編制、調試典型的SLR（1）語法分析程序，實現對實驗一所得詞法分析程序所提供的單詞序列進行語法檢查和結構分析，進一步掌握常見的語法分析方法。二、實驗內容選擇對各種常見高級程序設計語言都較為通用的語法結構無符號數的算術四則運算作為分析對象，給出其文法描述（注意應與所采用的語法分析方法比較貼近），設計并實現一個完整的語法分析程序。輸入：由實驗一輸出的單詞類別串，如1，3，1。輸出：對于所輸入的源程序，如果輸入符號串是給定文法定義的合法句子，則輸出“RIGHT”，而且給出每一步歸約的過程；如果不是句子，即輸入串有錯誤，則輸出“ERROR”，而且顯示已經歸約出的各個文法符號，以及必要的出錯說明信息。三、實現方法與環境首先根據算術四則運算的語法定義，構造SLR（1）分析表。無符號數的算術四則運算的語法可表示為：E->E+T|E-T|TT->T*F|T/F|FF->(E)|i2、語法分析程序編寫設置輸入緩沖區、狀態棧、符號棧，并根據SLR（1）分析表利用某種語言（C語言或JAVA語言）直接編寫移進、歸約、接受子程序，編寫語法分析程序。3、語法分析程序測試用于測試的實例源文件中應有語法正確的，也應有語法錯誤的符號串，以對照的形式將分析結果信息在輸出文件中表示出來。四、擴展實驗1、對以下復合語句進行語法分析器的設計與實現。G[<復合語句>]：<復合語句>→begin<語句表>end<語句表>→<語句>|<語句>;<語句表><語句>→<賦值語句><賦值語句>→<變量>:=<算術表示式><算術表示式>→<項>|<算術表示式>+<項>|<算術表示式>-<項><項>→<因式>|<項>*<因式>|<項>/<因式><因式>→<變量>|<常數>|(<算術表示式>)<變量>→<標識符><標識符>→<標識符><字母>|<標識符><數字>|<字母><常數>→<整數>|<浮點數><整數>→<數字>|<數字><整數><浮點數>→?<整數>|<整數>?<整數><字母>→A|B|C|…|X|Y|Z|a|b|c|…|x|y|z<數字>→0|1|2|…|92、增強語法檢查功能，對出錯位置、錯誤類型給予提示。

實驗三語義分析程序實現一、實驗目的與要求經過設計、編制、調試一個簡單的語義處理分析程序，實現對實驗一和實驗二所得單詞和語句的語義信息簡單處里，進一步掌握語義處理的內容和簡單方法。二、實驗內容對實驗一進行擴展，對識別的無符號數進行計值，并將輸出形式改為（類別碼，值）的二元式形式。對實驗二進行擴展，在語法分析的基礎上，增加語義操作來實現語法制導翻譯。對于給定文法中的每一產生式，編寫相應的語義子程序。在語法分析過程中，每當用一產生式進行推導或歸約時，語法分析程序除執行相應的語法分析動作之外，還要調用相應的語義子程序，計算并輸出算術表示式的值。將實驗一與實驗二的程序合并，以能對完整的輸入源文件進行詞法分析生成中間文件，然后進行語法制導翻譯，輸出最終翻譯結果。輸入：由無符號數和+，—，*，/,(,)構成的算術表示式。輸出：如果輸入單詞串是合法的無符號數的算術四則運算，輸出運算結果，而且給出每一步的分析過程；如果不是無符號數的算術四則運算，輸出“非法四則運算表示式”。三、基本實驗題目對實驗一中每個無符號數識別狀態插入計值處理，最終獲得無符號數的取值。對實驗二進行擴展，在歸約（分析表中的歸約動作已經反應了運算優先級）處理子程序中加入計值處理，接受子程序中加入輸出算數表示式值的處理。四、參考資料與無符號數狀態轉換圖對應的包含語義處理過程（據此可計算求得無符號數的數字值）的狀態矩陣和參考程序如下所示。表3包含語義處理過程的識別無符號數的狀態矩陣根據加入語義過程說明的狀態轉換圖直接編寫詞法分析程序，部分實現代碼如下：1#include<stdio.h>2#include<ctype.h>3#include<math.h>4#defineLETTER05#defineDIGIT16#definePOINT27#defineOTHER38#definePOWER49#definePLUS510#defineMINUS611#defineUCON7//Supposetheclassnumberofunsignedconstantis712#defineClassOther20013#defineEndState-114intw,n,p,e,d;15intClass;//Usedtoindicateclassoftheword16intICON;17floatFCON;18staticintCurrentState;//Usedtopresentcurrentstate,theinitialvalue:01920intGetChar(void);21intEXCUTE(int,int)；22intLEX(void)；23intHandleOtherWord(void)24{returnClassOther;25}26intHandleError(void)27{printf("Error!＼n");return0;}2829intGetChar(void)30{31intc;3233if(isdigit(c)){d=c-′0′;returnDIGIT;}34if(c==′.′)returnPOINT;35if(c==′E′||c==′e′)returnPOWER;36if(c==′+′)returnPLUS;37if(c==′-′)returnMINUS;38returnOTHER;39}40intEXCUTE(intstate,intsymbol)41{42switch(state)43{44case0:switch(symbol)45{46caseDIGIT:n=0;p=0;e=1;w=d;CurrentState=1;Class=UCON;break;47casePOINT:w=0;n=0;p=0;e=1;CurrentState=3;Class=UCON;break;48default:HandleOtherWord();Class=ClassOther;49CurrentState=EndState;50}51break;52case1:switch(symbol)53{54caseDIGIT:w=w*10+d;break;//CurrentState=155casePOINT:CurrentState=2;break;56casePOWER:CurrentState=4;break;57default:ICON=w;CurrentState=EndState;58}59break；60case2:switch(symbol)61{62caseDIGIT:n++;w=w*10+d;break;63casePOWER:CurrentState=4;break;64default:FCON=w*pow(10,e*p-n);CurrentState=EndState;65}66break;67case3:switch(symbol)68{69caseDIGIT:n++;w=w*10+d;CurrentState=2;break;70default:HandleError()；CurrentState=EndState;71}72break；73case4:switch(symbol)74{75caseDIGIT:p=p*10+d;CurrentState=6;break;76caseMINUS:e=-1;CurrentState=5;break;77casePLUS:CurrentState=5;break;78default:HandleError();CurrentState=EndState;79}80break；81case5:switch(symbol)82{83caseDIGIT:p=p*10+d;CurrentState=6;break;84default:HandleError();CurrentState=EndState;85}86break;87case6:switch(symbol)88{89case:DIGIT:p=p*10+d;break;90default:FCON=w*pow(10,e*p-n);CurrentState=EndState;