woaidongmao

Lex 和 Yacc 是 UNIX 兩個非常重要的、功能強(qiáng)大的工具。事實上，如果你熟練掌握 Lex 和 Yacc 的話，它們的強(qiáng)大功能使創(chuàng)建 FORTRAN 和 C 的編譯器如同兒戲。Ashish Bansal 為您詳細(xì)的討論了編寫自己的語言和編譯器所用到的這兩種工具，包括常規(guī)表達(dá)式、聲明、匹配模式、變量、Yacc 語法和解析器代碼。最后，他解釋了怎樣把 Lex 和 Yacc 結(jié)合起來。

Lex 代表 Lexical Analyzar。Yacc 代表 Yet Another Compiler Compiler。 讓我們從 Lex 開始吧。

Lex

Lex 是一種生成掃描器的工具。掃描器是一種識別文本中的詞匯模式的程序。這些詞匯模式（或者常規(guī)表達(dá)式）在一種特殊的句子結(jié)構(gòu)中定義，這個我們一會兒就要討論。

一種匹配的常規(guī)表達(dá)式可能會包含相關(guān)的動作。這一動作可能還包括返回一個標(biāo)記。當(dāng) Lex 接收到文件或文本形式的輸入時，它試圖將文本與常規(guī)表達(dá)式進(jìn)行匹配。它一次讀入一個輸入字符，直到找到一個匹配的模式。如果能夠找到一個匹配的模式，Lex 就執(zhí)行相關(guān)的動作（可能包括返回一個標(biāo)記）。另一方面，如果沒有可以匹配的常規(guī)表達(dá)式，將會停止進(jìn)一步的處理，Lex 將顯示一個錯誤消息。

Lex 和 C 是強(qiáng)耦合的。一個 .lex 文件（Lex 文件具有 .lex 的擴(kuò)展名）通過 lex 公用程序來傳遞，并生成 C 的輸出文件。這些文件被編譯為詞法分析器的可執(zhí)行版本。

Lex 的常規(guī)表達(dá)式

常規(guī)表達(dá)式是一種使用元語言的模式描述。表達(dá)式由符號組成。符號一般是字符和數(shù)字，但是 Lex 中還有一些具有特殊含義的其他標(biāo)記。下面兩個表格定義了 Lex 中使用的一些標(biāo)記并給出了幾個典型的例子。

用 Lex 定義常規(guī)表達(dá)式

常規(guī)表達(dá)式舉例

Lex 中的標(biāo)記聲明類似 C 中的變量名。每個標(biāo)記都有一個相關(guān)的表達(dá)式。（下表中給出了標(biāo)記和表達(dá)式的例子。）使用這個表中的例子，我們就可以編一個字?jǐn)?shù)統(tǒng)計的程序了。我們的第一個任務(wù)就是說明如何聲明標(biāo)記。

標(biāo)記聲明舉例

Lex 編程

Lex 編程可以分為三步：

1. 以 Lex 可以理解的格式指定模式相關(guān)的動作。
2. 在這一文件上運行 Lex，生成掃描器的 C 代碼。
3. 編譯和鏈接 C 代碼，生成可執(zhí)行的掃描器。

注意: 如果掃描器是用 Yacc 開發(fā)的解析器的一部分，只需要進(jìn)行第一步和第二步。關(guān)于這一特殊問題的幫助請閱讀 Yacc和 將 Lex 和 Yacc 結(jié)合起來部分。

現(xiàn)在讓我們來看一看 Lex 可以理解的程序格式。一個 Lex 程序分為三個段：第一段是 C 和 Lex 的全局聲明，第二段包括模式（C 代碼），第三段是補充的 C 函數(shù)。 例如, 第三段中一般都有 main() 函數(shù)。這些段以%%來分界。 那么，回到字?jǐn)?shù)統(tǒng)計的 Lex 程序，讓我們看一下程序不同段的構(gòu)成。

C 和 Lex 的全局聲明

這一段中我們可以增加 C 變量聲明。這里我們將為字?jǐn)?shù)統(tǒng)計程序聲明一個整型變量，來保存程序統(tǒng)計出來的字?jǐn)?shù)。我們還將進(jìn)行 Lex 的標(biāo)記聲明。

字?jǐn)?shù)統(tǒng)計程序的聲明

       %{

        int wordCount = 0;

        %}

        chars [A-za-z\_\'\.\"]

        numbers ([0-9])+

        delim [" "\n\t]

        whitespace {delim}+

        words {chars}+

        %%

兩個百分號標(biāo)記指出了 Lex 程序中這一段的結(jié)束和三段中第二段的開始。

Lex 的模式匹配規(guī)則

讓我們看一下 Lex 描述我們所要匹配的標(biāo)記的規(guī)則。（我們將使用 C 來定義標(biāo)記匹配后的動作。）繼續(xù)看我們的字?jǐn)?shù)統(tǒng)計程序，下面是標(biāo)記匹配的規(guī)則。

字?jǐn)?shù)統(tǒng)計程序中的 Lex 規(guī)則

       {words} { wordCount++; /*

        increase the word count by one*/ }

        {whitespace} { /* do

        nothing*/ }

        {numbers} { /* one may

        want to add some processing here*/ }

        %%

C 代碼

Lex 編程的第三段，也就是最后一段覆蓋了 C 的函數(shù)聲明（有時是主函數(shù)）。注意這一段必須包括 yywrap() 函數(shù)。 Lex 有一套可供使用的函數(shù)和變量。 其中之一就是 yywrap。一般來說，yywrap() 的定義如下例。我們將在 高級 Lex 中探討這一問題。

字?jǐn)?shù)統(tǒng)計程序的 C 代碼段

       void main()

        {

        yylex(); /* start the

        analysis*/

        printf(" No of words:

        %d\n", wordCount);

        }

        int yywrap()

        {

        return 1;

        }

上一節(jié)我們討論了 Lex 編程的基本元素，它將幫助你編寫簡單的詞法分析程序。在 高級 Lex 這一節(jié)中我們將討論 Lex 提供的函數(shù)，這樣你就能編寫更加復(fù)雜的程序了。

將它們?nèi)拷Y(jié)合起來

.lex文件是 Lex 的掃描器。它在 Lex 程序中如下表示：

   $ lex <file name.lex>

這生成了 lex.yy.c 文件，它可以用 C 編譯器來進(jìn)行編譯。它還可以用解析器來生成可執(zhí)行程序，或者在鏈接步驟中通過選項?ll 包含 Lex 庫。

這里是一些 Lex 的標(biāo)志：

• -c表示 C 動作，它是缺省的。
• -t寫入 lex.yy.c 程序來代替標(biāo)準(zhǔn)輸出。
• -v提供一個兩行的統(tǒng)計匯總。
• -n不打印 -v 的匯總。
•  

高級 Lex

Lex 有幾個函數(shù)和變量提供了不同的信息，可以用來編譯實現(xiàn)復(fù)雜函數(shù)的程序。下表中列出了一些變量和函數(shù)，以及它們的使用。詳盡的列表請參考 Lex 或 Flex 手冊（見后文的 資源）。

Lex 變量

Lex 函數(shù)

對 Lex 的討論就到這里。下面我們來討論 Yacc...

Yacc

Yacc 代表 Yet Another Compiler Compiler。 Yacc 的 GNU 版叫做 Bison。它是一種工具，將任何一種編程語言的所有語法翻譯成針對此種語言的 Yacc 語 法解析器。它用巴科斯范式(BNF, Backus Naur Form)來書寫。按照慣例，Yacc 文件有 .y 后綴。編譯行如下調(diào)用 Yacc 編譯器：

       $ yacc <options>

        <filename ending with .y>

在進(jìn)一步闡述以前，讓我們復(fù)習(xí)一下什么是語法。在上一節(jié)中，我們看到 Lex 從輸入序列中識別標(biāo)記。如果你在查看標(biāo)記序列，你可能想在這一序列出現(xiàn)時執(zhí)行某一動作。這種情況下有效序列的規(guī)范稱為語法。Yacc 語法文件包括這一語法規(guī)范。它還包含了序列匹配時你想要做的事。

為了更加說清這一概念，讓我們以英語為例。 這一套標(biāo)記可能是：名詞, 動詞, 形容詞等等。為了使用這些標(biāo)記造一個語法正確的句子，你的結(jié)構(gòu)必須符合一定的規(guī)則。一個簡單的句子可能是名詞+動詞或者名詞+動詞+名詞。(如 I care. See spot run.)

所以在我們這里，標(biāo)記本身來自語言（Lex），并且標(biāo)記序列允許用 Yacc 來指定這些標(biāo)記(標(biāo)記序列也叫語法)。

用 Yacc 來創(chuàng)建一個編譯器包括四個步驟：

1. 通過在語法文件上運行 Yacc 生成一個解析器。
2. 說明語法：
• 編寫一個 .y 的語法文件（同時說明 C 在這里要進(jìn)行的動作）。
• 編寫一個詞法分析器來處理輸入并將標(biāo)記傳遞給解析器。 這可以使用 Lex 來完成。
• 編寫一個函數(shù)，通過調(diào)用 yyparse() 來開始解析。
• 編寫錯誤處理例程（如 yyerror()）。
3. 編譯 Yacc 生成的代碼以及其他相關(guān)的源文件。
4. 將目標(biāo)文件鏈接到適當(dāng)?shù)目蓤?zhí)行解析器庫。

用 Yacc 編寫語法

如同 Lex 一樣, 一個 Yacc 程序也用雙百分號分為三段。它們是：聲明、語法規(guī)則和 C 代碼。我們將解析一個格式為 姓名 = 年齡的文件作為例子，來說明語法規(guī)則。我們假設(shè)文件有多個姓名和年齡，它們以空格分隔。在看 Yacc 程序的每一段時，我們將為我們的例子編寫一個語法文件。

C 與 Yacc 的聲明

C 聲明可能會定義動作中使用的類型和變量，以及宏。還可以包含頭文件。每個 Yacc 聲明段聲明了終端符號和非終端符號（標(biāo)記）的名稱，還可能描述操作符優(yōu)先級和針對不同符號的數(shù)據(jù)類型。 lexer (Lex) 一般返回這些標(biāo)記。所有這些標(biāo)記都必須在 Yacc 聲明中進(jìn)行說明。

在文件解析的例子中我們感興趣的是這些標(biāo)記：name, equal sign, 和 age。Name 是一個完全由字符組成的值。 Age 是數(shù)字。于是聲明段就會像這樣：

文件解析例子的聲明

       %

        #typedef char* string; /*

        to specify token types as char* */

        #define YYSTYPE string /*

        a Yacc variable which has the value of returned token */

        %}

        %token NAME EQ AGE

        %%

你可能會覺得 YYSTYPE 有點奇怪。但是類似 Lex, Yacc 也有一套變量和函數(shù)可供用戶來進(jìn)行功能擴(kuò)展。 YYSTYPE 定義了用來將值從 lexer 拷貝到解析器或者 Yacc 的 yylval （另一個 Yacc 變量）的類型。默認(rèn)的類型是 int。 由于字符串可以從 lexer 拷貝，類型被重定義為 char*。 關(guān)于 Yacc 變量的詳細(xì)討論，請參考 Yacc 手冊（見 資源）。

Yacc 語法規(guī)則

Yacc 語法規(guī)則具有以下一般格式：

       result: components { /*

        action to be taken in C */ }

        ;

在這個例子中，result 是規(guī)則描述的非終端符號。Components 是根據(jù)規(guī)則放在一起的不同的終端和非終端符號。 如果匹配特定序列的話 Components 后面可以跟隨要執(zhí)行的動作。 考慮如下的例子：

       param : NAME EQ NAME {

        printf("\tName:%s\tValue(name):%s\n", $1,$3);}

            | NAME EQ VALUE{

            printf("\tName:%s\tValue(value):%s\n",$1,$3);}

        ;

如果上例中序列 NAME EQ NAME 被匹配，將執(zhí)行相應(yīng)的 { } 括號中的動作。 這里另一個有用的就是 $1 和 $3 的使用, 它們引用了標(biāo)記 NAME 和 NAME（或者第二行的 VALUE）的值。 lexer 通過 Yacc 的變量 yylval 返回這些值。標(biāo)記 NAME 的 Lex 代碼是這樣的：

       char [A-Za-z]

        name {char}+

        %%

        {name} { yylval = strdup(yytext);

        return NAME; }

文件解析例子的規(guī)則段是這樣的：

文件解析的語法

       file : record file

        | record

        ;

        record: NAME EQ AGE {

        printf("%s is now %s years old!!!", $1, $3);}

        ;

        %%

附加 C 代碼

現(xiàn)在讓我們看一下語法文件的最后一段，附加 C 代碼。（這一段是可選的，如果有人想要略過它的話：）一個函數(shù)如 main() 調(diào)用 yyparse() 函數(shù)（Yacc 中 Lex 的 yylex() 等效函數(shù)）。 一般來說，Yacc 最好提供 yyerror(char msg) 函數(shù)的代碼。 當(dāng)解析器遇到錯誤時調(diào)用 yyerror(char msg)。錯誤消息作為參數(shù)來傳遞。一個簡單的 yyerror( char* ) 可能是這樣的：

       int yyerror(char* msg)

        {

        printf("Error: %s

        encountered at line number:%d\n", msg, yylineno);

        }

yylineno 提供了行數(shù)信息。

這一段還包括文件解析例子的主函數(shù)：

附加 C 代碼

       void main()

        {

            yyparse();

        }

        int yyerror(char* msg)

        {

        printf("Error: %s

        encountered \n", msg);

要生成代碼，可能用到以下命令：

       $ yacc _d <filename.y>

這生成了輸出文件 y.tab.h 和 y.tab.c，它們可以用 UNIX 上的任何標(biāo)準(zhǔn) C 編譯器來編譯（如 gcc）。

命令行的其他常用選項

• '-d' ,'--defines' : 編寫額外的輸出文件，它們包含這些宏定義：語法中定義的標(biāo)記類型名稱，語義的取值類型 YYSTYPE, 以及一些外部變量聲明。如果解析器輸出文件名叫 'name.c', 那么 '-d' 文件就叫做 'name.h'。 如果你想將 yylex 定義放到獨立的源文件中，你需要 'name.h', 因為 yylex 必須能夠引用標(biāo)記類型代碼和 yylval變量。
• '-b file-prefix' ,'--file-prefix=prefix' : 指定一個所有Yacc輸出文件名都可以使用的前綴。選擇一個名字，就如輸入文件名叫 'prefix.c'.
• '-o outfile' ,'--output-file=outfile' : 指定解析器文件的輸出文件名。其他輸出文件根據(jù) '-d' 選項描述的輸出文件來命名。

Yacc 庫通常在編譯步驟中自動被包括。但是它也能被顯式的包括，以便在編譯步驟中指定 ?ly選項。這種情況下的編譯命令行是：

       $ cc <source file

        names> -ly

將 Lex 與 Yacc 結(jié)合起來

到目前為止我們已經(jīng)分別討論了 Lex 和 Yacc。現(xiàn)在讓我們來看一下他們是怎樣結(jié)合使用的。

一個程序通常在每次返回一個標(biāo)記時都要調(diào)用 yylex() 函數(shù)。只有在文件結(jié)束或者出現(xiàn)錯誤標(biāo)記時才會終止。

一個由 Yacc 生成的解析器調(diào)用 yylex() 函數(shù)來獲得標(biāo)記。 yylex() 可以由 Lex 來生成或完全由自己來編寫。 對于由 Lex 生成的 lexer 來說，要和 Yacc 結(jié)合使用，每當(dāng) Lex 中匹配一個模式時都必須返回一個標(biāo)記。 因此 Lex 中匹配模式時的動作一般格式為：

       {pattern} { /* do smthg*/

        return TOKEN_NAME; }

于是 Yacc 就會獲得返回的標(biāo)記。當(dāng) Yacc 編譯一個帶有 _d 標(biāo)記的 .y文件時，會生成一個頭文件，它對每個標(biāo)記都有 #define 的定義。 如果 Lex 和 Yacc 一起使用的話，頭文件必須在相應(yīng)的 Lex 文件 .lex中的 C 聲明段中包括。

讓我們回到名字和年齡的文件解析例子中，看一看 Lex 和 Yacc 文件的代碼。

Name.y - 語法文件

       %

        typedef char* string;

        #define YYSTYPE string

        %}

        %token NAME EQ AGE

        %%

        file : record file

        | record

        ;

        record : NAME EQ AGE {

        printf("%s is %s years old!!!\n", $1, $3); }

        ;

        %%

        int main()

        {

        yyparse();

        return 0;

        }

        int yyerror(char *msg)

        {

        printf("Error

        encountered: %s \n", msg);

        }

Name.lex - Lex 的解析器文件

       %{

        #include "y.tab.h"

        #include <stdio.h>

        #include <string.h>

        extern char* yylval;

        %}

        char [A-Za-z]

        num [0-9]

        eq [=]

        name {char}+

        age {num}+

        %%

        {name} { yylval = strdup(yytext);

        return NAME; }

        {eq} { return EQ; }

        {age} { yylval = strdup(yytext);

        return AGE; }

        %%

        int yywrap()

        {

        return 1;

        }

作為一個參考，我們列出了 y.tab.h, Yacc 生成的頭文件。

y.tab.h - Yacc 生成的頭文件

       # define NAME 257

        # define EQ 258

        # define AGE 259

我們對于 Lex 和 Yacc的討論到此為止。今天你想要編譯什么語言呢？

參考資料

• 您可以參閱本文在 developerWorks 全球站點上的 英文原文.
• Lex and Yacc, Levine, Mason 和 Branson, O?Reilly 及其合作公司，2nd Ed。
• Program Development in UNIX, J. T. Shen, Prentice-Hall India。
• Compilers: Principles, Techniques and Tools, Ahoo, Sethi 和 Ullman, Addison-Wesley Pub. Co., 1985，11。
• Lex and Yacc and compiler writing指導(dǎo)。
• Java 版的 Lex 指導(dǎo), 叫做 Jlex。
• 使用 Lex 和 Yacc 的 formalizing a grammar實例。