Lex 與 Yacc 介紹
Ashish Bansal (
abansal@ieee.org), 軟件工程師, Sapient 公司
2000 年 11 月 01 日
Lex和 Yacc 是 UNIX 兩個(gè)非常重要的、功能強(qiáng)大的工具。事實(shí)上，如果你熟練掌握 Lex 和 Yacc 的話，它們的強(qiáng)大功能使創(chuàng)建FORTRAN 和 C 的編譯器如同兒戲。Ashish Bansal為您詳細(xì)的討論了編寫自己的語言和編譯器所用到的這兩種工具，包括常規(guī)表達(dá)式、聲明、匹配模式、變量、Yacc語法和解析器代碼。最后，他解釋了怎樣把 Lex 和 Yacc 結(jié)合起來。
Lex 代表 Lexical Analyzar。Yacc 代表 Yet Another CompilerCompiler。 讓我們從 Lex 開始吧。
Lex是一種生成掃描器的工具。掃描器是一種識(shí)別文本中的詞匯模式的程序。這些詞匯模式（或者常規(guī)表達(dá)式）在一種特殊的句子結(jié)構(gòu)中定義，這個(gè)我們一會(huì)兒就要討論。
一種匹配的常規(guī)表達(dá)式可能會(huì)包含相關(guān)的動(dòng)作。這一動(dòng)作可能還包括返回一個(gè)標(biāo)記。當(dāng) Lex接收到文件或文本形式的輸入時(shí)，它試圖將文本與常規(guī)表達(dá)式進(jìn)行匹配。它一次讀入一個(gè)輸入字符，直到找到一個(gè)匹配的模式。如果能夠找到一個(gè)匹配的模式，Lex就執(zhí)行相關(guān)的動(dòng)作（可能包括返回一個(gè)標(biāo)記）。另一方面，如果沒有可以匹配的常規(guī)表達(dá)式，將會(huì)停止進(jìn)一步的處理，Lex將顯示一個(gè)錯(cuò)誤消息。
Lex 和 C 是強(qiáng)耦合的。一個(gè).lex 文件（Lex 文件具有.lex 的擴(kuò)展名）通過 lex 公用程序來傳遞，并生成 C的輸出文件。這些文件被編譯為詞法分析器的可執(zhí)行版本。
回頁首常規(guī)表達(dá)式是一種使用元語言的模式描述。表達(dá)式由符號(hào)組成。符號(hào)一般是字符和數(shù)字，但是Lex 中還有一些具有特殊含義的其他標(biāo)記。 下面兩個(gè)表格定義了 Lex中使用的一些標(biāo)記并給出了幾個(gè)典型的例子。
字符 含義
A-Z, 0-9, a-z 構(gòu)成了部分模式的字符和數(shù)字。
. 匹配任意字符，除了 \n。
- 用來指定范圍。例如：A-Z 指從 A 到 Z 之間的所有字符。
[ ] 一個(gè)字符集合。匹配括號(hào)內(nèi)的 任意 字符。如果第一個(gè)字符是 ^ 那么它表示否定模式。例如: [abC] 匹配 a, b, 和 C中的任何一個(gè)。
* 匹配 0個(gè)或者多個(gè)上述的模式。
+ 匹配 1個(gè)或者多個(gè)上述模式。
匹配 0個(gè)或1個(gè)上述模式。
$ 作為模式的最后一個(gè)字符匹配一行的結(jié)尾。
{ } 指出一個(gè)模式可能出現(xiàn)的次數(shù)。 例如: A{1,3} 表示 A 可能出現(xiàn)1次或3次。
\ 用來轉(zhuǎn)義元字符。同樣用來覆蓋字符在此表中定義的特殊意義，只取字符的本意。
^ 否定。
| 表達(dá)式間的邏輯或。
"<一些符號(hào)>" 字符的字面含義。元字符具有。
/ 向前匹配。如果在匹配的模版中的“/”后跟有后續(xù)表達(dá)式，只匹配模版中“/”前 面的部分。如：如果輸入 A01，那么在模版 A0/1 中的 A0 是匹配的。
( ) 將一系列常規(guī)表達(dá)式分組。
常規(guī)表達(dá)式 含義
joke[rs] 匹配 jokes 或 joker。
A{1,2}shis+ 匹配 AAshis, Ashis, AAshi, Ashi。
(A[b-e])+ 匹配在 A 出現(xiàn)位置后跟隨的從 b 到 e 的所有字符中的 0 個(gè)或 1個(gè)。
Lex 中的標(biāo)記聲明類似 C中的變量名。每個(gè)標(biāo)記都有一個(gè)相關(guān)的表達(dá)式。（下表中給出了標(biāo)記和表達(dá)式的例子。）使用這個(gè)表中的例子，我們就可以編一個(gè)字?jǐn)?shù)統(tǒng)計(jì)的程序了。我們的第一個(gè)任務(wù)就是說明如何聲明標(biāo)記。
標(biāo)記 相關(guān)表達(dá)式 含義
數(shù)字(number) ([0-9])+ 1個(gè)或多個(gè)數(shù)字
字符(chars) [A-Za-z] 任意字符
空格(blank) " " 一個(gè)空格
字(word) (chars)+ 1個(gè)或多個(gè) chars
變量(variable) (字符)+(數(shù)字)*(字符)*(數(shù)字)*
回頁首Lex 編程可以分為三步：
以 Lex 可以理解的格式指定模式相關(guān)的動(dòng)作。
在這一文件上運(yùn)行 Lex，生成掃描器的 C 代碼。
編譯和鏈接 C 代碼，生成可執(zhí)行的掃描器。
注意: 如果掃描器是用 Yacc開發(fā)的解析器的一部分，只需要進(jìn)行第一步和第二步。關(guān)于這一特殊問題的幫助請(qǐng)閱讀
Yacc和
將 Lex 和 Yacc 結(jié)合起來部分。
現(xiàn)在讓我們來看一看 Lex 可以理解的程序格式。一個(gè) Lex程序分為三個(gè)段：第一段是 C 和 Lex 的全局聲明，第二段包括模式（C代碼），第三段是補(bǔ)充的 C 函數(shù)。 例如, 第三段中一般都有 main()函數(shù)。這些段以%%來分界。 那么，回到字?jǐn)?shù)統(tǒng)計(jì)的 Lex程序，讓我們看一下程序不同段的構(gòu)成。
回頁首這一段中我們可以增加 C變量聲明。這里我們將為字?jǐn)?shù)統(tǒng)計(jì)程序聲明一個(gè)整型變量，來保存程序統(tǒng)計(jì)出來的字?jǐn)?shù)。我們還將進(jìn)行 Lex 的標(biāo)記聲明。
%{
int wordCount = 0;
%}
chars [A-za-z\_\‘\.\"]
numbers ([0-9])+
delim [" "\n\t]
whitespace {delim}+
words {chars}+
%%
兩個(gè)百分號(hào)標(biāo)記指出了 Lex程序中這一段的結(jié)束和三段中第二段的開始。
回頁首讓我們看一下 Lex 描述我們所要匹配的標(biāo)記的規(guī)則。（我們將使用 C來定義標(biāo)記匹配后的動(dòng)作。）繼續(xù)看我們的字?jǐn)?shù)統(tǒng)計(jì)程序，下面是標(biāo)記匹配的規(guī)則。
{words} { wordCount++; /*
increase the word count by one*/ }
{whitespace} { /* do
nothing*/ }
{numbers} { /* one may
want to add some processing here*/ }
%%
回頁首Lex 編程的第三段，也就是最后一段覆蓋了 C的函數(shù)聲明（有時(shí)是主函數(shù)）。注意這一段必須包括 yywrap() 函數(shù)。 Lex有一套可供使用的函數(shù)和變量。 其中之一就是 yywrap。一般來說，yywrap() 的定義如下例。我們將在
高級(jí) Lex中探討這一問題。
void main()
{
yylex(); /* start the
analysis*/
printf(" No of words:
%d\n", wordCount);
}
int yywrap()
{
return 1;
}
上一節(jié)我們討論了 Lex編程的基本元素，它將幫助你編寫簡(jiǎn)單的詞法分析程序。 在
高級(jí) Lex 這一節(jié)中我們將討論 Lex提供的函數(shù)，這樣你就能編寫更加復(fù)雜的程序了。
回頁首.lex文件是 Lex 的掃描器。它在 Lex 程序中如下表示：
$ lex <file name.lex>
這生成了 lex.yy.c 文件，它可以用 C編譯器來進(jìn)行編譯。它還可以用解析器來生成可執(zhí)行程序，或者在鏈接步驟中通過選項(xiàng)?ll 包含 Lex 庫。
這里是一些 Lex 的標(biāo)志：
-c表示 C 動(dòng)作，它是缺省的。
-t寫入 lex.yy.c 程序來代替標(biāo)準(zhǔn)輸出。
-v提供一個(gè)兩行的統(tǒng)計(jì)匯總。
-n不打印 -v 的匯總。
回頁首Lex有幾個(gè)函數(shù)和變量提供了不同的信息，可以用來編譯實(shí)現(xiàn)復(fù)雜函數(shù)的程序。下表中列出了一些變量和函數(shù)，以及它們的使用。 詳盡的列表請(qǐng)參考 Lex或 Flex 手冊(cè)（見后文的
資源）。
yyin FILE* 類型。 它指向 lexer 正在解析的當(dāng)前文件。
yyout FILE* 類型。 它指向記錄 lexer 輸出的位置。 缺省情況下，yyin 和 yyout 都指向標(biāo)準(zhǔn)輸入和輸出。
yytext 匹配模式的文本存儲(chǔ)在這一變量中（char*）。
yyleng 給出匹配模式的長(zhǎng)度。
yylineno 提供當(dāng)前的行數(shù)信息。 （lexer不一定支持。）
yylex() 這一函數(shù)開始分析。 它由 Lex 自動(dòng)生成。
yywrap() 這一函數(shù)在文件（或輸入）的末尾調(diào)用。 如果函數(shù)的返回值是1，就停止解析。 因此它可以用來解析多個(gè)文件。 代碼可以寫在第三段，這就能夠解析多個(gè)文件。 方法是使用 yyin 文件指針（見上表）指向不同的文件，直到所有的文件都被解析。 最后，yywrap() 可以返回 1 來表示解析的結(jié)束。
yyless(int n) 這一函數(shù)可以用來送回除了前?n? 個(gè)字符外的所有讀出標(biāo)記。
yymore() 這一函數(shù)告訴 Lexer 將下一個(gè)標(biāo)記附加到當(dāng)前標(biāo)記后。
對(duì) Lex 的討論就到這里。下面我們來討論 Yacc...
回頁首Yacc 代表 Yet Another Compiler Compiler。 Yacc 的 GNU 版叫做Bison。它是一種工具，將任何一種編程語言的所有語法翻譯成針對(duì)此種語言的Yacc 語 法解析器。它用巴科斯范式(BNF, Backus NaurForm)來書寫。按照慣例，Yacc 文件有 .y 后綴。編譯行如下調(diào)用 Yacc編譯器：
$ yacc <options>
<filename ending with .y>
在進(jìn)一步闡述以前，讓我們復(fù)習(xí)一下什么是語法。在上一節(jié)中，我們看到Lex 從輸入序列中識(shí)別標(biāo)記。如果你在查看標(biāo)記序列，你可能想在這一序列出現(xiàn)時(shí)執(zhí)行某一動(dòng)作。這種情況下有效序列的規(guī)范稱為語法。Yacc 語法文件包括這一語法規(guī)范。它還包含了序列匹配時(shí)你想要做的事。
為了更加說清這一概念，讓我們以英語為例。 這一套標(biāo)記可能是：名詞,動(dòng)詞,形容詞等等。為了使用這些標(biāo)記造一個(gè)語法正確的句子，你的結(jié)構(gòu)必須符合一定的規(guī)則。一個(gè)簡(jiǎn)單的句子可能是名詞+動(dòng)詞或者名詞+動(dòng)詞+名詞。(如 I care. Seespot run.)
所以在我們這里，標(biāo)記本身來自語言（Lex），并且標(biāo)記序列允許用 Yacc來指定這些標(biāo)記(標(biāo)記序列也叫語法)。
終端符號(hào) : 代表一類在語法結(jié)構(gòu)上等效的標(biāo)記。 終端符號(hào)有三種類型：
命名標(biāo)記: 這些由 %token 標(biāo)識(shí)符來定義。 按照慣例，它們都是大寫。
字符標(biāo)記 : 字符常量的寫法與 C 相同。例如, -- 就是一個(gè)字符標(biāo)記。
字符串標(biāo)記 : 寫法與 C 的字符串常量相同。例如，"<<" 就是一個(gè)字符串標(biāo)記。
lexer 返回命名標(biāo)記。
非終端符號(hào) : 是一組非終端符號(hào)和終端符號(hào)組成的符號(hào)。 按照慣例，它們都是小寫。 在例子中，file 是一個(gè)非終端標(biāo)記而 NAME 是一個(gè)終端標(biāo)記。
用 Yacc 來創(chuàng)建一個(gè)編譯器包括四個(gè)步驟：
通過在語法文件上運(yùn)行 Yacc 生成一個(gè)解析器。
說明語法： 編寫一個(gè) .y 的語法文件（同時(shí)說明 C 在這里要進(jìn)行的動(dòng)作）。
編寫一個(gè)詞法分析器來處理輸入并將標(biāo)記傳遞給解析器。 這可以使用 Lex 來完成。
編寫一個(gè)函數(shù)，通過調(diào)用 yyparse() 來開始解析。
編寫錯(cuò)誤處理例程（如 yyerror()）。
編譯 Yacc 生成的代碼以及其他相關(guān)的源文件。
將目標(biāo)文件鏈接到適當(dāng)?shù)目蓤?zhí)行解析器庫。
回頁首如同 Lex 一樣, 一個(gè) Yacc 程序也用雙百分號(hào)分為三段。它們是：聲明、語法規(guī)則和 C 代碼。 我們將解析一個(gè)格式為 姓名 = 年齡的文件作為例子，來說明語法規(guī)則。我們假設(shè)文件有多個(gè)姓名和年齡，它們以空格分隔。 在看 Yacc程序的每一段時(shí)，我們將為我們的例子編寫一個(gè)語法文件。
回頁首C 聲明可能會(huì)定義動(dòng)作中使用的類型和變量，以及宏。還可以包含頭文件。每個(gè) Yacc聲明段聲明了終端符號(hào)和非終端符號(hào)（標(biāo)記）的名稱，還可能描述操作符優(yōu)先級(jí)和針對(duì)不同符號(hào)的數(shù)據(jù)類型。lexer (Lex) 一般返回這些標(biāo)記。所有這些標(biāo)記都必須在 Yacc聲明中進(jìn)行說明。
在文件解析的例子中我們感興趣的是這些標(biāo)記：name, equal sign, 和age。Name 是一個(gè)完全由字符組成的值。 Age是數(shù)字。于是聲明段就會(huì)像這樣：
%
#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
%%
你可能會(huì)覺得 YYSTYPE 有點(diǎn)奇怪。但是類似 Lex, Yacc也有一套變量和函數(shù)可供用戶來進(jìn)行功能擴(kuò)展。 YYSTYPE 定義了用來將值從lexer 拷貝到解析器或者 Yacc 的 yylval （另一個(gè) Yacc 變量）的類型。默認(rèn)的類型是 int。 由于字符串可以從 lexer 拷貝，類型被重定義為char*。 關(guān)于 Yacc 變量的詳細(xì)討論，請(qǐng)參考 Yacc 手冊(cè)（見
資源）。
回頁首Yacc 語法規(guī)則具有以下一般格式：
result: components { /*
action to be taken in C */ }
;
在這個(gè)例子中，result 是規(guī)則描述的非終端符號(hào)。Components是根據(jù)規(guī)則放在一起的不同的終端和非終端符號(hào)。 如果匹配特定序列的話Components 后面可以跟隨要執(zhí)行的動(dòng)作。 考慮如下的例子：
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)的 { }括號(hào)中的動(dòng)作。 這里另一個(gè)有用的就是 $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);}
;
%%
回頁首現(xiàn)在讓我們看一下語法文件的最后一段，附加 C 代碼。（這一段是可選的，如果有人想要略過它的話：）一個(gè)函數(shù)如 main() 調(diào)用yyparse() 函數(shù)（Yacc 中 Lex 的 yylex() 等效函數(shù)）。 一般來說，Yacc最好提供 yyerror(char msg) 函數(shù)的代碼。 當(dāng)解析器遇到錯(cuò)誤時(shí)調(diào)用yyerror(char msg)。錯(cuò)誤消息作為參數(shù)來傳遞。 一個(gè)簡(jiǎn)單的 yyerror(char* ) 可能是這樣的：
int yyerror(char* msg)
{
printf("Error: %s
encountered at line number:%d\n", msg, yylineno);
}
yylineno 提供了行數(shù)信息。
這一段還包括文件解析例子的主函數(shù)：
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 定義放到獨(dú)立的源文件中，你需要 ‘name.h‘, 因?yàn)?yylex 必須能夠引用標(biāo)記類型代碼和 yylval變量。
‘-b file-prefix‘ ,‘--file-prefix=prefix‘ : 指定一個(gè)所有Yacc輸出文件名都可以使用的前綴。選擇一個(gè)名字，就如輸入文件名叫 ‘prefix.c‘.
‘-o outfile‘ ,‘--output-file=outfile‘ : 指定解析器文件的輸出文件名。其他輸出文件根據(jù) ‘-d‘ 選項(xiàng)描述的輸出文件來命名。
Yacc庫通常在編譯步驟中自動(dòng)被包括。但是它也能被顯式的包括，以便在編譯步驟中指定ly選項(xiàng)。這種情況下的編譯命令行是：
$ cc <source file
names> -ly
回頁首到目前為止我們已經(jīng)分別討論了 Lex 和Yacc?，F(xiàn)在讓我們來看一下他們是怎樣結(jié)合使用的。
一個(gè)程序通常在每次返回一個(gè)標(biāo)記時(shí)都要調(diào)用yylex()函數(shù)。只有在文件結(jié)束或者出現(xiàn)錯(cuò)誤標(biāo)記時(shí)才會(huì)終止。
一個(gè)由 Yacc 生成的解析器調(diào)用yylex()函數(shù)來獲得標(biāo)記。yylex() 可以由 Lex來生成或完全由自己來編寫。 對(duì)于由 Lex 生成的 lexer 來說，要和 Yacc結(jié)合使用，每當(dāng) Lex 中匹配一個(gè)模式時(shí)都必須返回一個(gè)標(biāo)記。 因此 Lex中匹配模式時(shí)的動(dòng)作一般格式為：
{pattern} { /* do smthg*/
return TOKEN_NAME; }
于是 Yacc 就會(huì)獲得返回的標(biāo)記。當(dāng) Yacc 編譯一個(gè)帶有 _d 標(biāo)記的.y文件時(shí)，會(huì)生成一個(gè)頭文件，它對(duì)每個(gè)標(biāo)記都有#define的定義。 如果 Lex 和 Yacc 一起使用的話，頭文件必須在相應(yīng)的 Lex 文件.lex中的 C 聲明段中包括。
讓我們回到名字和年齡的文件解析例子中，看一看 Lex 和 Yacc文件的代碼。
%
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);
}
%{
#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;
}
作為一個(gè)參考，我們列出了y.tab.h, Yacc 生成的頭文件。
# define NAME 257
# define EQ 258
# define AGE 259
我們對(duì)于 Lex 和Yacc的討論到此為止。今天你想要編譯什么語言呢？
您可以參閱本文在 developerWorks 全球站點(diǎn)上的
英文原文.
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實(shí)例。
Ashish Bansal 具有印度瓦臘納西 Banaras Hindu 大學(xué)技術(shù)學(xué)院的電子與通信工程學(xué)士學(xué)位。 他目前是 Sapient 公司的軟件工程師。他的Email是
abansal@sapient.com。
