Lex和Yacc解釋程序實現方法

劉麗娜，楊純輝，張 靜

(1.中國電子科技集團公司第四十七研究所，沈陽110032 2.空軍駐遼寧地區軍事代表室，沈陽110034)

1 引言

計算機程序輸入通常有一些特定的結構，每一個計算機程序的輸入都會被定義成可接受的“輸入語言”。輸入語言可以是復雜的可編程語言，也可以是簡單的數字。但是，輸入工具總是會受到不同程度的限制，使用起來十分困難，而且經常是伴隨著大量的語法檢查。

Lex和Yacc可以幫助我們編寫程序轉換結構化輸入。Lex使用一系列對可能標記的描述產生一個能識別那些標記的C例程，這些描述稱為Lex規范;Yacc使用特定的語法規則解釋Lex得到的標記并且生成一棵語法樹，語法樹把各種標記當作分級結構，生成編譯器原代碼，對語法樹進行深度遍歷生成原代碼。

2 Lex和Yacc語法規則介紹

2.1 Lex語法規則

Lex使用的技術是有限狀態自動機(FSA)，它包括一個開始狀態以及一個或多個結束狀態或接受狀態。Lex把正則表達式翻譯成模擬FSA的一個計算機程序。它使正則表達式匹配輸入的字符串并且把它們轉換成對應的標記，標記通常是代表字符串或簡單過程的數值。

在圖1中，狀態0是開始狀態，狀態2是接受狀態。當讀入字符時，狀態機就進行狀態轉換。當讀入第一個字母時，程序就轉換到狀態1，如果后面讀入的也是字母或數字，程序就繼續保持在狀態1;如果讀入的字符不是字母或數字，程序就轉換到狀態2，即接受狀態。每一個FSA都表現為一個計算機程序。

圖1 有限狀態自動機

通常，Lex上的每個字符串對應一個動作，動作返回一個代表被匹配的字符串的標記給后面的剖析器(Yacc)使用。Lex的輸入文件分成三個段，段間用%%來分隔。

－－－－－－定義－－－－－－

%%

－－－－－－規則－－－－－－

%%

－－－－－－子程序－－－－－－

規則段是必須存在的，如果我們不指定任何規則，默認動作就是匹配任意字符然后直接輸出到輸出文件。默認的輸入文件和輸出文件分別是stdin和stdout。當Lex讀完輸入文件后就會調用函數yywrap。如果返回1表示程序的工作已經完成，否則返回0。yylex是Lex掃描器的入口。

下面的例子是使用Lex實現字數統計的Lex定義:

%{

int wordCount=0;

int number=0;

int w_space=0;

%}

chars［A －za－z—’。”］

numbers(［0－9］)+

delim［"" ］

whitespace{delim}+

words{chars}+

%%

接下來就是Lex規則的實現:

{words}{wordCount++;}

{whitespace}{w_space++;}

{numbers}{number++;}

%%

最后一段就是C代碼的實現:

void main()

{

yylex();

printf("No.of words:%d "，wordCount);

}

int yywrap()

{

return 1;

}

2.2 Yacc語法規則

Yacc為描述計算機程序的輸入提供了通用的工具，它是基于BNF(Backus－Naur form)文法規則的。Yacc的內部有兩個棧，一個分析棧和一個內容棧。分析棧中保存著終結符和非終結符，并且代表當前剖析狀態;內容棧是一個YYSTYPE元素的數組，對應于分析棧中每一個元素保存的值。

Yacc程序實際上是有關語法規則的說明書，它也是由定義部分、規則部分和子程序三部分組成的。Yacc程序的定義部分類似于Lex程序的定義部分，只是在其后可帶有Yacc聲明，其中包括詞法單詞、語法變量、優先級和結合性信息;規則部分由語法規則和相應的動作組成;子程序部分可以包括在前面規則部分用到的子程序定義。接下來是main主程序，它調用yyparse子程序來對輸入進行語法分析，yyparse反復地調用yylex子程序來獲得輸入單詞，在語法出錯時可通過yyerror子程序來處理，當Yacc發現一個解析錯誤時，默認動作是調用yyerror，然后從yylex中返回一個值或1。

下面的例子是使用Yacc實現網表分析的Yacc定義:

變量定義部分:

%{

char*version;

%}

%token EDIF EDIFVERSION

%start edif

%%

規則部分:

edif:EDIF edifVersion{"Edif Version is"%s，version};

%%

子程序部分:

#include"lex.yy.c"

void parse()

{

yyparse();

}

3 Lex和Yacc的調試過程

Lex有很多方便調試的工具，不同版本的Lex其特征可能各不相同。通常的調用方法如下:$lex＜filename.lex＞，通過命令行參數“－d”，Lex會在 lex.yy.c中生成調試狀態，通過設置變量yy_flex_debug可以打開或關閉flex中調試信息的輸出;“－t”寫入lex.yy.c程序來代替標準輸出;“－v”提供一個兩行的統計匯總;“－n”不打印－v的匯總。輸出信息包括應用規則和相應的匹配文字。如果Lex和Yacc一起使用，需要在Yacc輸入文件中增加下面的代碼:

extern int yy_flex_debug;

int main(void){

yy_flex_debug=1;

yyprase();}

Yacc允許包含有調試的工具，這個特性可能隨Yacc版本的不同而不同。通常的調用方法如下:$yacc_d ＜filename.y＞。通過定義YYDEBUG并且把它設置成非零值，Yacc就會在y.tab.c中生成調試狀態代碼，這也需要在命令行指定參數“－t”。如果設置了YYDEBUG，通過設置yydebug可以打開或者關閉調試信息的輸出;命令行參數“－v”保存剖析狀態，狀態保存在文件y.output中。

#define YYDEBUG 1

%%

int main(void){

#if YYDEBUG

yydebug=1;

#endif

yylex();}

圖2顯示了Lex和Yacc使用的整個流程，首先指定Lex所有的模式匹配規則(bas.l)和Yacc的全部語法規則(bas.y)，然后對這兩個文件進行編譯，最后將這兩個文件連接起來，組成可執行程序bas.exe。

Yacc讀入bas.y中的語法描述后生成一個剖析器，即 y.tab.c 中的函數 yyparse，bas.y 中包含的是一系列的標記聲明。Lex讀入bas.l中正則表達式的說明，包含文件y.tab.h，然后生成詞匯解釋器，即文件lex.yy.c中的函數yylex。最后這個解釋器和剖析器被連接到一起組成一個可執行程序bas.exe。

圖2 由Lex和Yacc構建的編譯器

4 結束語

Lex和Yacc工具的出現，大大簡化了編寫編譯器的工作，使用Lex和Yacc無論是構建程序的一部分，還是構建輔助編程的工具，都是方便有效的，是目前UNIX系統上使用的重要的、功能強大的工具。

［1］呂映芝，張素琴，蔣維杜，等.編譯原理［M］.北京:清華大學出版社，1998.

［2］John R.Levine，Tony Mason 著.Lex與 Yacc［M］.楊作梅，張旭東，等譯.北京:機械工業出版社，2003.