Flex & Bison

简介

Flex

Flex是一个词法分析工具，词法分析可以称为lexical analysis，或称scanning；

词法分析把输入分割成一个个有意义的词块，称为记号（token）；

Bison

Bison是一个语法分析工具，语法分析可以称为syntax analysis，或称parsing；

语法分析主要是确定词法分析记号（token）是如何彼此关联的；

基本所有的编译器项目中，都会使用lex或者flex做词法分析，并利用Yacc或者Bison对词法分析的结果进行语法分析。

flex和bison最早是用来生成编译器的，他们具备处理结构化的输入的能力，后来发现他们可以用在很多地方，例如解析css文件、json文件、XML文件等。

语法

上下文无关文法

当我们编写一个语法分析器，就需要我们用一定的方法来描述记号转化为语法分析树的规则。
这种描述的方法在计算机中最常用的就是上下文无关文法Context-Free Grammar。
上下文无关文法就是说这个文法中所有的产生式左边只有一个非终结符。

例如下面这个就是上下文无关文法

1	S -> aSb \| ab 这个文法产生了语言 {a^n * b^n : n ≥ 1}

这个文法有两个产生式，每个产生式左边只有一个非终结符S，这就是上下文无关文法，因为你只要找到符合产生式右边的串，就可以把它归约为对应的非终结符。

要理解什么是上下文无关文法，可以先感受一下上下文有关文法，例如

1
2
3

S -> ab

aSb -> aaSbb

这就是上下文相关文法，因为它的第一个产生式左边有不止一个符号，所以你在匹配这个产生式中的S的时候必需确保这个S有正确的“上下文”，也就是左边的a和右边的b，所以叫上下文相关文法。

因为上下文无关文法有足够强的表达力来表示大多数程序设计语言的语法，上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。

BNF文法

为了编写一个语法分析器，需要一定的方法来描述语法分析器所使用的把一系列记号转化为语法分析树的规则。在计算机分析程序里最常用的语言就是上下文无关文法（Context-Free Grammar, CFG）。书写上下文无关文法的标准格式就是Backus-Naur范式（BackusNaur Form，BNF）。

BNF文法用起来是非常简单易懂的，例如我们可以用下面的表达式来表示 1 * 2 + 3 * 4 + 5:

<exp> ::= <factor> | <exp> + <factor>

<factor> ::= NUMBER | <factor> * NUMBER

每一行就是一条规则，用来说明如何创建语法分析树的分支。
有效的BNF总是带有递归性的，规则会直接或者间接地指向自身。

Flex语法结构

以最简单的word count的程序word_count.l来看

%{
	int chars = 0;
	int words = 0;
	int lines = 0; 
%}


%%

[a-zA-Z]+ 	{ words++; chars += strlen(yytext); } 
\n 			{ chars++; lines++; }
. 			{ chars++; }

%%


int main(int argc, char **argv)
{
	yylex();
	printf("%8d%8d%8d\n", lines, words, chars); 
	return 0;
}

MacOS下编译代码命令

1 2	flex word_count.l cc lex.yy.c -ll

变量声明

声明部分可以进行声明和选项设置。
可以在%{和%}包围的部分里面定义c代码，里面的内容会被完整地复制到lex.yy.c 的开头，通常会用来放置include、define的信息。

规则定义

规则声明部分被两个%%包围，规则为

正则表达式 {匹配到之后执行的C代码}

例如：
[a-zA-Z]+ { words++; chars += strlen(yytext); }
在任意一个flex的动作中，变量yytext总是被设为指向本次匹配的输入文本。
前面的部分就是模式，处于一行的开始位置，后面的部分就是动作，也就是，输入中匹配到了这个模式的时候，对应的进行什么动作。
yytext，在输入匹配到该模式的时候，匹配的部分就存储到yytext里面。

C代码部分

这部分是C代码，它们会被复制到lex.yy.c的最末尾。

程序主要由一系列带有指令的正则表达式组成，这些指令确定了正则表达式匹配后相应的动作（action）。

Bison语法结构

bison的语法规则也分为三部分，以flex 和 bison协同的计算器程序为例

flex部分：创建calculator.l并声明

%{
    //calculator_def中定义了记号
	#include "calculator_def.h"
%}


%%

"+" 	{ return ADD; }
"-" 	{ return SUB; }
"*" 	{ return MUL; }
"/" 	{ return DIV; }
"|" 	{ return ABS; }
[0-9]+ 	{ yylval = atoi(yytext); return NUMBER; } 
\n 		{ return EOL; }
[ \t]	{ /**whitespace**/ }
.		{ printf("Mystery character %c\n", *yytext); }

%%

bison代码：创建calculator.y并编写代码

%{
#include <stdio.h>
%}

/* declare tokens */ 
%token NUMBER
%token ADD SUB MUL DIV ABS 
%token EOL


%%
calclist:
		| calclist exp EOL { printf("= %d\n", $2); } 


exp: factor
	| exp ADD factor { $$ = $1 + $3; } 
	| exp SUB factor { $$ = $1 - $3; } ;

factor: term
	| factor MUL term { $$ = $1 * $3; } 
	| factor DIV term { $$ = $1 / $3; } ;

term: NUMBER
	| ABS term { $$ = $2 >= 0? $2 : - $2; } ;

%%

int main(int argc, char **argv)
{
	yyparse();
	return 0;
}

yyerror(char *s)
{
	fprintf(stderr, "error: %s\n", s);
}

声明部分和C代码部分

被%{和%}包围的部分，里面的内容会被完整地复制到lex.yy.c 的开头，通常会用来放置include、define的信息。

除此之外一般还要进行token设置。
token用于标记语法解析中用到的基本语素，教程里称之为“记号”。
用枚举来定义，而且为了避免冲突一般枚举的值从258开始。
语法是：
%token 记号，例如

1
2
3

%token NUMBER
%token ADD SUB MUL DIV ABS 
%token EOL

这里一般是当flex成功匹配到一个模式的时候，会return一个token，然后在bison的规则中查找应该进行的动作。

规则部分

规则部分遵循DNF范式的定义，每一个bison语法分析器在分析其输入时都会构造一棵语法分析树。
在有些应用里，它把整棵树作为一个数据结构创建在内存中以便于后续使用。
在其他应用里，语法分析树只是隐式地包含在语法分析器进行的一系列操作中。

%%
calclist:
		| calclist exp EOL { printf("= %d\n", $2); } ;


exp: factor
	| exp ADD factor { $$ = $1 + $3; } 
	| exp SUB factor { $$ = $1 - $3; } ;

factor: term
	| factor MUL term { $$ = $1 * $3; } 
	| factor DIV term { $$ = $1 / $3; } ;

term: NUMBER
	| ABS term { $$ = $2 >= 0? $2 : - $2; } ;

%%

第三部分是用户自定义代码

以上可以使用如下命令生成编译结果：

1
2
3

bison -d calculator.y
flex calculator.l
cc -o calculator calculator.tab.c lex.yy.c -ll

总结

利用flex & bison 除了可以进行语言的词法和文法分析，还可以接续几乎所有的结构化文本。

文章中提到的代码，我放到了github上：https://github.com/zhangdongxuan/Flex-Bison。