Lex和yacc工具介绍

不要皱眉 2012-07-06

在编译过程中,词法分析和语法分析是两个重要阶段。lex和yacc是Unix环境下非常著名的两个工具,可以生成分别完成词法分析和语法分析功能的C代码。在学习编译原理过程中,可以善加利用这两个工具,加深对两个阶段的理解。在平时的工作中,这两个工具也会起到重要的作用。Lex是LEXicalcompiler的缩写,主要功能是生成一个词法分析器(scanner)的C源码。描述词法分析器的文件,经过lex编译后,生成一个lex.yy.c的文件,然后由C编译器编译生成一个词法分析器。词法分析器,简单来说,其任务就是将输入的各种符号,转化成相应的标识符(token),转化后的标识符很容被后续阶段处理。

先让我们来看一个简单的例子:

intnum_lines=0,num_chars=0;

%%

\n{++num_lines;++num_chars;}

.{++num_chars;}

%%

main()

{

yylex();

printf("#oflines=%d,#ofchars=%d\n",num_lines,num_chars);

}

然后编译,输入一个文本试试:

$flexsample1.l$mvlex.yy.csample1.c$gccsample1.c-osample1-ll$./sample1正则表达式声明。希望出现在目标C源码中的代码,用%{…%}扩在一起。比如:

%

{#include

#include"y.tab.h"

typedefchar*YYSTYPE;

char*yylval;

%

}

正则表达式声明如下

/*regulardefinitions*/

delim[\t\n]

ws{delim}+

letter[A-Za-z]

digit[0-9]

id{letter}({letter}{digit})*

number{digit}+(\.{digit}+)?(E[+\-]?{digit}+}?

这段正则表达式描述识别数(number)、标识符(id)的"规则"。过一会我们再细说正则表达式。

规则段是由正则表达式和相应的动作组成的。

p1{action1}

p2{action2}

……

pn{actionn}

值得注意的是,lex依次尝试每一个规则,尽可能地匹配最长的输入流。如果有一些内容根本不匹配任何规则,那么lex将只是把它拷贝到标准输出。比如

%%

A{printf("you");}

AA{printf("love");}

AAAA{printf("I");}

%%编译后运行一下,

$./sample3

AAAAAAA

Iloveyou

可以看出lex的确按照最长的规则匹配。

程序段部分放一些扫描器的其它模块,比如一些动作执行时需要的模块。也可以在另一个程序文件中编写,最后再链接到一起。生成C代码后,需用C的编译器编译。连接时需要指定链接库。gcc的连接参数为-ll。

[编辑]正则表达式

正则表达式(regularexpression)可以描述有穷状态自动机(finiteautomata)接受的语言,也就是定义一个可以接受的串的集合。限于篇幅,我们就不展开关于这方面的话题了。有兴趣的请参考[4]。这里只介绍一下lex中用到的正则表达式的一些规则。

转义字符(也称操作符):

"\[]^-?.*+|()$/{}%这些符号有特殊含义,不能用来匹配自身。如果需要匹配的话,可以通过引号(")或者转义符号(\)来指示。比如

C"++"C\+\+都可以匹配C++。

非转义字符:所有除了转义字符之外的字符都是非转义字符。一个非转义字符可以匹配自身。比如

integer匹配文本中出现的integer。

通配符:通配符就是.(dot),可以匹配任何一个字符。

字符集:用一对[]指定的字符构成一个字符集。比如[abc]表示一个字符集,可以匹配a、b、c中的任意一个字符。使用可以指定范围。比如[a-z]表示可以匹配所有小写字母的字符集。

重复:

*任意次重复+至少一次的重复,相当于xx*?零次或者一次选择和分组:|符号表示选择,二者则一;括号表示分组,括号内的组合被看作是一个原子。比如(ab|cd)匹配ab或者cd。

简单来说,yacc(YetAnotherCompiler-Compiler)就是编译器的编译器。Yacc是一个通用的工具,能够根据用户指定的规则,生成一个词法分析程序。yacc能识别LALR(1)且无歧义的文法,它的输入是词法分析器的输出。我们知道,生成词法分析器是lex分内的事,因此lex和yacc常常珠联璧合。

先让我们看一下yacc文件的格式。和前面介绍的lex的格式类似:

declarations(声明)

%%rules(规则)%%

programs(代码)

其中声明段声明一些符号常量,可以为空。同lex一样,声明段中可以有出现在目标C程序中的代码,放在%{…%}中;还有一些yacc关键词可以指示出token的结合顺序:%left左结合%right右结合%nonassoc不结合%token声明token

俗话说"没有规矩,不成方圆"。规则段描述规则,自然是重中之重了。规则段的结构是如下,

A:BODY;

A表示非终结符名,BODY表示产生式和动作。产生式包括非终结符和终结符,终结符用''引用。一些转义字符,比如'\r','\n'等,和C里面的表示是一样的。动作(action)则是在输入被当前规则识别出来时而执行的。动作实际上就是C的代码,写在{}中。为了沟通词法分析器和动作,yacc引入了形式变量,以$开头。如果希望获得词法分析器和前面的动作返回的值,我们可以使用$1,$2,…。$i表示一条规则右侧第i个单元的值。比如有这样的一条规则,

A:BCD;C的返回值为$2,D为$3。依此类推。

程序段放一些其它的程序,也可以省略,连%%都可以不要。

连接时需要指定连接库,gcc的参数为-ly。

[编辑]举例

让我们看一个典型的例子,它实现一个简单的计算器:

%

{

#include

#include

intregs[26];

intbase;%

}

%startlist

%tokenDIGITLETTER

%left'|'

%left'&'

%left'+''-'

%left'*''/''%'

%leftUMINUS/*suppliesprecedenceforunaryminus*/

%%

/*beginningofrulessection

*/list:

/*empty*/

|liststat'\n'

|listerror'\n'

{

yyerrok;

};

stat:expr

{printf("=%d\n",$1);}

|LETTER'='expr

{regs[$1]=$3;};

expr:'('expr')'

{$=$2;}

|expr'+'expr

{$=$1+$3;}

|expr'-'expr

{$=$1-$3;}

|expr'*'expr

{$=$1*$3;}

|expr'/'expr

{$=$1/$3;}

|expr'%'expr

{$=$1%$3;}

|expr'&'expr

{$=$1&$3;}

|expr'|'expr

{$=$1|$3;}

|'-'expr%precUMINUS

{$=-$2;}

|LETTER

{$=regs[$1];}

|number;number:DIGIT{$=$1;base=($1==0)?8:10;}|numberDIGIT{$=base*$1+$2;};%%/*startofprograms*/yylex(){/*lexicalanalysisroutine*//*returnsLETTERforalowercaseletter,yylval=0through25*//*returnDIGITforadigit,yylval=0through9*//*allothercharactersarereturnedimmediately*/intc;while((c=getchar())==''){/*skipblanks*/}/*cisnownonblank*/if(islower(c)){yylval=c-'a';return(LETTER);}if(isdigit(c)){yylval=c-'0';return(DIGIT);}return(c);}编译、执行:

$bisonexample.y

$gccexample.tab.cly-oexample

$./example

20+30*50=1520

小结

lex是词法分析器的生成工具,yacc是文法分析器的生成工具。lex的描述规则采用正则表达式,关于正则表达式的详细讨论,参见文献[1];yacc的描述规则采用无歧异文法。在GNU中有相应lex和yacc工具:flex和bison,与lex和yacc兼容。