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

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

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

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

4、語言。在整個編譯過程中還包括對表格的操作和對錯誤的處理，這些也都是非常重要的環(huán)節(jié)。1.1源、目標語言簡介使用C語言做簡單語法分析器，C語言是一門高級計算機編程語言，設計目標是提供一種能以簡易的方式編譯、處理低級存儲器、產(chǎn)生少量的機器碼以及不需要任何運行環(huán)境支持便能運行的編程語言1.2實現(xiàn)平臺與運行平臺簡介在win32環(huá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語言的源代碼轉變?yōu)橹虚g代碼的編譯器，更好地理解編譯的過程，鍛煉我們組的編

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

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

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

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

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

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

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

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

13、設計.2013-07-23:6頁4 線性大樹.百度文庫. 編譯原理詞法語法語義設計實現(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 (以#結束):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; 結果：/*語法分析器源代碼*/#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; /*輸出推導式*/ 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() /*推導式計算*/ 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='#'結果：/*中間代碼生成器源代碼*/#include<string>#include <iostream>using namespace std;#define DEFAULT_SIZE 100char EMachine(char w); /表達式E的自動機char TMachine(char w); /表達式T的自動機char FMachine(char w); /表達式F的自動機bool ZMachine(); /表達式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) /棧類的構造函數(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; /進行一個循環(huán)操作控制docout<<"請輸入算術表達式："<<endl;noOfT = 1; /每次結束詢問ZMachine();cout<<endl<<"Continue?Yes or Not:"

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

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