[工學(xué)]編譯原理實(shí)驗(yàn)指導(dǎo)書(shū)

1、.編譯原理課程實(shí)驗(yàn)指導(dǎo)書(shū)計(jì)算機(jī)學(xué)院編年月實(shí)驗(yàn)一 C語(yǔ)言子集編譯程序一、實(shí)驗(yàn)?zāi)康挠肅語(yǔ)言對(duì)一個(gè)C語(yǔ)言的子集編制一個(gè)一遍掃描的編譯程序，以加深對(duì)編譯原理的理解，掌握編譯程序的實(shí)現(xiàn)方法和技術(shù)。1設(shè)計(jì)、編制并調(diào)試一個(gè)詞法分析程序，加深對(duì)詞法分析原理的理解。2編制一個(gè)遞歸下降分析程序，并對(duì)C語(yǔ)言的簡(jiǎn)單子集進(jìn)行分析。3通過(guò)上機(jī)實(shí)習(xí)，加深對(duì)語(yǔ)法制導(dǎo)翻譯原理的理解，掌握將語(yǔ)法分析所識(shí)別的語(yǔ)法成分變換中間代碼的語(yǔ)義翻譯方法。二、實(shí)驗(yàn)要求、內(nèi)容及學(xué)時(shí)詞法分析部分：2學(xué)時(shí)（一）待分析的C語(yǔ)言子集的詞法：1關(guān)鍵字main if else int return void while所有關(guān)鍵字都是小寫(xiě)。2專用符號(hào)= +

2、- * / = = != ; : , ( )3.其他標(biāo)記ID和NUM通過(guò)以下正規(guī)式定義其他標(biāo)記：IDletter(letter|digit)*NUMdigit(digit)*lettera|z|A|Z digit0|94.空格由空白、制表符和換行符組成空格一般用來(lái)分隔ID、NUM、專用符號(hào)和關(guān)鍵字，詞法分析階段空格通常被忽略。各種單詞符號(hào)對(duì)應(yīng)的類別碼：（采用一符一類別碼,見(jiàn)下表）單詞符號(hào)類別碼單詞符號(hào)類別碼單詞符號(hào)類別碼main1-23;34int2*2435char3/25=37else5)27=38for628=39while729!=40ID103001000NUM2031ERROR-1

3、=21，32+22：33（二）詞法分析程序的功能：輸入：所給文法的源程序字符串。輸出：二元組（syn,token或sum）構(gòu)成的序列。其中，syn 為單詞類別碼。token 為存放的單詞自身字符串。sum 為整型常量。具體實(shí)現(xiàn)時(shí)，可以將單詞的二元組用結(jié)構(gòu)進(jìn)行處理。例如：對(duì)源程序main()int i=10;while(i) i=i-1;的源文件，經(jīng)詞法分析后輸出如下序列：(1,main) (26,() (27,) (30,) (2,int) (10,i) (21,=) (20,10)(34,;) (7,while) (26,() (10,i) (27,) (10,i) (21,=) (10,i

4、)(23,-) (20,1) (34,;) (31, )（三）詞法分析程序主要算法思想：算法的基本任務(wù)是從字符串表示的源程序中識(shí)別出具有獨(dú)立意義的單詞符號(hào)，其基本思想是根據(jù)掃描到單詞符號(hào)的第一個(gè)字符的種類，拼出相應(yīng)的單詞符號(hào)。1主程序示意結(jié)構(gòu)圖（如下）：置初值調(diào)用掃描子程序輸出單詞二元組直至輸入串結(jié)束注：關(guān)鍵字表初值關(guān)鍵字作為特殊標(biāo)識(shí)符處理，把它們預(yù)先安排在一張表格中（稱為關(guān)鍵字），當(dāng)掃描程序識(shí)別出標(biāo)識(shí)符時(shí)，查關(guān)鍵字表。如能查到匹配的單詞，則該單詞為關(guān)鍵字，否則為一般標(biāo)識(shí)符。關(guān)鍵字表可處理為一個(gè)字符串?dāng)?shù)組（實(shí)際為指向字符數(shù)組的指針數(shù)組），其描述如下：char *KEY_WORDS8=“main

5、”,”int”,”char”,”if”,”else”,”for”,”while”;為分析方便,這里把main作關(guān)鍵字處理。程序中需要用到的主要變量：syn,token和sum。2掃描子程序（scaner）的算法思想首先設(shè)置三個(gè)變量：token用來(lái)存放構(gòu)成單詞符號(hào)的字符串；sum用來(lái)存放整型單詞；syn用來(lái)存放單詞的類別碼。掃描子程序主要部分NS圖如下：變量初始化忽略空格文件是否結(jié)束TF是否字母TF拼字符串是否數(shù)字是否關(guān)鍵字TFTF拼數(shù)是否運(yùn)算符、界符等符號(hào)syn為對(duì)應(yīng)關(guān)鍵字的類別碼syn=10syn=20TF給出相應(yīng)的syn值報(bào)錯(cuò)語(yǔ)法分析部分：2學(xué)時(shí)（一）待分析的C語(yǔ)言子集的語(yǔ)法用擴(kuò)充的BNF

6、表示如下：1main()2. 3. ;4. |5. ID=6. if()7. while()8. 9. +|-10.*|/11.ID|NUM|()12.|=|=|!=（二）語(yǔ)法分析程序的主要算法思想1主程序結(jié)構(gòu)示意圖如下：置初值調(diào)用scaner讀下一個(gè)單詞符號(hào)調(diào)用lrparser結(jié)束2遞歸下降分析程序結(jié)構(gòu)示意圖如下：注：上接lrparser是否單詞串main()TF調(diào)用scaner出錯(cuò)處理調(diào)用語(yǔ)句塊分析函數(shù)源程序是否結(jié)束TF輸出分析成功出錯(cuò)處理3語(yǔ)句塊分析結(jié)構(gòu)示意圖。是否TF調(diào)用scaner出錯(cuò)處理調(diào)用語(yǔ)句串分析函數(shù)（過(guò)程）是否TF出錯(cuò)處理4語(yǔ)句串分析結(jié)構(gòu)示意圖如下：調(diào)用statement函數(shù)

7、當(dāng)為；時(shí)調(diào)用scaner調(diào)用statement函數(shù)出錯(cuò)處理5statement函數(shù)NS圖如下：是否標(biāo)識(shí)符TF調(diào)用scaner是否if是否=TFTF調(diào)用scaner是否while調(diào)用scaner出錯(cuò)處理調(diào)用conditionTF調(diào)用expression調(diào)用語(yǔ)句塊調(diào)用scaner出錯(cuò)處理調(diào)用condition調(diào)用語(yǔ)句塊6expression函數(shù)結(jié)構(gòu)示意圖如下：調(diào)用term是否+、-TF調(diào)用scaner出錯(cuò)處理調(diào)用term7term函數(shù)結(jié)構(gòu)示意圖如下：調(diào)用factor是否*、/TF調(diào)用scaner出錯(cuò)處理調(diào)用factor8.condition函數(shù)結(jié)構(gòu)示意圖如下：調(diào)用expression是否邏輯運(yùn)算符

8、TF調(diào)用scaner出錯(cuò)處理調(diào)用expression9factor函數(shù)結(jié)構(gòu)示意圖如下：是否標(biāo)識(shí)符TF調(diào)用scaner是否數(shù)字TF調(diào)用scaner是否（TF調(diào)用scaner出錯(cuò)處理調(diào)用expression是否）TF調(diào)用scaner出錯(cuò)處理語(yǔ)義分析部分：2學(xué)時(shí)（一）實(shí)驗(yàn)的輸入和輸出輸入是語(yǔ)法分析提供的正確的單詞串，輸出是四元式序列。例如，對(duì)于語(yǔ)句串i=2*3+4;if(i10) j=3;while(j0) k=1;輸出的四元式序列如下：1:*,2,3,T12:+,T1,4,T23:=,T2,i4:j,i,10,65:j,76:=,3,j7:j,j,0,98:j,119:=,1,k10:j,7（二）

9、算法思想1設(shè)置語(yǔ)義過(guò)程int gen(op,arg1,arg2,result)該函數(shù)是將四元式(op,arg1,arg2,result)送到四元式表中。char *newtemp()該函數(shù)回送一個(gè)新的臨時(shí)變量名，臨時(shí)變量名產(chǎn)生的順序?yàn)椋篢1，T2，int merg(p1,p2)該函數(shù)將以p1和p2為頭指針的兩條鏈合并為一，合并后的鏈表首為返回值。int bp(p,t)該函數(shù)的功能是把p所鏈接的每個(gè)四元式的第四區(qū)段都填為t。2主程序示意圖如下：置初值調(diào)用scaner調(diào)用lrparser打印四元式列表結(jié)束3函數(shù)lrparse在原來(lái)語(yǔ)法分析的基礎(chǔ)上插入相應(yīng)的語(yǔ)義動(dòng)作。將輸入串翻譯成四元式序列。在實(shí)驗(yàn)

10、中我們只對(duì)表達(dá)式、if語(yǔ)句和while語(yǔ)句進(jìn)行翻譯，其具體翻譯程序見(jiàn)實(shí)例。算符優(yōu)先分析法部分：（選作）算符優(yōu)先分析法特別有利于表達(dá)式的處理，宜于手工實(shí)現(xiàn)。算符優(yōu)先分析過(guò)程是自下而上的歸約過(guò)程，但這種歸約未必是嚴(yán)格的規(guī)范歸約。因此，所謂算符優(yōu)先分析法就是定義算符之間的某種優(yōu)先關(guān)系，并借助這種關(guān)系尋找句型的最左素短語(yǔ)進(jìn)行歸約。算符優(yōu)先分析法通常有兩種：優(yōu)先矩陣法和優(yōu)先函數(shù)法。前者是提供一張算符優(yōu)先關(guān)系表，后者提供兩個(gè)優(yōu)先函數(shù)（入棧優(yōu)先函數(shù)f和比較優(yōu)先函數(shù)g），優(yōu)先函數(shù)法比優(yōu)先矩陣法節(jié)約存儲(chǔ)空間，所以較為普遍。下面介紹使用優(yōu)先函數(shù)法的分析過(guò)程。分析過(guò)程：先在算符棧置“$”，然后開(kāi)始順序掃描表達(dá)式。若

11、讀來(lái)的單詞符號(hào)是操作數(shù)，則直接進(jìn)操作數(shù)棧，然后繼續(xù)下一個(gè)單詞符號(hào)。分析過(guò)程從頭開(kāi)始，并重復(fù)進(jìn)行；若讀來(lái)的單詞符號(hào)是運(yùn)算符，則將當(dāng)前處于運(yùn)算符棧頂?shù)倪\(yùn)算符的入棧優(yōu)先函數(shù)f與的比較優(yōu)先函數(shù)g進(jìn)行比較。1若，則進(jìn)算符棧，并繼續(xù)順序往下掃描，分析過(guò)程重復(fù)進(jìn)行。2若，則產(chǎn)生對(duì)操作數(shù)棧頂?shù)娜舾身?xiàng)進(jìn)行運(yùn)算的中間代碼，并從運(yùn)算符棧頂移去，且從操作數(shù)棧頂移去相應(yīng)若干項(xiàng)，然后把執(zhí)行運(yùn)算的結(jié)果壓入操作數(shù)棧。接著以運(yùn)算符棧新的項(xiàng)與進(jìn)行上述比較。3重復(fù)步驟1，2，直到“$”和“$”配對(duì)為止。三、實(shí)驗(yàn)環(huán)境DOS或Windows操作系統(tǒng)TURBO C 2.0或Visual C+四、實(shí)驗(yàn)部分參考（約定常量名及函數(shù)名）#ifn

12、def _GLOBALS_H#define _GLOBALS_H#include#include#include#define _SYN_MAIN 1#define _SYN_INT 2#define _SYN_CHAR 3#define _SYN_IF 4#define _SYN_ELSE 5#define _SYN_FOR 6#define _SYN_WHILE 7#define _SYN_ID 10#define _SYN_NUM 20#define _SYN_ASSIGN 21#define _SYN_PLUS 22#define _SYN_MINUS 23#define _SYN_T

13、IMES 24#define _SYN_DIVIDE 25#define _SYN_LPAREN 26#define _SYN_RPAREN 27#define _SYN_LEFTBRACKET1 28#define _SYN_RIGHTBRACKET1 29#define _SYN_LEFTBRACKET2 30#define _SYN_RIGHTBRACKET2 31#define _SYN_COMMA 32#define _SYN_COLON 33#define _SYN_SEMICOLON 34#define _SYN_LG 35#define _SYN_LT 36#define _S

14、YN_ME 37#define _SYN_LE 38#define _SYN_EQ 39#define _SYN_NE 40#define _SYN_END 1000#define _SYN_ERROR -1#define MAXLENGTH 255#ifndef _SEMANTEM_H#define _SEMANTEM_H/*四元組的結(jié)構(gòu)*/typedef struct QUADchar opMAXLENGTH; /*操作符*/char argv1MAXLENGTH;/*第一個(gè)操作數(shù)*/char argv2MAXLENGTH;/*第二個(gè)操作數(shù)*/char resultMAXLENGTH;/*

15、運(yùn)算結(jié)果*/QUATERNION;void lrparse(void);/*語(yǔ)法語(yǔ)義分析主函數(shù)*/#endifunion WORDCONTENTchar T1MAXLENGTH;int T2;char T3;typedef struct WORDint syn;union WORDCONTENT value;WORD;#ifndef _SCAN_H#define _SCAN_H#define _TAB_LEGNTH 4#define _KEY_WORD_END waiting for you expandingvoid Scaner(void);#endifQUATERNION *pQuad;

16、int nSuffix,nNXQ,ntc,nfc;extern WORD uWord;extern int gnColumn,gnRow;FILE *fw;char *strFileName;char *strSource;char *Expression(void);char *Term(void);char *Factor(void);void Statement_Block(int *nChain);/*FILE *Source;*/FILE *fw;char *strSource;void Do_Tag(char *strSource);void Do_Digit(char *strS

17、ource);void Do_EndOfTag(char *strSource);void Do_EndOfDigit(char *strSource);void Do_EndOfEqual(char *strSource);void Do_EndOfPlus(char *strSource);void Do_EndOfSubtraction(char *strSource);void Do_EndOfMultiply(char *strSource);void Do_EndOfDivide(char *strSource);void Do_EndOfLParen(char *strSourc

18、e);void Do_EndOfRParen(char *strSource);void Do_EndOfLeftBracket1(char *strSource);void Do_EndOfRightBracket1(char *strSource);void Do_EndOfLeftBracket2(char *strSource);void Do_EndOfRightBracket2(char *strSource);void Do_EndOfColon(char *strSource);void Do_EndOfComma(char *strSource);void Do_EndOfS

19、emicolon(char *strSource);void Do_EndOfMore(char *strSource);void Do_EndOfLess(char *strSource);void Do_EndOfEnd(char *strSource);void PrintWord(WORD uWord);void ApartWord(char *strSource);void PrintError(int nColumn,int nRow,char chInput);void Scaner(void);int gnColumn,gnRow,gnLocate,gnLocateStart;

20、WORD uWord;char *KEY_WORDS20=main,int,char,if,else,for,while,void,_KEY_WORD_END;int IsDigit(char chInput)/判斷掃描的字符是否數(shù)字if(chInput=0) return 1;else return 0;int IsChar(char chInput)/判斷掃描的字符是否字母if(chInput=a)|(chInput=A)return 1;else return 0;void Do_Start(char *strSource)/開(kāi)始識(shí)別一個(gè)單詞gnLocateStart=gnLocate;

21、switch(strSourcegnLocate)case +: Do_EndOfPlus(strSource); break;case -: Do_EndOfSubtraction(strSource);break;case *: Do_EndOfMultiply(strSource); break;case /: Do_EndOfDivide(strSource);break;case (: Do_EndOfLParen(strSource);break;case ): Do_EndOfRParen(strSource);break;case : Do_EndOfLeftBracket1(

22、strSource);break;case : Do_EndOfRightBracket1(strSource);break;case : Do_EndOfLeftBracket2(strSource);break;case : Do_EndOfRightBracket2(strSource);break;case : Do_EndOfColon(strSource);break;case ,: Do_EndOfComma(strSource);break;case ;: Do_EndOfSemicolon(strSource);break;case : Do_EndOfMore(strSou

23、rce);break;case =);gnLocate+;gnRow+;return;void Do_EndOfLess(char *strSource)if(strSourcegnLocate+1!=)uWord.syn=_SYN_LT;uWord.value.T3=strSourcegnLocate;elsegnLocate+;gnRow+;uWord.syn=_SYN_LE;strcpy(uWord.value.T1,=);gnLocate+;gnRow+;return;void Do_EndOfEnd(char *strSource)uWord.syn=_SYN_END;uWord.v

24、alue.T3=strSourcegnLocate;gnLocate+;gnRow+;return;void PrintWord(WORD uWord)/輸出單詞二元組（種別碼，單詞）if(uWord.synCol:%dtRow:%dtChar:%c,nColumn,nRow,chInput);return;void Scaner(void)/詞法分析框架函數(shù)Do_Start(strSource);PrintWord(uWord);return;/以下注釋中為詞法分析部分的測(cè)試主函數(shù)/*void main()strSource=main()int i=10;while(i) i=i-1;fw=

25、stdout;ApartWord(strSource);*/只要做詞法分析，則下面代碼不要void LocateError(int nColumn,int nRow)/輸出錯(cuò)誤所在的行、列提示信息fprintf(fw,nCol:%dtRow:%d-,nColumn+1,nRow);void error(char *strError)/輸出具體錯(cuò)誤信息（傳給fw指向的文件，即輸出文件），/本程序錯(cuò)誤信息種類設(shè)置較簡(jiǎn)單，可以自己補(bǔ)充。LocateError(gnColumn,gnRow);fprintf(fw,%s,strError);return;void Match(int syn,char

26、*strError)/判斷當(dāng)前識(shí)別出的單詞是否與語(yǔ)法中約定的相符，/若相符，調(diào)用scaner()識(shí)別下一個(gè)單詞備用；否則報(bào)語(yǔ)法分析錯(cuò)if(syn=uWord.syn) Scaner();else error(strError);return;void gen(char *op,char *argv1,char *argv2,char *result)/隨著進(jìn)程生成四元組，將其保存在pQuad結(jié)構(gòu)體數(shù)組中，為輸出作準(zhǔn)備sprintf(pQuadnNXQ.op,op);sprintf(pQuadnNXQ.argv1,argv1);sprintf(pQuadnNXQ.argv2,argv2);spr

27、intf(pQuadnNXQ.result,result);nNXQ+;return;void PrintQuaternion(void)/輸出四元組int nLoop;for(nLoop=1;nLoopnNXQ;nLoop+)fprintf(fw,n%d:%s,t%s,t%s,t%s,nLoop,pQuadnLoop.op,pQuadnLoop.argv1,pQuadnLoop.argv2,pQuadnLoop.result);char *Newtemp(void)/自動(dòng)產(chǎn)生中間結(jié)果標(biāo)識(shí)“T1”,“T2”等字符串，以備輸出四元組用char *strTempID=(char *)malloc(

28、MAXLENGTH);sprintf(strTempID,T%d,+nSuffix);return strTempID;int merg(int p1,int p2)/合并p1和p2int p,nResult;if(p2=0) nResult=p1;elsenResult=p=p2;while(atoi(pQuadp.result)p=atoi(pQuadp.result);sprintf(pQuadp.result,%s,p1);return nResult;void bp(int p,int t)/將中間結(jié)果（如：t1,t2等）填到四元組中int w,q=p;while(q)w=atoi(

29、pQuadq.result);sprintf(pQuadq.result,%d,t);q=w;return;char *Expression(void)/處理表達(dá)式char oppMAXLENGTH,*eplace,eplace1MAXLENGTH,eplace2MAXLENGTH;eplace=(char *)malloc(MAXLENGTH);strcpy(eplace1,Term();strcpy(eplace,eplace1);while(uWord.syn=_SYN_PLUS|uWord.syn=_SYN_MINUS)sprintf(opp,%c,uWord.value.T3);Sc

30、aner();strcpy(eplace2,Term();strcpy(eplace,Newtemp();gen(opp,eplace1,eplace2,eplace);strcpy(eplace1,eplace);return eplace;char *Term(void)/處理相乘或相除（可以連乘連除,所以下面的分析是一個(gè)循環(huán)）的項(xiàng)char opp2,*eplace,*eplace1,*eplace2;eplace=(char *)malloc(MAXLENGTH);eplace=eplace1=Factor();strcpy(eplace,eplace1);while(uWord.syn

31、=_SYN_TIMES|uWord.syn=_SYN_DIVIDE)sprintf(opp,%c,uWord.value.T3);Scaner();eplace2=Factor();eplace=Newtemp();gen(opp,eplace1,eplace2,eplace);eplace1=eplace;return eplace;char *Factor(void)/處理表達(dá)式中的因子，如a1*12中的a1和12,即可以為數(shù)或標(biāo)識(shí)符.char *eplace=(char *)malloc(MAXLENGTH);if(uWord.syn=_SYN_ID|uWord.syn=_SYN_NUM

32、)if(uWord.syn=_SYN_ID)sprintf(eplace,%s,uWord.value.T1);else sprintf(eplace,%d,uWord.value.T2);Scaner();elseMatch(_SYN_LPAREN,();eplace=Expression();Match(_SYN_RPAREN,);return eplace;void Condition(int *etc,int *efc)/處理?xiàng)l件表達(dá)式char opp3,*eplace1,*eplace2;char strTemp4;eplace1=Expression();if(uWord.syn=

33、_SYN_LG)switch(uWord.syn)case _SYN_LT:case _SYN_LG:sprintf(opp,%c,uWord.value.T3);break;default:sprintf(opp,%s,uWord.value.T1);break;Scaner();eplace2=Expression();*etc=nNXQ;*efc=nNXQ+1;sprintf(strTemp,j%s,opp);gen(strTemp,eplace1,eplace2,0);gen(j,0);/條件表達(dá)式對(duì)應(yīng)的四元組第一項(xiàng)加標(biāo)志jelse error(關(guān)系運(yùn)算符);void Statemen

34、t(int *nChain)/分析賦值、if、while語(yǔ)句char strTempMAXLENGTH,eplaceMAXLENGTH;int nChainTemp,nWQUAD;switch(uWord.syn)/處理賦值語(yǔ)句case _SYN_ID:strcpy(strTemp,uWord.value.T1);Scaner();Match(_SYN_ASSIGN,=);strcpy(eplace,Expression();Match(_SYN_SEMICOLON,;);gen(=,eplace,strTemp);*nChain=0;break;/處理if語(yǔ)句case _SYN_IF:Match(_SYN_IF,if);Match(_SYN_LPAREN,();Condition(&ntc,&nfc);bp(ntc,nNXQ);Match(_SYN_RPAREN,);Statement_Block(&nChainTemp);*nChain=merg(nChainTemp,nfc);break;/處理while語(yǔ)句case _SYN_WHILE: