上一节给大家介绍了Flex语法规则，本节接着上一节内容继续给大家介绍一下Bison的语法规则，还不了解Bison的同学可以去看第一节内容Flex和Bison背景介绍
BNF文法（BackusNaur Form）
为了描述语法分析树的规则，我们通常采用的是上下文无关文法（Context-Free Grammar，CFG），书写上下文无关文法的标准格式就是BNF范式，例如针对1 * 2 + 3 * 4 + 5的BNF范式如下：
<exp> ::= <factor>
| <exp> + <factor>
<factor> ::= NUMBER
| <factor> * NUMBER
每一行就是一条规则，::=可以看出编程语言中的赋值操作，｜为“或”操作，规则左边的为非终结符，归约和移进的流程可参考下面代码示：
1-> <factor> //可以匹配第三条规则
1 * -> <factor> * //暂时匹配不是任何规则，直接入栈
1 * 2 -> <factor> //可以匹配上第四条规则
1 * 2 + -> <factor> + //暂时匹配不是任何规则，直接入栈
1 * 2 + 3 -> <factor> + <factor> //第三条规则
1 * 2 + 3 * -> <factor> + <factor> * //暂时匹配不是任何规则，直接入栈
1 * 2 + 3 * 4 -> <factor> + <factor> //可以匹配上第四条规则
1 * 2 + 3 * 4 + -> <factor> + <factor> + //暂时匹配不是任何规则，直接入栈
1 * 2 + 3 * 4 + 5 -> <factor> + <factor> + <factor> //第三条规则
<factor> + <factor> + <factor> -> <exp> + <factor> //可以匹配上第一条规则
<exp> + <factor> -> <exp> // 可以匹配上第二条规则，最后也会得到表达式的值
Bison语法规则
先从一个简单的计算器示例来给大家说明Bison的语法规则
%{
#include <stdio.h>
int yylex();
void yyerror(char *s);
%}
/*declare tokens */
%token NUMBER
%token ADD SUB MUL DIV ABS
%token EOL
/**
每个bison规则中的语法符号都有一个语义值，目标符号（冒号左边的语法符号）的值在动作中代码用$$代替，
右边语法符号的语义值依次为$1, $2,直到这条规则的结束。
当词法分析器返回记号时，记号值总是储存在yyval里。其他语法符号的语义值则在语法分析器的规则里进行设置。
*/
%%
calclist:/*空规则*/
| calclist exp EOL { printf("=%d\n", $2); }
;
exp: factor {$$ = $1}
| exp ADD factor { $$ = $1 + $3; }
| exp SUB factor { $$ = $1 - $3; }
;
factor: term {$$ = $1}
| factor MUL term { $$ = $1 * $3; }
| factor DIV term { $$ = $1 / $3; }
;
term: NUMBER {$$ = $1}
| ABS term {$$ = $1 >= 0 ? $2 : -$2}
;
%%
int main(int argc, char ** argv)
{
yyparse();
}
void yyerror(char *s)
{
fprintf(stderr, "error:%s\n", s);
}
Bison的程序结构和Flex非常相似（不是巧合），都包含三个部分，以%%分割。
第一部分为声明部分，声明部分为 %{和%}之间的内容，会被直接拷贝到生成的C代码中，%token为记号声明，告诉Bison在语法分析程序中记号的名称，通常来说使用大写字母来表示（Bison并没有强制规定必须要大写）。如果一个语法符号既不是记号也没有出现在任何规则的左边，它就会像程序中未定义的变量，最好避免出现这种问题。
第二部分包含了BNF定义的规则，Bison使用的是单一冒号来表示赋值操作，分号表示规则的结束，类似于Flex，匹配之后需要执行的操作代码用花括号括起。每条规则中的语法符合都有一个语义值，目标符号（冒号左边的非终结符）的值在动作代码中用$$代替，右边的语法符号语意值依此为$1,$2...，直到这条规则的结束，当词法分析器返回记号时，记号值存储在yyval里，在上述示例中，头两条规则定义来calclist语法符号，第一条规则为空所以不进行任何匹配，第二条规则主要匹配我们需要计算的表达式，并通过$2打印出表达式的值，其余的规则实现了计算器的相关操作逻辑。
第三部分为C代码部分，会直接拷贝到生成的C文件中，在本例中主要包含一个主函数入口和错误打印函数，在主函数中会调用yyparse函数开始语法分析。
编译和运行
在编译之前，我们先把对应的Flex词法分析文件补充完整，代码如下：
%option noyywrap
%{
#include "fb_1_5.tab.h"
%}
/**
前5个模式就是操作符本身，用引号引起。引号告诉Flex使用引号内文本的原义，而不是解释为正则表达式
*/
%%
"+" {return ADD;}
"-" {return SUB;}
"*" {return MUL;}
"/" {return DIV;}
"|" {return ABS; }
[0-9]+ {yylval = atoi(yytext); return NUMBER;}
\n {return EOL;}
[ \t] {}
. {printf("Mystery character:%c\n", *yytext);}
%%
fb_1_5.tab.h这个头文件是运行完Bison后生成的文件，对应的还会生产一个C文件fb_1_5.tab.c，有兴趣的可以比对一下上面的示例代码看看，由于本次编译涉及的文件较多，我们编写一个Makefile文件来统一管理编译和清除，代码示例如下：
fb_1_5: fb_1_5.l fb_1_5.y
bison -d fb_1_5.y
flex fb_1_5.l
gcc -o $@ fb_1_5.tab.c lex.yy.c
clean:
rm -rf fb_1_5.tab.c lex.yy.c fb_1_5 fb_1_5.tab.h
然后在终端窗口中执行make命令，再执行测试代码
% make
bison -d fb_1_5.y
flex fb_1_5.l
gcc -o fb_1_5 fb_1_5.tab.c lex.yy.c
% ./fb_1_5
1+3
=4
1+5*2
=11
通过上面的计算器案例，相信大家对于Bison应该有一个比较直观的认识了，大家在实际操作过程中有什么问题，欢迎大家随时提出与讨论，谢谢～
网友评论