華科編譯原理實驗報告

1、洋中科技大善課程實驗報告課程名稱:編譯原理計算機科學(xué)與技術(shù)學(xué)院實驗一詞法分析程序?qū)崿F(xiàn)一、實驗?zāi)康呐c要求通過編寫和調(diào)試一個詞法分析程序，掌握在對程序設(shè)計語言的源程序進行掃描的過程 中，將字符形式的源程序流轉(zhuǎn)化為一個由各類單詞符號組成的流的詞法分析方法。 二、實驗內(nèi)容根據(jù)教學(xué)要求并結(jié)合學(xué)生自己的興趣和具體情況， 從具有代表性的高級程序設(shè)計語言的 各類典型單詞中，選取一個適當大小的子集。 例如，可以完成無符號常數(shù)這一類典型單詞的 識別后，再完成一個盡可能兼顧到各種常數(shù)、 關(guān)鍵字、標識符和各種運算符的掃描器的設(shè)計 和實現(xiàn)。輸入：由符合或不符合所規(guī)定的單詞類別結(jié)構(gòu)的各類單詞組成的源程序。輸出：把單詞的字

2、符形式的表示翻譯成編譯器的內(nèi)部表示，即確定單詞串的輸出形式。例如，所輸出的每一單詞均按形如（ CLASS, VALUE ）的二元式編碼。對于變量和常數(shù)， CLASS字段為相應(yīng)白類別碼；VALUE字段則是該標識符、常數(shù)的具體值或在其符號表中登 記項的序號（要求在變量名表登記項中存放該標識符的字符串；常數(shù)表登記項中則存放該常數(shù)的二進制形式）。對于關(guān)鍵字和運算符，采用一詞一類的編碼形式；由于采用一詞一類的編碼方式，所以僅需在二元式的CLASS字段上放置相應(yīng)的單詞的類別碼，VALUE字段則為“空”。另外，為便于查看由詞法分析程序所輸出的單詞串，要求在 CLASS字段上放置 單詞類別的助記符。三、實現(xiàn)方

3、法與環(huán)境詞法分析是編譯程序的第一個處理階段，可以通過兩種途徑來構(gòu)造詞法分析程序。其一是根據(jù)對語言中各類單詞的某種描述或定義（如BNF）,用手工的方式（例如可用 C語言）構(gòu)造詞法分析程序。 一般地，可以根據(jù)文法或狀態(tài)轉(zhuǎn)換圖構(gòu)造相應(yīng)的狀態(tài)矩陣，該狀態(tài)矩陣同控制程序便組成了編譯器的詞法分析程序；也可以根據(jù)文法或狀態(tài)轉(zhuǎn)換圖直接編寫詞法分析程序。構(gòu)造詞法分析程序的另外一種途徑是所謂的詞法分析程序的自動生成，即首先用正規(guī)式對語言中的各類單詞符號進行詞型描述，并分別指出在識別單詞時，詞法分析程序所應(yīng)進行的語義處理工作，然后由一個所謂詞法分析程序的構(gòu)造程序?qū)ι鲜鲂畔⑦M行加工。如美國BELL實驗室研制的LEX就

4、是一個被廣泛使用的詞法分析程序的自動生成工具。總的來說，開發(fā)一種新語言時，由于它的單詞符號在不停地修改，采用 LEX等工具生 成的詞法分析程序比較易于修改和維護。一旦一種語言確定了， 則采用手工編寫詞法分析程序效率更高。四、實驗設(shè)計1）題目1:試用手工編碼方式構(gòu)造識別以下給定單詞的某一語言的詞法分析程序。語言中具有的單詞包括五個有代表性的關(guān)鍵字begin、end、if、then、else；標識符；整型常數(shù)；六種關(guān)系運算符；一個賦值符和四個算術(shù)運算符。參考實現(xiàn)方法簡述如下。單詞的分類：構(gòu)造上述語言中的各類單詞符號及其分類碼表。表I語言中的各類單詞符號及其分類碼表單詞符號類別編碼類別碼的助記符單詞

5、值begin1BEGINend2ENDif3IFthen4THENelse5ELSE標識符6ID字母打頭的字母數(shù)字串整常數(shù)7INT數(shù)字串8LT=9LE=10EQ11NE12GT=13GE:=14IS+15PL-16MI*17MU/18DI處理過程：在一個程序設(shè)計語言中， 一般都含有若干類單詞符號，為此可首先為每類單詞建立一張狀態(tài)轉(zhuǎn)換圖， 然后將這些狀態(tài)轉(zhuǎn)換圖合并成一張統(tǒng)一的狀態(tài)圖，即得到了一個有限自動機，再進行必要的確定化和狀態(tài)數(shù)最小化處理，最后據(jù)此構(gòu)造詞法分析程序。在此為了使詞法分析程序結(jié)構(gòu)比較清晰，且盡量避免某些枝節(jié)問題的糾纏，假定要編譯的語言中， 全部關(guān)鍵字都是保留字，程序員不得將它們作

6、為源程序中的標識符；在源程序的輸入文本中，關(guān)鍵字、標識符、整常數(shù)之間，若未出現(xiàn)關(guān)系和算術(shù)運算符以及賦值符，則至少須用一個空白字符加以分隔。 作了這些限制以后， 就可以把關(guān)鍵字和標識符的識別統(tǒng)一進行處理。即每當開始識別一個單詞時，若掃視到的第一個字符為字母，則把后續(xù)輸入的字母或數(shù)字字符依 次進行拼接，直至掃視到非字母、數(shù)字字符為止，以期獲得一個盡可能長的字母數(shù)字字符串， 然后以此字符串查所謂保留字表（此保留字表已事先造好），若查到此字符串，則取出相應(yīng)的類別碼；反之，則表明該字符串應(yīng)為一標識符。采用上述策略后，針對表I中部分單詞可以構(gòu)造一個如圖1所示的有限自動機（以狀態(tài)轉(zhuǎn)換圖表示）。在圖1中添加了

7、當進行狀態(tài)轉(zhuǎn) 移時，詞法分析程序應(yīng)執(zhí)行的語義動作。題目2：將表I單詞集中的整常數(shù)改為無符號常數(shù)，修改題目 1中已開發(fā)的掃描器。無符號常數(shù)的單詞分類碼助記符：UCON ;其值為無符號常數(shù)的機內(nèi)二進制表示。描述無符號數(shù)的 BNF定義和狀態(tài)轉(zhuǎn)換圖：無符號數(shù)的文法G如下：無符號數(shù)- d余留無符號數(shù)小數(shù)部分無符號數(shù)f- 無符號數(shù)-d 余留無符號數(shù)- d余留無符號數(shù) 余留無符號數(shù)-十進小數(shù)余留無符號數(shù)- E指數(shù)部分 余留無符號數(shù)-d 余留無符號數(shù)f- 十進小數(shù)- E指數(shù)部分 十進小數(shù)f d十進小數(shù) 十進小數(shù)-d 小數(shù)部分f d十進小數(shù) 小數(shù)部分d 指數(shù)部分f d余留整指數(shù) 指數(shù)部分f +整指數(shù) 指數(shù)部分-

8、整指數(shù) 指數(shù)部分d整指數(shù)fd余留整指數(shù) 整指數(shù)-d余留整指數(shù)-d余留整指數(shù) 余留整指數(shù)-d圖2所示為上述文法的狀態(tài)轉(zhuǎn)換圖，其中編號 0、1、2、6分別代表非終結(jié)符號 無符號數(shù) 、余留無符號數(shù) 、十進小數(shù) 、小數(shù)部分 、指數(shù)部分 、整指數(shù) 及余留 整指數(shù)。實現(xiàn)無符號數(shù)識別的參考方法：在計算機內(nèi)實現(xiàn)狀態(tài)轉(zhuǎn)換圖的方法之一，是以狀態(tài)圖中的各個狀態(tài)為行，以可能輸入的各個輸入符號為列，組成一個狀態(tài)矩陣。其中，矩陣的元素 用來指明下一個狀態(tài)和掃描器應(yīng)完成的語義動作（如拼接字符、數(shù)制轉(zhuǎn)換、查填符號表以及輸出單詞的內(nèi)部表示等）。由于在一個狀態(tài)矩陣中，通常有許多狀態(tài)都是出錯狀態(tài)，為了節(jié) 省存放狀態(tài)矩陣的存儲空間，

9、在具體實現(xiàn)時，常常采用更為緊湊和有效的數(shù)據(jù)結(jié)構(gòu)。例如， 對于文法G卜無符號數(shù)刁的狀態(tài)轉(zhuǎn)換圖，可按表 II的形式來存放其狀態(tài)矩陣。表 II中的第 一列為各狀態(tài) Si的編號，第二列分別列出了在每一狀態(tài)下可能掃視到的輸入符號aj （其中“other”是一個符號集合，用來表示在相應(yīng)狀態(tài)所屬的那一欄中，除其前所列字符之外的全部其它字符），第三列指出當（ Si,aj）出現(xiàn)時應(yīng)執(zhí)行的語義動作（通常用若干個語句來實 現(xiàn)，若其后空，則表示不進行任何處理），最后一欄用來指明下一狀態(tài)的編號（若其后NULL或“結(jié)束”則表示無后繼狀態(tài)）。狀態(tài)矩陣中所嵌入的語義動作，其功能是在掃描源程序字符串的過程中，把識別出的字符串形

10、式的無符號數(shù)，逐步轉(zhuǎn)換為相應(yīng)的二進制整數(shù)（ICON）或二進制浮點數(shù)（FCON）的內(nèi)部形式，方法見教材第56頁。（注：考慮能否采用 C語言的庫函數(shù)實現(xiàn)此語義處理工作。）表II包含語義處理過程的識別無符號數(shù)的狀態(tài)矩陣當前狀態(tài)目耀宇科語文處理偉或桂登動作后卑求毒d但如 fQw-d()I(胃=。+ n=0| p=0( 更=1|：3other證別突敷NULLidw=w lO+d/1*2E4other同迷!（常就lCON=*i）結(jié)理2d+ 1 W - W - IC + d 1 ；2E4othej，回送實京ft FWN * * pu*EKLe * p nh僑柬3d加+i w=w * lO+D2other也利

11、失數(shù)NULL4dp=p 】0+d*6十5一圖1識別表I所列語言中的部分單詞的DFA及相關(guān)的語義過程圖1及程序一中所出現(xiàn)的語義變量及語義函數(shù)的含義和功能說明如下。函數(shù)GETCHAR :每調(diào)用一次，就把掃描指示器當前所指示的源程序字符送入字符變量ch,然后把掃描指示器前推一個字符位置。字符數(shù)組TOKEN :用來依次存放一個單詞詞文中的各個字符。函數(shù)CAT :每調(diào)用一次，就把當前 ch中的字符拼接于TOKEN中所存字符串的右邊。函數(shù)LOOKUP :每調(diào)用一次，就以 TOKEN中的字符串查保留字表，若查到，就將相應(yīng)關(guān)鍵字的類 別碼賦給整型變量 c；否則將c置為零。函數(shù)RETRACT :每調(diào)用一次，就把

12、掃描指示器回退一個字符位置（即退回多讀的那個字符）。函數(shù)OUT : 一般僅在進入終態(tài)時調(diào)用此函數(shù)，調(diào)用的形式為OUT（c, VAL）。其中，實參c為相應(yīng)單詞的類別碼或其助記符；當所識別的單詞為標識符和整數(shù)時，實參 VAL為TOKEN （即詞文分別為字母數(shù) 字串和數(shù)字串），對于其余種類的單詞，VAL均為空串。函數(shù) OUT的功能是，在送出一個單詞的內(nèi)部表示之后，返回到調(diào)用該詞法分析程序的那個程序。五、源程序#include #include char prog80,token6; char ch;int syn,p,m,n,sum;char * rwtab6= begin , if , then

13、, while , do , end ;main()p=0;printf( nplease intput string: );doch=getchar();progp+=ch;while (ch!= #);p=0;doscaner();switch (syn)case 11:printf(%d,%d)n ,syn,sum); break;case -1:printf( input errorn ); break;default :printf(%d,%s)n ,syn,token);while (syn!=0);getch();/*詞法掃描程序：*/scaner()for (n=0;n8;n+

14、)tokenn=NULL;m=0;ch=progp+;while (ch= )ch=progp+;if (ch=a )|(ch=A)while (ch=a )|(ch=A )|(ch=0) tokenm+=ch;ch=progp+;tokenm+= 0;ch=prog-p;syn=10;for (n=0;n6;n+)if (strcmp(token,rwtabn)=0)(syn=n+1;break;elseif (ch=0)(sum=0;while (ch=0)(sum=sum*10+ch- 0;ch=progp+;ch=prog-p;syn=11;else switch (ch)(case

15、)(syn=21; tokenm+=ch;elseif (ch=)(syn=22; tokenm+=ch;else(syn=20;ch=prog-p; break ; case :tokenm+=ch;ch=progp+;if (ch=)syn=24;tokenm+=ch;elsesyn=23;ch=prog-p;break ;case : :tokenm+=ch;ch=progp+;if (ch=)syn=18;tokenm+=ch;elsesyn=17;ch=prog-p;breakcase+:syn=13;token0=ch;break;case-:syn=14;token0=ch;br

16、eak;case*:syn=15;token0=ch;break;case/:syn=16;token0=ch;break;case:=:syn=18;token0=ch;break ;case:syn=21;token0=ch;break ;case=:syn=24;token0=ch;break ;case=:syn=25;token0=ch;break;case，.， ;:syn=26;token0=ch;break;case(:syn=27;token0=ch;break;case):syn=28;token0=ch;break;case#:syn=0;token0=ch;break;

17、default :syn=-1;六、源程序說明:字符數(shù)組TOKEN用來依次存放一個單詞詞文中的各個字符。函數(shù)getchar ：每調(diào)用一次，就把掃描指示器當前所指示的源程序字符送入字符變量ch,然后把掃描指示器前推一個字符位置。函數(shù)lookup :每調(diào)用一次，就以 TOKEN中的字符串查保留字表，若查到，就將相應(yīng) 關(guān)鍵字的類別碼賦給整形變量c；否則將c置為零。函數(shù)ungetc :每調(diào)用一次，就把掃描指示器回退一個字符位置(即退回多讀的那個字 符)。函數(shù)out : 一般僅在進入終態(tài)時調(diào)用此函數(shù)，調(diào)用的形式為 out (c)。其中，實參 c為 相應(yīng)單詞的類別碼。函數(shù)根據(jù)類別碼選擇輸出形式。七實驗結(jié)果

18、及分析(包括結(jié)果描述、實驗現(xiàn)象分析、影響因素討論、綜合分析和結(jié)論等)(1)輸入字符串 begin x:=9; ifx0 then x:= 2*x+1/3; end #其結(jié)果如下圖所示(2)輸入字符串hello#其輸出結(jié)果如下圖所示:(3)輸入字符串if x2; y=3; end # 其結(jié)果如下圖所示:實驗二語法分析程序?qū)崿F(xiàn)一、實驗?zāi)康呐c要求通過設(shè)計、編制、調(diào)試一個典型的語法分析程序(任選有代表性的語法分析方法，如算符優(yōu)先法、遞歸下降法、LL(1)、SLR(1)、LR(1)等，作為編制語法分析程序的依據(jù))，對掃描器所提供的單詞序列進行語法檢查和結(jié)構(gòu)分析，實現(xiàn)并進一步掌握常用的語法分析方法。二、實

19、驗內(nèi)容選擇對各種常見高級程序設(shè)計語言都較為通用的語法結(jié)構(gòu)作為分析對象，給出其文法描述(注意應(yīng)與所采用的語法分析方法比較貼近)，設(shè)計并實現(xiàn)一個完整的語法分析程序。輸入：源程序以文件的形式輸入。輸出：對于所輸入的源程序，如果輸入符號串是給定文法定義的合法句子，則輸出“RIGHT ，并且給出每一步歸約的過程；如果不是句子，即輸入串有錯誤，則輸出“ERROR”,并且顯示已經(jīng)歸約出的各個文法符號。三、基本實驗題目以如下文法G1所定義的算術(shù)表達式的賦值語句作為分析對象，編寫并調(diào)試一個語法分析程序。G1賦值語句:賦值語句 - 變量 := 算術(shù)表達式算術(shù)表達式 項 | 算術(shù)表達式+項 | 算術(shù)表達式 -項項

20、f 因式 | 項*因式 | 項/因式因式 f 變量 | 常數(shù) | ( 算術(shù)表達式)變量 f 標識符標識符 - 標識符 字母 | 標識符 數(shù)字 | 字母常數(shù) - 整數(shù) | 浮點數(shù)整數(shù) f 數(shù)字 | 數(shù)字 整數(shù)浮點數(shù) f?整數(shù) | 整數(shù) ?整數(shù)字母 A| B| C| | X| Y|Z|a|b|c| |x|y|z數(shù)字 -0| 1| 2| 9四、源程序#include iostreamusing namespace std;#include stdio.h#include string.h#define MAX 150/詞法分析表的最大容量#define MAXBUF 255 /緩沖區(qū)的最大緩沖量 v

21、oid term();void lrparser();void statement。；void yucu();void expression。；void factor();char progMAXBUF,tokenMAX;char ch;int syn,p,m,n,sum,kk;char * rwtab6= begin , if , then , while , do , end ; / /*詞法掃描程序：*/ void scaner() for (m=0;mMAX;m+) tokenm=NULL; m=0;sum=0; ch=progp+;while (ch= )ch=progp+;if (

22、ch=a )|(ch=A) while (ch=a )|(ch=A )|(ch=0) tokenm+=ch; ch=progp+; /讀取下一個字符 tokenm+= 0; ch=prog-p; syn=10;for (n=0;n6;n+) if (strcmp(token,rwtabn)=0) syn=n+1;給出 syn 值break; else if (ch=0) sum=0;while (ch=0) sum=sum*10+ch- 0; ch=progp+; ch=prog-p; syn=11; elseswitch (ch)(case )(syn=21;tokenm+=ch;elsei

23、f (ch=)(syn=22;tokenm+=ch;else(syn=20;ch=prog-p;break ;case :tokenm+=ch;ch=progp+;if (ch=)(syn=24;tokenm+=ch;else(syn=23;ch=prog-p;break ;case : :tokenm+=ch;ch=progp+;if (ch=)(syn=18;tokenm+=ch;elsesyn=17;ch=prog-p;breakcase+:syn=13;token0=ch;break;case-:syn=14;token0=ch;break;case*:syn=15;token0=ch

24、;break;case/:syn=16;token0=ch;break;case:=:syn=18;token0=ch;breakcase:syn=21;token0=ch;breakcase=:syn=24;token0=ch;breakcase=:syn=25;token0=ch;break;case，.， ;:syn=26;token0=ch;break;case(:syn=27;token0=ch;break;case):syn=28;token0=ch;break;case#:syn=0;token0=ch;break;default :syn=-1;break;/void stat

25、ement。if (syn=10)scaner();/讀下一個單詞符號if (syn=18)scaner();/讀下一個單詞符號expression。；/ 調(diào)用 expression 函數(shù)elseprintf( error!);kk=1;elseerror!);printf(kk=1; return ;/void expression。term();while (syn=13 | syn=14)scaner();term();return ;/void term()factor();while (syn=15 | syn=16)scaner();factor();return ;/void lrparser()if (syn=1) /b