編譯原理實驗報告

1、編譯原理實驗報告軟件131 陳萬全 一、 需求分析通過對一個常用高級程序設(shè)計語言的簡單語言子集編譯系統(tǒng)中詞法分析、語法分析、語義處理模塊的設(shè)計、開發(fā)，掌握實際編譯系統(tǒng)的核心結(jié)構(gòu)、工作流程及其實現(xiàn)技術(shù)，獲得分析、設(shè)計、實現(xiàn)編譯程序等方面的實際操作能力，增強(qiáng)設(shè)計、編寫和調(diào)試程序的能力。通過開源編譯器分析、編譯過程可視化等擴(kuò)展實驗，促進(jìn)學(xué)生增強(qiáng)復(fù)雜系統(tǒng)分析、設(shè)計和實現(xiàn)能力，鼓勵學(xué)生創(chuàng)新意識和能力。實驗項目實 驗 內(nèi) 容1、詞法分析程序設(shè)計與實現(xiàn)構(gòu)造具有關(guān)鍵字、運(yùn)算符、標(biāo)識符、無符號常數(shù)等單詞的詞法分析程序。輸入由符合及不符合規(guī)定單詞類別結(jié)構(gòu)的各類單詞組成的源程序。輸出單詞串的二元式編碼（CLASS，

2、VALUE）。2、語法分析程序設(shè)計與實現(xiàn)將詞法分析程序輸出的單詞串作為輸入，針對常見的表達(dá)式、賦值語句、條件語句、循環(huán)語句等語法成分，選擇有代表性的語法分析方法，如遞歸下降法、算符優(yōu)先分析、LL(1)、LR等方法之一，設(shè)計實現(xiàn)相應(yīng)的語法分析程序。3、語義分析程序設(shè)計與實現(xiàn)對各語法單位增加語義子程序，將表達(dá)式或可執(zhí)行語句翻譯為四元式序列輸出，并能進(jìn)行錯誤檢查與處理，將錯誤信息輸出。1、 詞法分析程序設(shè)計與實現(xiàn)假定一種高級程序設(shè)計語言中的單詞主要包括五個關(guān)鍵字begin、end、if、then、else；標(biāo)識符；無符號常數(shù)；六種關(guān)系運(yùn)算符；一個賦值符和四個算術(shù)運(yùn)算符，試構(gòu)造能識別這些單詞的詞法分析

3、程序。輸入：由符合和不符合所規(guī)定的單詞類別結(jié)構(gòu)的各類單詞組成的源程序文件。輸出：把所識別出的每一單詞均按形如（CLASS，VALUE）的二元式形式輸出，并將結(jié)果放到某個文件中。對于標(biāo)識符和無符號常數(shù)，CLASS字段為相應(yīng)的類別碼的助記符；VALUE字段則是該標(biāo)識符、常數(shù)的具體值；對于關(guān)鍵字和運(yùn)算符，采用一詞一類的編碼形式，僅需在二元式的CLASS字段上放置相應(yīng)單詞的類別碼的助記符，VALUE字段則為“空”。2、 語法分析程序設(shè)計與實現(xiàn)選擇對各種常見高級程序設(shè)計語言都較為通用的語法結(jié)構(gòu)算術(shù)表達(dá)式的一個簡化子集作為分析對象，根據(jù)如下描述其語法結(jié)構(gòu)的BNF定義G2，任選一種學(xué)過的語法分析方法，針對運(yùn)

4、算對象為無符號常數(shù)和變量的四則運(yùn)算，設(shè)計并實現(xiàn)一個語法分析程序。G2： | + | - | * | / | ()若將語法范疇、和分別用E、T、F和i代表，則G2可寫成：G2E：E T | E+T | E-T T F | T*F | T/F F i | (E)輸入：由實驗一輸出的單詞串，例如：UCON，PL，UCON，MU，ID 輸出：若輸入源程序中的符號串是給定文法的句子，則輸出“RIGHT”，并且給出每一步分析過程；若不是句子，即輸入串有錯誤，則輸出“ERROR”，并且顯示分析至此所得的中間結(jié)果，如分析棧、符號棧中的信息等，以及必要的出錯說明信息。3、語義分析程序設(shè)計與實現(xiàn)對文法G2中的產(chǎn)生

5、式添加語義處理子程序，完成運(yùn)算對象是簡單變量（標(biāo)識符）和無符號數(shù)的四則運(yùn)算的計值處理，將輸入的四則運(yùn)算轉(zhuǎn)換為四元式形式的中間代碼。輸入：包含測試用例（由標(biāo)識符、無符號數(shù)和+、*、/、(、)構(gòu)成的算術(shù)表達(dá)式）的源程序文件。輸出：將源程序轉(zhuǎn)換為中間代碼形式表示，并將中間代碼序列輸出到文件中。若源程序中有錯誤，應(yīng)指出錯誤信息2、 設(shè)計思路1、 詞法分析程序設(shè)計與實現(xiàn)1)單詞分類為了編程的實現(xiàn)。我們假定要編譯的語言中，全部關(guān)鍵字都是保留字，程序員不得將它們作為源程序中的標(biāo)識符；作了這些限制以后，就可以把關(guān)鍵字和標(biāo)識符的識別統(tǒng)一進(jìn)行處理。即每當(dāng)開始識別一個單詞時，若掃視到的第一個字符為字母，則把后續(xù)輸入

6、的字母或數(shù)字字符依次進(jìn)行拼接，直至掃視到非字母、數(shù)字字符為止，以期獲得一個盡可能長的字母數(shù)字字符串，然后以此字符串查所謂保留字表（此保留字表要事先造好），若查到此字符串，則取出相應(yīng)的類別碼；反之，則表明該字符串應(yīng)為一標(biāo)識符。表1 語言中的各類單詞符號及其分類碼表單詞符號類別編碼類別碼的助記符單詞值begin1BEGINend2ENDif3IFthen4THENelse5ELSE標(biāo)識符6ID字母打頭的字母數(shù)字串無符號常數(shù)7UCON機(jī)內(nèi)二進(jìn)制表示8LT=9LE=10EQ11NE12GT=13GE:=14IS+15PL-16MI*17MU/18DI2） 詞法分析器的設(shè)計函數(shù)GETCHAR：每調(diào)用一次

7、，就把掃描指示器當(dāng)前所指示的源程序字符送入字符變量ch，然后把掃描指示器前推一個字符位置。字符數(shù)組TOKEN：用來依次存放一個單詞詞文中的各個字符。函數(shù)CAT：每調(diào)用一次，就把當(dāng)前ch中的字符拼接于TOKEN中所存字符串的右邊。函數(shù)LOOKUP：每調(diào)用一次，就以TOKEN中的字符串查保留字表，若查到，就將相應(yīng)關(guān)鍵字的類別碼賦給整型變量c；否則將c置為零。函數(shù)RETRACT：每調(diào)用一次，就把掃描指示器回退一個字符位置（即退回多讀的那個字符）。函數(shù)OUT：一般僅在進(jìn)入終態(tài)時調(diào)用此函數(shù)，調(diào)用的形式為OUT(c，VAL)。圖1 識別表I所列語言中的部分單詞的DFA及相關(guān)的語義過程3）詞法分析程序的實現(xiàn)

8、編寫的掃描器:char TOKEN20,TOKEND20,TOKENDO20;int lookup (char*);void out (int, char*);void report_error (void);/extern void LEX(void);int siagn=0;/標(biāo)志位FILE *fp1; char *KeyWordTableMAX_KEY_NUMBER=begin,end, if, then, else, KEY_WORD_END;/* 查保留字表，判斷是否為關(guān)鍵字 */int lookup (char *token)int n=0;while (strcmp(KeyWor

9、dTablen, KEY_WORD_END) /*strcmp比較兩串是否相同，若相同返回0*/if (!strcmp(KeyWordTablen, token) /*比較token所指向的關(guān)鍵字和保留字表中哪個關(guān)鍵字相符*/return n+1; /*根據(jù)單詞分類碼表I，設(shè)置正確的關(guān)鍵字類別碼，并返回此類別碼的值*/break;n+;return 0;void scanner_example (FILE *fp)char ch; int i, c, isd,cpoint; double o;ch=fgetc (fp);/fgetc函數(shù) 在文件中讀取一個字符if (isalpha (ch) /

10、*it must be a identifer! 它必須是一個標(biāo)識符 判斷字符ch是否為英文字母，若為小寫字母，返回2，若為大寫字母，返回1。若不是字母，返回0*/TOKEN0=ch; ch=fgetc(fp); i=1;while (isalnum (ch)|ch=.)/isalnum函數(shù) 判斷ch是否為空 當(dāng)ch為數(shù)字0-9或字母a-z及A-Z時，返回非零值，否則返回零if(ch=.)cpoint=-1;/標(biāo)志字符串中有小數(shù)點(diǎn)TOKENi=ch; i+;ch=fgetc (fp);TOKENi= 0;if(ch=|ch=|ch=:) fseek (fp,-2,1);siagn=1;else

11、 fseek (fp,-1,1);/fseek(fp,-1,1); /* retract fseek函數(shù) 每調(diào)用一次，就把掃描指示器回退一個字符位置（即退回多讀的那個字符）*/i=0;if(TOKENi=o|TOKENi=O)i+;if(TOKENi=x|TOKENi=X)i+;while(TOKENi!=0)if(!isdigit(TOKENi)|TOKENi!=a|TOKENi!=b|TOKENi!=c|TOKENi!=d|TOKENi!=e|TOKENi!=f|TOKENi!=A|TOKENi!=B|TOKENi!=C|TOKENi!=D|TOKENi!=E|TOKENi!=F|TOKE

12、Ni!=.)isd=-1;isd=16;/標(biāo)志字符串十六進(jìn)制i+;else if(TOKENi=0|TOKENi=1|TOKENi=2|TOKENi=3|TOKENi=4|TOKENi=5|TOKENi=6|TOKENi=7|TOKENi=.)isd=8;/標(biāo)志字符串八進(jìn)制i+;while(TOKENi!=0)if(TOKENi!=0|TOKENi!=1|TOKENi!=2|TOKENi!=3|TOKENi!=4|TOKENi!=5|TOKENi!=6|TOKENi!=7|TOKENi!=.)isd=-1;isd=8;i+;if(isd=8)strncpy(TOKEND,TOKEN+1,str

13、len(TOKEN)-1);/拷貝函數(shù)/printf(%o,atof(TOKEND);o=octal(TOKEND);/printf(%g,o);sprintf(TOKENDO, %g,octal(TOKEND);out(OCTAL,TOKENDO);else if(isd=16)strncpy(TOKEND,TOKEN+2,strlen(TOKEN)-2);/拷貝函數(shù)o=octal(TOKEND);/printf(%g,o);sprintf(TOKENDO, %g,hex(TOKEND);out(HEX,TOKENDO);elseif(cpoint=-1)report_error();/當(dāng)字

14、符串中有小數(shù)點(diǎn)時，為錯誤elsec=lookup (TOKEN);/looup查詢函數(shù) 查找保留字if (c=0) out (ID,TOKEN); else out (c, );/out函數(shù) 輸出功能elseif(isdigit(ch)/isdigit函數(shù) 檢查參數(shù)c是否為阿拉伯?dāng)?shù)字0到9。/*TOKEN0=ch; ch=fgetc(fp); i=1;while(isdigit(ch)|ch=-|ch=E|ch=e|ch=.)TOKENi=ch; i+;ch=fgetc(fp);TOKENi= 0;*/int Class;fseek (fp,-1,1);Class=LEX(fp);if(Cla

15、ss=1)char pi30 = ;itoa(ICON,pi,10);out(INT,pi);else if(Class=2)char pd30 = ;sprintf(pd, %g,FCON);out(DOUBLE,pd);elsereport_error( );/fseek(fp,-1,1);if(chf=|chf=|chf=:|chf=+|chf=-|chf=*|chf=/) fseek (fp,-2,1);siagn=1;else fseek (fp,-1,1);siagn=1;elseswitch(ch)case ) ch=fgetc(fp);if(isalnum (ch) fseek

16、 (fp,-2,1);else fseek (fp,-1,1);siagn=1;out (NE, );elsech=fgetc(fp);if(isalnum (ch) fseek (fp,-2,1);else fseek (fp,-1,1);siagn=1;out (LT, );break;case =:ch=fgetc(fp);if(isalnum (ch) fseek (fp,-2,1);else fseek (fp,-1,1);siagn=1;out(EQ, );break;case : ch=fgetc(fp);if(ch=)ch=fgetc(fp);if(isalnum (ch) f

17、seek (fp,-2,1);else fseek (fp,-1,1); siagn=1;out(GE, );elsech=fgetc(fp);if(isalnum (ch) fseek (fp,-2,1);else fseek (fp,-1,1);siagn=1;out(GT, );break;case :ch=fgetc(fp);if(ch=)ch=fgetc(fp);if(isalnum (ch) fseek (fp,-2,1);else fseek (fp,-1,1);siagn=1;out(IS, );else report_error();break;case+:ch=fgetc(

18、fp);if(isalnum (ch) fseek (fp,-2,1); else fseek (fp,-1,1);siagn=1;out(PL, ); break;case-:ch=fgetc(fp);if(isalnum (ch) fseek (fp,-2,1);else fseek (fp,-1,1);siagn=1;out(MI, ); break;case*:ch=fgetc(fp);if(isalnum (ch) fseek (fp,-2,1);else fseek (fp,-1,1);siagn=1;out(MU, ); break;case/:ch=fgetc(fp);if(i

19、salnum (ch) fseek (fp,-2,1);else fseek (fp,-1,1);siagn=1;out(DI, ); break;case :break;/當(dāng)遇到空格時繼續(xù)向下走default: report_error( ); break;/report_error函數(shù) 單詞錯誤時輸出的內(nèi)容if(ch= |siagn=1)fseek(fp,1,1); siagn=0;scanner_example(fp);if(ch=EOF)return;/ return;void report_error()printf(errorn);void out(int c, char *vp)

20、char* cl = NULL;switch (c)case 1:cl = BEGIN; break;case 2:cl = END; break;case 3:cl = IF; break;case 4:cl = THEN; break;case 5:cl = ELSE; break;case 6:cl = ID; break;case 7:cl = UCON; break;case 8:cl = LT; break;case 9:cl = LE; break;case 10: cl = EQ; break;case 11: cl = NE; break;case 12: cl = GT;

21、break;case 13: cl = GE; break;case 14: cl = IS; break;case 15: cl = PL; break;case 16: cl = MI; break;case 17: cl = MU; break;case 18: cl = DI; break;case 19: cl = UCON; break;case 20: cl = DOUBLE; break;case 21: cl = OCTAL; break;case 22: cl = HEX; break;printf(e(%s,%s)n,cl, vp);fprintf(fp1,e(%s,%s

22、)n,cl, vp);fseek(fp1,0,1); void main()char *fname=test1.txt;/讀取為文件fp FILE *fp;if(fp1=fopen(asd.txt,w)=NULL) /*建立文件 寫入文件的文件fp1*/ printf(nopen file error); getchar(); exit(1); if(fp=fopen(fname,r)=NULL)printf(nSorry, Cant open the file!n);getchar();exit(0); else scanner_example(fp); fclose(fp);fclose(

23、fp1);本程序從文件test1.txt中讀入要分析的單詞并把掃描的結(jié)果輸入asd.txt文件中；利用gechar（）方法從文件中一個個讀入字符，并采用遞歸的方法對字符多次讀入直到讀到文件的結(jié)尾停止。字符讀入程序后采用圖一的方法進(jìn)行分析解決。4)無符號常數(shù)的識別針對掃描程序所得到的數(shù)字我們可以進(jìn)行無符號數(shù)的處理。加入了語義過程說明的識別無符號數(shù)的狀態(tài)矩陣，編寫詞法分析程序，部分實現(xiàn)代碼如程序二所示。表2 包含語義處理過程的識別無符號數(shù)的狀態(tài)矩陣程序2 單詞分類碼為UCON的無符號數(shù)的識別程序7 假定無符號常量的類數(shù)為7#define ClassOther 200#define EndState

24、 -1int w,n,p,e,d;int Class=-1; /Used to indicate class of the word 用于表示單詞的類型 1位int 2為double int ICON;double FCON;static int CurrentState; /Used to present current state, the initial value:0 用于當(dāng)前狀態(tài)，初始值：0int GetChar (FILE *p);int EXCUTE (int,int);int LEX (FILE *p);int HandleOtherWord (void)return Clas

25、sOther;int HandleError (void)printf (Error!n); return 0;int GetChar (FILE *p) chf=fgetc(p); if(isdigit(chf) d=chf-0;return DIGIT; if (chf=.) return POINT; if (chf=E|chf=e) return POWER; if (chf=+) return PLUS; if (chf=-) return MINUS; return OTHER;int EXCUTE (int state, int symbol) switch (state) ca

26、se 0:switch (symbol) case DIGIT: n=0;p=0;e=1;w=d;CurrentState=1;break; case POINT: w=0;n=0;p=0;e=1;CurrentState=3;break; default: HandleOtherWord( );Class=ClassOther; CurrentState=EndState; break; case 1:switch (symbol) case DIGIT: w=w*10+d;break; /CurrentState=1 case POINT: CurrentState=2;break; ca

27、se POWER: CurrentState=4;break; default: ICON=w;Class=1;CurrentState=EndState; break; case 2:switch (symbol) case DIGIT: n+;w=w*10+d;break; case POWER: CurrentState=4;break; default: FCON=w*pow(10,e*p-n);Class=2;CurrentState=EndState; break; case 3:switch (symbol) case DIGIT: n+;w=w*10+d;CurrentStat

28、e=2;break; default: HandleError( );CurrentState=EndState; break; case 4:switch (symbol) case DIGIT: p=p*10+d;CurrentState=6;break; case MINUS: e=-1;CurrentState=5;break; case PLUS: CurrentState=5;break; default: HandleError( );CurrentState=EndState; break; case 5:switch (symbol) case DIGIT: p=p*10+d

29、;CurrentState=6;break; default: HandleError( );CurrentState=EndState; break; case 6:switch (symbol) case DIGIT:p=p*10+d;break; default: FCON=w*pow(10,e*p-n);Class=2;CurrentState=EndState; break; return CurrentState; int LEX (FILE *p) int ch; CurrentState=0; while (CurrentState!=EndState)ch=GetChar(p

30、);EXCUTE (CurrentState,ch); return Class; 5)八進(jìn)制與十六進(jìn)制數(shù)的處理在無符號數(shù)的處理過程中沒有設(shè)計八進(jìn)制與十六進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制的數(shù)，但為了方面以后的使用我們進(jìn)入進(jìn)制的轉(zhuǎn)換。設(shè)計思路：判斷八進(jìn)制是以0開頭，十六進(jìn)制為0X開頭，并且判斷后面所跟數(shù)字是否超出八進(jìn)制或十六進(jìn)制的范圍，若超出則錯誤，如不超出則用8或16轉(zhuǎn)換為相應(yīng)十進(jìn)制數(shù)字再次讀入寫個字符循環(huán)，直到數(shù)字結(jié)束。程序3 單詞分類碼為八進(jìn)制的無符號數(shù)的識別程序double octal(char *TP)int x,y=-1,ypoint=0;/計數(shù) ypoint=-1記錄有小數(shù)點(diǎn) y記錄是第幾位小數(shù)

31、int m=0;double FINALL=0.0;/放結(jié)果while(*TP!=0)if(*TP=.)ypoint=-1;elsex=*TP-0;if(ypoint!=-1)FINALL=FINALL*8+x;if(ypoint=-1)FINALL=FINALL+x*pow(8,y);y-;TP+;return FINALL;程序4 單詞分類碼為十六進(jìn)制的無符號數(shù)的識別程序double hex(char *TP)int x,y=-1,ypoint=0;/計數(shù) ypoint=-1記錄有小數(shù)點(diǎn) y記錄是第幾位小數(shù)int m=0;double FINALL=0.0;/放結(jié)果while(*TP!=0

32、)if(*TP=.)ypoint=-1;elseif(ypoint!=-1)if(*TP=0&*TP=a&*TP=A&*TP=0&*TP=a&*TP=A&*TP=F)x=*TP-a+1;FINALL=FINALL+x*pow(16,y);y-;TP+;return FINALL;2、語法分析程序設(shè)計與實現(xiàn)語法分析，采用的是算符優(yōu)先文法實現(xiàn)；重點(diǎn)與難點(diǎn)為根據(jù)文法求出FirstVt與LastVt集合，構(gòu)造出算符表。語法分析程序的輸入結(jié)構(gòu)為詞法分析的輸出結(jié)果。數(shù)字的標(biāo)志位都設(shè)為i 如（i，25.8）；運(yùn)算符的標(biāo)志位為其本身如（+， ）其他符號暫不計算，以方便語法分析程序的編寫。算符優(yōu)先總流程圖 圖2

33、1） 判斷是否為算符文法程序5/judge1是判斷是否是算符文法：若產(chǎn)生式中含有兩個相繼的非終結(jié)符則不是算符文法int judge1(int n)int j=3,flag=0;for(int i=0;i=n;i+)while(strij!=0)char a=strij;char b=strij+1;if(IsLetter(a)&IsLetter(b)flag=1;break;else j+; if(flag=1)return 0; elsereturn 1;結(jié)果：輸入文件輸入結(jié)果2） 判斷是否為算符優(yōu)先文法程序5judge2是判斷文法G是否為算符優(yōu)先文法：若不是算符文法或若文法中含空字或終結(jié)符

34、的優(yōu)先級不唯一則不是算符優(yōu)先文法void judge2(int n)for(int i=0;i=n;i+)if(stri3=|judge1(n)=0|FLAG=1)/代表空字cout該文法不是算符優(yōu)先文法!n)cout該文法是算符優(yōu)先文法!endl; 3） 求FristVt( )和LastVt（）集合程序6 /createF函數(shù)是用F數(shù)組存放每個終結(jié)符與非終結(jié)符和組合，并且值每隊的標(biāo)志位為0;F數(shù)組是一個結(jié)構(gòu)體void createF(int n)int k=0,i=1;char g;char t10;/t數(shù)組用來存放非終結(jié)符t0=str00;while(i=n) if(tk!=stri0)

35、k+;tk=stri0;g=tk;i+; else i+;kk=0; char c;for(i=0;i=n;i+) int j=3; while(strij!=0) c=strij; if(IsLetter(c)=0) if(!search1(r,kk,c) rkk=c;kk+;/r數(shù)組用來存放終結(jié)符 j+; m=0;for(i=0;ik;i+) for(int j=0;jkk-1;j+) Fm.R=ti; Fm.r=rj; Fm.flag=0; m+; /search函數(shù)是將在F數(shù)組中尋找到的終結(jié)符與非終結(jié)符對的標(biāo)志位值為1void search(charLode w)for(int i=0

36、;im;i+) if(Fi.R=w.E&Fi.r=w.e) Fi.flag=1;break;void FirstVT(int n)/求FirstVTcharstack sta;charLode w;int i=0;Initstack(sta);while(i=n) int k=3; w.E=stri0; char a=strik; char b=strik+1; if(!IsLetter(a)/產(chǎn)生式的后選式的第一個字符就是終結(jié)符的情況 w.e=a; push(sta,w); search(w); i+; else if(IsLetter(a)&b!=0&!IsLetter(b)/產(chǎn)生式的后選

37、式的第一個字符是非終結(jié)符的情況 w.e=b; push(sta,w); search(w); i+; else i+;charLode ww;while(!IsEmpty(sta) pop(sta,ww); for(i=0;i=n;i+) w.E=stri0; if(stri3=ww.E&stri4=0) w.e=ww.e; push(sta,w); search(w); break; p=0;int k=1;i=1;while(im) if(Fi-1.flag=1) arrp0=Fi-1.R; arrpk=Fi-1.r; while(Fi.flag=0&im) i+; if(Fi.flag=

38、1) if(Fi.R=arrp0) k+; else arrpk+1=0;p+;k=1; i+; void LastVT(int n)/求LastVTcharstack sta;charLode w;for(int i=0;im;i+) Fi.flag=0;i=0;Initstack(sta);while(i=n) int k=strlen(stri); w.E=stri0; char a=strik-1; char b=strik-2; if(!IsLetter(a) w.e=a; push(sta,w); search(w); i+; else if(IsLetter(a)&!IsLett

39、er(b) w.e=b; push(sta,w); search(w); i+; else i+;charLode ee;while(!IsEmpty(sta) pop(sta,ee); for(i=0;i=n;i+) w.E=stri0; if(stri3=ee.E&stri4=0) w.e=ee.e; push(sta,w); search(w); int k=1;i=1;ppp=0;while(im) if(Fi-1.flag=1) brrppp0=Fi-1.R; brrpppk=Fi-1.r; while(Fi.flag=0&im) i+; if(Fi.flag=1) if(Fi.R=arrppp0) k+; else brrpppk+1=0