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

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

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

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

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