【Bison学习笔记】1：生成简易的语法分析程序,使Bsion和Flex协同工作

简述

Bison是在Yacc上改写并添加了大量特性后诞生的语法分析生成器，在编译前端（词法分析->语法分析->语义分析）中处在中间的位置，它可以用来生成特定的语法分析程序。

安装Bison：

apt-get install bison

没有专用于Bison的IDE，可以在VSCode安装Lex Flex Yacc Bison插件，可以让Bison语法高亮。

Bsion和Flex协同工作

在之前按照课本，用Flex生成了一个简易计算器的词法分析程序，这节书写Bison生成它的语法分析程序，然后让它们协同工作，来完成这个求解器。

Bison部分

Bison写在.y文件中，也和Flex一样由两个%%分割成了声明部分、规则部分、例程部分。下面是书写的Bison文件SimpleCalculator.y（课本程序是错的，这里改正了）：

/*1 声明部分*/

%{
#include <stdio.h>
%}

//声明记号(Token)
%token NUMBER
%token ADD SUB MUL DIV ABS
%token EOL

%%

/*2 规则部分，在这里写BNF规则，左部是语法符号(Symbol)*/

//计算列表的语法
calclist: //空，即计算列表::=\epsilon
    | calclist exp EOL { printf("= %d\n", $2); } //或者，计算列表::=计算列表.表达式.文件尾
    ; //分号表示规则结束

//表达式的语法
exp: term { $$ = $1; } //表达式:=项
    | exp ADD term { $$ = $1 + $3; } //或者，表达式::=表达式+项
    | exp SUB term { $$ = $1 - $3; } //或者，表达式::=表达式-项
    ;

//项的语法
term: factor { $$ = $1; } //项::=因子
    | term MUL factor { $$ = $1 * $3; } //或者，项::=项*因子
    | term DIV factor { $$ = $1 / $3; } //或者，项::=项/因子
    ;

//因子的语法
factor: NUMBER { $$ = $1; } //因子::=数字
    | ABS factor { $$ = $2>=0 ? $2 : -$2; } //或者，因子::=绝对值.因子
    ;

%%

/*3 C代码部分*/

//主函数中调用解析器yyparse()
int main(int argc, char **argv) {
    yyparse();
    return 0;
}

//定义解析出错时的处理
void yyerror(char *s) {
    fprintf(stderr, "error: %s\n", s);
}

这里在声明部分用%token声明了若干记号，这些记号实际上后面会给Flex使用，而Bison会自动为这些记号编号。

接下来在规则部分，用BNF来书写了上下文无关文法，这里用{c代码}将求解的计算写在了每条子规则的后面。这里$$表示规则左部的语法符号(Symbol)，$1表示规则右部的第一个语法符号，以此类推。

最后在例程部分，Bison生成的语法分析程序要调用yyparse()进行语法分析。

Flex部分

Flex部分和之前的基本一样。下面是修改的Flex文件SimpleCalculator.l：

%{
//包含Bison翻译出来的头文件，文件中就定义了各个记号(Token)的编号，以及yylval记号值
//SimpleCalculator.tab.h是由SimpleCalculator.y这个Bison文件经过`bison -d`命令翻译得来的
#include "SimpleCalculator.tab.h"
%}

%%

"+"     { return ADD; }
"-"     { return SUB; }
"*"     { return MUL; }
"/"     { return DIV; }
"|"     { return ABS; }
[0-9]+  { yylval = atoi(yytext); return NUMBER; } //匹配到数字时，将其转为int写入记号值的变量中
\n      { return EOL; }
[ \t]   { } //忽略空白符
.       { printf("Mystery charactor %c\n", *yytext); } //其它字符是不合法的，提示错误

%%

//这部分例程不写了，因为Bison生成的语法分析器会调用这里Flex生成的词法分析器

去掉声明部分，是因为声明部分直接使用Bison编译出的.h文件中对记号(Token)的声明，直接就统一了。

去掉例程部分，是因为词法分析的yylex()要给Bison生成的语法分析器去调用，编译的时候编译到一起就可以了。

Makefile

创建Makefile文件：

SimpleCalculator: SimpleCalculator.l SimpleCalculator.y
	bison -d SimpleCalculator.y
	flex SimpleCalculator.l
	gcc -o $@ SimpleCalculator.tab.c lex.yy.c -lfl

clean:
	rm -f SimpleCalculator lex.yy.c SimpleCalculator.tab.c SimpleCalculator.tab.h

第一句是用Bison翻译SimpleCalculator.y，生成语法分析器SimpleCalculator.tab.c和其头文件SimpleCalculator.tab.h。

第二句是用Flex翻译SimpleCalculator.l生成词法分析器lex.yy.c。

第三句是用GCC将语法分析器、词法分析器、Flex库文件这三者编译到一起，-o指定输出的文件名，这里$@代表所有的目标文件，也就是SimpleCalculator。

编译：

make SimpleCalculator

运行

lzh@DESKTOP-HCSIG2E:/mnt/e/Compiler/flex_bison$ ./SimpleCalculator
12+34*|0-3
= 9
123-456
= -333