編譯原理實(shí)驗(yàn)題目

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

2、| term mod factor( expr ) print( print( print( print( * ) / ) div ) mod ) | id| num print( ) print( num.value ) 三、設(shè)計(jì)要求1、使用模塊化設(shè)計(jì)思想來設(shè)計(jì)該編譯器；2、詞法分析模塊用于讀入輸入串，并將其轉(zhuǎn)換成供語法分析模塊使用的記號流。其中包括濾掉空格和注釋、識(shí)別常數(shù)、識(shí)別標(biāo)識(shí)符和關(guān)鍵字等功能；3、要求在語法分析模塊中利用語法制導(dǎo)翻譯技術(shù)完成具體的中綴表達(dá)式到后綴表達(dá)式的翻譯，其中包括按前述翻譯器的規(guī)格說明構(gòu)建對應(yīng)表達(dá)式、項(xiàng)、因子的非終結(jié)符expr、 term和 fac

3、tor 的函數(shù)以及檢查記號是否匹配的函數(shù)；并在不匹配時(shí)調(diào)用錯(cuò)誤處理模塊；4、要求符號表管理模塊主要完成符號表對應(yīng)數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)功能；5、錯(cuò)誤處理模塊負(fù)責(zé)報(bào)告錯(cuò)誤信息及位置，并終止分析過程；6、輸出模塊完成翻譯后所得到的后綴表達(dá)式的輸出。四、運(yùn)行結(jié)果1、從鍵盤輸入任意中綴表達(dá)式，如：4 - 5 * 6 div 4 + 8 mod 2輸出相應(yīng)的后綴表達(dá)式：456*4div-82mod+1、 若鍵盤輸入串為非中綴表達(dá)式時(shí)，如：4 !+* 5 - 6 div 4 + 8 mod 2輸出相應(yīng)語法錯(cuò)誤報(bào)告信息，并停止語法分析，如：line 1 : compiler error !五、提示1、將各功能模

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

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

6、識(shí)符，定義為字母開頭，后跟若干個(gè)字母，數(shù)字或下劃線；4、根據(jù)各常量名緊跟等號“=”后面的內(nèi)容判斷常量的類型。其中：字符型常量定義為放在單引號內(nèi)的一個(gè)字符；字符串常量定義為放在雙引號內(nèi)所有內(nèi)容；整型常量定義為帶或不帶 +、-號，不以 0 開頭的若干數(shù)字的組合；實(shí)型常量定義為帶或不帶+、-號，不以 0 開頭的若干數(shù)字加上小數(shù)點(diǎn)再后跟若干數(shù)字的組合；5、統(tǒng)計(jì)并輸出串或文件中包含的各種類型的常量個(gè)數(shù)；6、以二元組 ( 類型 , 值 ) 的形式輸出各常量的類型和值；7 、根據(jù)常量說明串置于高級語言源程序中時(shí)可能出現(xiàn)的錯(cuò)誤情況，模仿高級語言編譯器對不同錯(cuò)誤情況做出相應(yīng)處理。四、運(yùn)行結(jié)果1、輸入如下正確的常

7、量說明串：constcount=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 錯(cuò)誤的常量說明串：ac

8、onstt count=10,sum=81.5,char1= f ;輸出類似下面的錯(cuò)誤提示信息：it is not a constant declaration statement!please input a string again!3、輸入類似如下含常量名或常量值錯(cuò)誤的常量說明串：const count=10,12sum=81.5,char1= ff ,max=0016 ；輸出類似下面的錯(cuò)誤提示信息：count(integer,10)12sum(wrong! it is not a identifier!)char1(wrong! there are more than one char

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

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

12、-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è)計(jì)重點(diǎn)有兩個(gè)：一是如何用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)預(yù)測分析表存儲(chǔ)和使用；二是如何實(shí)現(xiàn)各規(guī)則右部串的逆序入棧處理。建議：使用結(jié)構(gòu)體數(shù)組。六、分析與討論1、若輸入串不是指定文法的句子，會(huì)出現(xiàn)什么情況？2、總結(jié)預(yù)測語法分析程序的設(shè)計(jì)和實(shí)現(xiàn)的一般方法。題目四基于算符優(yōu)先分析方法的表達(dá)式語法分析器一、設(shè)計(jì)目的了解用算符優(yōu)先法對表達(dá)進(jìn)

13、行語法分析的方法，編程實(shí)現(xiàn)算符優(yōu)先表達(dá)式語法分析器。二、設(shè)計(jì)內(nèi)容對簡單表達(dá)式文法構(gòu)造算符優(yōu)先分析器。三、設(shè)計(jì)要求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)來實(shí)現(xiàn)算符優(yōu)先分析：設(shè)置兩個(gè)棧： 存放運(yùn)算符的optr棧和存放操作數(shù)或運(yùn)算結(jié)果的opnd棧。具體算法描述如下：（ 1）首先置操作數(shù)opnd棧為空棧，將 #入運(yùn)算符optr棧。（ 2）依次讀入表達(dá)式中每個(gè)單詞，若是操作數(shù)則進(jìn)opnd棧，若是運(yùn)算符則轉(zhuǎn)（3）。（ 3）當(dāng)前設(shè)讀入的運(yùn)算符為 2，查找算符優(yōu)先關(guān)系表

14、，比較 2 與 optr棧頂元素 1 ：若 1-*/(=i#=2、 參考嚴(yán)蔚敏等編著、清華大學(xué)出版社出版的c 語言版數(shù)據(jù)結(jié)構(gòu) p52-p54 的表達(dá)式求值算法。題目五遞歸下降分析法一、設(shè)計(jì)目的掌握遞歸下降分析法的基本原理， 掌握預(yù)測符集的求法， 掌握遞歸下降分析程序的構(gòu)造方法。二、設(shè)計(jì)內(nèi)容假設(shè)文法中有如下的產(chǎn)生式a1 | 2 | |n，則應(yīng)按如下方法編寫語法分析子程序procedure a()beginif tokenpredict(a) then(11) elseif tokenpredict(a2) then(2) elseif tokenpredict(an) then(n) elsee

15、rror()end其中對 i =x 1x 2xn， (i) = 1);(x 2);(x ; n); (x如果 x iv n， (xi)= x i如果 x i， (xv ti )= match(x i)如果 x i=, ( ) = 空skip(語句 )三、設(shè)計(jì)要求：理解遞歸下降語法分析方法的主要原理，理解遞歸下降分析法對文法的要求，predict 集合的求法，熟練掌握文法變換算法（消除左遞歸和消除公共前綴）。熟練掌握四、提示：1. 基本原理遞歸下降法是語法分析中最易懂的一種方法。它的主要原理是，對每個(gè)非終極符按其產(chǎn)生式結(jié)構(gòu)構(gòu)造相應(yīng)語法分析子程序，其中終極符產(chǎn)生匹配命令，而非終極符則產(chǎn)生過程調(diào)用命

16、令。因?yàn)槲姆ㄟf歸相應(yīng)子程序也遞歸，所以稱這種方法為遞歸子程序下降法或遞歸下降法。其中子程序的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎是一致的。2. 文法要求遞歸下降法要滿足的條件：假設(shè)a 的全部產(chǎn)生式為a 1| 2| | n ，則必須滿足如下條件才能保證可以唯一的選擇合適的產(chǎn)生式predict(ai) predict(aj)= ,當(dāng) i j.五、實(shí)驗(yàn)步驟1求 snl 文法中每個(gè)產(chǎn)生式predict 集合predict(a)= first(，)當(dāng)first()= ( first(-) follow(a) ，當(dāng)first()根據(jù) predict 集合的定義求snl 的文法中每個(gè)產(chǎn)生式的predict 集合，判斷是否滿

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

18、編譯器參考源程序/*全局頭文件myglobal.h,用于存放需加載的頭文件、宏定義、全局變量*/#include #include #include /*加載字符測試函數(shù)*/#define bufsize 128 /*#define none -1#define eostr0 定義緩沖區(qū)大小*/#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

19、token;struct table 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 (isalp

20、ha(t)int p,b=0;while(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;elsetokenval=none;return t;/* 語法分析程序 paserx.c*/ #incl

21、ude “ global.h ”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(looka

22、head)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(“ syntax er

23、ror”);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” ,tval);

24、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=last

25、entry;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(“ lexemes array full” );lastentry=lastentry+1;symtablelastentry.token=tok;symtablelastentry.lexptr=&lexem

26、eslastchar+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);/*錯(cuò)誤處理程序error.c*/#include“ global.h

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

28、tdio.h#includectype.h#definen 80#definem 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(ch

29、ar);t0=p3;t1=p1;t2=p2;gets(p0);while(*p0!= )/*檢查輸入串是否以“const”開頭*/if (*p0=*t3)p0+;t3+;elseprintf(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)識(shí)符，并將其作為常量名存放到串 p1 中 */if (*

30、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 (!isdigit(*p0)&*p0!=&*p

31、0!=.)printf(n const data is wrong . exit !);break;else if (*p0=)/* 處理字符和字符串常量*/do*p2=*p0;p0+;p2+;while(*p0!=;);if (*(p0-1)!=) printf(n stringdata is wrong. exit !);break;p2=t2;if (strlen(p2)=3)cc+;printf( data:%s ;t type:char !n,p2);elsecs+;printf( data:%s ;t type:string !n,p2);if (*p0=.)/*處理由點(diǎn)號開頭的實(shí)

32、數(shù)*/if (*(p0+1)=;) printf(n floatdata is wrong. exit !);break;else if (isdigit(*(p0+1)do*p2=*p0;p0+;p2+;if (!isdigit(*p0)&*p0!=;) printf(n floatdata is wrong. exit !);break;while(*p0!=;);p2=t2;cf+;printf( data:%s ;t type: float !n,p2);if (*p0=0)/* 處理整數(shù)0 或由 0 作整數(shù)部分的實(shí)型常量*/*p2=*p0;p0+;p2+;if (*p0=;)ci+;

33、printf( data:%c ;t type:int !n,*(p2-1);else if (*p0=.)do*p2=*p0;p0+;p2+;if (!isdigit(*p0)&*p0!=;) printf(n floatdata is wrong. exit !);break;while(*p0!=;);p2=t2;cf+;printf( data:%s ;t type:float !n,p2);if (isdigit(*p0)&(*p0!=0)/*處理其它整型常量和實(shí)型常量*/ p3=t0; p3=int; ci+;do*p2=*p0;p0+;p2+;if (!isdigit(*p0)&*p0!=;&*p0!=.) printf(n intdata 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 處理完 */ elsep0+; /*輸入串 p0 處理完*/printf( ntotal:n tintnumbers: %dn tflo