編譯原理實驗題目

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

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

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

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

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

6、開的文本文件中的常量名。常量名必須是標識符，定義為字母開頭，后跟若干個字母，數(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)的錯誤情況，模仿高級語言編譯器對不同錯誤情況做出相應處理。四、運行結(jié)果1

7、、輸入如下正確的常量說明串：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、輸入類似如下的保留字const錯誤的常量說明串：A

8、constt 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 than one char in

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

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

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

12、3#TUBm+m*m#B->m12#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ù)臄?shù)據(jù)結(jié)構(gòu)實現(xiàn)預測分析表存儲和使用；二是如何實現(xiàn)各規(guī)則右部串的逆序入棧處理。建議：使用結(jié)構(gòu)體數(shù)組。六、分析與討論1、若輸入串不是指定文法的句子，會出現(xiàn)什么情況？2、總結(jié)預測語法分析程序的設計和實現(xiàn)的一般

13、方法。題目四 基于算符優(yōu)先分析方法的表達式語法分析器一、設計目的了解用算符優(yōu)先法對表達進行語法分析的方法，編程實現(xiàn)算符優(yōu)先表達式語法分析器。二、設計內(nèi)容對簡單表達式文法構(gòu)造算符優(yōu)先分析器。三、設計要求1、對下列簡單表達式文法G E構(gòu)造算符優(yōu)先關系表。E # E #E E + T | TT T * F | FF P / F PP ( E )i2、根據(jù)算符優(yōu)先關系表，使用棧結(jié)構(gòu)來實現(xiàn)算符優(yōu)先分析：設置兩個棧：存放運算符的OPTR棧和存放操作數(shù)或運算結(jié)果的OPND棧。具體算法描述如下：（1）首先置操作數(shù)OPND棧為空棧，將#入運算符OPTR棧。（2）依次讀入表達式中每個單詞，若是操作數(shù)則進OPND棧

14、，若是運算符則轉(zhuǎn)（3）。（3）當前設讀入的運算符為2，查找算符優(yōu)先關系表，比較2與OPTR棧頂元素1 ：若1<2,則2進OPTR棧，轉(zhuǎn)（2）； 若12, 如2為#，則分析成功，否則OPTR棧頂元素1出棧，并轉(zhuǎn)（2）；若12，則出棧OPND棧頂元素存放到b，又出棧其新棧頂元素存放到a，再出棧OPTR棧頂元素至t，進行運算r=a t b (t為運算符)，并將結(jié)果r存入棧OPND后轉(zhuǎn)（2）；（4）若1和2之間無優(yōu)先關系，則報錯。1、 從鍵盤輸入表達式，利用算符優(yōu)先法求出其值，如輸入表達式有錯，則給出報錯提示。表達式以“#”結(jié)尾。 四、運行結(jié)果1、從鍵盤輸入表達式串： 10+15*4#輸出： 7

15、02、從鍵盤輸入表達式串：10+*15+輸出： The expression is error!五、提示1、 構(gòu)造算符優(yōu)先關系表如下：+-*/()i#+>><<<><>->><<<><>*>>>><><>/>>>><><>(<<<<<=<)>>>>>>i>>>>>>#<<<<

16、<<=2、 參考嚴蔚敏等編著、清華大學出版社出版的C語言版數(shù)據(jù)結(jié)構(gòu)P52-P54的表達式求值算法。題目五遞歸下降分析法一、設計目的掌握遞歸下降分析法的基本原理，掌握預測符集的求法， 掌握遞歸下降分析程序的構(gòu)造方法。二、設計內(nèi)容假設文法中有如下的產(chǎn)生式Aàb1 | b2 | | bn，則應按如下方法編寫語法分析子程序procedure A() beginif tokenÎPredict(Aàb1) then (b1) else if tokenÎPredict(Aàb2) then (b2) else if tokenÎPr

17、edict(Aàbn) then (bn) else error() end其中對bi =X1X2Xn，(bi) =(X1); (X2); (Xn);l 如果XiÎVN，(Xi)= Xil 如果XiÎVT，(Xi)= Match(Xi) l 如果Xi= e, () = skip(空語句)三、設計要求：理解遞歸下降語法分析方法的主要原理，理解遞歸下降分析法對文法的要求， 熟練掌握Predict集合的求法， 熟練掌握文法變換算法（消除左遞歸和消除公共前綴）。四、提示：1. 基本原理遞歸下降法是語法分析中最易懂的一種方法。它的主要原理是，對每個非終極符按其產(chǎn)生式結(jié)構(gòu)構(gòu)造

18、相應語法分析子程序，其中終極符產(chǎn)生匹配命令，而非終極符則產(chǎn)生過程調(diào)用命令。因為文法遞歸相應子程序也遞歸，所以稱這種方法為遞歸子程序下降法或遞歸下降法。其中子程序的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎是一致的。2. 文法要求遞歸下降法要滿足的條件：假設A的全部產(chǎn)生式為Aà1|2|n ，則必須滿足如下條件才能保證可以唯一的選擇合適的產(chǎn)生式predict(Aài)predict(Aàj)=,當ij.五、實驗步驟1求SNL文法中每個產(chǎn)生式Predict集合Predict(Aà)= First() ，      

19、0;    當eÏFirst()= (First()- e) Follow(A)，當eÎFirst()根據(jù)Predict集合的定義求SNL的文法中每個產(chǎn)生式的Predict集合，判斷是否滿足遞歸下降法分析條件，若不滿足用消除左遞歸和消除公共前綴等文法等價變化算法對文法進行變換，使其滿足遞歸下降法的要求。2. 構(gòu)造遞歸下降語法分析程序采用了遞歸子程序方法進行語法分析,對文法中的每個非終極符號按其產(chǎn)生式結(jié)構(gòu)產(chǎn)生相應的語法分析子程序,完成相應的識別任務。其中終結(jié)符產(chǎn)生匹配命令，非終結(jié)符則產(chǎn)生調(diào)用命令。每次進入子程序之前都預先讀入一個單詞。因為使用了遞

20、歸下降方法,所以程序結(jié)構(gòu)和層次清晰明了,易于手工實現(xiàn),且時空效率較高。實際的語法分析工作,從調(diào)用總程序的分析子程序開始，根據(jù)產(chǎn)生式進行遞歸調(diào)用各個分析子程序。附錄A 部分課程設計題目參考源程序A.1 基于語法制導翻譯的表達式轉(zhuǎn)換編譯器參考源程序/*全局頭文件myglobal.h,用于存放需加載的頭文件、宏定義、全局變量*/#include <stdio.h>#include <string.h>#include <ctype.h> /* 加載字符測試函數(shù)*/#define BUFSIZE 128 /* 定義緩沖區(qū)大小*/#define NONE -1#def

21、ine 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 symtable;/* 定義符號表*/*詞法分析程序lex.c*/#include “global.h”char lexbufBUFSIZE;int lineno=1;int tokenval=NONE;int lex() /*

22、詞法分析函數(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; while(isalnum(t) lexbufb=t;t=getchar();b=b+1;if (b>BUFSIZE) error(“compiler error!”); lexbufb=EOSTR;if (t!=EOF)

23、 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”int lookahead;void parse() lookahead=lex(); while (lookahead!=DONE) express();match(;);void express() int

24、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(lookahead) case *: case /: case DIV: case MOD:t= lookahead;match(lookahead); factor(); emit(t,NONE); continue;de

25、fault: 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(“syntax error”); void match(int t) if (lookahead=t) lookahead=lex();else error(“syntax error”);/*輸出程序emitter.c*

26、/#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”,tval);break; case ID:printf(“%sn”,symtabletval.lexptr);break;default:printf(“token %d, tokenval %dn”,t,tval);

27、/*符號表處理程序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=lastentry;p>0;p-) if (strcmp(symtablep.lexptr,s)=0) return p; return 0;int insert(char *s,int tok) int len; le

28、n=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=&lexemeslastchar+1;lastchar=lastchar+len+1;strcpy(symtablelastentry.lexptr,s);return lastentr

29、y;/*在符號表中填入關鍵字程序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 error( char *m) fprintd(stderr,“l(fā)ine %d: %sn”,lineno,m); exit(1); /*主程序mian.c

30、*/#include “global.h”main() init();parse();exit(0);A.2 說明語句的詞法分析器參考源程序一、說明1、本例中字符和字符串都用“”來識別，引號中只包含一個字符時為字符型常量，否則，為字符串常量；2、本例只起示范性作用，并沒有全面考慮高級語言編譯器對常量說明串中可能出現(xiàn)錯誤的處理方法。2、 實際構(gòu)造本課程設計的常量說明串的詞法分析程序時，建議進行模塊化處理。二、源代碼#include"stdio.h"#include"ctype.h"#define N 80#define M 16main()char *p0

31、,*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);t0=p3;t

32、1=p1;t2=p2;gets(p0);while(*p0!=' ') /* 檢查輸入串是否以“'const”開頭 */if (*p0=*t3) p0+; t3+; else printf("nThis string isn't a const declaration!"); exit(0); while (*p0!='!') /* 開始處理輸入串 p0 */ while (p1<t1+M) *p1='0' p1+; p1=t1; while (p2<t2+M) *p2='0' p2

33、+; p2=t2;if (*(p0-1)=' '|*(p0-1)='') /*從串p0中取標識符，并將其作為常量名存放到串p1中 */ 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!='_'&&

34、amp;!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 (!isdigit(*p0)&&*p0!='"'&&*p0!='.') printf("n Const data

35、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

36、 cs+; printf(" Data:%s ;t Type: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 wro

37、ng. Exit !"); break; while(*p0!=''); p2=t2; cf+; printf(" Data:%s ;t Type: float !n",p2); if (*p0='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+

38、; 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!='0') /* 處理其它整型常量和實型常量*/ p3=t0;p3="int"ci+;do *p2=*p0; p0+; p

39、2+; 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+; /

40、* 輸入串p0處理完 */ printf(" n Total:n tint numbers: %dn tfloat numbers: %d",ci,cf); printf(" n tstring numbers: %dn tchar numbers: %d",cs,cc); printf(" n tbool numbers: %d",cb); /* 輸出各類型常量個數(shù)的統(tǒng)計結(jié)果 */A.3 基于預測分析方法的表達式語法分析器參考源程序#include <stdio.h>#include <string.h>#i

41、nclude <ctype.h>#define max 100#define ERROR 1char stackmax;int top=0;struct production char a; char X;char M5; prod13=/* 將預測分析表的數(shù)據(jù)結(jié)構(gòu)定義為結(jié)構(gòu)體數(shù)組*/'m','S',"AT",'(','S',"AT"), '+','T',"+AT", ')','T',"$",'#','T',"$", 'm','A',"BU", '(','A',"BU"), '+','U',"$",'*','U',"*BU",')'