編譯原理詞法語法語義分析器設(shè)計(jì)(共32頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上編譯技術(shù)課程設(shè)計(jì)班 級(jí) 計(jì)算機(jī)0802 學(xué) 號(hào) 姓 名 周勇 指導(dǎo)老師 朱玉全 二零一一年 七 月編譯技術(shù)課程設(shè)計(jì)一、目的<<編譯技術(shù)>>是理論與實(shí)踐并重的課程，而其實(shí)驗(yàn)課要綜合運(yùn)用一、二年級(jí)所學(xué)的多門課程的內(nèi)容，用來完成一個(gè)小型編譯程序。從而鞏固和加強(qiáng)對(duì)詞法分析、語法分析、語義分析、代碼生成和報(bào)錯(cuò)處理等理論的認(rèn)識(shí)和理解；培養(yǎng)學(xué)生對(duì)完整系統(tǒng)的獨(dú)立分析和設(shè)計(jì)的能力，進(jìn)一步培養(yǎng)學(xué)生的獨(dú)立編程能力。二、任務(wù)及要求基本要求：1 詞法分析器 產(chǎn)生下述小語言的單詞序列這個(gè)小語言的所有的單詞符號(hào)，以及它們的種別編碼和內(nèi)部值如下表： 單詞符號(hào)種別編碼助記符內(nèi)碼

2、值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)形式-對(duì)于這個(gè)小語言，有幾點(diǎn)重要的限制：首先，所有的關(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ù)先安排在一張表

3、格中（此表叫作保留字表）。當(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= 1;而絕對(duì)不要寫成 IFi>0 i=1;因?yàn)閷?duì)于后者，我們的分析器將無條件地將IFI看成一個(gè)標(biāo)識(shí)符。這個(gè)小語言的單詞符號(hào)的狀態(tài)轉(zhuǎn)換圖，如下圖： 2 語法分析器 能識(shí)別由加+ 減- 乘* 除/ 乘方 括號(hào)（）操作數(shù)所組成的算術(shù)表達(dá)式，其文法如下：EE+T|E-T|TTT*F|T/F|FFPF|Pp(E)|i 使用的算

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

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

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

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

8、while11printf12scanf13標(biāo)識(shí)符100內(nèi)部字符串常數(shù)（整）200二進(jìn)制數(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)，標(biāo)識(shí)符詞法分析流程圖(b), 數(shù)字（整）詞法分析流程圖(c), 其

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

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

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

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

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

14、;using 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; /存儲(chǔ)輸入句子string cnt500;/標(biāo)識(shí)符int temp=0; /數(shù)組下標(biāo)int is_r

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

16、;status=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 =

18、10;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; /標(biāo)識(shí)符（）else if (ch >= '0') && (ch <= '9') /數(shù)字（） number = 0; while (ch >= '0' ) && (ch <= '9&#

19、39; ) number = number*10+(ch-'0'); ch = programi+;flag = 200;i-;else switch (ch) /運(yùn)算符和標(biāo)點(diǎn)符號(hào)case '=': if (ch = '=') wordsj+ = ch; wordsj = '0' ch = programi+; if (ch = '=') wordsj+ = ch; wordsj = '0' flag = 401; else i-; flag = 402; break; case'>&

20、#39;: 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、#39;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;wor

23、dsj = '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、'/':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;brea

25、k;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;words

26、j+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、39;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)cou

30、t<<"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&l

31、t;<"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|flagst

32、emp!=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&&

33、flagstemp!=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)"<<e

34、ndl;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()n

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

36、;<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();siyua

37、n(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) re

38、turn 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,t

39、1,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=newTe

40、mp();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<<"請(qǐng)輸入測(cè)試程序或者表達(dá)式，以$結(jié)

41、束"<<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