lex&yacc 学习笔记

前一段时间在项目中要使用一个规则表达式计算的功能,而且想可以任意扩展计算功能,比如计算AUB,A和B都表示一个号码包,计算并集,当然实际使用的公式会更为复杂,这里举例说明。在计算时候要判断如果A包已经计算ok了就可以使用A包,如果没有计算成功就需要发起计算并且等待计算成功,B包也是要同样的处理过程,最后再计算并集。当然这样一个功能自己定义写肯定是没问题的,但是还要想到后面的扩展性和程序代码可移交等问题,还是想有一个通用的方法来解决,所以在最后想到了使用yacc和lex来组织解决。实际上后来发现用yacc和lex非常方便的可以解决这类问题,而且在扩展性上非常好。所以想这里先总结一下yacc和lex使用的一些语法特点和具体我们使用的方式。现在这篇中总体总结一下yacc和lex的语法特点,下一篇再写具体使用中的一些过程。

首先看看lex,lex是什么,我们通常叫做“词法解析器”,主要做输入内容的解析,按照事先定义的规范来解析,并输出给yacc来使用。lex把解析出来的词都叫做token,对于特定的编程语言或者具体实现的token总是有限的,不会像真实的语言一样有很多的词。

lex工具对我们定义好的词法文件进行编译,即可生成一个函数yylex,yacc在调用这个函数就可以把输入的内容解析为具体的token和类型。lex的输入函数一般是xxx.l文件,使用lex xxx.l编译后就可以生成lex.yy.c文件,这里面就包含了yacc要调用的词法解析函数。

yacc呢,yacc是什么呢?我们通常叫做“语法解析器”,主要作用就是根据lex解析输入的结果和实现定义好的对token的处理过程,进行一个解析执行,有点像单词和语法的关系。yacc的定义文件名为xxx.y,通过yacc -d xxx.y就可以得到两个输出文件: y.tab.h y.tab.c,前者包含了lex需要的token类型定义,需要被include进 .l文件中。

说了这么多,我们来看看到底xxx.l和xxx.y这两个文件是怎么定义的。首先看其格式:

Definition section

%%

Rules section

%%

code section

xxx.l和xxx.y的文件格式都是分成三段,用%%来分割,三个section的含义是:

Definition Section 

可以放编程语言的各种include,define等声明语句,但是要用%{ %}括起来。 

如果是.l文件,可以放预定义的正则表达式:minus “-” 还要放token的定义,方法是:代号正则表达式。然后到了,Rules Section就可以通过{符号} 来引用正则表达式

如果是.y文件,可以放token的定义,如:%token INTEGER PLUS ,这里的定一个的每个token都可以在y.tab.h中看到 

Rules section

.l文件在这里放置的rules就是每个正则表达式要对应的动作,一般是返回一个token

.y文件在这里放置的rules就是满足一个语法描述时要执行的动作

不论是.l文件还是.y文件这里的动作都是用{}扩起来的,用语言来描述,这些代码可以做你任何想要做的事情 

C code Section

main函数,yyerror函数等的定义 ,还有其它使用的一些函数的定义都可以放到这里

下面我们以一个具体的例子来看看lex和yacc是怎么配合做事的,实验环境是debian,实际上Lex和Yacc是一种标准,当然会有很多的实现了,其中有2个是免费的(好像还有商业版本),那就是flex和bison,这里我们先以c语言版本的来说明,实际上我们在项目中是是用golang的版本来的。如果在debian上安装,会很简单,直接运行一下命令即可。

sudo apt-get install flex bison

接下来我们以网上非常经典的例子来说明,用lex和yacc实现一个数字计算器。

lex文件就是定义为如下格式:

文件名cal.l

%{ 

// 引入c的函数头

#include<string.h>  

#include “y.tab.h”  

extern int yylval;  

%}  

// 定义token,如数字,加,减等

numbers ([0-9])+  

plus “+”  

minus “-”  

times “*”  

divide “/”  

lp “(”  

rp “)”  

delim [ /n/t]  

ws {delim}*  

%%  

// 第二部分,主要就是怎么解析token,token解析的规则

{numbers} {sscanf(yytext, “%d”, &yylval); return INTEGER;}  

{plus} {return PLUS;}  

{minus} {return MINUS;}  

{times} {return TIMES;}  

{divide} {return DIVIDE;}  

{lp} {return LP;}  

{rp} {return RP;}  

{ws}       ;   

. {printf(“Error”);exit(1);}    

%% 

yacc的文件定义如下:

cal.y

%{

// 引入c头文件

#include <stdio.h>

#include “lex.yy.c”

#define YYSTYPE int  

int yyparse(void);

void yyerror(char* s);

int yywrap();

%}

// 这里是申明token,和cal.l中的相对应

%token INTEGER PLUS MINUS TIMES DIVIDE LP RP

%%

// token的运算规则

command : exp {printf(“%d/n”,$1);}

// 这里定义有嵌套的含义在里面,其实就是定义了规则执行的优先级,可以看出,括号中先执行,乘除的再执行,最后是加减

exp: exp PLUS term {$$ = $1 + $3;}

|exp MINUS term {$$ = $1 – $3;}

|term {$$ = $1;}

;

term : term TIMES factor {$$ = $1 * $3;}

|term DIVIDE factor {$$ = $1/$3;}

|factor {$$ = $1;}

;

factor : INTEGER {$$ = $1;}

| LP exp RP {$$ = $2;}

;

%%

// 运行的main函数和异常处理函数,这几个函数都是必须定义的,后面有这几个函数的具体作用

int main()

{

return yyparse();

}

void yyerror(char* s)

{

fprintf(stderr,”%s”,s);

}

int yywrap()

{

return 1;

}

使用方式: 

yacc -d cal.y 

flex cal.l

gcc -o cal y.tab.c 

运行./cal 然后输入3+4 ctrl+D就可以看到结果了

关于lex和yacc中一些预定义的东西

Lex 变量

yyin

FILE* 类型。 它指向 lexer 正在解析的当前文件。

yyout

FILE* 类型。 它指向记录 lexer 输出的位置。 缺省情况下,yyin 和 yyout 都指向标准输入和输出。

yytext

匹配模式的文本存储在这一变量中(char*)。

yyleng

给出匹配模式的长度。

yylineno

提供当前的行数信息。 (lexer不一定支持。)

Lex 函数

yylex()

这一函数开始分析。 它由 Lex 自动生成。

yywrap()

这一函数在文件(或输入)的末尾调用。 如果函数的返回值是1,就停止解析。 因此它可以用来解析多个文件。 代码可以写在第三段,这就能够解析多个文件。 方法是使用 yyin 文件指针(见上表)指向不同的文件,直到所有的文件都被解析。 最后,yywrap() 可以返回 1 来表示解析的结束。

yyless(int n)

这一函数可以用来送回除了前n 个字符外的所有读出标记。

yymore()

这一函数告诉 Lexer 将下一个标记附加到当前标记后。

参考资料:

首先推荐《lex and yacc tutorial》  http://epaperpress.com/lexandyacc/download/LexAndYaccTutorial.pdf

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章