城市學(xué)院編譯原理試驗(yàn)參考指導(dǎo)書

《編譯原理》試驗(yàn)指導(dǎo)書適用試驗(yàn)課時：30適用對象：城市學(xué)院計算機(jī)系

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

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

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

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