編譯原理詞法語法語義分析器設(shè)計

1、編譯技術(shù)課程設(shè)計班 級 計算機0802 學 號 3080602049 姓 名 周勇 指導老師 朱玉全 二零一一年 七 月編譯技術(shù)課程設(shè)計一、目的<<編譯技術(shù)>>是理論與實踐并重的課程，而其實驗課要綜合運用一、二年級所學的多門課程的內(nèi)容，用來完成一個小型編譯程序。從而鞏固和加強對詞法分析、語法分析、語義分析、代碼生成和報錯處理等理論的認識和理解；培養(yǎng)學生對完整系統(tǒng)的獨立分析和設(shè)計的能力，進一步培養(yǎng)學生的獨立編程能力。二、任務(wù)及要求基本要求：1 詞法分析器 產(chǎn)生下述小語言的單詞序列這個小語言的所有的單詞符號，以及它們的種別編碼和內(nèi)部值如下表： 單詞符號種別編碼助記符內(nèi)碼值D

2、IMIFDOSTOPEND標識符常數(shù)（整）=+*，（）1234567891011121314$DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR$RPAR-內(nèi)部字符串標準二進形式-對于這個小語言，有幾點重要的限制：首先，所有的關(guān)鍵字（如IFWHILE等）都是“保留字”。所謂的保留字的意思是，用戶不得使用它們作為自己定義的標示符。例如，下面的寫法是絕對禁止的： IF（5）=x 其次，由于把關(guān)鍵字作為保留字，故可以把關(guān)鍵字作為一類特殊標示符來處理。也就是說，對于關(guān)鍵字不專設(shè)對應(yīng)的轉(zhuǎn)換圖。但把它們（及其種別編碼）預先安排在一張表格中

3、（此表叫作保留字表）。當轉(zhuǎn)換圖識別出一個標識符時，就去查對這張表，確定它是否為一個關(guān)鍵字。再次，如果關(guān)鍵字、標識符和常數(shù)之間沒有確定的運算符或界符作間隔，則必須至少用一個空白符作間隔（此時，空白符不再是完全沒有意義的了）。例如，一個條件語句應(yīng)寫為 IF i>0 i= 1;而絕對不要寫成 IFi>0 i=1;因為對于后者，我們的分析器將無條件地將IFI看成一個標識符。這個小語言的單詞符號的狀態(tài)轉(zhuǎn)換圖，如下圖： 2 語法分析器 能識別由加+ 減- 乘* 除/ 乘方 括號（）操作數(shù)所組成的算術(shù)表達式，其文法如下：EE+T|E-T|TTT*F|T/F|FFPF|Pp(E)|i 使用的算法可

4、以是：預測分析法；遞歸下降分析法；算符優(yōu)先分析法；LR分析法等。3 中間代碼生成器 產(chǎn)生上述算術(shù)表達式的中間代碼（四元式序列）較高要求：1 擴充上述小語言的單詞；2 增加語法分析器的功能，能識別條件語句和循環(huán)語句等；3 增加中間代碼生成器的功能，能產(chǎn)生條件語句和循環(huán)語句等的中間代碼（四元式序列）4 增加報錯功能；5 將中間代碼翻譯成匯編語言。三、實現(xiàn)過程說明給出各題目的詳細算法描述，數(shù)據(jù)結(jié)構(gòu)和函數(shù)說明，流程圖。（1） 詞法分析器：1算法描述：詞法分析階段的基本任務(wù)是從以字符串表示的源程序中識別出具有獨立意義的單詞符號。通過DOS環(huán)境手動輸入字符串序列（以$作為結(jié)束標志）作為帶分析的源程序，調(diào)用

5、詞法掃描子程序?qū)⒆址远M的形式輸出（若有不屬于該語言單詞符號出現(xiàn)，則進行出錯處理），詞法掃描子程序包括了對源程序的預處理（忽略、回車換行符等字符），以及對單詞的識別和分類，以形成（單詞種別，單詞自身的值）形式的二元組。具體思路如下：首先建立關(guān)鍵字表，將關(guān)鍵字作為特殊標示符處理，把它們預先安排在char *keywords13中，將需要被識別出的關(guān)鍵字存入表中，當掃描程序識別出標識符時，查關(guān)鍵字表。如能查到匹配的單詞，則該單詞為關(guān)鍵字，否則為一般標識符。在主函數(shù)中讓用戶輸入要識別的符號串，然后將輸入的符號串讀入到 program500，遇$結(jié)束。再依次掃描program500中的每一個符號

6、，調(diào)用Scan ()子函數(shù)分析每一個符號，再將分析的結(jié)果輸出，也是遇$結(jié)束。2函數(shù)說明和數(shù)據(jù)結(jié)構(gòu)：在Scan ()子函數(shù)中，先全部初始化，然后讀一個字符，分析它是什么類型:如果是字母類型，則接著往下讀，直到讀到非字母的字符，存入words10中，依次對比關(guān)鍵字表中的元素，如果相同，則將flags置為相應(yīng)的種別碼，如果全都掃描后沒發(fā)現(xiàn)相同的關(guān)鍵字，則為普通的標識符,返回主函數(shù)輸出。如果是數(shù)字類型，首先分析第一個符號，接著讀下一個字符串，直到讀到一個不是數(shù)字的字符串位置，每讀一個數(shù)字字符，就將他們轉(zhuǎn)化為相應(yīng)的數(shù)字，使用輾轉(zhuǎn)相乘法，每次都讓number先自乘10，然后加上這個數(shù)字，這樣就將字符串表示

7、的數(shù)字轉(zhuǎn)化成了相應(yīng)的數(shù)，返回主函數(shù)輸出。如果是其他單詞表的符號，則將他們的flags置為相應(yīng)的種別碼，并將字符存到words 中返回主函數(shù)輸出。主要變量說明： 用words10存放構(gòu)成單詞符號的字符串，并且用于判斷是否為關(guān)鍵字。flags500 存放單詞符號的種別碼。Number存放整數(shù)值，words存放標識符，關(guān)鍵字或者其他符號。cntnum按順序存放讀到的字符，為下面語義分析做準備。Status用于判斷是否為關(guān)鍵字，1是，0不是。 3 具體的種別編碼和內(nèi)部值：單詞符號種別編碼單詞值void1main2if3then4break5int6char 7fioat8include9for10wh

8、ile11printf12scanf13標識符100內(nèi)部字符串常數(shù)（整）200二進制數(shù)值表示= =401=402>=403>404<=405<406!=407!408 += 409 + 410 +411 -= 412- -413 -414 *=415 *416 /=417 / 418 419 ; 501( 502 ) 503 504 505 506 507: 508 “ 509 %= 510 % 511 , 512 # 513 514 空格 515 $ 04. 流程圖：主流程圖掃描程序流程圖：(a)，標識符詞法分析流程圖(b), 數(shù)字（整）詞法分析流程圖(c), 其他字

9、符流程圖 (a)(b) (c)（2） 語法分析器1算法描述：語法分析階段的基本任務(wù)是將詞法分析階段產(chǎn)生的二元組作為輸入，根據(jù)語言的語法規(guī)則，識別出各種語法成分，并判斷該單詞符號序列是否是該語言的一個句子。在語法分析階段，采用自上而下的遞歸下降分析法，根據(jù)遞歸下降分析函數(shù)編寫規(guī)則來編寫相應(yīng)的函數(shù)，在各個函數(shù)的分析過程中調(diào)用詞法分析程序中的掃描程序，發(fā)出“取下一個單詞符號”的命令，以取得下一個單詞符號的語法分析。詞法分析和語法分析的整體設(shè)計思想可由以下圖示表示： 語法分析是在詞法分析的基礎(chǔ)上加上判斷是否符合語法規(guī)則的語句。語法分析的基本任務(wù)是使用詞法分析的結(jié)果，使用遞歸下降算法分析是否符合語法規(guī)則

10、，如果符合，則輸出“分析成功”，若果不符合，則輸出“分析失敗”。2.函數(shù)說明和數(shù)據(jù)結(jié)構(gòu)在main函數(shù)調(diào)用e()函數(shù)，如果調(diào)用之后返回時,如果(flagstemp=0)&&is_right)為真，就輸出“分析成功”，否則輸出“分析失敗”。其中is_right為設(shè)定的標志，初值為1，如果在調(diào)用子函數(shù)的過程中如果有錯誤，則置is_right為0。e函數(shù): 調(diào)用t函數(shù)，調(diào)用f函數(shù), 調(diào)用p函數(shù),返回后看是否是+或-，如果是，則調(diào)用 e1函數(shù)，再調(diào)用e2函數(shù)，如果不是，進行出錯處理，置is_right為0。e1函數(shù)：判斷是不是”+”或者“-” 如果是，調(diào)用f函數(shù)，如果不是，進行出錯處理，

11、置is_right為0。t函數(shù): 調(diào)用f函數(shù), 調(diào)用p函數(shù),返回后看是否是*或/，如果是，則調(diào)用t1函數(shù)，再調(diào)用t2函數(shù)，如果不是，進行出錯處理，置is_right為0。t1函數(shù)：判斷是不是”*”或者“/” 如果是，調(diào)用f函數(shù)，如果不是，進行出錯處理，置is_right為0。f函數(shù)：調(diào)用p函數(shù)，f1函數(shù)。f1函數(shù)：判斷是不是”,如果是，調(diào)用f函數(shù)，如果不是，進行出錯處理，置is_right為0。p函數(shù): 檢查是否標識符，如果是，調(diào)用f1函數(shù)，如果不是，檢查是否是數(shù)值，如果是，調(diào)用f1函數(shù)，如果不是，檢查是否是(，如果不是，進行出錯處理，置is_right為0。如果是，調(diào)用e函數(shù)，返回后檢查是否

12、是),如果不是，進行出錯處理，置is_right為0。如果是，調(diào)用f1函數(shù)，返回。3 流程圖： 主流程圖e函數(shù)流程圖：調(diào)用t函數(shù)p函數(shù)流程圖：t函數(shù)流程圖：f函數(shù)流程圖：（3） 中間代碼生成器1算法描述：下面以簡單算術(shù)表達式語句的翻譯為例詳細說明算法設(shè)計。實現(xiàn)簡單算術(shù)表達式的翻譯一般采取下列步驟： i. 分析文法。ii. 設(shè)置一系列語義變量，定義語義過程，語義函數(shù)。iii. 設(shè)計算術(shù)表達式的遞歸下降子程序的程序分析算法。2.函數(shù)說明和數(shù)據(jù)結(jié)構(gòu)：Strn用來存放臨時變量的序號。temp用來存放數(shù)組的下表，在主程序中語法分析結(jié)束后，置0.定義函數(shù)newtemp()用于門生一個新的臨時變量的名字，具

13、體實現(xiàn)時每產(chǎn)生一個T，就及時送到符號表中，也可以不進符號表，直接將單詞值用整數(shù)碼表示。定義函數(shù)siyuan（）,輸出一個四元式。定義函數(shù)ye() 進行中間代碼生成3主流程圖（4） 較高要求i. 擴充上述小語言的單詞；ii. 增加語法分析器的功能，能識別條件語句和循環(huán)語句等；iii. 增加中間代碼生成器的功能，能產(chǎn)生條件語句和循環(huán)語句等的中間代碼（四元式序列）iv. 增加報錯功能；v. 將中間代碼翻譯成匯編語言。 其中1，4功能完成；四實驗程序#include "stdafx.h"#include <iostream>#include<string>u

14、sing namespace std;#include<stdio.h>#include<stdlib.h> #include<sstream>int i,j,k,flag,number,status;/*status which is use to judge the string is keywords or not!*/char ch;char words10 = " "char program500;int flags500; /存儲輸入句子string cnt500;/標識符int temp=0; /數(shù)組下標int is_rig

15、ht; /判斷輸出信息/-詞法分析-int Scan(char program) char *keywords13 = "void","main","if","then","break","int","char","float","include","for","while","printf","scanf" /關(guān)鍵字number=0;s

16、tatus=0;j=0;ch=programi+; /遍歷if (ch >= 'a') && (ch <= 'z' ) /字母 while (ch >= 'a') && (ch <= 'z' ) wordsj+=ch; ch=programi+; i-; wordsj+ = '0'for (k = 0; k < 13; k+)if (strcmp (words,keywordsk) = 0) /判斷是否為關(guān)鍵字switch(k)case 0:flag =

17、 1;status = 1;break;case 1:flag = 2;status = 1;break;case 2:flag = 3;status = 1;break;case 3:flag = 4;status = 1;break;case 4:flag = 5;status = 1;break;case 5:flag = 6;status = 1;break;case 6:flag = 7;status = 1;break;case 7:flag = 8;status = 1;break;case 8:flag = 9;status = 1;break;case 9:flag = 10

18、;status = 1;break;case 10:flag = 11;status = 1;break;case 11:flag = 12;status = 1;break;case 12:flag = 13;status = 1;break;if (status = 0)flag = 100; /標識符（）else if (ch >= '0') && (ch <= '9') /數(shù)字（） number = 0; while (ch >= '0' ) && (ch <= '9'

19、; ) number = number*10+(ch-'0'); ch = programi+;flag = 200;i-;else switch (ch) /運算符和標點符號case '=': if (ch = '=') wordsj+ = ch; wordsj = '0' ch = programi+; if (ch = '=') wordsj+ = ch; wordsj = '0' flag = 401; else i-; flag = 402; break; case'>

20、9;: if (ch = '>') wordsj+ = ch; wordsj = '0' ch = programi+; if (ch = '=') wordsj+ = ch; wordsj = '0' flag = 403; else i-; flag = 404; break; case'<': if (ch = '<')wordsj+ = ch;wordsj = '0'ch = programi+;if (ch = '=')wordsj+ =

21、ch;wordsj = '0'flag = 405;elsei-;flag = 406;break;case'!':if (ch = '!')wordsj+ = ch;wordsj = '0'ch = programi+;if (ch = '=')wordsj+ = ch;wordsj = '0'flag = 407;elsei-;flag = 408;break;case'+':if (ch = '+')wordsj+ = ch;wordsj = '0

22、9;ch = programi+;if (ch = '=')wordsj+ = ch;wordsj = '0'flag = 409;else if (ch = '+')wordsj+ = ch;wordsj = '0'flag = 410;elsei-;flag = 411;break;case'-':if (ch = '-')wordsj+ = ch;wordsj = '0'ch = programi+;if (ch = '=')wordsj+ = ch;words

23、j = '0'flag = 412;else if( ch = '-')wordsj+ = ch;wordsj = '0'flag = 413;elsei-;flag = 414;break;case'*':if (ch = '*')wordsj+ = ch;wordsj = '0'ch = programi+;if (ch = '=')wordsj+ = ch;wordsj = '0'flag = 415;elsei-;flag = 416;break;case&#

24、39;/':if (ch = '/')wordsj+ = ch;wordsj = '0'ch = programi+;if (ch = '=')wordsj+ = ch;wordsj = '0'flag = 417;elsei-;flag = 418;break;case'':wordsj = ch;wordsj+1 = '0'flag = 419;break;case'':wordsj = ch;wordsj+1 = '0'flag = 501;break;

25、case'(':wordsj = ch;wordsj+1 = '0'flag = 502;break;case')':wordsj = ch;wordsj+1 = '0'flag = 503;break;case'':wordsj = ch;wordsj+1 = '0'flag = 504;break;case'':wordsj = ch;wordsj+1 = '0'flag = 505;break;case'':wordsj = ch;wordsj+

26、1 = '0'flag = 506;break;case'':wordsj = ch;wordsj+1 = '0'flag = 507;break;case':':wordsj = ch;wordsj+1 = '0'flag = 508;break;case'"':wordsj = ch;wordsj+1 = '0'flag = 509;break;case'%':if (ch = '%')wordsj+ = ch;wordsj = '

27、;0'ch = programi+;if (ch = '=')wordsj+ = ch;wordsj = '0'flag = 510;elsei-;flag = 511;break;case',':wordsj = ch;wordsj+1 = '0'flag = 512;break;case'#':wordsj = ch;wordsj+1 = '0'flag = 513;break;case'':wordsj = ch;wordsj+1 = '0'flag =

28、 514;break;case' ':/空格 wordsj ='_' wordsj+1 = '0' flag = 515; break;case'$':wordsj = '#'wordsj+1 = '0'flag = 0;break;default:flag = -1;break;return flag;/-語法分析（遞歸下降）-void e();void e1();void e2();void t();void t1();void t2();void f();void f1();void p();

29、void e()cout<<"E->TE''"<<endl;t();e2();void e1()if(flagstemp=411)cout<<"E'->+T"<<endl;temp+;t();else if(flagstemp=414)cout<<"E'->-T"<<endl;temp+;t();elseis_right=0;void e2()if(flagstemp=411|flagstemp=414)cout&

30、lt;<"E''->E'E''"<<endl; e1(); e2(); else if (flagstemp!=0|flagstemp!=503) cout<<"E''->"<<endl; return ; elseis_right=0;void t()cout<<"T->FT''"<<endl;f();t2();void t1()if(flagstemp=416)cout<

31、<"T'->*F"<<endl;temp+;f();else if(flagstemp=418)cout<<"T'->/F"<<endl;temp+;f();else is_right=0;void t2()if(flagstemp=416|flagstemp=418)cout<<"T''->T'T''"<<endl;t1();t2();else if (flagstemp!=0|flagstem

32、p!=503) cout<<"T''->"<<endl; return ; else is_right=0;void f()cout<<"F->PF'"<<endl;p(); f1();void f1() if(flagstemp=419) cout<<"F'->F"<<endl;temp+;f(); else if (flagstemp!=0&&flagstemp!=503&&fl

33、agstemp!=411&&flagstemp!=414&&flagstemp!=416&&flagstemp!=418) cout<<"F'->"<<endl;is_right=0; void p()if(flagstemp=100|flagstemp=200)cout<<"P->i"<<endl;temp+;elseif(flagstemp=502)cout<<"P->(E)"<<end

34、l;temp+;e();if(flagstemp=503)cout<<"P->(E)"<<endl;temp+;elseis_right=0;else is_right =0;/-語義分析以及中間代碼生成-int ye();int ye1(int a);int ye2(int a);int yt();int yt1(int a);int yt2(int a);int yf();int yf1(int a);int yp();int v=-1;int num=0;int ww;string strn;int nn;int newTemp()num

35、+;nn+; stringstream stream;stream<<nn;stream>>strn;stream.clear();cntnum-1="temp" cntnum-1.operator+=(strn);/把字符串s連接到當前字符串的結(jié)尾 /cntnum-1=strcat("Temp",strn); / cntnum-1="temp"return num-1;void siyuan(int a,int b,int c,int d)/輸出四元cout<<"("<&

36、lt;cnta<<","<<cntb<<","<<cntc<<","<<cntd<<")"<<endl;int ye()int rt,t1;rt=yt();t1=rt;rt=ye2(t1);return rt;int ye1(int a)int rt,t1;t1=a; if(flagstemp=411) /加法temp+;int tt=v+1;v+;int t2=yt();int rr=newTemp();siyuan(

37、tt,t1,t2,rr);rt=rr;return rt;else if(flagstemp=414) /減法temp+;int tt=v+1;v+;int t2=yt();int rr=newTemp();siyuan(tt,t1,t2,rr);rt=rr;return rt;else return t1;int ye2(int a)int rt,t1;t1=a;if(flagstemp=411|flagstemp=414) rt=ye1(t1); t1=rt; rt=ye2(t1); return rt; else if (flagstemp!=0|flagstemp!=503) retu

38、rn t1; else return t1;int yt()int rt,t1;rt=yf();t1=rt;rt=yt2(t1);return rt;int yt1(int a)int rt,t1;t1=a;if(flagstemp=416) /乘法int tt=v+1;v+;temp+;int t2=yf();int rr=newTemp();siyuan(tt,t1,t2,rr); rt=rr;return rt;else if(flagstemp=418) /除法temp+;int tt=v+1;v+; int t2=yf();int rr=newTemp();siyuan(tt,t1,

39、t2,rr);rt=rr; return rt;else return t1;int yt2(int a)int rt,t;t=a;if(flagstemp=416|flagstemp=418)rt=yt1(t);t=rt; rt=yt2(t);return rt;else return t;int yf()int t1,rt; rt=yp();t1=rt; rt=yf1(t1); return rt;int yf1(int a) /乘方int rt,t1;t1=a; if(flagstemp=419)temp+;int tt=v+1;v+;int t2=yf();int rr=newTemp

40、();siyuan(tt,t1,t2,rr);rt=rr;return rt;else return t1;int yp()int rt,t1;if(flagstemp=100|flagstemp=200)v+;rt=v; temp+; return rt;else if(flagstemp=502) /(v+; temp+; rt=ye();if(flagstemp=503) /)v+; temp+;return rt;else return ww;else return ww;void main() int i=0; cout<<"請輸入測試程序或者表達式，以$結(jié)束&

41、quot;<<endl; do ch =getchar(); programi+ = ch; while(ch != '$'); i = 0; cout<<"詞法分析："<<endl; do flag = Scan(program);/詞法分析 if (flag = 200) cout<<"("<<flag<<","<<number<<")"<<endl;flagsnum=flag;stringstream stream;stream<<number; stream>>cntnum;stream.clear();num+; else if (flag = -1) cout<<"error!"<<endl; else cout<<&qu