編譯原理實驗五：編譯器自動生成工具

一、詞法分析程式自動生成工具的使用（4小時）

實驗目的

學習使用詞法分析自動工具LEX。

實驗任務

使用LEX工具實作編譯器的詞法分析程式。

實驗内容

(a) 學習文檔“LEX的用法.pdf”。

(b) 準備一個LEX工具，如這裡提供的“FLEX251.ZIP”，可上網搜尋下載下傳更新的版本。

(c) 以文檔中提供的4個輸入檔案為例，測試LEX工具。有些版本的FLEX需要在輔助程式部分增加yywrap()函數：

int yywrap() {return 1;}

1. 生成LEX版本的TINY詞法分析器，與其它部分組合成一個完整的TINY語言編譯器，并完成測試驗證。（參見tiny編譯器的使用.ppt）
2. 編寫某語言（如：C-語言）的詞法描述檔案，生成其詞法分析器，與其它部分組合成一個完整的TINY語言編譯器，并完成測試驗證。（提示：可利用增量程式設計，修改TINY語言的詞法描述檔案tiny.l，為C-語言編寫詞法描述檔案。）

（二）文法分析程式自動生成工具的使用（4小時）

學習使用文法分析程式自動生成工具YACC；使用YACC工具實作編譯器的詞法分析程式。

實驗内容

(a) 學習文檔“YACC的用法.pdf”。

(b) 準備一個YACC工具，如這裡提供的“bison.zip”，可上網搜尋下載下傳更新的版本。（有源程式可供參考）

(c) 以文檔中提供的輸入檔案為例，測試YACC工具。需要将兩個檔案拷貝到特殊目錄，詳情請閱readme.txt。

1. 生成YACC版本的TINY文法分析器，與其它部分組合成一個完整的TINY語言編譯器，并完成測試驗證。（提示：全局頭檔案GLOBALS.H需要替換為YACC目錄下的那個。）

（3）編寫某語言（如：C-語言）的文法描述檔案，生成其文法分析器，與其它部分組合成一個完整的TINY語言編譯器，并完成測試驗證。（提示：可利用增量程式設計，修改TINY語言的文法描述檔案tiny.y，為C-語言編寫文法描述檔案，全局頭檔案GLOBALS.H在替換為YACC目錄下的那個後需相應修改。）

實驗工具及源代碼下載下傳

https://pan.baidu.com/s/14nbZ3Xu5nsaGCRPcycJUHw

密碼：msry

實驗原理講解

1、LEX工具的使用

（1）以文檔中提供的4個輸入檔案為例，測試LEX工具。

步驟：

1.将flex.exe複制到tiny.l的目錄中

2.輸入指令“FLEX tiny.l”生成lex.yy.c

3.将main.c lex.yy.c util.c globals.h util.h scan.h放入一個工程中，編譯生成.exe檔案

FLEX語言的結構如下：

其中，FLEX檔案是使用一種特殊的語言——LEX，編寫的，它描述了一種語言的詞法結構：其中，第一部分為定義，FLEX工具在處理這一部分的時候，會将definitions部分的所有代碼原封不動的插入到lex.yy.c（詞法分析代碼）中，我們可以在這一部分中寫程式需要用到的頭檔案等内容，通常情況下，這些代碼被放在放在“%{”和“%}”之内，直接插入lex.yy.c。

第二部分是詞法規則部分：格式為【模式 { 動作 }】，其中模式為正規表達式，動作是代碼片段。當比對相對應的正規表達式時，這些代碼片段就會被執行。

最後一個部分包括着一些C代碼，這些函數被稱為輔助函數，它們用于在第2個部分被調用且不在任何地方被定義的輔助程式。如果要将Lex輸出作為獨立程式來編譯，則這一部分還會有一個主程式。LEX對此部份不作任何處理，僅僅将之直接拷貝到輸出檔案lex.yy.c的尾部。在些部份，可定義對模式進行處理的C語言函數、主函數和yylex要調用的函數yywrap()等。如果使用者在其它C子產品中提供這些函數，使用者代碼部份可以省略。

通過執行以上步驟，可以順利生成對應詞法分析代碼lex.yy.c。如圖是檔案夾内部的情況。如果需要正式編譯程式進行完整的詞法分析，還需要加上主函數部分。

（2）使用增量程式設計，将tiny詞法分析器改為C-詞法分析器。

這一部分的代碼其實在上面的壓縮包裡面有。。。。

C-的詞法規則結構要比TINY複雜，同時，TINY詞法中也含有一些C-沒有的關鍵字，比如repeat這些。由于C-的定義與tiny有所差別，隻需要根據C-的規則，對TINY.L進行增删操作即可。

以下是改進後的C-.L源程式：

%{
#include "globals.h"
#include "util.h"
#include "scan.h"
/* lexeme of identifier or reserved word */
char tokenString[MAXTOKENLEN+1];
%}

digit       [0-9]
number      {digit}+
letter      [a-zA-Z]
identifier  {letter}+
newline     \n
whitespace  [ \t]+

%%

"if"            {return IF;}
"while"          {return WHILE;}
"else"          {return ELSE;}
"return"         {return RETURN;}
"int"          {return INT;}
"void"         {return VOID;}
"="            {return ASSIGN;}
"=="             {return EQ;}
"<"             {return LT;}
"<="             {return LTEQ;}
">"             {return RT;}
">="             {return RTEQ;}
"!="             {return UNEQ;}
"+"             {return PLUS;}
"-"             {return MINUS;}
"*"             {return TIMES;}
","             {return NOB;}
"/"             {return OVER;}
"("             {return LPAREN;}
")"             {return RPAREN;}
";"             {return SEMI;}
"["             {return MLPAREN;}
"]"             {return MRPAREN;}
"{"             {return LLPAREN;}
"}"             {return LRPAREN;}
{number}        {return NUM;}
{identifier}    {return ID;}
{newline}       {lineno++;}
{whitespace}    {/* skip whitespace */}
"/*"            {     char c;
                      char d='f';
                      do
                      {     c = input();
                            if (c == EOF) break;
                            if (c == '\n') lineno++;
                            if (c == '*'){
                                c = input();
                                if (c == '/') d = 'a';
                            }
                      } while (d == 'f');
                }
.               {return ERROR;}

%%
TokenType getToken(void)
{    static int firstTime = TRUE;
     TokenType currentToken;
     if (firstTime)
     {     firstTime = FALSE;
           lineno++;
           yyin = source;
           yyout = listing;
     }
     currentToken = yylex();
     strncpy(tokenString,yytext,MAXTOKENLEN);
     if (TraceScan) {
        fprintf(listing,"\t%d: ",lineno);
        printToken(currentToken,tokenString);
     }
     return currentToken;
}
           

首先是第一部分：宏定義和詞法正規表達式描述，這些根據文檔中的定義就可以完成，且C-的詞法分析器與TINY一樣，需要包含globals.h中的宏定義、SCAN.h中的掃描檔案方法，這些頭檔案都需要包含進去。

第二部分是比對規則部分：這裡将TINY的關鍵字全部修改為C-語言的關鍵字，同時結合實驗二中所做的詞法分析程式，将字元的傳回标記全部更改好。通過增量程式設計的思想，在TINY.L中對相關語句進行修改即可。

第三部分是使用者自定義函數。這一部分與TINY沒有差别。

最後，我們還需要對TINY編譯器中的其他元件——utils.c、globals.h等檔案進行修改，使其符合C-語言的關鍵字标準。主要是将utils.c中的printtoken函數，更改為适應C-詞法分析的關鍵字代碼即可，做出符合增量程式設計的一些調整，就可以組合成完整的C-詞法分析器。

最終的C-詞法分析器包含以下這些元件：

2、YACC工具的使用

（1）以文檔中提供的輸入檔案為例，測試YACC工具。

步驟：（與LEX詞法分析類似）

1、将文法分析YACC工具BISON和文法描述檔案.Y放入同一個檔案夾内。

2、指令行中輸入“bison .y類型的檔案名”就可以生成文法分析代碼.Y.tab.C。

3、将生成的文法分析代碼與其他部件組合在一起，就可以生成完整的文法分析器。

類似于詞法分析檔案lex，文法描述語言YACC檔案的格式也由三部分組成：定義、規則、函數。

首先是定義部分：定義部分包括Yacc需要用來建立分析程式的有關記号、資料類型以及文法規則的資訊。它還包括了必須在它的開始時直接進入輸出檔案的任何C代碼(主要是其他源代碼檔案的#include訓示)。說明檔案的這個部分可以是空的。

規則部分包括修改的BNF格式中的文法規則以及将在識别出相關的文法規則時被執行的C代碼中的動作。文法規則中使用的元符号慣例如下：通常，豎線被用作替換(也可分别寫出替換項)。

最後是使用者自定義函數部分，輔助程式部分包括了過程和函數聲明，這個部分也可為空。此部分與詞法分析中無太大差别。

（2）編寫某語言（如：C-語言）的文法描述檔案，生成其文法分析器。

由于C-的文法與TINY十分不同，根據實驗指導書上C-的29條文法規則，參照TINY.Y中的格式，進行編寫：

上圖展示的是C-文法分析檔案的其中一部分，完整代碼太長，沒辦法全部貼出，具體實作部分在檔案夾的【Cminus增量文法】檔案夾下。

實作完上面的C-文法描述檔案後，我們通過更改一系列TINY語言中使用過的輔助檔案如utils.c、globals.h等，讓它們适應C-的文法特點（主要是關鍵字的實作有差别）之後生成一個工程，即可完成C-的文法分析器構造。

上面這個代碼，壓縮包裡面也有，下載下傳一下吧，emmm。。。

3、生成完整編譯器

這是這個實驗指導書上規定的最後一步，但是我很不了解，為什麼到這裡隻實作了詞法和文法的時候，就要去要求，能生成整個編譯器呢？？

明顯，是實驗的安排出現了問題。

整體的編譯器還需要語義分析、代碼生成，甚至如果需要一個能夠執行C-代碼的虛拟機環境！！這個地方當時助教驗收，很多人都是懵的，如果之後這個實驗還有這個需求，那我也沒有辦法，直接用TINY語言的去驗收吧。

【下面展示的是有源代碼的TINY編譯器的生成過程】