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 将下一个标记附加到当前标记后。
参考资料:
感觉有意思?来鼓励鼓励我!
打赏黑光技术

Leave a Reply

Your email address will not be published. Required fields are marked *