編譯原理-課程設(shè)計(jì)報(bào)告-簡單編譯器實(shí)現(xiàn)

1、成績： 課 程 設(shè) 計(jì)題 目：簡單編譯器實(shí)現(xiàn)學(xué) 院：信息工程學(xué)院計(jì)算機(jī)系專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班 級(jí)：計(jì)科1103班組 長：小組成員：指導(dǎo)教師：2014年12月19日目錄1 概述31.1源、目標(biāo)語言簡介31.2實(shí)現(xiàn)平臺(tái)與運(yùn)行平臺(tái)簡介31.3其它42簡單詞法分析器的設(shè)計(jì)與實(shí)現(xiàn)42.1 基礎(chǔ)理論說明42.2 需求分析42.3 概要設(shè)計(jì)52.4 詳細(xì)設(shè)計(jì)52.5 測(cè)試數(shù)據(jù)與結(jié)果72.6 心得體會(huì)73 簡單語法分析器設(shè)計(jì)與實(shí)現(xiàn)83.1 基礎(chǔ)理論說明83.2 需求分析83.3 概要設(shè)計(jì)83.4 詳細(xì)設(shè)計(jì)83.5 測(cè)試數(shù)據(jù)與結(jié)果93.6 心得體會(huì)104 中間代碼產(chǎn)生器的設(shè)計(jì)與實(shí)現(xiàn)104.1 基礎(chǔ)理論說明

2、104.2 需求分析104.3 概要設(shè)計(jì)104.4 詳細(xì)設(shè)計(jì)114.5 測(cè)試數(shù)據(jù)與結(jié)果124.6 心得體會(huì)12附錄：14附錄A：主要源程序與系統(tǒng)截圖14附錄B： 任務(wù)分配表及個(gè)人完成的程序模塊33附錄C： 小組討論與研發(fā)記錄341 概述編譯程序的工作過程一般可以分為五個(gè)階段：詞法分析、語法分析、語義分析與中間代碼產(chǎn)生、優(yōu)化、目標(biāo)代碼生成。每一個(gè)階段在功能上是相對(duì)獨(dú)立的，它一方面從上一個(gè)階段獲取分析的結(jié)果來進(jìn)行分析，另一方面由將結(jié)果傳遞給下一個(gè)階段。由編譯程序的五個(gè)階段就對(duì)應(yīng)了編譯系統(tǒng)的結(jié)構(gòu)。其中詞法分析器利用超前搜索、狀態(tài)轉(zhuǎn)換等方法，將源程序轉(zhuǎn)化成為一個(gè)一個(gè)的單詞符號(hào)二元式。一般程序語言的單詞

3、符號(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)作，來生成中間代碼。上面三個(gè)過程可以與硬件無關(guān)，而接下來的優(yōu)化器和目標(biāo)代碼生成器是針對(duì)某一種處理器而言的。代碼優(yōu)化是將語義分析生成的中間代碼進(jìn)行優(yōu)化，產(chǎn)生執(zhí)行效率更高的代碼。目標(biāo)代碼生成器最終生成可以在某種機(jī)器上運(yùn)行的機(jī)器語言或者匯編

4、語言。在整個(gè)編譯過程中還包括對(duì)表格的操作和對(duì)錯(cuò)誤的處理，這些也都是非常重要的環(huán)節(jié)。1.1源、目標(biāo)語言簡介使用C語言做簡單語法分析器，C語言是一門高級(jí)計(jì)算機(jī)編程語言，設(shè)計(jì)目標(biāo)是提供一種能以簡易的方式編譯、處理低級(jí)存儲(chǔ)器、產(chǎn)生少量的機(jī)器碼以及不需要任何運(yùn)行環(huán)境支持便能運(yùn)行的編程語言1.2實(shí)現(xiàn)平臺(tái)與運(yùn)行平臺(tái)簡介在win32環(huán)境下進(jìn)行編譯，Win32是指Microsoft Windows操作系統(tǒng)的32位環(huán)境，是目前使用最多的操作系統(tǒng)。實(shí)驗(yàn)環(huán)境：需要TC、VC+ 6.0等開發(fā)工具作為本次試驗(yàn)的環(huán)境。1.3其它通過實(shí)現(xiàn)一個(gè)可以把類似c語言的源代碼轉(zhuǎn)變?yōu)橹虚g代碼的編譯器，更好地理解編譯的過程，鍛煉我們組的編

5、程能力。2簡單詞法分析器的設(shè)計(jì)與實(shí)現(xiàn)2.1 基礎(chǔ)理論說明詞法分析負(fù)責(zé)對(duì)源程序的字符串進(jìn)行掃描和分解，根據(jù)構(gòu)詞法將字符流(Character Stream)轉(zhuǎn)化成單詞流(Token Stream)。2.2 需求分析詞法分析器 產(chǎn)生下述小語言的單詞序列這個(gè)小語言的所有的單詞符號(hào)，以及它們的種別編碼和內(nèi)部值1如下表： 單詞符號(hào)種別編碼助記符內(nèi)碼值DIMIFDOSTOPEND標(biāo)識(shí)符常數(shù)（整）=+*，（）1234567891011121314$DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR$RPAR-內(nèi)部字符串標(biāo)準(zhǔn)二進(jìn)形式-2.3

6、概要設(shè)計(jì)首先，所有的關(guān)鍵字（如IFWHILE等）都是“保留字”。所謂的保留字的意思是，用戶不得使用它們作為自己定義的標(biāo)示符。例如，下面的寫法是絕對(duì)禁止的： IF（5）=x 其次，由于把關(guān)鍵字作為保留字，故可以把關(guān)鍵字作為一類特殊標(biāo)示符來處理。也就是說，對(duì)于關(guān)鍵字不專設(shè)對(duì)應(yīng)的轉(zhuǎn)換圖。但把它們（及其種別編碼）預(yù)先安排在一張表格中（此表叫作保留字表）。當(dāng)轉(zhuǎn)換圖識(shí)別出一個(gè)標(biāo)識(shí)符時(shí)，就去查對(duì)這張表，確定它是否為一個(gè)關(guān)鍵字。再次，如果關(guān)鍵字、標(biāo)識(shí)符和常數(shù)之間沒有確定的運(yùn)算符或界符作間隔，則必須至少用一個(gè)空白符作間隔（此時(shí)，空白符不再是完全沒有意義的了）。例如，一個(gè)條件語句應(yīng)寫為 IF i>0 i=

7、1;而絕對(duì)不要寫成 IFi>0 i=1;因?yàn)閷?duì)于后者，我們的分析器將無條件地將IFI看成一個(gè)標(biāo)識(shí)符。2.4 詳細(xì)設(shè)計(jì)狀態(tài)轉(zhuǎn)換圖2詞法分析器的流程圖32.5 測(cè)試數(shù)據(jù)與結(jié)果2.6 心得體會(huì)設(shè)計(jì)該詞法分析器的過程中雖然沒有實(shí)際將所有的狀態(tài)轉(zhuǎn)移表建立出來，但是所用的思想是根據(jù)狀態(tài)轉(zhuǎn)移表實(shí)現(xiàn)對(duì)單詞的識(shí)別。首先構(gòu)造一個(gè)保留字表,然后,每輸入一個(gè)字符就檢測(cè)應(yīng)該進(jìn)入什么狀態(tài),并將該字符連接到d串后繼續(xù)輸入,如此循環(huán),最后根據(jù)所在的接受狀態(tài)以及保留字表識(shí)別單詞3 簡單語法分析器設(shè)計(jì)與實(shí)現(xiàn)3.1 基礎(chǔ)理論說明在計(jì)算機(jī)科學(xué)和語言學(xué)中，語法分析（英：Syntacticanalysis，也叫Parsing）是根

8、據(jù)某種給定的形式文法對(duì)由單詞序列（如英語單詞序列）構(gòu)成的輸入文本進(jìn)行分析并確定其語法結(jié)構(gòu)的一種過程。語法分析器（Parser）通常是作為編譯器或解釋器的組件出現(xiàn)的，它的作用是進(jìn)行語法檢查、并構(gòu)建由輸入的單詞組成的數(shù)據(jù)結(jié)構(gòu)（一般是語法分析樹、抽象語法樹等層次化的數(shù)據(jù)結(jié)構(gòu)）。語法分析器通常使用一個(gè)獨(dú)立的詞法分析器從輸入字符流中分離出一個(gè)個(gè)的“單詞”，并將單詞流作為其輸入。實(shí)際開發(fā)中，語法分析器可以手工編寫，也可以使用工具（半）自動(dòng)生成。3.2 需求分析語法分析是編譯過程的核心部分。它的任務(wù)是在詞法分析識(shí)別出單詞符號(hào)串的基礎(chǔ)上，分析并判定程序的語法結(jié)構(gòu)是否符合語法規(guī)則。語法分析器的工作本質(zhì)上是按文法

9、的產(chǎn)生式，識(shí)別輸入串是否是一個(gè)句子。自上而下分析法的主旨是，對(duì)任何輸入串，試圖用一切可能的方法，從文法開始符號(hào)出發(fā)，自上而下地為輸入串建立一棵語法樹。這種方法本質(zhì)上是一種試探過程，是反復(fù)使用不同產(chǎn)生式謀求匹配輸入串的過程。3.3 概要設(shè)計(jì)語法分析器 能識(shí)別由加+ 減- 乘* 除/ 乘方 括號(hào)（）操作數(shù)所組成的算術(shù)表達(dá)式，其文法如下：EE+T|E-T|TTT*F|T/F|FFPF|Pp(E)|i 使用的算法可以是：預(yù)測(cè)分析法；遞歸下降分析法；算符優(yōu)先分析法；LR分析法等3.4 詳細(xì)設(shè)計(jì)語法分析器主程序圖43.5 測(cè)試數(shù)據(jù)與結(jié)果3.6 心得體會(huì)此次實(shí)驗(yàn)，讓我們組對(duì)編譯原理的基本知識(shí)有了深入的了解，

10、加強(qiáng)了對(duì)語法分析的認(rèn)識(shí)。代碼的編寫過程中用到了一些以前從未用過的函數(shù)，都是現(xiàn)學(xué)現(xiàn)用，掌握還不是很深。在代碼調(diào)試過程中結(jié)果出現(xiàn)許多無法解釋的錯(cuò)誤，但仍舊堅(jiān)持下來了，最終調(diào)試出了結(jié)果。通過這次實(shí)驗(yàn)，我們組的動(dòng)手實(shí)踐能力得到很大的提高。4 中間代碼產(chǎn)生器的設(shè)計(jì)與實(shí)現(xiàn)4.1 基礎(chǔ)理論說明在進(jìn)行了語法分析和語義分析階段的工作之后，有的編譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)部表示形式，這種內(nèi)部表示形式叫做中間語言或中間表示或中間代碼。所謂“中間代碼”是一種結(jié)構(gòu)簡單、含義明確的記號(hào)系統(tǒng)，這種記號(hào)系統(tǒng)復(fù)雜性介于源程序語言和機(jī)器語言之間，容易將它翻譯成目標(biāo)代碼。另外，還可以在中間代碼一級(jí)進(jìn)行與機(jī)器無關(guān)的優(yōu)化。產(chǎn)生中間代碼的

11、過程叫中間代碼生成。4.2 需求分析定義一種語言除了要求定義語法外，還要求定義語義，即對(duì)語言的各種語法單位賦予具體的意義。語義分析的任務(wù)是首先對(duì)每種語法單位進(jìn)行靜態(tài)的語義審查，然后分析其含義，并用另一種語言形式，即比源語言更加接近于目標(biāo)語言的一種中間代碼來進(jìn)行描述這種語言。因此，中間代碼就顯得十分重要，它關(guān)系著整個(gè)程序語言的正確編譯與否，同時(shí)也是進(jìn)行下一步編譯的重要先決條件。4.3 概要設(shè)計(jì)產(chǎn)生上述算術(shù)表達(dá)式的中間代碼（四元式序列）遞歸下降子程序：數(shù)據(jù)結(jié)構(gòu)： SYN 算符棧；SEM 語義棧；4.4 詳細(xì)設(shè)計(jì)中間代碼生成器流程圖5：4.5 測(cè)試數(shù)據(jù)與結(jié)果4.6 心得體會(huì)我們知道，定義一種語言除了

12、要求定義語法外，還要求定義語義，即對(duì)語言的各種語法單位賦予具體的意義。語義分析的任務(wù)是首先對(duì)每種語法單位進(jìn)行靜態(tài)的語義審查，然后分析其含義，并用另一種語言形式，即比源語言更加接近于目標(biāo)語言的一種中間代碼來進(jìn)行描述這種語言。因此，中間代碼就顯得十分重要，它關(guān)系著整個(gè)程序語言的正確編譯與否，同時(shí)也是進(jìn)行下一步編譯的重要先決條件。參考文獻(xiàn)1 Alfred D.Ullman.Compilers: Principles,Techniques,and Tools:4頁2 zjbujs.百度文庫.編譯原理詞法語法語義分析器設(shè)計(jì).2013-07-23:5頁3 zjbujs.百度文庫.編譯原理詞法語法語義分析器

13、設(shè)計(jì).2013-07-23:6頁4 線性大樹.百度文庫. 編譯原理詞法語法語義設(shè)計(jì)實(shí)現(xiàn).2014-06-06:8頁5 LWH1989216.百度文庫.編譯原理詞法分析和語法分析 (C語言版)2011-05-11:10頁附錄： 附錄A：主要源程序與系統(tǒng)截圖 /*詞法分析器源代碼*/#include<stdio.h>#include<iostream.h>#include<string.h>#define MAX 150 /詞法分析表的最大容量#define MAXBUF 255/緩沖區(qū)的最大緩沖量char progMAXBUF,tokenMAX;char ch

14、;int syn,p,m,n,sum;char *rwtab6="begin","if","then","while","do","end"/詞法分析程序/void scaner()for(m=0;m<MAX;m+)tokenm=NULL;m=0;sum=0;ch=progp+;while(ch=' ') ch=progp+;/讀取下一個(gè)字符; if(ch>=65&&ch<=122 /*是字母字符*/) while(ch>

15、;=65&&ch<=122|ch>=48&&ch<=57)/*為字母字符或數(shù)字字符*/ tokenm+=ch; ch=progp+;/讀取下一個(gè)字符； tokenm+='0' p=p-1; syn=10; for(n=0;n<6;n+) if(strcmp(token,rwtabn)=0) syn=n+1;/給出syn值; break; else if(ch>=48&&ch<=57/*ch為數(shù)字字符*/)while(ch>=48&&ch<=57/*ch為數(shù)字字符*/)

16、sum=sum*10+ch-'0' ch=progp+;/讀取下一個(gè)字符；p=p-1;/回退一個(gè)字符；syn=11;else switch(ch) case '<': m=0;tokenm+=ch; ch=progp+;/讀取下一個(gè)字符； if(ch='>') syn=21; tokenm+=ch; else if(ch='=') syn=22; tokenm+=ch; else syn=20; p=p-1;/回退一個(gè)字符； break; case'>': tokenm+=ch; ch=progp

17、+;/讀取下一個(gè)字符； if(ch='=') syn=24;/將>=的中別碼=>syn; tokenm+=ch; else syn=23; p=p-1;/回退一個(gè)字符； break; case':': tokenm+=ch; ch=progp+;/讀取下一個(gè)字符； if(ch='=') syn=18; tokenm+=ch; else syn=17; p=p-1;/回退一個(gè)字符； break; case'+': syn=13;token0=ch; break; case'-': syn=14;token

18、0=ch; break; case'*': syn=15;token0=ch; break; case'/': syn=16;token0=ch; break; case'=': syn=25;token0=ch; break; case'': syn=26;token0=ch; break; case'(': syn=27;token0=ch; break; case')': syn=28;token0=ch; break; case'#': syn=0;token0=ch; br

19、eak; default: syn=-1; break;/主函數(shù)/void main()char A;cout<<"*"<<endl;loop: p=0;cout<<"*"<<endl; printf("please input string (以#結(jié)束):n");doscanf("%c",&ch);progp+=ch;/輸入源程序字符串，送到緩沖區(qū)progp+中；while(ch!='#');p=0;doscaner();switch(syn

20、)case 11:cout<<"( "<<syn<<","<<sum<<" )"<<endl;/輸出（數(shù)的二元組）； break;case -1:cout<<"error"<<endl; break;default:cout<<"( "<<syn<<","<<token<<" )"<<end

21、l;/輸出(其他單詞二元組);while(syn!=0);cout<<"*"<<endl;cout<<"請(qǐng)確定是否繼續(xù)使用程序:S為繼續(xù)；其它為退出；"<<endl;cout<<"是否繼續(xù):"cin>>A;switch(A) case 'S': goto loop; default: cout<<"*"<<endl; cout<<"Thank you ! Bye Bye !"

22、;<<endl; cout<<"*"<<endl; break; 結(jié)果：/*語法分析器源代碼*/#include <stdio.h>#include<dos.h>#include<stdlib.h>#include<string.h>char a50 ,b50,d200,e10;char ch;int n1,i1=0,flag=1,n=5;int total=0; int E();int E1();int T();int G();int S();int F();void input();vo

23、id input1();void output();void main() /*遞歸分析*/ int f,p,j=0; char x; d0='E' d1='=' d2='>' d3='T' d4='G' d5='#' printf("Please input character string(length<50,end of '#'):n"); do scanf("%c",&ch); aj=ch; j+; while(ch

24、!='#'); n1=j; ch=b0=a0; printf("步驟t文法t分析串tt分析字符t剩余串n"); f=E1(); if (f=0) return; if (ch='#') printf("nAccept! Right Expression!nn"); p=0; x=dp; while(x!='#') printf("%c",x);p=p+1;x=dp; /*輸出推導(dǎo)式*/ else printf("nError!n"); printf("回車返

25、回n"); getchar();getchar(); return; printf("n"); printf("回車返回n"); getchar(); getchar();int E1() int f,t; printf("%dtE->TGt",total);total+; flag=1; input(); input1(); f=T(); if (f=0) return(0); t=G(); if (t=0) return(0); else return(1);int E() int f,t; printf(&quo

26、t;%dtE->TGt",total);total+; e0='E'e1='='e2='>'e3='T'e4='G'e5='#' output(); flag=1; input(); input1(); f=T(); if (f=0) return(0); t=G(); if (t=0) return(0); else return(1);int T() int f,t; printf("%dtT->FSt",total);total+; e0=

27、9;T'e1='='e2='>'e3='F'e4='S'e5='#' output(); flag=1; input(); input1(); f=F(); if (f=0) return(0); t=S(); if (t=0) return(0); else return(1);int G() int f; if(ch='+') bi1=ch; printf("%dtG->+TGt",total);total+; e0='G'e1='

28、='e2='>'e3='+'e4='T'e5='G'e6='#' output(); flag=0; input();input1(); ch=a+i1; f=T(); if (f=0) return(0); G(); return(1); printf("%dtG->t",total);total+; e0='G'e1='='e2='>'e3=''e4='#' output(); flag

29、=1; input();input1(); return(1);int S() int f,t; if(ch='*') bi1=ch;printf("%dtS->*FSt",total);total+; e0='S'e1='='e2='>'e3='*'e4='F'e5='S'e6='#' output(); flag=0; input();input1(); ch=a+i1; f=F(); if (f=0) return(0); t=S

30、(); if (t=0) return(0); else return(1); printf("%dtS->t",total);total+; e0='S'e1='='e2='>'e3=''e4='#' output(); flag=1; ai1=ch; input();input1(); return(1);int F() int f; if(ch='(') bi1=ch;printf("%dtF->(E)t",total);total+;

31、 e0='F'e1='='e2='>'e3='('e4='E'e5=')'e6='#' output(); flag=0; input();input1(); ch=a+i1; f=E(); if (f=0) return(0); if(ch=')') bi1=ch;printf("%dtF->(E)t",total);total+; flag=0;input();input1(); ch=a+i1; else printf("

32、;nError!n"); return(0); else if(ch='i') bi1=ch;printf("%dtF->it",total);total+; e0='F'e1='='e2='>'e3='i'e4='#' output(); flag=0;input();input1(); ch=a+i1; else printf("nError!n");return(0); return(1);void input() int j=0;

33、 for (;j<=i1-flag;j+) printf("%c",bj); /*輸出分析串*/ printf("tt"); printf("%ctt",ch); /*輸出分析字符*/ void input1() int j; for (j=i1+1-flag;j<n1;j+) printf("%c",aj); /*輸出剩余字符*/ printf("n"); void output() /*推導(dǎo)式計(jì)算*/ int m,k,j,q; int i=0; m=0;k=0;q=0; i=n;

34、 dn='='dn+1='>'dn+2='#'n=n+2;i=n; i=i-2; while(di!='>'&&i!=0) i=i-1; i=i+1; while(di!=e0) i=i+1; q=i; m=q;k=q; while(dm!='>') m=m-1; m=m+1; while(m!=q) dn=dm;m=m+1;n=n+1; dn='#' for(j=3;ej!='#'j+) dn=ej; n=n+1; k=k+1; while(dk!

35、='=') dn=dk;n=n+1;k=k+1; dn='#'結(jié)果：/*中間代碼生成器源代碼*/#include<string>#include <iostream>using namespace std;#define DEFAULT_SIZE 100char EMachine(char w); /表達(dá)式E的自動(dòng)機(jī)char TMachine(char w); /表達(dá)式T的自動(dòng)機(jī)char FMachine(char w); /表達(dá)式F的自動(dòng)機(jī)bool ZMachine(); /表達(dá)式Z的自動(dòng)機(jī)string intToString(int

36、a); /整形變成字符串形函數(shù)class stack/棧類定義private: int top; string *stacka; int maxsize;public: stack(int size=DEFAULT_SIZE); stack() delete stacka; void push(const string &item); string pop(void); string gettop(void) const ; bool empty(void) const return (top=-1); bool full(void) const return (top=maxsize

37、-1); void clear(void) top=-1; ;stack:stack(int size) /棧類的構(gòu)造函數(shù) top=-1; maxsize=size; stacka=new stringmaxsize; if(!stacka) cerr<<"allocate memory failed."<<endl; exit(1); void stack:push(const string &item) /壓棧操作 if(full() cerr<<"stack full, cannot push."<

38、<endl; return; top+; stackatop=item;string stack:pop(void) /出棧操作 if(empty() cerr<<"stack empty, cannot pop."<<endl; exit(1) ; string item=stackatop; top-; return item;string stack:gettop(void) const /取棧頂操作 if(empty() cerr<<"stack empty, cannot gettop."<<

39、;endl; exit(1) ; return stackatop;static stack wordStack; /符號(hào)棧static int noOfQuet=0; /靜態(tài)四元式個(gè)數(shù)記錄static int noOfT = 1; /靜態(tài)狀態(tài)個(gè)數(shù)記錄void main() /主函數(shù)char yesOrNo; /進(jìn)行一個(gè)循環(huán)操作控制docout<<"請(qǐng)輸入算術(shù)表達(dá)式："<<endl;noOfT = 1; /每次結(jié)束詢問ZMachine();cout<<endl<<"Continue?Yes or Not:"

40、 cin>>yesOrNo; /輸入“Y”則繼續(xù)while(yesOrNo='y'); /否則程序結(jié)束bool ZMachine() /Z自動(dòng)機(jī)char w;cin>>w;w = EMachine(w); /調(diào)用E自動(dòng)機(jī)if(w='#') /遇到“#”則結(jié)束return true;elsereturn false;char EMachine(char w) /E自動(dòng)機(jī)string operate,a,b,c;string state5;w = TMachine(w); /調(diào)用T自動(dòng)機(jī)while(w='+'|w='-

41、') /是加或減符號(hào)operate = w;cin>>w; /讀入下一字符w = TMachine(w); /調(diào)用T自動(dòng)機(jī)b = wordStack.pop(); /字符棧彈出a = wordStack.pop(); /兩個(gè)操作字符cout<<"(""<<operate<<"","<<a<<","<<b<<",t"<<noOfT<<")"<<endl;c = "t"+intToString(noOfT); /輸出四元式wordStack.push(