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文件这里的动作都是用{}扩起来的，用语言来描述，这些代码可以做你任何想要做的事情 

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
```lex
%{ 
// 引入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", &amp;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 变量

Lex 函数

参考资料：

首先推荐《lex and yacc tutorial》