劉麗娜，楊純輝，張 靜

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

1 引言

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

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

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

2.1 Lex語(yǔ)法規(guī)則

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

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

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

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

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

%%

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

%%

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

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

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

%{

int wordCount=0;

int number=0;

int w_space=0;

%}

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

numbers(［0－9］)+

delim［"" ］

whitespace{delim}+

words{chars}+

%%

接下來(lái)就是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語(yǔ)法規(guī)則

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

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

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

extern int yy_flex_debug;

int main(void){

yy_flex_debug=1;

yyprase();}

Yacc允許包含有調(diào)試的工具，這個(gè)特性可能隨Yacc版本的不同而不同。通常的調(diào)用方法如下:$yacc_d ＜filename.y＞。通過(guò)定義YYDEBUG并且把它設(shè)置成非零值，Yacc就會(huì)在y.tab.c中生成調(diào)試狀態(tài)代碼，這也需要在命令行指定參數(shù)“－t”。如果設(shè)置了YYDEBUG，通過(guò)設(shè)置yydebug可以打開(kāi)或者關(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使用的整個(gè)流程，首先指定Lex所有的模式匹配規(guī)則(bas.l)和Yacc的全部語(yǔ)法規(guī)則(bas.y)，然后對(duì)這兩個(gè)文件進(jìn)行編譯，最后將這兩個(gè)文件連接起來(lái)，組成可執(zhí)行程序bas.exe。

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

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

4 結(jié)束語(yǔ)

Lex和Yacc工具的出現(xiàn)，大大簡(jiǎn)化了編寫編譯器的工作，使用Lex和Yacc無(wú)論是構(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.