1、華蛀#力*芳課程設計報告（2010- 2011年度第1學期）名稱:編譯技術課程設計A題目:L語言編譯器的設計與實現院系：計算機系班級：軟件0802學號:2學生姓名：指導教師：設計周數：2 周成績：日期： 2011年1月14日編譯技術課程設計任務書一、課程設計的目的與要求1 任務：實現一個簡單的編譯程序，能夠對指定程序設計語言進行編譯。2 目的： 加深對課堂講授知識的理解， 熟練掌握編譯程序設計原理及常用的技術， 建 立編譯程序的整體概念，使得學生初步具有研究、設計、編制和調試編譯程序的能力。3 要求： 熟悉有關定義、概念和實現算法， 設計出程序流程框圖和數據結構， 編寫出 完整的源程序， 進行

2、靜態檢查， 設計出輸入數據、 顯示輸出數據； 基本功能完善， 方便易用， 操作無誤； 通過課程設計學會編譯程序設計與實現的常用技術， 具備初步分析、 設計和開發 編譯程序的能力，具備分析與檢查軟件錯誤、解決和處理實驗結果的能力。4 學生要求人數： 2人，1 人負責掃描器和目標代碼生成器的設計和實現，另 1人負 責語法分析器和語法制導翻譯程序的設計和實現。二、 主要內容下面是課程設計主要內容的簡介，詳細內容請見編譯技術課程設計指導書 。1 掃描器設計 該掃描器是一個子程序，其輸入是源程序字符串，每調用一次輸出一個單詞符號。為了 避免超前搜索， 提高運行效率， 簡化掃描器的設計，假設程序設計語言中

3、， 基本字不能用作 一般標識符， 如果基本字、 標識符和常數之間沒有確定的運算符或界符作間隔， 則用空白作 間隔。2 語法分析器設計 以算法優先分析方法為例，設計一個算符優先語法分析程序。算符優先分析屬于自下而 上的分析方法，該語法分析程序的輸入是終結符號串（即單詞符號串，以一個“#”結尾），如果輸入串是句子則輸出“ YES”，否則輸出“ NO”和錯誤信息。當然，也可采用預測分析 等方法設計語法分析器，具體方法自定。3 語法制導翻譯程序設計采用語法制導翻譯方法， 實現算術表達式、 賦值語句和基本控制語句等的翻譯。 本語法 制導翻譯程序的輸入是終結符號串（即單詞符號串，以一個“#”結尾），如果輸

4、入符號串是句子 , 則按照其語義進行翻譯 , 輸出等價的四元式序列。4 目標代碼生成器設計將程序設計語言的中間代碼翻譯為目標代碼， 輸入是四元式序列， 輸出是匯編代碼文件。進度計劃序號設計內容完成時間備注1任務布置，資料查詢，方案制定第一周周一2算法設計，程序實現第一周周二至第二周周四3撰寫報告，軟件驗收第二周周五4四、設計成果要求1. 完成規定的課程設計任務，所設計軟件功能符合要求;2.完成課程設計報告， 要求格式規范，內容具體而翔實，應體現自身所做的工作，注重對設計思路的歸納和對問題解決過程的總結。,_-rr 、 、 r、五、考核方式1.平時成績+驗收答辯+實驗報告；2.五級分制。學生姓名

5、：指導教師：魯斌李莉2011年1月4日本組組員：龔澤瀅(200809020205)邵婧婕(200809020224)其中我負責語法/語義分析部分。6語法/語義分析通過設計、編制、調試一個典型的語法分析程序，實現對詞法分析程序所提供的單詞序列進行語法檢查和結構分析進一步掌握常用的語法分析方法。在詞法分析程序產生的toke此，可把語法件語咕號應的中間代碼一一四元式序列。 符號表文件四元式序列文件E語法和語義分析，產生相/語義分析作為獨立的一遍進行處理。符號表文件采用如下四元式:操作碼助記符四元式意義(51, a, 0, r )r J a+(43, a, b, r )r J a+b-(45, a,

6、b, r )r J a-b*(41, a, b, r )r J a*b/(48, a, b, r )r J b/aj<(53, a, b, n )若a<b轉至第n個四元式j<=(54, a, b, n )若a<=b轉至第n個四元式j>(57, a, b, n )若a>b轉至第n個四元式j>=(58, a, b, n )若a>=b轉至第n個四元式j =(56, a, b, n )若a=b轉至第n個四元式j(52, 0, 0, n )轉至第n個四元式j <>(55, a, b, n )若a<>b轉至第n個四元式實驗正文數據結構

7、1輸入token文件、符號表文件，其數據結構與詞法分析產生的文件相同。 2輸出四元式序列文件，其紀錄結構如下：typedef struct equint op;/四元式操作碼int opl; 操作數在符號表中的入口地址int op2; 操作數在符號表中的入口地址int result; 結果變量在符號表中的入口地址 equ;程序中可用數組 Equ存放四元式序列，定義為：equ EquEQU_LEN可用變量int LineOfEqu做指針，指向下一個即將產生的四元式符號表文件的結構與輸入相同，語法分析中對于符號表不做操作，只是在文件頭 部增加一個記錄變量多少的數據。程序結構說明為方便編程，將語言文

8、法整理如下:L t S | S ; LSt id := ESt if b then SSt if b then S else SSt while B do SSt begi n L end變量說明語句的文法:St var D| &D t l : K ; | L : K ; DK t in teger | bool | real其中，B表示布爾表達式,e 表示算術表a達式?達式可采用遞歸下降分析法或其它方法進行語法分析。語法/語義分析程序可劃分為三個模塊，結構如下:DeclearL_Begi nparser為主程序模塊，Declear為說明語句分析模塊，L_begin為復合語句分析模塊。

9、其中L_begin結構圖如下:經常使用的過程和函數：gen(int op,int a,int b, int r):生成一個四元式NewTemp():產生一個臨時變量，返回其在符號表中的入口地址BackPatch(int addr, int add：回填函數，完成四元式轉移目標的回填void getbuf():獲取文件中的一組數據void program。：程序由程序首部、程序體和；組成void proghead():程序首部： program+ 標識符 +；void block():程序體部分，常量說明、變量說明、語句部分實驗算法思想(包含主程序的示意圖)(1 )主程序的示意圖如下圖所示：(2

10、)遞歸下降分析程序示意圖如下圖所示:是杏begin?調用scan er調用語句串分析函數調用 scant'r打印分析成功出錯處理(3)語法串分析過程示意圖如下圖所示:(4) statement語句分析函數示意圖如下圖所示:(5) expression表達式分析函數如下圖所示:35(6) term分析函數示意圖如下圖所示:(7) factor分析過程示意圖如下圖所示:調I 用 scarfecr出帶處理|週后址川也(8)語義分析器：設置語義過程1、emit(char *result,char *ag1,char *op,char *ag2)該函數的功能是生成一個三地址語句送到四元式表中四元

11、式表的結構如下：struct char result8;char ag18;char op8;char ag28;quad20;(2) char *newtemp()該函數回送一個新的臨時變量名，臨時變量名產生的順序為T1 , T2，char *newtemp(void) char *p;char m8;p=(char *)malloc(8);k+;itoa(k,m,10); strcpy(p+1,m); p0= 't' return(p);2、設計思想函數 lrparser 在語法分析的基礎上插入相應的語義動作：將輸入串翻譯成四元 式序列。分析程序可知，需要進行四元式翻譯的只

12、有賦值語句、表達式和if 語句、while 語句等控制語句。 在實現時， 我采用這樣的方法： 先建立一個關于四元式的結 構體，并建立一個存放這樣的結構體的向量。當遇到賦值號 :=時，聲明一個結構體， 并把這個結構體插入向量中。 由于在賦值號前必然是一個變量 ID ，可以在遇到一個 變量ID時，就把這個ID的值存入臨時變量tmp。由于在后面可能要用到也可能用 不到，所以不用擔心 tmp 值覆蓋的問題。在向量中插入結構體變量后，需要將 ID 填入對應的項中，然后可以繼續遍歷。 遇到下一個 ID 則寫入。若 :=后面是一個表達 式，則可以在再新建一個結構體變量，在其中處理表達式的四元式生成。然后把所

13、 得的地址存入上一層的對應位置。實驗總結這次的實驗比較難。 剛剛拿到手的時候感覺無從下手， 找不到一個突破點。 其主要難點在于如何實現回填技術。在實現語法分析器時，整體采用模塊化編程的思想。將一個程序拆分成各個部分， 分別實現。在實現各個子模塊時需要注意的地方就是在實現語法分析時要考慮到各種情 況，比如同時定義多個變量等。 對此我采用了后綴的處理方式。后綴可有可無。這樣就 能解決在順序分析程序時出現多條相同類型的語句以及在一條語句中出現多個變量定 義等情況。還有就是在處理語義分析時如何處理表達式和控制語句回填位置這樣的問 題。本次實驗雖然比較大， 但不得不說， 它在很大程度上鍛煉了我們分析、

14、處理問題的 能力。 由于我采用的是模塊化編程的方式。 這樣編程的好處在于程序的結構清晰， 緊密 相連。 但是帶來的負面結果是程序的函數多。 無論在寫函數還是在調試程序的時候需要 極大的耐心。實驗中也遇到了不少小問題。 比如讀文件時如何才能使指針回退等。 這些都通過自 己的努力和同學的幫助， 不僅僅是克服了這些問題， 更重要的意義在于我又學會了一些 以前不懂的知識。同時我也感受到了理論與實現之間的差距。那些平時上課時覺得很容易懂的知識， 要通過自己在計算機上進行實現并不像想象中的那么容易。 我們能理解的知識用計算機 語言表述成計算機能理解的語言， 這不僅需要很扎實的編程基礎， 更要徹徹底底的搞懂

15、 所學的理論知識， 并達到將所學知識融會貫通的程度。 這樣才能自由的應付實現時出現 的細節問題。總之，這次的課程設計讓我收獲頗多。參考資料 【1】陳火旺、劉春林、譚慶平、趙克佳、劉越，編譯原理（第三版）. 北京：國防工業出版社【2】黃賢英、王柯柯，編譯原理及實踐教程。北京：清華大學出版社 【3】馬知行、曹啟君，編譯方法。機械工業出版社附錄一：程序代碼#include <iostream>#include <windows.h>#include <stdio.h>using namespace std;#defineAND 1#defineBEGIN 2#de

16、fineBOOL 3#defineDO 4#defineELSE 5#defineEND 6#defineFALSE 7#defineIF 8#defineINTEGER 9#defineNOT 10#defineOR 11#definePROGRAM 12#defineREAL 13#defineTHEN 14#defineTRUE 15#defineVAR 16#defineWHILE 17#defineID 18#define整數 19#define實數 20#defineLBR 21#defineRBR 22#defineADD 23#defineSUB 24#defineMUL 25

17、#defineDIV 26#defineDOT 27#defineCOM 28#defineCOL 29#defineSEM 30#defineASS 31#defineEQU 32#defineLEQ 33#defineLAB 34#defineNEQ 35#defineRAB 36#defineGEQ 37#defineODD 38#pragma oncetypedefstruct tokenintlabel; / 單詞序號char name30; / 單詞本身int code; / 單詞的機內碼int addr; / 地址，單詞為保留字時為 -1 ，為標識符或常數時為大于的數值，即在符號

18、表中的入口 地址。token() label=0;code=0;addr=0;token;void getbuf();void program();void proghead(); / 程序首部由 program 標識符組成void block(); / 程序體部分void error( int n);void consdefi();void consexpl();void conssuff();void varexpl();void vardefi();void varsuff();/void procdefi();/void procedh();/void procsuff();void

19、typeil();void assipro();void sentence();void suffix();void ifsent();void read();void whilesent();void idsuff();void write();void compsent();void exprsuff();void sentsuff();void conditio();void termsuff();void express();void term();void factsuff();void factor();void addoper();void muloper();void resp

20、oper();void argument();token t;FILE *opt=fopen( "token.txt" ,"r" );bool flag= true ; / 還能否讀void main()getbuf();program();printf( "the program is right!n" );/*Sleep(5000);*/fclose(opt);void getbuf()if (opt=NULL)cout<< "can't open the file!n"exit(0);if

21、 (feof(opt)flag= false ; / 到了結尾不可再讀cout<< "file endsn" ;elsefscanf(opt, "%d %s %d %dn" ,&t.label,,&t.code,&t.addr);void program() / 程序由程序首部、程序體和 ; 組成proghead();block();if (t.code=SEM)getbuf();elsecout<< "miss ''n" ;exit(0);void prog

22、head() / 程序首部： program+ 標識符 +；if (t.code=PROGRAM) getbuf();if (t.code=ID) getbuf();if (t.code=SEM) getbuf();elsecout<< "miss ''n" ; exit(0);elsecout<< "error of IDn" ;elsecout<< "miss keyword programn" ; exit(0);void block() / 程序體部分，常量說明、變量說明、語

23、句部分 / 變量說明、復合句consexpl();varexpl();/*procdefi(t);*/compsent();void consexpl() / 常量說明部分：整數 | 實數if (t.code= 整數 |t.code= 實數 ) getbuf(); consdefi();conssuff();if (t.code=SEM) getbuf();elsecout<< "miss ''n"exit(0);void consdefi() / 常量定義：標識符 +等號 +無符號數 if (t.code=ID) getbuf();if (t.

24、code=EQU) getbuf();if (t.code=INTEGER)getbuf(); else cout<< "miss INTEGERn" ; exit(0); elsecout<< "miss '='" ; exit(0);elsecout<< "miss IDn" ; exit(0);void conssuff() / 常量定義后綴：， +常量定義后綴if (t.code=COM) getbuf(); consdefi();conssuff();if (t.code=

25、SEM)getbuf();elsecout<< "miss ''n"exit(0);void varexpl() / 變量說明部分， var+ 變量定義 +變量定義后綴if (t.code=VAR)getbuf();vardefi();varsuff();void vardefi() / 變量定義：標識符 +標識符后綴 +：+類型+；|標識符+標識符后綴 +：+類型+；+變量定義 if (t.code=ID)getbuf();idsuff();if (t.code=COL)getbuf();typeil();if (t.code=SEM)getb

26、uf();elsecout<< "miss ''n" ;exit(0);elsecout<< "miss ':'n"exit(0);void varsuff() / 變量后綴：變量定義 +變量后綴 | 空if (t.code=ID)vardefi();varsuff();void typeil() / 類型 :real|bool|integerif (t.code=REAL|t.code=BOOL|t.code=INTEGER)getbuf();elsecout<< "wron

27、g tyoe of definen"exit(0);/void procdefi(token t)/ 過程定義：程序首部 +分程序 + / if(=/void compsent() / 復合句： begin+ 語句表 +endif (t.code=BEGIN)getbuf(); sentence(); sentsuff();if (t.code=END) getbuf();elsecout<< "miss BEGIN as the startn"exit(0);void sentence() / 賦值語句、 if 語句、 while 語句、

28、復合句 if (t.code=ID)assipro();else if (t.code=IF)ifsent();else if (t.code=WHILE)whilesent();else if (t.code=BEGIN)compsent();void sentsuff() / 語句后綴：； +語句 +語句后綴if (t.code=SEM)getbuf();sentence(); sentsuff();void assipro() / 賦值語句if (t.code=ID)getbuf(); suffix();elsecout<< "賦值語句錯誤 n" ;exi

29、t(0);void suffix() / 賦值號的后綴為賦值語句，否則為過程調用語句 if (t.code=ASS)getbuf(); express();else if (t.code=LBR)getbuf(); express();if (t.code=RBR)getbuf();elsecout<< " 缺少右半邊括號 n" ; exit(0);void express() / 表達式：正負號 +項+項后綴if (t.code=SUB)getbuf();term(); termsuff();else if (t.code= 整數 |t.code= 實數 |t

30、.code=ID)term(); termsuff();void exprsuff() / 表達式后綴：， +表達式 +表達式后綴 if (t.code=COM)getbuf();express();exprsuff();void term() / 項：因子 +因子后綴factor();factsuff();void termsuff() / 項后綴：加減型運算符 +因子 +因子后綴 | 空if (t.code=ADD|t.code=SUB)getbuf();factor();factsuff();void factsuff() / 因子后綴：因子 +因子后綴 | 空if (t.code=MU

31、L|t.code=DIV)getbuf();factor();factsuff();void factor() / 因子：標識符 +整數、實數 +括號內的表達式if (t.code=ID)getbuf();factsuff();else if (t.code= 整數 |t.code= 實數 )getbuf();factsuff();else if (t.code=LBR)getbuf();express();if (t.code=RBR)getbuf();elsecout<< " 缺少右半邊括號 n" ;exit(0);elsecout<< &quo

32、t;因子定義錯誤 n" ;exit(0);void ifsent() /if 語句： if+ 條件 +then+ 語句if (t.code=IF)getbuf();conditio();if (t.code=THEN)getbuf();sentence();elsecout<< "if 語句缺少 thenn" ;exit(0);elsecout<< "if 語句定義錯誤 n" ;exit(0);void conditio() / 作用在表達式上或者兩個表達式進行比較if (t.code=ID|t.code=LBR)exp

33、ress(); / 可能出錯respoper();express();void whilesent() /while 語句：while 語句、if 語句、do語句 if (t.code=WHILE)getbuf(); conditio();if (t.code=DO)getbuf(); sentence();elsecout<< "while 語句缺少 don" ; exit(0);elsecout<< "while 語句定義錯誤 n" ;exit(0); void idsuff() / 標識符后綴：， +標識符 +標識符后綴 i

34、f (t.code=COM)getbuf();if (t.code=ID)getbuf(); idsuff();elsecout<< " 標識符定義錯誤 n" ; exit(0);void addoper() / 加型運算，加 +減if (t.code=ADD|t.code=SUB)getbuf();elsecout<< " 加減運算定義錯誤 n" ;exit(0);void muloper() / 乘型運算，乘 +除if (t.code=MUL|t.code=DIV)getbuf();elsecout<< "

35、;乘除運算定義錯誤 n" ;exit(0);void respoper() / 比較運算符是否為 =， <>,<,<=,>,>=if (t.code>=EQU&&t.code<=GEQ)getbuf();elsecout<< " 比較運算定義錯誤 n" ;exit(0);#include<stdio.h>#include<string.h>#include<iostream.h>#include<stdlib.h>structchar res

36、ult12;char ag112;char op12;char ag212;quad;char prog80,token12;char ch;int syn,p,m=O,n,sum=O,kk;p 是緩沖區 prog 的指針，m是 token 的指針char *rwtab6="begin","if","then","while","do","end"void scaner();char *factor(void);char *term(void);char *expressio

37、n(void);int yucu();void emit(char *result,char *ag1,char *op,char *ag2);char *newtemp();int statement();int k=O;void emit(char *result,char *ag1,char *op,char *ag2)strcpy(quad.result,result);strcpy(quad.ag1,ag1);strcpy(quad.op,op);strcpy(quad.ag2,ag2);cout<<quad.result<<"="<

38、<quad.ag1<<quad.op<<quad.ag2<<endl;char *newtemp()char *p;char m12;p=(char *)malloc(12);k+;itoa(k,m,10);strcpy(p+1,m);p0='t'return (p);void scaner()for(n=0;n<8;n+) tokenn=NULL;ch=progp+;while(ch=' ')ch=progp;p+;if(ch>='a'&&ch<='z'

39、)|(ch>='A'&&ch<='Z')m=0;while(ch>='0'&&ch<='9')|(ch>='a'&&ch<='z')|(ch>='A'&&ch<='Z') tokenm+=ch;ch=progp+;tokenm+='0'p-;syn=10;for(n=0;n<6;n+)if(strcmp(token,rwtabn)=0)

40、syn=n+1;break;else if(ch>='0'&&ch<='9')sum=0;while(ch>='0'&&ch<='9')sum=sum*10+ch-'0'ch=progp+;p-;syn=11;if(sum>32767)syn=-1;else switch(ch)case'<':m=0;tokenm+=ch;ch=progp+;if(ch='>')syn=21;tokenm+=ch;else i

41、f(ch='=')syn=22;tokenm+=ch;elsesyn=23;p-;break;case'>':m=0;tokenm+=ch;ch=progp+;if(ch='=')syn=24;tokenm+=ch;elsesyn=20;p-;break;case':':m=0;tokenm+=ch;ch=progp+;if(ch='=')syn=18;tokenm+=ch;elsesyn=17;p-;break;case'*':syn=13;token0=ch;break;case'

42、/':syn=14;token0=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;break

43、;default: syn=-1;break;int lrparser() /cout<<" 調用 lrparser"<<endl;int schain=0;kk=0;if(syn=1)scaner();schain=yucu();if(syn=6)scaner();if(syn=0 && (kk=0)cout<<"success!"<<endl;elseif(kk!=1)cout<<" 缺 end!"<<endl;kk=1;elsecout<

44、;<" 缺 begin!"<<endl;kk=1;return(schain);int yucu()/ cout<<" 調用 yucu"<<endl;int schain=0;schain=statement();while(syn=26)scaner();schain=statement();return(schain);int statement() /cout<<" 調用 statement"<<endl;char *eplace,*tt;eplace=(char

45、 *)malloc(12);tt=(char *)malloc(12);int schain=0;switch(syn)case 10:strcpy(tt,token);scaner();if(syn=18)scaner();strcpy(eplace,expression();emit(tt,eplace,"",""); schain=0;elsecout<<" 缺少賦值符 !"<<endl; kk=1;return(schain);break;return(schain);char *expression(

46、void)char *tp,*ep2,*eplace,*tt; tp=(char *)malloc(12); ep2=(char *)malloc(12);/ 調用 term 分析產生表達式計算的第一項 eplaceeplace=(char *)malloc(12); tt =(char *)malloc(12); strcpy(eplace,term ();while(syn=15)|(syn=16)if(syn=15)strcpy(tt,"+");else strcpy(tt,"-");scaner();strcpy(ep2,term();/ 調用

47、term 分析產生表達式計算的第二項 ep2strcpy(tp,newtemp();/ 調用 newtemp 產生臨時變量 tp 存儲計算結果emit(tp,eplace,tt,ep2);/ 生成四元式送入四元式表strcpy(eplace,tp);return(eplace);char *term(void)/ cout<<" 調用 term"<<endl;char *tp,*ep2,*eplace,*tt;tp=(char *)malloc(12); ep2=(char *)malloc(12); eplace=(char *)malloc(12); tt=(char *)malloc(12); strcpy(ep