Lex和Yacc解釋程序?qū)崿F(xiàn)方法

劉麗娜，楊純輝，張 靜

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

1 引言

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

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

2 Lex和Yacc語法規(guī)則介紹

2.1 Lex語法規(guī)則

Lex使用的技術(shù)是有限狀態(tài)自動機(jī)(FSA)，它包括一個開始狀態(tài)以及一個或多個結(jié)束狀態(tài)或接受狀態(tài)。Lex把正則表達(dá)式翻譯成模擬FSA的一個計算機(jī)程序。它使正則表達(dá)式匹配輸入的字符串并且把它們轉(zhuǎn)換成對應(yīng)的標(biāo)記，標(biāo)記通常是代表字符串或簡單過程的數(shù)值。

在圖1中，狀態(tài)0是開始狀態(tài)，狀態(tài)2是接受狀態(tài)。當(dāng)讀入字符時，狀態(tài)機(jī)就進(jìn)行狀態(tài)轉(zhuǎn)換。當(dāng)讀入第一個字母時，程序就轉(zhuǎn)換到狀態(tài)1，如果后面讀入的也是字母或數(shù)字，程序就繼續(xù)保持在狀態(tài)1;如果讀入的字符不是字母或數(shù)字，程序就轉(zhuǎn)換到狀態(tài)2，即接受狀態(tài)。每一個FSA都表現(xiàn)為一個計算機(jī)程序。

圖1 有限狀態(tài)自動機(jī)

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

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

%%

－－－－－－規(guī)則－－－－－－

%%

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

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

下面的例子是使用Lex實(shí)現(xiàn)字?jǐn)?shù)統(tǒng)計的Lex定義:

%{

int wordCount=0;

int number=0;

int w_space=0;

%}

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

numbers(［0－9］)+

delim［"" ］

whitespace{delim}+

words{chars}+

%%

接下來就是Lex規(guī)則的實(shí)現(xiàn):

{words}{wordCount++;}

{whitespace}{w_space++;}

{numbers}{number++;}

%%

最后一段就是C代碼的實(shí)現(xiàn):

void main()

{

yylex();

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

}

int yywrap()

{

return 1;

}

2.2 Yacc語法規(guī)則

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

Yacc程序?qū)嶋H上是有關(guān)語法規(guī)則的說明書，它也是由定義部分、規(guī)則部分和子程序三部分組成的。Yacc程序的定義部分類似于Lex程序的定義部分，只是在其后可帶有Yacc聲明，其中包括詞法單詞、語法變量、優(yōu)先級和結(jié)合性信息;規(guī)則部分由語法規(guī)則和相應(yīng)的動作組成;子程序部分可以包括在前面規(guī)則部分用到的子程序定義。接下來是main主程序，它調(diào)用yyparse子程序來對輸入進(jìn)行語法分析，yyparse反復(fù)地調(diào)用yylex子程序來獲得輸入單詞，在語法出錯時可通過yyerror子程序來處理，當(dāng)Yacc發(fā)現(xiàn)一個解析錯誤時，默認(rèn)動作是調(diào)用yyerror，然后從yylex中返回一個值或1。

下面的例子是使用Yacc實(shí)現(xiàn)網(wǎng)表分析的Yacc定義:

變量定義部分:

%{

char*version;

%}

%token EDIF EDIFVERSION

%start edif

%%

規(guī)則部分:

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

%%

子程序部分:

#include"lex.yy.c"

void parse()

{

yyparse();

}

3 Lex和Yacc的調(diào)試過程

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

extern int yy_flex_debug;

int main(void){

yy_flex_debug=1;

yyprase();}

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

#define YYDEBUG 1

%%

int main(void){

#if YYDEBUG

yydebug=1;

#endif

yylex();}

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

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

圖2 由Lex和Yacc構(gòu)建的編譯器

4 結(jié)束語

Lex和Yacc工具的出現(xiàn)，大大簡化了編寫編譯器的工作，使用Lex和Yacc無論是構(gòu)建程序的一部分，還是構(gòu)建輔助編程的工具，都是方便有效的，是目前UNIX系統(tǒng)上使用的重要的、功能強(qiáng)大的工具。

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

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