城市學院編譯原理試驗參考指導書

《編譯原理》試驗指導書適用試驗課時：30適用對象：城市學院計算機系

試驗目標和內(nèi)容編譯原理試驗目標是使學生將編譯理論利用到實際當中，實現(xiàn)一個簡單語言集詞法分析程序、語法分析程序和簡單語義處理程序，驗證實際編譯系統(tǒng)實現(xiàn)方法，并加深對編譯理論認識?；A試驗分為三個部分，試驗一識別無符號數(shù)詞法分析器設計實現(xiàn)、試驗二無符號數(shù)算術四則運算LR語法分析器設計實現(xiàn)，試驗三是無符號數(shù)算術四則運算語義處理程序實現(xiàn)，總試驗課時為30課時。要求每個學生獨立完成全部試驗要求。每部分基礎試驗還包含若干擴展試驗，供編程能力較強學生自愿進行。

試驗一詞法分析程序實現(xiàn)一、試驗目標和要求經(jīng)過編寫和調(diào)試一個詞法分析程序，掌握在對程序設計語言源程序進行掃描過程中，將字符形式源程序流轉化為一個由各類單詞符號組成流詞法分析方法。二、試驗內(nèi)容選擇無符號數(shù)算術四則運算中各類單詞為識別對象，要求將其中各個單詞識別出來。輸入：由無符號數(shù)和+，－，*，/,(,)組成算術表示式，如1.5E+2－100。輸出：對識別出每一單詞均單行輸出其類別碼（無符號數(shù)值暫不要求計算）。三、實現(xiàn)方法和環(huán)境1、首先設計識別各類單詞狀態(tài)轉換圖。描述無符號常數(shù)確實定、最小化狀態(tài)轉換圖圖1所表示。其中編號0，1，2，…，6代表非終止符號<無符號數(shù)>、<余留無符號數(shù)>、<十進小數(shù)>、<小數(shù)部分>、<指數(shù)部分>、<整指數(shù)>及<余留整指數(shù)>，1，2和6為終態(tài)，分別代表整數(shù)、小數(shù)和科學計數(shù)識別結束狀態(tài)。圖1文法G[<無符號數(shù)>]狀態(tài)轉換圖其中編號0，1，2，…，6代表非終止符號<無符號數(shù)>、<余留無符號數(shù)>、<十進小數(shù)>、<小數(shù)部分>、<指數(shù)部分>、<整指數(shù)>及<余留整指數(shù)>，1，2和6為終態(tài)，分別代表整數(shù)、小數(shù)和科學計數(shù)識別結束狀態(tài)。在一個程序設計語言中，通常全部含有若干類單詞符號，為此可首先為每類單詞建立一張狀態(tài)轉換圖，然后將這些狀態(tài)轉換圖合并成一張統(tǒng)一狀態(tài)圖，即得到了一個有限自動機，再進行必需確實定化和狀態(tài)數(shù)最小化處理，最終據(jù)此結構詞法分析程序。四則運算算術符號識別很簡單，直接在狀態(tài)圖0狀態(tài)分別引出對應標識矢線至一個新終態(tài)即可。依據(jù)自己習慣，也能夠將其轉換為狀態(tài)矩陣形式。2、詞法分析程序編寫依據(jù)描述語言中各類單詞文法狀態(tài)轉換圖或狀態(tài)矩陣，利用某種語言（C語言或JAVA語言）直接編寫詞法分析程序。3、詞法分析程序測試用于測試掃描器實例源文件中應有詞法正確，也應有錯誤字符串，對于輸入測試用例源程序文件，以對照形式將掃描器分析結果信息在輸出文件中表示出來。四、參考資料實現(xiàn)無符號數(shù)識別參考方法：將設計狀態(tài)轉換圖直接轉化為一張程序步驟圖，并在外層再增加一個以EOF為循環(huán)終止條件while循環(huán)，即形成能連續(xù)識別各類單詞詞法分析程序。各類單詞編碼提議如表1。表1單詞內(nèi)部編碼單詞符號類別碼（CLASS）單詞值（VALUE）無符號數(shù)1數(shù)字值+2無值－3無值*4無值/5無值(6無值)7無值五、擴展試驗1、試對基礎試驗識別單詞種類進行擴充，結構識別以下單詞詞法分析程序。語言中含有單詞包含五個有代表性關鍵字begin、end、if、then、else；標識符；整型常數(shù)；六種關系運算符；一個賦值符和四個算術運算符。參考實現(xiàn)方法簡述以下。表2擴展單詞分類碼表單詞符號類別編碼類別碼助記符單詞值begin1BEGINend2ENDif3IFthen4THENelse5ELSE標識符6ID字母打頭字母數(shù)字串整常數(shù)7INT數(shù)字串<8LT<=9LE=10EQ<>11NE>12GT>=13GE:=14IS+15PL-16MI*17MU/18DI處理過程：在此為了使詞法分析程序結構比較清楚，且盡可能避免一些枝節(jié)問題糾纏，假定要編譯語言中，全部關鍵字全部是保留字，程序員不得將它們作為源程序中標識符；在源程序輸入文本中，關鍵字、標識符、整常數(shù)之間，若未出現(xiàn)關系和算術運算符和賦值符，則最少須用一個空白字符加以分隔。作了這些限制以后，就能夠把關鍵字和標識符識別統(tǒng)一進行處理。即每當開始識別一個單詞時，若掃視到第一個字符為字母，則把后續(xù)輸入字母或數(shù)字字符依次進行拼接，直至掃視到非字母、數(shù)字字符為止，以期取得一個盡可能長字母數(shù)字字符串，然后以此字符串查所謂保留字表（此保留字表已事先造好），若查到此字符串，則取出對應類別碼；反之，則表明該字符串應為一標識符。采取上述策略后，針對表2中部分單詞能夠結構一個圖2所表示有限自動機（以狀態(tài)轉換圖表示）。在圖2中添加了當進行狀態(tài)轉移時，詞法分析程序應實施語義動作。依據(jù)圖2，可用C語言編寫出符合以上幾項要求一個對應掃描器程序，如程序一所表示。圖2識別表I所列語言中部分單詞DFA及相關函數(shù)圖2所出現(xiàn)變量及函數(shù)含義和功效說明以下：函數(shù)GETCHAR：每調(diào)用一次，就把掃描指示器目前所指示源程序字符送入字符變量ch，然后把掃描指示器前推一個字符位置。字符數(shù)組TOKEN：用來依次存放一個單詞詞文中各個字符。函數(shù)CAT：每調(diào)用一次，就把目前ch中字符拼接于TOKEN中所存字符串右邊。函數(shù)LOOKUP：每調(diào)用一次，就以TOKEN中字符串查保留字表，若查到，就將對應關鍵字類別碼賦給整型變量c；不然將c置為零。函數(shù)RETRACT：每調(diào)用一次，就把掃描指示器回退一個字符位置（即退回多讀那個字符）。函數(shù)OUT：通常僅在進入終態(tài)時調(diào)用此函數(shù)，調(diào)用形式為OUT(c，VAL)。其中，實參c為對應單詞類別碼或其助記符；當所識別單詞為標識符和整數(shù)時，實參VAL為TOKEN（即詞文分別為字母數(shù)字串和數(shù)字串），對于其它種類單詞，VAL均為空串。函數(shù)OUT功效是，在送出一個單詞內(nèi)部表示以后，返回到調(diào)用該詞法分析程序那個程序。參考程序：#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;}提醒：掃描器所用若干函數(shù)和主程序有待于具體編寫，并需事先建立好保留字表，以備查詢。比如：/*建立保留字表*/#defineMAX_KEY_NUMBER20/*關鍵字數(shù)量*/#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;/*單詞不是關鍵字，而是標識符*/}另外，在掃描源程序字符串時，一旦識別出關鍵字、標識符、整常數(shù)和運算符中之一，即以二元式形式（類別編碼，值）輸出單詞到指定文件中。每次調(diào)用詞法分析程序，它均能自動繼續(xù)掃描下去，形成下一個單詞，直至整個源程序全部掃描完成，并形成對應單詞串形式源程序。2、在詞法分析過程中建立變量名表和常數(shù)表，以備以后編譯過程（如語法分析）查詢；擴充關鍵字數(shù)目、增加單詞類別（如邏輯運算符等）、將常數(shù)分成字符串常量、整型常量和實型常量等；添加詞法分析中單詞犯錯位置、錯誤類型檢驗，和刪除注釋部分等。

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

試驗三語義分析程序實現(xiàn)一、試驗目標和要求經(jīng)過設計、編制、調(diào)試一個簡單語義處理分析程序，實現(xiàn)對試驗一和試驗二所得單詞和語句語義信息簡單處里，深入掌握語義處理內(nèi)容和簡單方法。二、試驗內(nèi)容對試驗一進行擴展，對識別無符號數(shù)進行計值，并將輸出形式改為（類別碼，值）二元式形式。對試驗二進行擴展，在語法分析基礎上，增加語義操作來實現(xiàn)語法制導翻譯。對于給定文法中每一產(chǎn)生式，編寫對應語義子程序。在語法分析過程中，每當用一產(chǎn)生式進行推導或歸約時，語法分析程序除實施對應語法分析動作之外，還要調(diào)用對應語義子程序，計算并輸出算術表示式值。將試驗一和試驗二程序合并，以能對完整輸入源文件進行詞法分析生成中間文件，然后進行語法制導翻譯，輸出最終翻譯結果。輸入：由無符號數(shù)和+，—，*，/,(,)組成算術表示式。輸出：假如輸入單詞串是正當無符號數(shù)算術四則運算，輸出運算結果，而且給出每一步分析過程；假如不是無符號數(shù)算術四則運算，輸出“非法四則運算表示式”。三、基礎試驗題目對試驗一中每個無符號數(shù)識別狀態(tài)插入計值處理，最終取得無符號數(shù)取值。對試驗二進行擴展，在歸約（分析表中歸約動作已經(jīng)反應了運算優(yōu)先級）處理子程序中加入計值處理，接收子程序中加入輸出算數(shù)表示式值處理。四、參考資料和無符號數(shù)狀態(tài)轉換圖對應包含語義處理過程（據(jù)此可計算求得無符號數(shù)數(shù)字值）狀態(tài)矩陣和參考程序以下所表示。表3包含語義處理過程識別無符號數(shù)狀態(tài)矩陣依據(jù)加入語義過程說明狀態(tài)轉換圖直接編寫詞法分析程序，部分實現(xiàn)代碼以下：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;91}92break;93}94returnCurrentState;95}96intLEX(void)97{98intch;99CurrentState=0;100whi