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

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

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

3、符號包括關(guān)鍵字、運算符、常數(shù)、標(biāo)識符和界符。語法分析器將這些單詞符號作為輸入，對它進(jìn)行語法分析。語法分析分為兩種方法：自上而下分析法和自下而上分析法。針對不同程序語言的語法規(guī)則可以采取不同的分析方法，當(dāng)然兩種方法也可以同時使用。語法分析器把語法單元作為輸入供語義分析器使用。一般的語義分析器主要采用的是語法制導(dǎo)方法，即在語法分析的同時進(jìn)行語法分析，并產(chǎn)生一定的語義動作，來生成中間代碼。上面三個過程可以與硬件無關(guān)，而接下來的優(yōu)化器和目標(biāo)代碼生成器是針對某一種處理器而言的。代碼優(yōu)化是將語義分析生成的中間代碼進(jìn)行優(yōu)化，產(chǎn)生執(zhí)行效率更高的代碼。目標(biāo)代碼生成器最終生成可以在某種機器上運行的機器語言或者匯編

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

5、程能力。2簡單詞法分析器的設(shè)計與實現(xiàn)2.1 基礎(chǔ)理論說明詞法分析負(fù)責(zé)對源程序的字符串進(jìn)行掃描和分解，根據(jù)構(gòu)詞法將字符流(Character Stream)轉(zhuǎn)化成單詞流(Token Stream)。2.2 需求分析詞法分析器 產(chǎn)生下述小語言的單詞序列這個小語言的所有的單詞符號，以及它們的種別編碼和內(nèi)部值1如下表： 單詞符號種別編碼助記符內(nèi)碼值DIMIFDOSTOPEND標(biāo)識符常數(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è)計首先，所有的關(guān)鍵字（如IFWHILE等）都是“保留字”。所謂的保留字的意思是，用戶不得使用它們作為自己定義的標(biāo)示符。例如，下面的寫法是絕對禁止的： IF（5）=x 其次，由于把關(guān)鍵字作為保留字，故可以把關(guān)鍵字作為一類特殊標(biāo)示符來處理。也就是說，對于關(guān)鍵字不專設(shè)對應(yīng)的轉(zhuǎn)換圖。但把它們（及其種別編碼）預(yù)先安排在一張表格中（此表叫作保留字表）。當(dāng)轉(zhuǎn)換圖識別出一個標(biāo)識符時，就去查對這張表，確定它是否為一個關(guān)鍵字。再次，如果關(guān)鍵字、標(biāo)識符和常數(shù)之間沒有確定的運算符或界符作間隔，則必須至少用一個空白符作間隔（此時，空白符不再是完全沒有意義的了）。例如，一個條件語句應(yīng)寫為 IF i>0 i=

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

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

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

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

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

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

13、設(shè)計.2013-07-23:6頁4 線性大樹.百度文庫. 編譯原理詞法語法語義設(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+;/讀取下一個字符; if(ch>=65&&ch<=122 /*是字母字符*/) while(ch>

15、;=65&&ch<=122|ch>=48&&ch<=57)/*為字母字符或數(shù)字字符*/ tokenm+=ch; ch=progp+;/讀取下一個字符； 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+;/讀取下一個字符；p=p-1;/回退一個字符；syn=11;else switch(ch) case '<': m=0;tokenm+=ch; ch=progp+;/讀取下一個字符； if(ch='>') syn=21; tokenm+=ch; else if(ch='=') syn=22; tokenm+=ch; else syn=20; p=p-1;/回退一個字符； break; case'>': tokenm+=ch; ch=progp

17、+;/讀取下一個字符； if(ch='=') syn=24;/將>=的中別碼=>syn; tokenm+=ch; else syn=23; p=p-1;/回退一個字符； break; case':': tokenm+=ch; ch=progp+;/讀取下一個字符； if(ch='=') syn=18; tokenm+=ch; else syn=17; p=p-1;/回退一個字符； 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<<"請確定是否繼續(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)式計算*/ 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的自動機char TMachine(char w); /表達(dá)式T的自動機char FMachine(char w); /表達(dá)式F的自動機bool ZMachine(); /表達(dá)式Z的自動機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; /符號棧static int noOfQuet=0; /靜態(tài)四元式個數(shù)記錄static int noOfT = 1; /靜態(tài)狀態(tài)個數(shù)記錄void main() /主函數(shù)char yesOrNo; /進(jìn)行一個循環(huán)操作控制docout<<"請輸入算術(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自動機char w;cin>>w;w = EMachine(w); /調(diào)用E自動機if(w='#') /遇到“#”則結(jié)束return true;elsereturn false;char EMachine(char w) /E自動機string operate,a,b,c;string state5;w = TMachine(w); /調(diào)用T自動機while(w='+'|w='-

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