編譯原理課程設(shè)計53590

1、 河海大學(xué)編譯原理課程設(shè)計學(xué)生姓名： 學(xué) 號： 班 級： 專 業(yè)： -指導(dǎo)教師： 編譯原理課程設(shè)計指導(dǎo)書題目一 基于語法制導(dǎo)翻譯的表達(dá)式轉(zhuǎn)換編譯器一、設(shè)計目的通過本課程設(shè)計獲得對實際編譯器的構(gòu)造原理、過程和方法的感性認(rèn)識，全面掌握語法制導(dǎo)翻譯技術(shù)。二、設(shè)計內(nèi)容采用語法制導(dǎo)翻譯模式設(shè)計一個包含詞法分析、語法分析、符號表管理、錯誤處理及輸出等功能模塊的、由中綴表達(dá)式到后綴表達(dá)式的完整編譯器。該翻譯器的規(guī)格說明如下：start list eoflist expr;list |expr expr + term print(+) | expr term print(-) | termterm term

2、* factor print(*) | term / factor print(/) | term div factor print(DIV) | term mod factor print(MOD) factor ( expr )| id print( ) | num print( num.value ) 三、設(shè)計要求1、使用模塊化設(shè)計思想來設(shè)計該編譯器；2、詞法分析模塊用于讀入輸入串，并將其轉(zhuǎn)換成供語法分析模塊使用的記號流。其中包括濾掉空格和注釋、識別常數(shù)、識別標(biāo)識符和關(guān)鍵字等功能；3、要求在語法分析模塊中利用語法制導(dǎo)翻譯技術(shù)完成具體的中綴表達(dá)式到后綴表達(dá)式的翻譯，其中包括

3、按前述翻譯器的規(guī)格說明構(gòu)建對應(yīng)表達(dá)式、項、因子的非終結(jié)符expr、term和factor的函數(shù)以及檢查記號是否匹配的函數(shù)；并在不匹配時調(diào)用錯誤處理模塊；4、要求符號表管理模塊主要完成符號表對應(yīng)數(shù)據(jù)結(jié)構(gòu)的具體實現(xiàn)功能；5、錯誤處理模塊負(fù)責(zé)報告錯誤信息及位置，并終止分析過程；6、輸出模塊完成翻譯后所得到的后綴表達(dá)式的輸出。四、運行結(jié)果1、從鍵盤輸入任意中綴表達(dá)式，如： 4 - 5 * 6 DIV 4 + 8 MOD 2輸出相應(yīng)的后綴表達(dá)式： 456*4DIV-82MOD+1、 若鍵盤輸入串為非中綴表達(dá)式時，如： 4 !+* 5 - 6 DIV 4 + 8 MOD 2輸出相應(yīng)語法錯誤報告信息，并停止

4、語法分析，如： line 1 : compiler error !五、提示1、將各功能模塊設(shè)計為獨立的源程序文件；2、建立一個全局頭文件，將本設(shè)計所需要用到的系統(tǒng)頭文件的打開、一些必要的宏定義和全局變量的聲明信息放在該全局頭文件中；3、將本設(shè)計所有文件加入一個工程文件。六、分析與討論1、如何修改錯誤處理模塊，使得編譯器在發(fā)現(xiàn)錯誤后能跳過出錯語句，繼續(xù)進(jìn)行語法分析；2、試使用手工構(gòu)造和自動生成相結(jié)合的方法來完成本課程設(shè)計；3、仔細(xì)研讀附錄C有關(guān)“PL/0語言詞法分析器的手工構(gòu)造和自動生成”的設(shè)計內(nèi)容，并通過借鑒PL/0語言詞法分析器的設(shè)計方法和具體實現(xiàn)技術(shù)，對本課程設(shè)計的綜合設(shè)計進(jìn)行優(yōu)化。題目二

5、 說明語句的詞法分析器一、設(shè)計目的了解詞法分析程序的基本構(gòu)造原理，掌握詞法分析程序的手工構(gòu)造及自動構(gòu)造方法。二、設(shè)計內(nèi)容根據(jù)PASCAL語言的說明語句形式，用手工及自動方法構(gòu)造一個對說明語句進(jìn)行詞法分析的程序。該程序能對從鍵盤輸入或從文件讀入的形如：“const count=10,sum=81.5,char1=f,string1=”hj”, max=169；”的常量說明串進(jìn)行處理，分析常量說明串中各常量名、常量類型及常量值，并統(tǒng)計各種類型常量個數(shù)。三、設(shè)計要求1、輸入的常量說明串，要求最后以分號作結(jié)束標(biāo)志；2、根據(jù)輸入串或讀入的文本文件中第一個單詞是否為“const”判斷輸入串或文本文件是否為

6、常量說明內(nèi)容；3、識別輸入串或打開的文本文件中的常量名。常量名必須是標(biāo)識符，定義為字母開頭，后跟若干個字母，數(shù)字或下劃線；4、根據(jù)各常量名緊跟等號“=”后面的內(nèi)容判斷常量的類型。其中：字符型常量定義為放在單引號內(nèi)的一個字符；字符串常量定義為放在雙引號內(nèi)所有內(nèi)容；整型常量定義為帶或不帶+、- 號，不以0開頭的若干數(shù)字的組合；實型常量定義為帶或不帶+、- 號，不以0開頭的若干數(shù)字加上小數(shù)點再后跟若干數(shù)字的組合；5、統(tǒng)計并輸出串或文件中包含的各種類型的常量個數(shù)；6、以二元組(類型,值)的形式輸出各常量的類型和值；7、根據(jù)常量說明串置于高級語言源程序中時可能出現(xiàn)的錯誤情況，模仿高級語言編譯器對不同錯誤

7、情況做出相應(yīng)處理。四、運行結(jié)果1、輸入如下正確的常量說明串：const count=10,sum=81.5,char1=f,max=169,str1=“h*54 2.4S!AAsj”, char2=,str2=“aa!+h”；輸出：count(integer,10)sum(float,81.5)char1(char, f)max(integer,169)str1(string,“h*54 2.4S!AAsj”)char2(char, )str2(string,“aa!+h”)int_num=2; char_num=2; string_num=2; float_num=1.2、輸入類似如下的保留

8、字const錯誤的常量說明串：Aconstt count=10,sum=81.5,char1=f;輸出類似下面的錯誤提示信息：It is not a constant declaration statement! Please input a string again!3、輸入類似如下含常量名或常量值錯誤的常量說明串：const count=10,12sum=81.5,char1=ff,max=0016；輸出類似下面的錯誤提示信息：count(integer,10)12sum(Wrong! It is not a identifier!)char1(Wrong! There are more

9、than one char in .)max(Wrong! The integer cant be started with 0.)int_num=1; char_num=0; string_num=0; float_num=0.4、其他類型的錯誤處理情況（略）。五、提示本課程設(shè)計重點有三個：一是作為常量名的標(biāo)識符的識別；二是如何根據(jù)“=”后出現(xiàn)的內(nèi)容來判斷常量類型；三是對各種錯誤的處理。難點是對整型和實型常量的判斷必須綜合考慮多種可能情況。提示：1、 用指針或數(shù)組與指針相結(jié)合來處理輸入的常量說明串；2、 對整型和實型常量處理時，重點考慮常數(shù)中0的位置。六、分析與討論1、若考慮用E或e的科學(xué)計

10、數(shù)法來表示整數(shù)和實數(shù)，應(yīng)該如何實現(xiàn)？2、若考慮布爾型常量，且規(guī)定其值只能為true或false，應(yīng)該如何實現(xiàn)？3、如何對手工構(gòu)造的詞法分析程序做進(jìn)一步的優(yōu)化，以提高代碼質(zhì)量和運行效率？題目三 基于預(yù)測分析方法的表達(dá)式語法分析器一、設(shè)計目的了解預(yù)測分析器的基本構(gòu)成及用自頂向下的預(yù)測法對表達(dá)式進(jìn)行語法分析的方法，掌握預(yù)測語法分析程序的手工構(gòu)造方法。二、設(shè)計內(nèi)容已知文法GS：S-ATA-BUT-+AT|$U-*BU|$B-(S)|m其中，$表示空串。對該文法構(gòu)造預(yù)測分析表，并手工構(gòu)造預(yù)測分析程序，對輸入串m+m*m#進(jìn)行語法分析，并根據(jù)棧的變化狀態(tài)輸出分析過程。三、設(shè)計要求：1、判斷上述文法GS是否

11、LL(1)文法，若不是，將其轉(zhuǎn)變?yōu)長L(1)文法；2、對轉(zhuǎn)變后的LL(1)文法建立預(yù)測分析表；3、根據(jù)清華大學(xué)出版、呂映之等編著的編譯原理教材教材第五章Page 88的圖5.11手工構(gòu)造預(yù)測分析程序；4、用預(yù)測分析程序?qū)︽I盤輸入串m+m*m#進(jìn)行語法分析，并根據(jù)棧的變化狀態(tài)輸出給定串的具體分析過程。四、運行結(jié)果從鍵盤輸入串：m+m*m#；輸出：用預(yù)測分析法分析符號串m+m*m#的過程StepStackStringRuleStepStackStringRule1#Sm+m*m#S-AT10#TUmm*m#M匹配2#TAm+m*m#A-BU11#TU*m#U-*BU3#TUBm+m*m#B-m12

12、#TUB*m#*匹配4#TUmm+m*m#M匹配13#TUBm#B-m5#TU+m*m#U-$14#TUmm#M匹配6#T+m*m#T-+AT15#TU#U-$7#TA+m*m#+匹配16#T#T-$8#TAm*m#A-BU17#接受9#TUBm*m#B-m五、提示本課程設(shè)計重點有兩個：一是如何用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)實現(xiàn)預(yù)測分析表存儲和使用；二是如何實現(xiàn)各規(guī)則右部串的逆序入棧處理。建議：使用結(jié)構(gòu)體數(shù)組。六、分析與討論1、若輸入串不是指定文法的句子，會出現(xiàn)什么情況？2、總結(jié)預(yù)測語法分析程序的設(shè)計和實現(xiàn)的一般方法。題目四 基于算符優(yōu)先分析方法的表達(dá)式語法分析器一、設(shè)計目的了解用算符優(yōu)先法對表達(dá)進(jìn)行語法分

13、析的方法，掌握自頂向下的預(yù)測語法分析程序的手工構(gòu)造方法。二、設(shè)計內(nèi)容對簡單表達(dá)式文法構(gòu)造算符優(yōu)先分析器。三、設(shè)計要求1、對下列簡單表達(dá)式文法G E構(gòu)造算符優(yōu)先關(guān)系表。E # E #E E + T | TT T * F | FF P / F PP ( E )i2、根據(jù)算符優(yōu)先關(guān)系表，使用棧結(jié)構(gòu)來實現(xiàn)算符優(yōu)先分析：設(shè)置兩個棧：存放運算符的OPTR棧和存放操作數(shù)或運算結(jié)果的OPND棧。具體算法描述如下：（1）首先置操作數(shù)OPND棧為空棧，將#入運算符OPTR棧。（2）依次讀入表達(dá)式中每個單詞，若是操作數(shù)則進(jìn)OPND棧，若是運算符則轉(zhuǎn)（3）。（3）當(dāng)前設(shè)讀入的運算符為2，查找算符優(yōu)先關(guān)系表，比較2與O

14、PTR棧頂元素1 ：若1-*/(=i#=2、 參考嚴(yán)蔚敏等編著、清華大學(xué)出版社出版的C語言版數(shù)據(jù)結(jié)構(gòu)P52-P54的表達(dá)式求值算法。題目五遞歸下降分析法一、設(shè)計目的掌握遞歸下降分析法的基本原理，掌握預(yù)測符集的求法， 掌握遞歸下降分析程序的構(gòu)造方法。二、設(shè)計內(nèi)容假設(shè)文法中有如下的產(chǎn)生式Ab1 | b2 | | bn，則應(yīng)按如下方法編寫語法分析子程序procedure A() beginif tokenPredict(Ab1) then (b1) else if tokenPredict(Ab2) then (b2) else if tokenPredict(Abn) then (bn) else

15、 error() end其中對bi =X1X2Xn，(bi) =(X1); (X2); (Xn);l 如果XiVN，(Xi)= Xil 如果XiVT，(Xi)= Match(Xi) l 如果Xi= e, () = skip(空語句)三、設(shè)計要求：理解遞歸下降語法分析方法的主要原理，理解遞歸下降分析法對文法的要求， 熟練掌握Predict集合的求法， 熟練掌握文法變換算法（消除左遞歸和消除公共前綴）。四、提示：1. 基本原理遞歸下降法是語法分析中最易懂的一種方法。它的主要原理是，對每個非終極符按其產(chǎn)生式結(jié)構(gòu)構(gòu)造相應(yīng)語法分析子程序，其中終極符產(chǎn)生匹配命令，而非終極符則產(chǎn)生過程調(diào)用命令。因為文法遞歸

16、相應(yīng)子程序也遞歸，所以稱這種方法為遞歸子程序下降法或遞歸下降法。其中子程序的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎是一致的。2. 文法要求遞歸下降法要滿足的條件：假設(shè)A的全部產(chǎn)生式為A1|2|n ，則必須滿足如下條件才能保證可以唯一的選擇合適的產(chǎn)生式predict(Ai)predict(Aj)=,當(dāng)ij.五、實驗步驟1求SNL文法中每個產(chǎn)生式Predict集合Predict(A)= First() ， 當(dāng)eFirst()= (First()- e) Follow(A)，當(dāng)eFirst()根據(jù)Predict集合的定義求SNL的文法中每個產(chǎn)生式的Predict集合，判斷是否滿足遞歸下降法分析條件，若不滿足用消除左遞

17、歸和消除公共前綴等文法等價變化算法對文法進(jìn)行變換，使其滿足遞歸下降法的要求。2. 構(gòu)造遞歸下降語法分析程序采用了遞歸子程序方法進(jìn)行語法分析,對文法中的每個非終極符號按其產(chǎn)生式結(jié)構(gòu)產(chǎn)生相應(yīng)的語法分析子程序,完成相應(yīng)的識別任務(wù)。其中終結(jié)符產(chǎn)生匹配命令，非終結(jié)符則產(chǎn)生調(diào)用命令。每次進(jìn)入子程序之前都預(yù)先讀入一個單詞。因為使用了遞歸下降方法,所以程序結(jié)構(gòu)和層次清晰明了,易于手工實現(xiàn),且時空效率較高。實際的語法分析工作,從調(diào)用總程序的分析子程序開始，根據(jù)產(chǎn)生式進(jìn)行遞歸調(diào)用各個分析子程序。附錄A 部分課程設(shè)計題目參考源程序A.1 基于語法制導(dǎo)翻譯的表達(dá)式轉(zhuǎn)換編譯器參考源程序/*全局頭文件myglobal.h

18、,用于存放需加載的頭文件、宏定義、全局變量*/#include #include #include /* 加載字符測試函數(shù)*/#define BUFSIZE 128 /* 定義緩沖區(qū)大小*/#define NONE -1#define EOSTR 0#define NUM 256#define DIV 257#define MOD 258#define ID 259#define DONE 260int tokenval; /* 定義單詞屬性值*/int lineno;struct table /* 定義符號表結(jié)構(gòu)*/ char *lexptr; int token;struct table

19、symtable;/* 定義符號表*/*詞法分析程序lex.c*/#include “global.h”char lexbufBUFSIZE;int lineno=1;int tokenval=NONE;int lex() /*詞法分析函數(shù)*/ int t;while(1)t=getchar();if (t=| t=t) ; /*濾掉空格*/else if (t=n) lineno+;else if (isdigit(t) ungetc(t,stdin); scanf(“%d”,&tokenval); return NUM;else if (isalpha(t) int p,b=0; whil

20、e(isalnum(t) lexbufb=t;t=getchar();b=b+1;if (bBUFSIZE) error(“compiler error!”); lexbufb=EOSTR;if (t!=EOF) ungetc(t,stdin);p=lookup(lexbuf);if (p=0) p=insert(lexbuf,ID); tokenval=p;return sysmtablep.token; else if (t=EOF)return DONE; else tokenval=NONE;return t; /*語法分析程序paserx.c*/#include “global.h”

21、int lookahead;void parse() lookahead=lex(); while (lookahead!=DONE) express();match(;);void express() int t; void term(); while (1) switch(lookahead) case +: case -:t= lookahead;match(lookahead); term(); emit(t,NONE); continue;default: return; void term()int t; void factor(); while (1) switch(lookah

22、ead) case *: case /: case DIV: case MOD:t= lookahead;match(lookahead); factor(); emit(t,NONE); continue;default: return; void factor() switch(lookahead) case (:match();express();match();break; case NUM:emit(NUM,tokenval);match(NUM);break;case ID:emit(ID,tokenval);match(ID);break;default: error(“synt

23、ax error”); void match(int t) if (lookahead=t) lookahead=lex();else error(“syntax error”);/*輸出程序emitter.c*/#include “global.h”voidemit(int t,int tval) switch(t) case +: case -: case *: case /:printf(“%cn”,t);break;case DIV:printf(“DIVn”);break;case MOD:printf(“MODn”);break; case NUM:printf(“%dn”,tva

24、l);break; case ID:printf(“%sn”,symtabletval.lexptr);break;default:printf(“token %d, tokenval %dn”,t,tval);/*符號表處理程序symbol.c*/#include “global.h”#define STRMAX 999#define SYMMAX 100char lexemesSTRMAX;int lasrchar=-1;struct entry symtableSYMMAX;int lastentry=0;int lookup(char *s) int p; for (p=lastent

25、ry;p0;p-) if (strcmp(symtablep.lexptr,s)=0) return p; return 0;int insert(char *s,int tok) int len; len=strlen(s); if (lastentry+1=SYMMAX) error(“symbol table full”); if (lastchar+len+1=STRMAX) error(“l(fā)exemes array full”);lastentry=lastentry+1;symtablelastentry.token=tok;symtablelastentry.lexptr=&le

26、xemeslastchar+1;lastchar=lastchar+len+1;strcpy(symtablelastentry.lexptr,s);return lastentry;/*在符號表中填入關(guān)鍵字程序init.c*/#include “global.h”struct entry keywords=“div”,DIV,“mod”,MOD,0,0void init() struct entry *p; for (p=keywords;p-token;p+) insert(p-lexptr,p-token);/*錯誤處理程序error.c*/#include “global.h”void

27、 error( char *m) fprintd(stderr,“l(fā)ine %d: %sn”,lineno,m); exit(1); /*主程序mian.c*/#include “global.h”main() init();parse();exit(0);A.2 說明語句的詞法分析器參考源程序一、說明1、本例中字符和字符串都用“”來識別，引號中只包含一個字符時為字符型常量，否則，為字符串常量；2、本例只起示范性作用，并沒有全面考慮高級語言編譯器對常量說明串中可能出現(xiàn)錯誤的處理方法。2、 實際構(gòu)造本課程設(shè)計的常量說明串的詞法分析程序時，建議進(jìn)行模塊化處理。二、源代碼#includestdio.

28、h#includectype.h#define N 80#define M 16main()char *p0,*t0,*p1,*t1, *p2,*t2,*p3,*t3=const;/*char *t=true,*f=false;*/int ci=0,cf=0,cc=0,cs=0,cb=0;printf(nInput string: );p0=(char *)malloc(N*sizeof(char);p1=(char *)malloc(M*sizeof(char);p2=(char *)malloc(M*sizeof(char);p3=(char *)malloc(M*sizeof(char)

29、;t0=p3;t1=p1;t2=p2;gets(p0);while(*p0!= ) /* 檢查輸入串是否以“const”開頭 */if (*p0=*t3) p0+; t3+; else printf(nThis string isnt a const declaration!); exit(0); while (*p0!=!) /* 開始處理輸入串 p0 */ while (p1t1+M) *p1=0; p1+; p1=t1; while (p2t2+M) *p2=0; p2+; p2=t2;if (*(p0-1)= |*(p0-1)=;) /*從串p0中取標(biāo)識符，并將其作為常量名存放到串p1

30、中 */ if (*p0!=_&(!isalpha(*p0) printf(n Const name is wrong . Exit !); break; else if (*p0=_|isalpha(*p0) do *p1=*p0; p0+; p1+; if (*p0!=&*p0!=_&!isalnum(*p0) printf(n Const name is wrong . Exit !); break; while(*p0!=); p1=t1; printf(n Name:%s;t,p1); else if (*(p0-1)=) /* 從串p0中取常量值存放到串p2中 */ if (!is

31、digit(*p0)&*p0!=&*p0!=.) printf(n Const data is wrong . Exit !); break; else if (*p0=) /* 處理字符和字符串常量 */ do *p2=*p0; p0+; p2+; while(*p0!=;); if (*(p0-1)!=) printf(n String data is wrong. Exit !); break; p2=t2; if (strlen(p2)=3) cc+; printf( Data:%s ;t Type:char !n,p2); else cs+; printf( Data:%s ;t T

32、ype:string !n,p2); if (*p0=.) /* 處理由點號開頭的實數(shù) */ if (*(p0+1)=;) printf(n Float data is wrong. Exit !); break; else if (isdigit(*(p0+1) do *p2=*p0; p0+; p2+; if (!isdigit(*p0)&*p0!=;) printf(n Float data is wrong. Exit !); break; while(*p0!=;); p2=t2; cf+; printf( Data:%s ;t Type: float !n,p2); if (*p0

33、=0) /* 處理整數(shù)0或由0作整數(shù)部分的實型常量 */ *p2=*p0; p0+; p2+; if (*p0=;) ci+;printf( Data:%c ;t Type:int !n,*(p2-1); else if (*p0=.) do *p2=*p0; p0+; p2+; if (!isdigit(*p0)&*p0!=;) printf(n Float data is wrong. Exit !); break; while(*p0!=;); p2=t2; cf+; printf( Data:%s ;t Type:float !n,p2); if (isdigit(*p0)&(*p0!

34、=0) /* 處理其它整型常量和實型常量*/ p3=t0;p3=int;ci+;do *p2=*p0; p0+; p2+; if (!isdigit(*p0)&*p0!=;&*p0!=.) printf(n Int data is wrong. Exit !); break; else if (*p0=.)p3=t0;p3=float;ci-;cf+; while(*p0!=;); p2=t2; printf( Data:%s ;t Type:%s !n,p2,p3); /* 存放常量值的p2處理完 */ else p0+; /* 輸入串p0處理完 */ printf( n Total:n tint numbers: %dn tfloat numbers: %d,ci,cf); printf( n tstring n