編譯原理實驗報告完整版河北工業

編譯原理實驗報告

班級姓名學號

自我評定：75

實驗一詞法分析程式實現

一、實驗目的與要求

通過編寫和除錯乙個詞法分析程式，掌握在對程式語言的源程式進行掃瞄的過程中，將字元形式的源程式流轉化為乙個由各類單詞符號組成的流的詞法分析方法。

二、實驗內容

根據教學要求並結合學生自己的興趣和具體情況，從具有代表性的高階程式語言的各類典型單詞中，選取乙個適當大小的子集。例如，可以完成無符號常數這一類典型單詞的識別後，再完成乙個盡可能兼顧到各種常數、關鍵字、識別符號和各種運算子的掃瞄器的設計和實現。

輸入：由符合或不符合所規定的單詞類別結構的各類單詞組成的源程式。

輸出：把單詞的字元形式的表示翻譯成編譯器的內部表示，即確定單詞串的輸出形式。例如，所輸出的每一單詞均按形如（class，value）的二元式編碼。

對於變數和常數，class欄位為相應的類別碼；value欄位則是該識別符號、常數的具體值或在其符號表中登記項的序號（要求在變數名錶登記項中存放該識別符號的字串；常數表登記項中則存放該常數的二進位制形式）。對於關鍵字和運算子，採用一詞一類的編碼形式；由於採用一詞一類的編碼方式，所以僅需在二元式的class欄位上放置相應的單詞的類別碼，value欄位則為「空」。另外，為便於檢視由詞法分析程式所輸出的單詞串，要求在class欄位上放置單詞類別的助記符。

三、實現方法與環境

詞法分析是編譯程式的第乙個處理階段，可以通過兩種途徑來構造詞法分析程式。其一是根據對語言中各類單詞的某種描述或定義（如bnf），用手工的方式（例如可用c語言）構造詞法分析程式。一般地，可以根據文法或狀態轉換圖構造相應的狀態矩陣，該狀態矩陣同控制程式便組成了編譯器的詞法分析程式；也可以根據文法或狀態轉換圖直接編寫詞法分析程式。

構造詞法分析程式的另外一種途徑是所謂的詞法分析程式的自動生成，即首先用正規式對語言中的各類單詞符號進行詞型描述，並分別指出在識別單詞時，詞法分析程式所應進行的語義處理工作，然後由乙個所謂詞法分析程式的構造程式對上述資訊進行加工。如美國bell實驗室研製的lex就是乙個被廣泛使用的詞法分析程式的自動生成工具。

總的來說，開發一種新語言時，由於它的單詞符號在不停地修改，採用lex等工具生成的詞法分析程式比較易於修改和維護。一旦一種語言確定了，則採用手工編寫詞法分析程式效率更高。

四、實驗設計

1）題目1：試用手工編碼方式構造識別以下給定單詞的某一語言的詞法分析程式。

語言中具有的單詞包括五個有代表性的關鍵字begin、end、if、then、else；識別符號；整型常數；六種關係運算子；乙個賦值符和四個算術運算子。參考實現方法簡述如下。

單詞的分類：構造上述語言中的各類單詞符號及其分類碼表。

表i 語言中的各類單詞符號及其分類碼表

處理過程：在乙個程式語言中，一般都含有若干類單詞符號，為此可首先為每類單詞建立一張狀態轉換圖，然後將這些狀態轉換圖合併成一張統一的狀態圖，即得到了乙個有限自動機，再進行必要的確定化和狀態數最小化處理，最後據此構造詞法分析程式。在此為了使詞法分析程式結構比較清晰，且盡量避免某些枝節問題的糾纏，假定要編譯的語言中，全部關鍵字都是保留字，程式設計師不得將它們作為源程式中的識別符號；在源程式的輸入文字中，關鍵字、識別符號、整常數之間，若未出現關係和算術運算子以及賦值符，則至少須用乙個空白字元加以分隔。

作了這些限制以後，就可以把關鍵字和識別符號的識別統一進行處理。即每當開始識別乙個單詞時，若掃視到的第乙個字元為字母，則把後續輸入的字母或數字字元依次進行拼接，直至掃視到非字母、數字字元為止，以期獲得乙個盡可能長的字母數字字串，然後以此字串查所謂保留字表（此保留字表已事先造好），若查到此字串，則取出相應的類別碼；反之，則表明該字串應為一識別符號。採用上述策略後，針對表i中部分單詞可以構造乙個如圖1所示的有限自動機（以狀態轉換圖表示）。

在圖1中新增了當進行狀態轉移時，詞法分析程式應執行的語義動作。

題目2：將表i單詞集中的整常數改為無符號常數，修改題目1中已開發的掃瞄器。

無符號常數的單詞分類碼助記符：ucon；其值為無符號常數的機內二進位制表示。

描述無符號數的bnf定義和狀態轉換圖：

無符號數的文法g如下：

〈無符號數〉→ d〈餘留無符號數〉

〈無符號數〉→ ·〈小數部分〉

〈無符號數〉→ d

〈餘留無符號數〉→ d〈餘留無符號數〉

〈餘留無符號數〉→ ·〈十進小數〉

〈餘留無符號數〉→ e〈指數部分〉

〈餘留無符號數〉→ d

〈餘留無符號數〉→ ·

〈十進小數〉→ e〈指數部分〉

〈十進小數〉→ d〈十進小數〉

〈十進小數〉→ d

〈小數部分〉→ d〈十進小數〉

〈小數部分〉→ d

〈指數部分〉→ d〈餘留整指數〉

〈指數部分〉→ +〈整指數〉

〈指數部分〉→ -〈整指數〉

〈指數部分〉→ d

〈整指數〉→ d〈餘留整指數〉

〈整指數〉→ d

〈餘留整指數〉→ d〈餘留整指數〉

〈餘留整指數〉→ d

圖2所示為上述文法的狀態轉換圖，其中編號0、1、2、…、6分別代表非終結符號《無符號數》、《餘留無符號數》、《十進小數》、《小數部分》、《指數部分》、《整指數》及《餘留整指數》。

圖2 文法g[《無符號數》]的狀態轉換圖

實現無符號數識別的參考方法：在計算機內實現狀態轉換圖的方法之一，是以狀態圖中的各個狀態為行，以可能輸入的各個輸入符號為列，組成乙個狀態矩陣。其中，矩陣的元素用來指明下乙個狀態和掃瞄器應完成的語義動作（如拼接字元、數制轉換、查填符號表以及輸出單詞的內部表示等）。

由於在乙個狀態矩陣中，通常有許多狀態都是出錯狀態，為了節省存放狀態矩陣的儲存空間，在具體實現時，常常採用更為緊湊和有效的資料結構。例如，對於文法g[《無符號數》]的狀態轉換圖，可按表ii的形式來存放其狀態矩陣。表ii中的第一列為各狀態si的編號，第二列分別列出了在每一狀態下可能掃視到的輸入符號aj（其中「other」是乙個符號集合，用來表示在相應狀態所屬的那一欄中，除其前所列字元之外的全部其它字元），第三列指出當（si,aj）出現時應執行的語義動作（通常用若干個語句來實現，若其後空，則表示不進行任何處理），最後一欄用來指明下一狀態的編號（若其後null或「結束」則表示無後繼狀態）。

狀態矩陣中所嵌入的語義動作，其功能是在掃瞄源程式字串的過程中，把識別出的字串形式的無符號數，逐步轉換為相應的二進位制整數（icon）或二進位制浮點數（fcon）的內部形式，方法見教材第56頁。（注：考慮能否採用c語言的庫函式實現此語義處理工作。

）表ii 包含語義處理過程的識別無符號數的狀態矩陣

圖1 識別表i所列語言中的部分單詞的dfa及相關的語義過程

圖1及程式一中所出現的語義變數及語義函式的含義和功能說明如下。

函式getchar：每呼叫一次，就把掃瞄指示器當前所指示的源程式字元送入字元變數ch，然後把掃瞄指示器前推乙個字元位置。

字元陣列token：用來依次存放乙個單詞詞文中的各個字元。

函式cat：每呼叫一次，就把當前ch中的字元拼接於token中所存字串的右邊。

函式lookup：每呼叫一次，就以token中的字串查保留字表，若查到，就將相應關鍵字的類別碼賦給整型變數c；否則將c置為零。

函式retract：每呼叫一次，就把掃瞄指示器回退乙個字元位置（即退回多讀的那個字元）。

函式out：一般僅在進入終態時呼叫此函式，呼叫的形式為out(c，val)。其中，實參c為相應單詞的類別碼或其助記符；當所識別的單詞為識別符號和整數時，實參val為token（即詞文分別為字母數字串和數字串），對於其餘種類的單詞，val均為空串。

函式out的功能是，在送出乙個單詞的內部表示之後，返回到呼叫該詞法分析程式的那個程式。

五、源程式

#include

char prog[80],token[6];

char ch;

int syn,p,m,n,sum;

char * rwtab[6]=;

main()

while(ch!='#');

p=0;

do}while(syn!=0);

getch();

}/*詞法掃瞄程式：*/

scaner()

token[m++]='\0';

ch=prog[--p];

syn=10;

for(n=0;n<6;n++)

if(strcmp(token,rwtab[n])==0)

}else

if((ch<='9'&&ch>='0'))

sum=0;

while((ch<='9'&&ch>='0'))

sum=sum*10+ch-'0';

ch=prog[p++];

ch=prog[--p];

syn=11;

else

switch(ch)

{case '<':m=0;token[m++]=ch;

編譯原理實驗報告完整版河北工業

PS完整版實驗報告

vb實驗報告完整版

北郵微機原理硬體實驗報告完整版

編譯原理實驗報告完整版河北工業

PS完整版實驗報告

vb實驗報告完整版

北郵微機原理硬體實驗報告完整版

相關推薦