bison语法分析

“ 对于该搜索引擎系列文章，以阿里在github开源的havenask引擎为例进行逐步阐述。github地址：https://github.com/alibaba/havenask”

使用搜索引擎时，首先会输入一个查询词，然后可选的做一些过滤筛选，这种简单的输入会在后端翻译成一长串的请求串（比如可以做query的纠错、改写、拼音转汉字等等），然后给到搜索引擎进行查询结果

对于搜索引擎而言，第一步面临的问题是：如何对这次查询串进行词法和语法分析，并转成引擎可理解的形式，比如一次查询如下：query=default:'手机' ANDNOT default:'蓝牙'，在havenask中，采用了flex和bison来做这件事情，本文则重点介绍Flex和Bison的相关知识点

01 Flex&Bison的名字由来

• Flex 用于词法分析（lexical analysis，或称 scanning）。Vern Paxson 把一种用 ratfor（当时流行的一种扩展的 Fortran 语言）写成的lex版本改写为C语言的，被称为 flex，意思是“快速词法分析器生成程序”（Fast Lexical Analyzer Generator）。
• Bison 用于语法分析（syntax analysis，或称 parsing）。bison 来源于 yacc（yet another compiler compiler ），之后，Richard Stallman 添加了大量的新特性并演化成为当前的 bison。

 

02 词法&语法分析的关系

词法&语法分析器在整个编译程序中的位置如下：

词法分析的任务：从左至右，依次扫描文本格式的源程序，从基于字符理解的源程序中分离出符合源语言词法的单词（Token）

语法分析的任务：将词法分析得到的单个token联合起来变为有意义的表达式，如将2 + 3这三个token变为一个算数运算结构并将结果赋值到左值表达式

对于词法&语法分析程序的联合使用，会有如上两种形式，第一种形式则会扫描两次，一次进行源程序的词法分析后得到单词序列，然后再对单词序列进行扫描得到语法结构；第二种形式则只会扫描一次，在对源程序进行词法分析时，调用语法分析程序生成的.h文件获取定义的token字符。

采用第二种方式，则Flex和Bison编译期互相依赖的关系如下：

那么，若不采用Flex&Bison，自己手写.c程序也可以，但比较麻烦，则各种正则表达式的去匹配和递归

03 Flex&Bison的安装

sudo apt install flex
sudo apt install bison
若缺少gcc，则 sudo apt-get install -y build-essential

04 Flex文件编写与实践

Flex的文件格式如下，共分为三部分：辅助定义部分、规则部分和用户子程序部分

4.1 辅助定义部分

包括了%option参数项的设定、%{...%}和定义一些表达式，使用%option来设置不同的选项

%option case-insensitive：使词法分析器忽略大小写。
%option yywrap：启用yywrap函数，用于在输入结束时进行缓冲区处理。
%option yylineno：启用行号跟踪功能，以便在出错时输出行号。
%option yyerror：指定一个自定义的错误处理函数，用于在扫描过程中出现错误时调用。
%option do-nothing-on-unbalanced-comment：在注释未正确结束时采取无操作行为（默认行为）。
%option yyllocals：启用本地变量支持，可以在规则中使用yytext等局部变量。
%option yyallow-nested-comment：允许嵌套注释。
%option yyreentrant：启用重入功能，使得多个线程可以安全地共享词法分析器。
%option bison-locations：启用Bison兼容的位置信息支持。
%option std=c99：使用C99标准进行词法分析器的编译。
%option prefix="prefix"：为生成的C程序中的变量和函数添加前缀，以避免与用户定义的变量和函数冲突
%option banner：在生成的C程序顶部添加一个横幅，用于显示版权信息、版本号等。
%option yymore：启用yymore函数，用于在扫描过程中读取更多的输入字符。
%option noyywrap：禁用yywrap函数，需要在输入结束时手动调用yywrap函数进行缓冲区处理。

%{...%} 这部分则会在生成C/C++程序时全部拷贝到源程序文件，比如写一些include源文件之类的，如：

%{
#include <string>
#include "ha3/queryparser/BisonParser.hh"
#include "ha3/queryparser/Scanner.h"

using namespace isearch_bison;
typedef BisonParser::token token;
typedef BisonParser::token_type token_type;
#define yyterminate() return token::END
%}

regexpr则是定义一些正则表达式，如

DIGIT            [0-9] 
ID_FIRST_CHAR    [_[:alpha:]] 
ID_CHAR          [_[:alnum:]] 
SIGNED_CHAR  [+-]

4.2 规则部分

声明了在满足设定的正则表达式后执行的动作，格式为：<表达式> {C/C++动作}，注意，这里的表达式要顶格写

AND {
     AUTIL_LOG(TRACE2, "|%s|AND|",YYText());
     return token::AND;
 }

OR   {
    AUTIL_LOG(TRACE2, "|%s|OR|",YYText());
    return token::OR;
}

4.3 用户子程序部分

可写一些错误处理或其他辅助类函数等，如：

void Scanner::setDebug(bool debug) {
    yy_flex_debug = debug;
}

4.4 Flex实现wc命令

编写wc0.l文件

编译并运行wc0.l文件

flex wc0.l; gcc lex.yy.c -o wc0; ./wc0 xx

05 Bison文件编写与实践

Bison文件以.y结尾，和Flex一样分为相同的三部分

%token定义一个终结符

%type定义一个非终结符

%start代表语法扫描的开始位置

%union使用一个联合体定义类型

$$代表表达式左值

$1代表第一个参数，$2代表第二个参数，以此类推

以上述文件为例，实现一个计算器。如下是对应的flex文件样例

然后，再写个主程序(main.c)

最后，进行编译&运行

bison -d calc.y ; flex calc.l ; gcc main.c calc.tab.c lex.yy.c -o calc

最后执行./calc，即可当作计算器使用

06 总结

Flex和Bison工具很擅长做根据文字生成语法树的事情，所以，在haveask中，Query语法树的生成和加工使用了该工具的组合，具体可看BisonParser.yy和Scanner.ll文件的编写，而使用flex和bison编译，则写在了defs.bzl文件

本文部分内容来自：华中科技大学词法分析课程