close

Lex 與 Yacc 介紹

Ashish Bansal
軟體工程師, Sapient 公司
2000 年 11 月

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

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

Lex
Lex 是一種生成掃瞄器的工具。掃瞄器是一種識別文本中的辭彙模式的程式。 這些辭彙模式（或者常規運算式）在一種特殊的句子結構中定義，這個我們一會兒就要討論。

一種匹配的常規運算式可能會包含相關的動作。這一動作可能還包括返回一個標記。 當 Lex 接收到檔或文本形式的輸入時，它試圖將文本與常規運算式進行匹配。 它一次讀入一個輸入字元，直到找到一個匹配的模式。 如果能夠找到一個匹配的模式，Lex 就執行相關的動作（可能包括返回一個標記）。 另一方面，如果沒有可以匹配的常規運算式，將會停止進一步的處理，Lex 將顯示一個錯誤消息。

Lex 和 C 是強耦合的。一個 .lex 檔（Lex 檔具有 .lex 的副檔名）通過 lex 公用程式來傳遞，並生成 C 的輸出檔。這些檔被編譯為詞法分析器的可執行版本。

Lex 的常規運算式
常規運算式是一種使用元語言的模式描述。運算式由符號組成。符號一般是字元和數位，但是 Lex 中還有一些具有特殊含義的其他標記。 下面兩個表格定義了 Lex 中使用的一些標記並給出了幾個典型的例子。

用 Lex 定義常規運算式

字元

含義

A-Z, 0-9, a-z

構成了部分模式的字元和數位。

.

匹配任意字元，除了 n。

-

用來指定範圍。例如：A-Z 指從 A 到 Z 之間的所有字元。

[ ]

一個字元集合。匹配括弧內的 任意 字元。如果第一個字元是 ^ 那麼它表示否定模式。例如: [abC] 匹配 a, b, 和 C中的任何一個。

*

匹配 0個或者多個上述的模式。

+

匹配 1個或者多個上述模式。

?

匹配 0個或1個上述模式。

$

作為模式的最後一個字元匹配一行的結尾。

{ }

指出一個模式可能出現的次數。 例如: A{1,3} 表示 A 可能出現1次或3次。

用來轉義元字元。同樣用來覆蓋字元在此表中定義的特殊意義，只取字元的本意。

^

否定。

|

運算式間的邏輯或。

"<一些符號>"

字元的字面含義。元字元具有。

/

向前匹配。如果在匹配的模版中的「/」後跟有後續運算式，只匹配模版中「/」前 面的部分。如：如果輸入 A01，那麼在模版 A0/1 中的 A0 是匹配的。

( )

將一系列常規運算式分組。

常規運算式舉例

常規運算式

含義

joke[rs]

匹配 jokes 或 joker。

A{1,2}shis+

匹配 AAshis, Ashis, AAshi, Ashi。

(A[b-e])+

匹配在 A 出現位置後跟隨的從 b 到 e 的所有字元中的 0 個或 1個。

Lex 中的標記聲明類似 C 中的變數名。每個標記都有一個相關的運算式。 （下表中給出了標記和運算式的例子。） 使用這個表中的例子，我們就可以編一個字數統計的程式了。 我們的第一個任務就是說明如何聲明標記。

標記聲明舉例

標記

相關運算式

含義

數字(number)

([0-9])+

1個或多個數字

字元(chars)

[A-Za-z]

任意字元

空格(blank)

" "

一個空格

字(word)

(chars)+

1個或多個 chars

變數(variable)

(字元)+(數位)*(字元)*(數位)*

 

Lex 編程
Lex 編程可以分為三步：

  1. 以 Lex 可以理解的格式指定模式相關的動作。

  2. 在這一檔上運行 Lex，生成掃瞄器的 C 代碼。

  3. 編譯和鏈結 C 代碼，生成可執行的掃瞄器。

注意: 如果掃瞄器是用 Yacc 開發的解析器的一部分，只需要進行第一步和第二步。 關於這一特殊問題的幫助請閱讀 Yacc和 將 Lex 和 Yacc 結合起來部分。

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

C 和 Lex 的全局聲明
這一段中我們可以增加 C 變數聲明。這裡我們將為字數統計程式聲明一個整型變數，來保存程式統計出來的字數。 我們還將進行 Lex 的標記聲明。

字數統計程式的聲明

 

 %{

 int wordCount = 0;

 %}

 chars [A-za-z_'."]

 numbers ([0-9])+

 delim [" "nt]

 whitespace {delim}+

 words {chars}+

 %%

 

兩個百分號標記指出了 Lex 程式中這一段的結束和三段中第二段的開始。

Lex 的模式匹配規則
讓我們看一下 Lex 描述我們所要匹配的標記的規則。（我們將使用 C 來定義標記匹配後的動作。） 繼續看我們的字數統計程式，下面是標記匹配的規則。

字數統計程式中的 Lex 規則

 

 {words} { wordCount++; /*

 increase the word count by one*/ }

 

 {whitespace} { /* do

 nothing*/ }

 

  {numbers} { /* one may

 want to add some processing here*/ }

 

  %%

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

字數統計程式的 C 代碼段

 

 void main()

 

 {

 

 yylex(); /* start the

 analysis*/

 

 printf(" No of words:

 %dn", wordCount);

 

 }

 

 int yywrap()

 

 {

 

 return 1;

 

 }

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

將它們全部結合起來
.lex檔是 Lex 的掃瞄器。它在 Lex 程式中如下表示：

 

 $ lex

這生成了 lex.yy.c 檔，它可以用 C 編譯器來進行編譯。它還可以用解析器來生成可執行程式，或者在鏈結步驟中通過選項 �ll 包含 Lex 庫。

這裡是一些 Lex 的標誌：

  • -c表示 C 動作，它是缺省的。

  • -t寫入 lex.yy.c 程式來代替標準輸出。

  • -v提供一個兩行的統計彙總。

  • -n不列印 -v 的彙總。

高級 Lex
Lex 有幾個函數和變數提供了不同的資訊，可以用來編譯實現複雜函數的程式。 下表中列出了一些變數和函數，以及它們的使用。 詳盡的列表請參考 Lex 或 Flex 手冊（見後文的 資源）。

Lex 變數

yyin

FILE* 類型。 它指向 lexer 正在解析的當前文件。

yyout

FILE* 類型。 它指向記錄 lexer 輸出的位置。 缺省情況下，yyin 和 yyout 都指向標準輸入和輸出。

yytext

匹配模式的文本存儲在這一變數中（char*）。

yyleng

給出匹配模式的長度。

yylineno

提供當前的行數資訊。 （lexer不一定支持。）

Lex 函數

yylex()

這一函數開始分析。 它由 Lex 自動生成。

yywrap()

這一函數在檔（或輸入）的末尾調用。 如果函數的返回值是1，就停止解析。 因此它可以用來解析多個檔。 代碼可以寫在第三段，這就能夠解析多個檔。 方法是使用 yyin 檔指標（見上表）指向不同的檔，直到所有的檔都被解析。 最後，yywrap() 可以返回 1 來表示解析的結束。

yyless(int n)

這一函數可以用來送回除了前�n? 個字元外的所有讀出標記。

yymore()

這一函數告訴 Lexer 將下一個標記附加到當前標記後。

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

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

 

 $ yacc

 

在進一步闡述以前，讓我們複習一下什麼是語法。在上一節中，我們看到 Lex 從輸入序列中識別標記。 如果你在查看標記序列，你可能想在這一序列出現時執行某一動作。 這種情況下有效序列的規範稱為語法。Yacc 語法檔包括這一語法規範。 它還包含了序列匹配時你想要做的事。

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

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

終端和非終端符號
終端符號 : 代表一類在語法結構上等效的標記。 終端符號有三種類型：

命名標記: 這些由 %token 識別字來定義。 按照慣例，它們都是大寫。

字元標記 : 字元常量的寫法與 C 相同。例如, -- 就是一個字元標記。

字串標記 : 寫法與 C 的字串常量相同。例如，"<<" 就是一個字串標記。

lexer 返回命名標記。

非終端符號 : 是一組非終端符號和終端符號組成的符號。 按照慣例，它們都是小寫。 在例子中，file 是一個非終端標記而 NAME 是一個終端標記。

用 Yacc 來創建一個編譯器包括四個步驟：

  1. 通過在語法檔上運行 Yacc 生成一個解析器。

  2. 說明語法：

  • 編寫一個 .y 的語法檔（同時說明 C 在這裡要進行的動作）。

  • 編寫一個詞法分析器來處理輸入並將標記傳遞給解析器。 這可以使用 Lex 來完成。

  • 編寫一個函數，通過調用 yyparse() 來開始解析。

  • 編寫錯誤處理常式（如 yyerror()）。

  • 編譯 Yacc 生成的代碼以及其他相關的原始檔案。

  • 將目標檔鏈結到適當的可執行解析器庫。

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

    C 與 Yacc 的聲明
    C     聲明可能會定義動作中使用的類型和變數，以及巨集。 還可以包含頭檔。每個 Yacc 聲明段聲明了終端符號和非終端符號（標記）的名稱，還可能描述操作符優先順序和針對不同符號的資料類型。 lexer (Lex) 一般返回這些標記。所有這些標記都必須在 Yacc 聲明中進行說明。

    在檔解析的例子中我們感興趣的是這些標記：name, equal sign, 和 age。Name 是一個完全由字元組成的值。 Age 是數字。於是聲明段就會像這樣：

    檔解析例子的聲明

     

     %

     

     #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 也有一套變數和函數可供用戶來進行功能擴展。 YYSTYPE 定義了用來將值從 lexer 拷貝到解析器或者 Yacc 的 yylval （另一個 Yacc 變數）的類型。 默認的類型是 int。 由於字串可以從 lexer 拷貝，類型被重定義為 char*。 關於 Yacc 變數的詳細討論，請參考 Yacc 手冊（見 資源）。

    Yacc 語法規則
    Yacc     語法規則具有以下一般格式：

     

     result: components { /*

     action to be taken in C */ }

     

     ;

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

     

     param : NAME EQ NAME {

     printf("tName:%stValue(name):%sn", $1,$3);}

     

     | NAME EQ VALUE{

      printf("tName:%stValue(value):%sn",$1,$3);}

     

     ;

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

     

     char [A-Za-z]

     

     name {char}+

     

     %%

     

     {name} { yylval = strdup(yytext);

     return NAME; }

    檔解析例子的規則段是這樣的：

    檔解析的語法

     

     file : record file

     

     

     | record

     

     ;

     

     record: NAME EQ AGE {

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

     

     ;

     

     %%

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

     

     int yyerror(char* msg)

     

     {

     

     printf("Error: %s

     encountered at line number:%dn", msg, yylineno);

     

     }

    yylineno 提供了行數資訊。

    這一段還包括檔解析例子的主函數：

    附加 C 代碼

     

     void main()

     

      {

     

     yyparse();

     

     }

     

     int yyerror(char* msg)

     

     {

     

     printf("Error: %s

     encountered n", msg);

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

     

     $ yacc _d

    這生成了輸出檔 y.tab.h 和 y.tab.c，它們可以用 UNIX 上的任何標準 C 編譯器來編譯（如 gcc）。

    命令行的其他常用選項

    • '-d' ,'--defines' : 編寫額外的輸出檔，它們包含這些巨集定義：語法中定義的標記類型名稱，語義的取值類型 YYSTYPE, 以及一些外部變數聲明。如果解析器輸出檔案名叫 'name.c', 那麼 '-d' 檔就叫做 'name.h'。 如果你想將 yylex 定義放到獨立的原始檔案中，你需要 'name.h', 因為 yylex 必須能夠引用標記類型代碼和 yylval變數。

    • '-b file-prefix' ,'--file-prefix=prefix' : 指定一個所有Yacc輸出檔案名都可以使用的首碼。選擇一個名字，就如輸入檔案名叫 'prefix.c'.

    • '-o outfile' ,'--output-file=outfile' : 指定解析器檔的輸出檔案名。其他輸出檔根據 '-d' 選項描述的輸出檔來命名。

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

     

     $ cc

     names> -ly

    將 Lex 與 Yacc 結合起來
    到目前為止我們已經分別討論了 Lex 和 Yacc。現在讓我們來看一下他們是怎樣結合使用的。

    一個程式通常在每次返回一個標記時都要調用 yylex() 函數。只有在檔結束或者出現錯誤標記時才會終止。

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

     

     {pattern} { /* do smthg*/

     return TOKEN_NAME; }

    於是 Yacc 就會獲得返回的標記。當 Yacc 編譯一個帶有 _d 標記的 .y檔時，會生成一個頭檔，它對每個標記都有 #define 的定義。 如果 Lex 和 Yacc 一起使用的話，頭檔必須在相應的 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

     

     #include

     

     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的討論到此為止。今天你想要編譯什麼語言呢？

    參考資料

    arrow
    arrow
      全站熱搜
      創作者介紹
      創作者 Bluelove1968 的頭像
      Bluelove1968

      藍色情懷

      Bluelove1968 發表在 痞客邦 留言(0) 人氣()

      E-mail轉寄