編譯原理_簡單編譯器課程設(shè)計(jì)報(bào)告

1、信息科學(xué)與工程學(xué)院課程設(shè)計(jì)任務(wù)書題目一個(gè)簡單編譯器的設(shè)計(jì)與分析姓 名:學(xué) 號(hào):專業(yè)班級(jí)：課 程: 編譯原理指導(dǎo)教師：職稱：講師完成時(shí)間：2011 年 12 月-2011 年 12 月棗莊學(xué)院信息科學(xué)與工程學(xué)院制2011年12月20日課程設(shè)計(jì)任務(wù)書及成績?cè)u(píng)定課程設(shè)計(jì)的任務(wù)和具體要求在理解編譯原理相關(guān)理論的基礎(chǔ)上， 要求用C或C+語言描述及上機(jī)調(diào)試, 實(shí)現(xiàn)一個(gè)小編譯器（包括符號(hào)表的構(gòu)造，詞法分析，語法分析，語義分析，目 標(biāo)代碼生成等重要子程序，其中詞法分析、語法分析及語義分析功能必須完成） 使學(xué)生將理論與實(shí)際應(yīng)用結(jié)合起來，受到軟件設(shè)計(jì)等開發(fā)過程的全面訓(xùn)練，從 而提高學(xué)生軟件開發(fā)的能力。指導(dǎo)教師簽字

2、：_日期：指導(dǎo)教師評(píng)語成績： 指導(dǎo)教師簽字： 日期： 課程設(shè)計(jì)所需軟件、硬件等硬件環(huán)境：Win dowsXP/Wi n7操作系統(tǒng)軟件環(huán)境：Microsoft visual C+6.0課程設(shè)計(jì)進(jìn)度計(jì)劃起至日期工作容備注2011-12-01 052011-12-06 102011-12-11 16查找資料理清思路，編寫程序完善程序，編輯文檔參考文獻(xiàn)、資料索引序號(hào)文獻(xiàn)、資料名稱編著者出版單位【1】 程序設(shè)計(jì)語言編譯原理火旺 春林國防工業(yè)【2】數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏清華大學(xué)【3】C+程序設(shè)計(jì)吳乃林況迎輝高等教育【4】C語言程序設(shè)計(jì)譚浩強(qiáng)清華大學(xué)【5】 程序設(shè)計(jì)語言編譯原理火旺、春林等 國防工業(yè)目錄一、 摘要

3、錯(cuò)誤!未定義書簽。二、 總體設(shè)計(jì)方案及主要設(shè)計(jì)原理 錯(cuò)誤!未定義書簽。1、 單詞符號(hào)及種別表 錯(cuò)誤!未定義書簽。2、 語法結(jié)構(gòu)定義 錯(cuò)誤!未定義書簽。3、 主要算法 錯(cuò)誤!未定義書簽。(1) 詞法分析主要算法 錯(cuò)誤!未定義書簽。(2) 語法分析主要思想 錯(cuò)誤!未定義書簽。(3) 語義分析主要算法 錯(cuò)誤!未定義書簽。三、 源程序代碼 錯(cuò)誤!未定義書簽。四、 測試及分析 錯(cuò)誤!未定義書簽。五、 心得體會(huì) 錯(cuò)誤!未定義書簽。一、摘要編譯程序的工作過程一般可以分為五個(gè)階段：詞法分析、語法分析、 語義分析與中間代碼產(chǎn)生、優(yōu)化、目標(biāo)代碼生成。每一個(gè)階段在功能上是 相對(duì)獨(dú)立的，它一方面從上一個(gè)階段獲取分析的

4、結(jié)果來進(jìn)行分析，另一方 面由將結(jié)果傳遞給下一個(gè)階段。由編譯程序的五個(gè)階段就對(duì)應(yīng)了編譯系統(tǒng) 的結(jié)構(gòu)。其中詞法分析器利用超前搜索、狀態(tài)轉(zhuǎn)換等方法，將源程序轉(zhuǎn)化成為一個(gè) 一個(gè)的單詞符號(hào)二元式。一般程序語言的單詞符號(hào)包括關(guān)鍵字、運(yùn)算符、 常數(shù)、標(biāo)識(shí)符和界符。語法分析器將這些單詞符號(hào)作為輸入，對(duì)它進(jìn)行語 法分析。語法分析分為兩種方法：自上而下分析法和自下而上分析法。針 對(duì)不同程序語言的語法規(guī)則可以采取不同的分析方法，當(dāng)然兩種方法也可 以同時(shí)使用。語法分析器把語法單元作為輸入供語義分析器使用。一般的 語義分析器主要采用的是語法制導(dǎo)方法，即在語法分析的同時(shí)進(jìn)行語法分 析，并產(chǎn)生一定的語義動(dòng)作，來生成中間代碼

5、。上面三個(gè)過程可以與硬件 無關(guān)，而接下來的優(yōu)化器和目標(biāo)代碼生成器是針對(duì)某一種處理器而言的。 代碼優(yōu)化是將語義分析生成的中間代碼進(jìn)行優(yōu)化，產(chǎn)生執(zhí)行效率更高的代 碼。目標(biāo)代碼生成器最終生成可以在某種機(jī)器上運(yùn)行的機(jī)器語言或者匯編 語言。在整個(gè)編譯過程中還包括對(duì)表格的操作和對(duì)錯(cuò)誤的處理，這些也都 是非常重要的環(huán)節(jié)。F圖給出了編譯系統(tǒng)的結(jié)構(gòu)框圖詞法分析器單詞符號(hào)語法分析器語法單元語義分析與中間代碼生成器優(yōu)化器中間代碼1中間代碼目標(biāo)代碼生成器目標(biāo)代碼二、總體設(shè)計(jì)方案及主要設(shè)計(jì)原理2.1、單詞符號(hào)及種別表示單詞符號(hào)種別編碼單詞值mai n1int2float3double4char5if6else7do8w

6、hile9l(l|d)*10部字符串(+|-|£ ) d*(.dd* |£ )( e ( +|-|£ )dd*| £ )20二進(jìn)制數(shù)值表示=21+22-23*24/25(26)27282930y31>32> =33<34<=35=36!=372.2、語法結(jié)構(gòu)定義程序 :=mai n（）v 語句塊語句塊 := 語句串''/程序用括號(hào)括起來語句串 := 語句；語句；語句 := 賦值語句|條件語句|循環(huán)語句賦值語句:=ID=表達(dá)式 /賦值語句用”=”號(hào)條件語句:=if條件語句塊 /條件怎么沒有括號(hào)，囧（自己加1 個(gè)）循環(huán)

7、語句:=do 語句塊while 條件條件 := 表達(dá)式 關(guān)系運(yùn)算符 表達(dá)式表達(dá)式 := 項(xiàng) +項(xiàng)|-項(xiàng)項(xiàng) := 因子*因子|/因子 因子 :=ID| nu m|（ 表達(dá)式 ）num:= （ +|-|£ ）數(shù)字*（.數(shù)字?jǐn)?shù)字* | c ）（ e （ +卜|£ ）數(shù)字?jǐn)?shù)字*| c ）ID:=字母（字母|d數(shù)字）*字母:=a|b|c |z|A|B|C |Z數(shù)字:=0|1|2 |9關(guān)系運(yùn)算符 :=|=|=|=|!=2.3、主要算法、詞法分析主要算法這部分對(duì)源文件進(jìn)行分析，允許/* */注釋。從源文件依次讀取字符，對(duì)字符進(jìn)行分析，組成字符串、數(shù)字、關(guān)系符等固定含義的token 符，并

8、把它們添加到token鏈中，如果遇到非法字符報(bào)錯(cuò)并退出程序。232、語法分析主要思想這部分對(duì)Token鏈進(jìn)行分析，利用自底向上的分析方法，構(gòu)建SLR（1）分析表的過程是手工完成的。語法分析的同時(shí)構(gòu)建語法樹，移進(jìn) 時(shí)創(chuàng)建葉子，規(guī)約時(shí)創(chuàng)建節(jié)點(diǎn)。、語義分析主要分析這部分對(duì)語法樹從左到右進(jìn)行遍歷，節(jié)點(diǎn)記錄了規(guī)約式的編號(hào)，遍歷到節(jié) 點(diǎn)時(shí)就進(jìn)行相應(yīng)處理。語義分析主要檢查變量、函數(shù)是否被定義或重定義，同 時(shí)產(chǎn)生四元式。三、源程序代碼#i nclude<stdio.h> #i ncludevstri ng.h> #in clude<math.h> #i nclude<std

9、lib.h>char prog80; /存放所有輸入字符char toke n 8; /存放詞組char ch; / 單個(gè)字符int syn ,p, m,n ,i; syn:種別編碼double sum;int count;int isSignal; /是否帶正負(fù)號(hào)（0不帶，1負(fù)號(hào)，2正號(hào)）int isError;int isDecimal; /是否是小數(shù)double decimal; / 小數(shù) int isExp; /是否是指數(shù)int in dex; /指數(shù)幕int isNegative; / 是否帶負(fù)號(hào)是否連續(xù)出現(xiàn)+,-double temp; int temp2; int repe

10、at; / int n extq;int kk; /臨時(shí)變量的標(biāo)號(hào)int ntc,nfc,nnc,nnb,nna;char *rwtab9="ma in ","i nt","float","double","char","if","else","do","wh ile"structchar result10; / 字符串(字符數(shù)組)char arg110;char opera10;char arg210;fourCo

11、m20; /結(jié)構(gòu)體數(shù)組void sca nn er(); /掃描void lrparser();void staBlock( int *n Chai n); /語句塊void staStri ng(int *n Chai n); /語句串void sta(i nt *n Chai n); /語句void fuzhi(); /賦值語句void tiaojia n(int *n Chai n); /條件語句void xun hua n(); /循環(huán)語句char* E(); /Expresiio n表達(dá)式char* T(); /Term 項(xiàng)char* F(); /Factor 因子char *n e

12、wTemp(); /自動(dòng)生成臨時(shí)變量void backpatch(i nt p,i nt t); /回填int merge(int p1,int p2); /合并 p1 和 p2void emit(char *res,char *nu m1,char *op,char *nu m2); /生成四元式void mai n()p=0;coun t=0;isDecimal=0;in dex=0;repeat=0;kk=0;prin tf("nPlease in put your source stri ng:n");doch=getchar(); progp+=ch;while(

13、ch!=#);p=0;isError=0;sca nn er();lrparser();for(i=1;i< nextq;i+) /循環(huán)輸出四元式prin tf("n%dt",i);prin tf("(%5s%5s%5st%5s )n",fourComi.arg1,fourComi.opera,fourComi.arg2,fourCo mi.result);void lrparser()int n Cha in;nfc=n tc=1;n extq=1;if(syn=1) mai nsca nn er();if(sy n=26) /(sca nn e

14、r();if(sy n=27) /)sca nn er();staBlock(&n Chai n);elseprintf("缺少右括號(hào)n");elseprintf("缺少左括號(hào)n"); elseprintf("缺少 mainn");/語句塊 :='' 語句串''void staBlock(i nt *n Chai n) /語句塊if(sy n=28) /sca nn er();staStri ng(n Cha in);backpatch(* nCha in,n extq);if(sy n=29)

15、 /sca nn er(); / 讀下一個(gè)elseprintf("缺少號(hào) n"); elseprin tf("缺少號(hào)n");/語句串 := 語句;語句;void staStri ng(i nt *n Chai n) /語句串sta( nChai n);backpatch(* nCha in,n extq);while(sy n=31) /;sca nn er(); sta( nChai n);/backpatch(* nChai n,n extq-1);void sta( int *n Chai n) /語句if(sy n=10)fuzhi();/*n

16、Chai n=0;else if(syn=6) /iftiaojian(n Cha in);else if(syn=8) /doxun hua n();/條件語句-if(條件 ) 語句塊void tiaojia n(i nt *n Cha in)char res10, num110, num210,op10; int n Cha in Temp;/條件 -表達(dá)式 關(guān)系運(yùn)算符表達(dá)式if(sy n=6) /ifsca nn er();strcpy( nu m1,E();if(sy n=26) /(sca nn er();strcpy( nu m1,E();if(sy n<=37)&&

17、amp;(sy n>=32)switch(s yn)case 32:strcpy(op,">"); break;case 33: strcpy(op,">="); break;case 34: strcpy(op,"<"); break;case 35: strcpy(op,"<="); break;case 36: strcpy(op,"="); break;case 37: strcpy(op,"!="); break;default:pri

18、n tf("error");sca nn er(); strcpy( nu m2,E();strcat( nu m1,op); strcat( nu m1, nu m2);nfc=n extq+1;ntc= nextq; /記住if語句位置emit("O","if", num1,"goto");nfc=n extq; /if中表達(dá)式為假emit("0","","","goto");/第一個(gè)0已回填backpatch(ntc,nextq)

19、; ntc的所有四元式都回填 nextqif(syn=27) /)sca nn er();staBlock(&n Chai nTemp); /語句塊*n Chai n=merge( nChai nTemp, nfc);/循環(huán)語句:=do 語句塊while 條件void xun hua n()char res10, num110, num210,op10;int n Cha in Temp;if(syn=8) /donnc=nextq; / 記住if 語句位置，emit之后 nextq 就變了emit("0","if", num1,"go

20、to");sca nn er();staBlock(&n Chai nTemp); /語句塊if(syn=9) /whilesca nn er();if(sy n=26) /(sca nn er();strcpy( nu m1,E();if(sy n=37)&&(sy n=32)switch(s yn)case 32:strcpy(op,"");break;case 33:strcpy(op,"=");break;case 34: strcpy(op,"<"); break;case 35: s

21、trcpy(op,"<="); break;case 36: strcpy(op,"="); break;case 37: strcpy(op,"!="); break;default:prin tf("error");sca nn er(); strcpy( nu m2,E();strcat( nu m1,op); strcat( nu m1, nu m2);nnb=n extq;emit("O","if", num1,"goto"); backp

22、atch( nnb,nn c);nna=n extq;emit("0","","","goto"); backpatch( nna,n extq);if(syn=27) /)sca nn er();void fuzhi() /賦值語句只有1個(gè)操作數(shù)char res10, nu m10; /num操作數(shù)if(sy n=10)/字符串strcpy(res,toke n); / 結(jié)果sea nn er();if(sy n=21)/1=sea nn er();strepy( nu m,E(); emit(res ,nu m

23、,"=",""); elseprin tf("缺少=號(hào) n");char* E() /Expressi on表達(dá)式char *res,* nu m1,*op,* nu m2; res=(char *)malloc(10);nu m1=(char *)malloc(10); op=(char *)malloc(10); num2=(char *)malloc(10);strcpy( nu m1,T(); while(s yn=22)|(sy n=23) /+ -if(sy n=22) /+ strcpy(op,"+"

24、);elsestrcpy(op,"-"); sca nn er();strcpy( nu m2,T(); strcpy(res ,n ewTemp(); emit(res ,nu m1,op, nu m2);strcpy( nu m1,res); return nu m1;char* T() /Term 項(xiàng)char *res,* nu m1,*op,* nu m2; res=(char *)malloc(10);nu m1=(char *)malloc(10); op=(char *)malloc(10);nu m2=(char *)malloc(10);strcpy( n

25、u m1,F(); while(syn=24)|(syn=25) /* / if(sy n=24) strcpy(op,"*");elsestrcpy(op,"/");sca nn er();strcpy( nu m2,F(); strcpy(res ,n ewTemp(); emit(res ,nu m1,op, nu m2); strcpy( nu m1,res);return nu m1;char* F() /Factor 因子char *res;res=(char *)malloc(10); if(sy n=10)/ 字符串 strcpy(res

26、,toke n);sca nn er();else if(sy n=20) /二進(jìn)制數(shù)itoa(i nt)sum,res,10); /整數(shù)轉(zhuǎn)換為字符串sca nn er();else if(sy n=26) /(sca nn er(); res=E(); if(sy n=27) /) sca nn er();else isError=1;elseisError=1;return res;Lchar *n ewTemp()char *p;char varTemp10;p=(char *)malloc(10);kk+;itoa(kk,varTemp,10); strcpy(p+1,varTemp)

27、;p0='T'return p;/將p所的每個(gè)四元式的第四個(gè)分量都回填tvoid backpatch(i nt p,i nt t)int w,circle=p;while(circle) /circle不為 0 的時(shí)候w=atoi(fourComcircle.result); /四元式 circle第四分量容strcpy(fourComcircle.result,t); /把 t 填進(jìn)四元式 circle 的第四分量spri ntf(fourComcircle.result,"%d",t);circle=w; /w 記錄的是鏈條上下一個(gè)四元式，移動(dòng)！retu

28、rn;int merge(int p1,int p2) /合并 p1 和 p2char circle ,n Result;if(p2=0)n Result=p1;elsen Result=circle=p2;while(atoi(fourComcircle.result) /四元式第四個(gè)分量不為 0circle=atoi(fourComcircle.result); strcpy(fourComcircle.result,p1); spri ntf(fourComcircle.result,"%s",p1);/目的是用p1的值覆蓋0kreturn nResult; p2是頭

29、，pl覆蓋0,接在p2后邊void emit(char *res,char *nu m1,char *op,char *nu m2)strcpy(fourCom nextq.result,res);strcpy(fourCom nextq.arg1, nu m1);strcpy(fourCom nextq.opera,op);strcpy(fourCom nextq.arg2, nu m2);n extq+;void sca nner()sum=0;decimal=0;m=0;for(n=0;n<8;n+)toke nn =NULL;ch=progp+; / 從prog中讀出一個(gè)字符到c

30、h中 while(ch=' '|ch='n') /跳過空字符(無效輸入)ch=progp+;if(ch>='a')&&( ch<='z')|(ch>='A')&&(ch<='Z') ch是字母字符while(ch>='a')&&(ch<='z')|(ch>='A')&&( ch<='Z')|(ch>='0'

31、;)&&(c h<='9')toke n m+=ch; /ch=>toke nch=progp+; /讀下一個(gè)字符toke nm+='0'p-; /回退一格syn=10; / 標(biāo)識(shí)符/ 如果是"begi n","if","the n","while","do","e nd"標(biāo)識(shí)符中的一個(gè)for(n=0;n<9;n+)if(strcmp(toke n, rwtab n)=0)syn=n+1;break;else

32、if(ch>='0')&&(ch<=9)IsNum:if(isSig nal=1)/toke nm+='-'while(ch>='0')&&( ch<='9')sum=sum*10+ch-'0' /ch中數(shù)字本身是當(dāng)做字符存放的ch=progp+;if(ch='.')isDecimal=1; ch=progp+;count=0; /之前忘了清零，123.123+123.123#兩個(gè)浮點(diǎn)數(shù)就無法識(shí) 別while(ch>='0'

33、; )&&(ch<='9')pow(x,y)計(jì)算x的y次幕temp=(ch-'0')*pow(0.1,+cou nt); decimal=decimal+temp;AddToDec(); ch=progp+; sum=sum+decimal;if(ch='e'|ch='E')isExp=1; ch=progp+;if(ch='-')isNegative=1; ch=progp+; while(ch>='0' )&&(ch<='9')/

34、指數(shù)in dex=i ndex*1O+ch-'O' ch=progp+;10的幕123e3代表 123*10 (3)sum=sum*pow(10,i ndex);是錯(cuò)誤的if(isNegative)sum=sum*pow(0.1,i ndex);elsesum=sum*pow(10,i ndex);if(isSig nal=1)sum=-sum;isSig nal=0;p-;sy n=20;else switch(ch)case '<':m=0;toke n m+=ch;ch=progp+;if(ch='=')syn=35;toke n m

35、+=ch;elsesyn=34;p-;break;case '>':m=0;toke n m+=ch;ch=progp+;if(ch='=')syn=33;toke n m+=ch;elsesyn=32;P-；break;case '=':m=0;toke n m+=ch;ch=progp+;if(ch='=')syn=36;toke n m+=ch;elsesyn=21;P-;break;case '+':temp2=progp;toke n m+=ch;if(temp2>='0')&&(temp2<='9')&&(repeat=1)isSig nal=2; ch=progp+;repeat=0;goto IsNum;if(temp2='+')|(temp2='-')&&( repeat=0) /如果重復(fù)出現(xiàn)符號(hào)，才將后邊的+,-視為正負(fù)號(hào)repeat=1; ch=progp+; sy n=22;break;case '-':temp2=progp;toke n m+=