1、編譯技術課程設計報告實驗名稱編譯器設計姓名 學號 班級 本課設的任務是完成一個完整的編譯器， 處理用戶提交的符合所定文法的源程序代 碼，生成四元式中間代碼，進而翻譯成等價的 X86平臺上匯編語言的目標程序。編譯程序的工作過程劃分為下列 5個過程：詞法分析，語法分析，語義分析和中間 代碼生成，代碼優化，目標代碼生成。其中，詞法分析階段的基本任務是從以字符串表示的源程序中識別出具有獨立意義 的單詞符號，并以二元組的形式輸出，以作為語法分析階段的輸入。語法分析階段的基 本任務是將詞法分析階段產生的二元組作為輸入，根據語言的語法規則，識別出各種語法成分，并判斷該單詞符號序列是否是該語言的一個句子。語義

2、分析的任務是首先對每 種語法單位進行靜態的語義審查，然后分析其含義，并用另一種語言形式（本課設采用四元式）來描述這種語義。代碼優化的任務是對前階段產生的中間代碼進行等價變換或 改造，以期獲得更為高效即省時間和空間的目標代碼。目標代碼生成的任務是將中間代 碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼（本課設生成匯編指令代碼）。在詞法分析階段，通過DOS環境手動輸入字符串序列 （以作為結束標志）作為帶 分析的源程序，調用詞法掃描子程序將字符串以二元組的形式輸出（若有不屬于該語言單詞符號出現，則進行出錯處理），詞法掃描子程序包括了對源程序的預處理（忽略多 余空格、回車換行符等空

3、白字符），以及對單詞的識別和分類，以形成（單詞種別，單 詞自身的值）形式的二元組，并將用戶自定義變量信息存入程序變量信息表。在語法分析階段，采用自上而下的遞歸下降分析法，從文法的開始符號出發，根據 文法規則正向推導出給定句子。根據遞歸下降分析函數編寫規則來編寫相應的函數，在各個函數的分析過程中調用詞法分析程序中的掃描程序，發出“取下一個單詞符號”的 命令，以取得下一個單詞符號作語法分析。在語義分析和中間代碼生成階段，采用語法制導翻譯法，使用屬性文法為工具來描述 程序設計語言的語義。首先審查詞法分析得到的每個語法結構的靜態語義，如果靜態語義正確再生成中間代碼（本課設中采用四元式）。使用屬性文法作

4、為描述程序設計語言 語義的工具，采用語法制導翻譯法完成對語法成分的翻譯工作，即在語法分析過程中， 依隨分析的過程，根據每個產生式所對應的語義子程序（或語義規則描述的語義處理的加工動作）進行翻譯。目標代碼生成是編譯程序的最后一個階段，根據符號表等信息，將中間代碼轉化為等價的目標代碼。為減少訪問計算機內存的次數， 應盡可能把基本塊內還要被引用的變 量放到寄存器中，而把基本塊內不用的變量所占的寄存器釋放。為了隨時掌握寄存器的使用情況和變量的存放情況， 以便生成適當地目標代碼， 可以建立寄存器描述表和變量 地址描述表。在編譯程序的各個階段中都要涉及到表格管理和錯誤處理。編譯程序在工作過程中需要建立一些

5、表格，以登記源程序中所提供的或在編譯過程中所產生的一些信息，編譯各個階段的工作都涉及到構造、查找、修改或存取有關表格中的信息（本課設中建立了 程序變量信息表，變量地址描述表，寄存器描述表）。一個好的編譯程序在編譯過程中， 應具有廣泛的程序查錯能力，并能準確地報告錯誤的種類及出錯位置，以便用戶查找和糾正，因此，在編譯程序中還必須有一個出錯處理程序。實驗的整體設計思想可由以下圖示表示：編譯器基本模塊設計詞法分析的任務是對字符串表示的源程序從左到右地進行掃描和分解，根據語言的詞法規則識別出一個一個具有獨立意義的單詞符號，包括關鍵字，標識符，常數，運非d+、d0的功能是識別由該非終結符所表示的語法成

6、此相應的這組函數采用自出給定的每個非終結符編寫一個函數，根據文法規則正向推導程序）,每個函數（或子程序） 去常常是遞歸定義的，因（或子程序）1312為每個非終結符編制一個遞歸下降分析函數，每個函數名是相應的非終結符，函 數體則是根據規則右部符號串的結構和順序編寫，完成相應非終結符匹配，通過所有子程序的相互調用，完成整個終結符號串的分析。(1) 當遇到終結符a時，則編寫語句if (當前讀來的輸入符號=a)讀下一個輸入符號；(2) 當遇到非終結符A時，則編寫語句調用 A();(3) 當遇到規則A-&時，則編寫語句if (當前讀來的輸入符號FOLLOW(A)error()；遞歸下降分析法是確定的自上

7、而下分析法，這種分析法要求文法是LL(1)文法。語法結構定義采用擴充的BNF表示法，避免了直接左遞歸規則，并且也沒有公共左因子。對于非終結符 L T +T ,函數T()用while語句描述如下：T ()F ();while ( sym = = =,JGE )|(,JG)|(v=,JLE)|(v,JL)說明：使用到的80X86宏匯編指令:一般傳送指令MOV OPD,OPS將字轉換成雙字指令(將AX中的符號擴展至 DX中)：CBW加指令：ADD OPD,OPS減指令：SUB OPD,OPS有符號乘指令：IMUL OPD,OPS有符號除指令：IDIV OPS(字除法：(DX,AX)/(OPS) AX

8、商 ),DX余數)比較指令：CMP OPD,OPS轉移指令：JE相等轉移JNE不相等轉移JG大于轉移JGE大于或等于轉移JL小于轉移JLE小于或等于轉移JMP無條件轉移指令限制:目的操作數不能是立即操作數；(2) 操作結束后，運算結果送人目的地址中；(3) 源操作數和目的操作數不能同時為存儲器操作數;(4) IMUL OPD,OPS OPD為寄存器(5) IDIV OPS中OPS不能是立即操作數1.流程框圖 1)詞法分析器seaner()函數流程圖2)語法分析器(遞歸下降法)P()函數流程圖B()函數流程圖SS(函數流程圖3)語義分析及中間代碼生成初始化:flag,nVar,index,nSu

9、ffix 置 0Parse()函數流程圖4)目標代碼生成2.函數相關說明1)詞法分析部分函數Scaner()識別源程序的一個單詞符號 詞法分析程序所用的全局變量如下：rwtab關鍵字對應到編碼值的映射表。prog字符數組，存放源程序ch字符變量，存放當前讀進的源程序字符。syn整型，當前單詞種別編碼token 字符數組,存放當前構成單詞符號的字符串。sum雙精度型，存放當前常量的數值。variable 用戶自定義變量信息表。flag 1表示剛讀取一個變量或常數，+/-為運算符；0反之，+/-可能為數值符號將從鍵盤輸入的字符串存儲到prog數組，用scaner()函數從prog中取出有獨立意義的

10、字符串存到token中：1、 首字符為字母，且其后為字母與數字的組合，syn對應到碼值10，進一步檢查此組合字符串是否在關鍵字表中，若在其中，則修改syn對應到相應碼值；2、 數字串的組合中：整數數字串、小數數字串碼值、(含有字母e)指數數字串，將其二進制數值存入sum；3、其他符號先判斷是否為符號組合一部分，若為符號組合，則繼續掃描，syn應到相應碼值；若為單個符號，則回退，syn對應到相應碼值。main():先從鍵盤輸入待編碼字符串，存入prog中，用#判斷是否輸入結束，然后調用scaner()函數，得到對應碼值，有 print函數顯示輸出。d) 語法分析部分(遞歸下降法)(1) 函數 S

11、caner()功能：讀進源程序的下一個單詞符號并將它放在全程變量 sym。(2) 函數 error()功能：出錯處理程序。數組 prog、token、rwtab，函數 scanner()作用同上。遞歸下降算法分析：調用 scan er()函數，對應出碼值若不為 0,則報錯；然后調用 語句串分析函數；判斷是否含有 end;若含有則再次調用 sca ner()函數，對應得相 應碼值；判斷是否由#提示結束；若是，則打印分析成功，若否則轉報錯處理。3. 輸入與輸出(包括出錯處理)a)詞法分析程序詞法分析程序的輸入是字符串形式的源程序，詞和詞之間可以用空白字符(空格、回車、制表符)隔開。詞法分析程序的輸

12、入是一個二元組，形式為：(單詞種別碼，單詞自身的值)。若輸入的字符串帶有不合法的字符，則對應的字符(串)在輸出中不以二元組的形式顯示，而以“ error!表示出錯。例如：輸入 main while if 123.455e+123#輸出：(1,ma in)(9,while)(6,if)(20,1.23455e+125)(0,#)b)語法分析程序語法分析程序的輸入與詞法分析的輸入一致，即字符串形式的源程序， 詞和詞之間可以用空白字符(空格、回車、制表符)隔開。語法程序的輸出是判斷所輸入字符串是否是該語言的句子的結果，也即“ success或者“ fail!” ，分別表示所輸入的字符串是該語言的一個

13、句子和字符串不是該語言的一個句子。出錯時結果為“fail! ”。例如：輸入 123.345e+123+(1*3+(2+4)/212)+12#結果為“ success! ”4. 程序運行結果(屏幕截圖)5. 編譯器使用說明語法分析器的輸入為字符串形式的源程序，詞與詞之間可以用空白字符(空格、回 車、制表符)隔開；語法程序的輸出是判斷所輸入字符串是否是該語言的句子的結果，也即“ success!或者“ fail!”，分別表示所輸入的字符串是該語言的一個句子和字符串不是該語言的一個句子。是則輸出“ success，出錯則輸出“ fail”。6. 心得與體會大部分系統軟件和應用軟件的開發，通常要用到編

14、譯的原理和技術。設計詞法分析 器的串匹配技術已用于正文編輯器、信息檢索系統和模式識別程序；上下文無關文法和語法制導定義已用于創建諸如排版、繪圖系統和語言結構化編輯器中，代碼優化技術已用于程序驗證器和從非結構化的程序產生結構化程序的編程之中。通過動手編寫程序對詞法語法的分析有了更加深入的體會，鞏固了編譯原理的基本 知識，親自動手實踐編譯程序，使我對編譯更加感興趣。此次實驗只是實現了編譯器最 基本的功能，不由得感嘆實際的編譯器實在太強大了！繼續認真學習，勤于思考，學習 編譯中的精妙思想，做好課設！7. 源程序清單#include stdafx.h#include #include #include

15、 #include #include #include /*/詞法分析#define max 10 char *rwtab 9 = main ,int ,float double ,char ,if ,else,do ,while;char prog1OO; 源程序int p;當前處理字符位置char ch; /當前處理字符int flag; /1表示剛讀取一個變量或常數，+/-為運算符；0反之，+/-可能為數值符號int syn;/種別編碼char token max; /保留字、內部字符串或操作符|double sum; / 數值char* variable;/ 變量信息表int nVar

16、;/*/ void scaner()int i;for(i=O;imax;i+) token i=0;sum=0;int m=0;int e=0;/數值指數ch=progp+;while(isspace(ch) ch=progp+;/預處理，去除注釋、多余空格、回車換行符等 if(isalpha(ch)/保留字、內部字符串while(isalnum(ch)tokenm+=ch;ch=progp+;tokenm+=0;p-;syn=10;for(i=0;i9;i+)if(strcmp (token ,rwtabi)=0)syn=i+1;flag=0;break;if(syn=1O)flag=1;

17、for (i=1;i=nVar;i+)if (!strcmp(token,variablei) return; strcpy(variable +nVar, token);else if (ch =+| ch =-| isdigit(ch)/ 數值、+、-if (!isdigit(ch)&(flag = 1|! isdigit(progp)tokenm+=ch;if (ch = +) syn =22;elsesyn = 23;flag = 0;elseint flag1 = 0;int flag2 = 0;if(ch = +| ch =-)ch=progp+;if(ch = -) flag1=

18、1;while(isdigit (ch)sum=sum*10+ ch-0;ch=progp+;int k=10;if(ch=. & isdigit (progp)ch=progp+;while(isdigit (ch)double d=ch-0;sum=sum+d/k;k=k*10;ch=prog p+; |if(ch=e | ch=E)char ch_tmp =prog p;if(ch_tmp=-+ | ch_tmp =-) & isdigit(progp+1) | isdigit (ch_tmp) ch=prog p+;if(!isdigit (ch)if(ch+)flag2=0;else

19、flag2=1;ch=progp+;while(isdigit (ch)e=e*10+ch-0;ch=progp+;if(flag2)sum=sum*pow(10.0,-e);elsesum=sum*pow(10.0,e);if(flag1) sum*=(-1);p-;syn=20;flag=1;else/運算符、分隔符flag = 0;m=0;switch (ch)casev:tokenm+=ch;ch=progp+;if(ch=)syn=35;tokenm+=ch;elsesyn=34;P-； break;case：tokenm+=ch; ch=progp+; if(ch=)syn=33;

20、 tokenm+=ch;elsesyn=32;P-; break;case=:tokenm+=ch; ch=progp+; if(ch=)syn=36; tokenm+=ch;elsesyn=21;p-; break;case!:tokenm+=ch; ch=progp+; if(ch=)syn=37; tokenm+=ch;elsesyn=-1; break;case*:syn=24; token0=ch; break;case/:syn=25; token 0=ch; break;case(:syn=26; token 0=ch; break;case):syn=27; token 0=c

21、h; break;case:syn=28; token 0=ch; break;case:syn=29; token 0=ch; break;case,:syn=30; token 0=ch; break;case;:syn=31; token 0=ch; break;case#:syn=0; token 0=ch; break;default:syn=-1; printf (illegal character %c/n ,ch);return ;/*/*語法語義分析*/*/遞歸下降法/void P (); / 程序void B (int *nChain); / 語句塊void SSint *

22、nChain); / 語句串void S (int *nChain); / 語句void AS(int *nChain); / 賦值語句void CS(int *nChain); / 條件語句void LS(int *nChain); / 循環語句void C (int *etc,int *efc); / 條件char * E ();/ 表達式char * T ();/ 項char * F ();/ 因子void error (); / 出錯處理/語法制導翻譯/1/typedef struct quaternion char opmax;char argv1max;char argv2max;

23、char resmax;quad;四元式quad *pQuad;四元式組指針int index,nSuffix;四元式編號，臨時變量編號/*void gen(char *op,char *argv1 ,char *argv2,char *result); char *NewTemp();int merg (int p1,int p2);void bp(int p,int t);void printQuad ();void Parse();/* void error ()if (syn=20) printf (Syntax error before %g ,sum); else printf (

24、Syntax error before %g ,token); syn=50;/程序 :=main()語句塊void P()int nChain;scaner();if (syn = 1)scaner();if(syn = 26)scaner();if (syn = 27)scaner();B(&n Chain);else error ();else error ();else error ();/語句塊 :=語句串void B(int * nChain)if (syn=28)scaner();SSnChain);if (syn = 29) scaner(); else error ();el

25、se error ();/語句串 :=語句;語句;void SS(int *nChain)S(nChain);if (syn=31) scaner();else error ();while (syn != 29)S(nChain);if (syn=31) scaner(); else error ();/語句 :=賦值語句|v條件語句|v循環語句void S(int *nChain)if(syn=10) AS(nChain);else if (syn=6) CS(nChain);else if (syn=8) LS(nChain);else error ();/賦值語句:=ID=表達式voi

26、d AS(int *nChain)char stempmax;char *place;if (syn=10)strcpy(stemp, token);scaner();if (syn=21)scaner();place=E();gen(=,place, ,stemp);*nChain = 0;else error ();else error ();bp(*nChain,index);/條件語句:=if條件 語句塊else 語句塊 void CSint *nChain)int nChaintmp ,ntc,nfc;if (syn=6)scaner();C(&ntc, &nfc);bp(ntc,i

27、ndex); B(&n Chaintmp);*nChain=merg(nChaintmp ,nfc);if (syn=7)int nfc1;scaner();nfc1 =index;gen(goto ,0);bp(*nChain,index);B(&n Chaintmp);*nChain=merg(nChaintmp ,nfc1);bp(*nChain,index);else*nChain=merg(nChaintmp ,nfc);bp(*nChain,index);else error ();/循環語句:=do 語句塊while 條件 void LS(int *nChain)int ntc

28、,nfc;if (syn = 8)int nChaintmp; scaner();int indextmp =index;B(&n Chaintmp);if (syn = 9)scaner();C(&ntc, &n fc); bp(ntc,indextmp); bp(nfc,index);*nChain=merg(nChaintmp ,nfc); bp(*nChain,index);else error ();else error ();/條件:=表達式v關系運算符 表達式void C(int *etc,int *efc) char opmax,optmpmax,* place1,* plac

29、e2; place1 =E();if (syn31 & syn38)sprintf (op,%s,token);scaner();place2=E();*etc=index;*efc=index+1;sprintf(optmp ,goto %s,op); gen(optmp ,place1 ,place2,0);gen(goto ,0);else error ();/表達式 := 項 +V項|-項char * E()char opmax,* placel ,* place2;char *place = (char *) malloc(max); place=place1=T();while (

30、syn = 22 | syn = 23)sprintf (op,%s,token ); scaner();place2=T(); place=NewTemp();gen(op,place1 ,place2,place); placel =place;return place;/項:= 因子*v因子|/v因子char * T()char opmax,* placel ,* place2;char *place ;place=place1=F();while (syn = 24 | syn = 25)sprintf (op,%s,token ); scaner();place2=F(); plac

31、e=NewTemp();gen(op,place1 ,place2,place); placel =place;return place;/ 因子 :=ID|num|( 表達式 )char * F() char *place = (char *) malloc(max); if (syn = 10)sprintf (place,%s,token); scaner();else if (syn = 20)sprintf (place ,%g,sum); scaner();else if (syn = 26)scaner();place=E();if(syn = 27) scaner();else

32、 error ();else error ();return place;/*/生成四元式void gen(char *op,char *argv1 ,char *argv2,char *result)sprintf (pQuadindex.op,%s,op);sprintf (pQuadindex. argv1,%s,argv1);sprintf (pQuadindex.argv2,%s,argv2);sprintf (pQuadindex. res,%s ,result); index+;/產生臨時變量char *NewTemp()char *tmplD = (char *)malloc

33、(max);sprintf (tmpID ,T%d,+nSuffix);return tmpID;/ 合并 p1、p2int merg (int p1,int p2)int p,nRes;if(p2 = 0)nRes = p1;elsep = p2;nRes = p2;while(atoi(pQuadp.res)p = atoi(pQuadp.res);sprintf (pQuadp.res,%s,p1);return nRes;/將t回填到p為首的四元式鏈void bp(int p,int t)int w,q = p;while (q)w=atoi(pQuadq.res);sprintf (

34、pQuadq.res,%d ,t);q=w;return ;/打印四元式序列到文件，控制臺輸岀void printQuad ()int n;FILE*fw = fopen (quaternion.txt ,w);printf (四元式序列如下：n);for (n=1;nindex;n+)fprintf (fw,n%2d:%7s,%5s,%5s,%5sn,pQuadn.op,pQuadn.argv1,pQuad n.argv2,pQuadn.res);printf (n%2d:%7s,%5s,%5s,%5sn,pQuadn.op,pQuadn.argv1,pQuad n.argv2,pQuadn

35、.res); fclose(fw);/*/語法分析、語義分析和中間代碼生成主程序void Parse() int i;p=0;flag = 0;/程序變量信息表variable = (char*) malloc(strlen(prog)*sizeof(char*);for (i=0;i strlen (prog); i+) variablei=(char *)malloc(max); nVar=0;/四元式序列pQuad = (quad *) malloc(strlen (prog)*sizeof(quad); index=1;/四元式臨時變量編號nSuffix=0;P();if(syn = 0)printf (Success!n);printQuad ();else printf (Fail!n);/*/目標代碼生成(匯編語言)*/*/typedef struct assembly_commandchar Lablemax;char OPmax;char OPDmax;char OPSmax;assemb;/匯編指令assemb * pAssemb;/匯編指令序列指針int indexA;/匯編指令編號int* lable;/四元式編號所對應匯編指令編號char* registerT