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.