Bison使用入门

前言

语法分析就是按照源语言的语法规则，从词法分析的结果中识别出相应的语法范畴，它本质上就是从Parsing -> AST（抽象语法树），也就是说，将前一阶段词法分析所产生的token流，转换为有序的树状结构。那么这样做有什么用呢？它其实是在实现对代码文本的解析，让程序理解其中的语法含义，从而能够针对文本的含义来进行操作，而非仅仅操作代码字符串本身。

语法分析的这种转换可以递归完成，即递归下降算法；同时也可以在满足一定限定条件的前提下，使用自底向上的移进-规约算法来完成。对于真实的使用场景，显然后者非递归的运行效率要远远高于前者，因此也是绝大多数语法分析器的实现方式。对于Bison语法分析器生成器而言，这里所谓的“限定条件”，即为输入的形式化语法只要满足LALR(1)文法，即可自动化地生成语法分析器。

抽象语法树

这里仅仅简单展示一下，什么是抽象语法树。简而言之，它就是把文本进行结构化转换的结果，从而在树状结构上更加方便分析其代码或者说文本的语义。因为从语法规则推导到具体的代码，本质上是一个递归的过程，因此树状结构非常适合用于展示这种带有递归子结构的抽象概念。

考虑下面这段辗转相除法的示意代码：

while b ≠ 0
if a > b
    a := a − b
else
    b := b − a
return a

经过语法分析后，其生成的抽象语法树示意图如下：

抽象语法树示意图

算数表达式求值

为了实现一个能够对简单算数表达式进行求值的程序，一方面我们可以使用数据结构中，双栈算术表达式求值的算法来完成这个任务；但是更为简洁优雅的实现是，直接使用Bison生成对应的语法分析器。

词法分析

首先进行词法分析，规则非常简单，就是用正则匹配出相应的浮点数以及运算符：

%{
#define YYSTYPE double
#include "eval.tab.h"
extern YYSTYPE yylval;
%}
FLOAT   (([0-9]+(\.[0-9]*)?)|(\.[0-9]+))([Ee][+-]?[0-9]+)?
WHITE   [ \t\n]|(\r\n)
%%
{FLOAT}     { sscanf(yytext, "%lf", &yylval); return NUMBER; }
{WHITE}     { /* do nothing */ }
.           { return yytext[0]; }
%%

LALR(1)文法

然后构造其LALR(1)文法：

statement  ::=  expression
expression ::=  expression + expression
                expression – expression
                expression * expression
                expression / expression
                - expression
                ( expression )
                Number

语法分析

接下来将上述文法对应转换为Bison可以识别的规则，并添加相应的操作：

%{
#include <stdio.h>
#include <math.h>
#define YYSTYPE double
%}

%token NAME NUMBER
%left '-' '+'
%left '*' '/'
%nonassoc UMINUS

%%
statement: expression { printf("result = %.3f\n", $1); };
expression: expression '+' expression   { $$ = $1 + $3; }
    |   expression '-' expression   { $$ = $1 - $3; }
    |   expression '*' expression   { $$ = $1 * $3; }
    |   expression '/' expression   { if (fabs($3) < 1e-10) yyerror ("divide by zero"); else $$ = $1 / $3; }
    |   '-' expression %prec UMINUS { $$ = - $2; }
    |   '(' expression ')'      { $$ = $2; }
    |   NUMBER              { $$ = $1; }
    ;
%%
int main (void) {
    return yyparse();
}
int yyerror (char *msg) {
    return fprintf (stderr, "YACC: %s\n", msg);
}

注意，为了消除移进-规约冲突，需要为负号运算符(UMINUS)指定上下文有关情形下的优先级。详情可以参考Bison手册第5.4节"Context-Dependent Precedence"。

效果

只需要上述两个文件便能够编译并得到一个可以运行的程序。最后，仅仅使用这十几行的代码，我们便轻松实现了一个健壮的表达式求值工具。其运行效果如下：

运行效果示意图

我们可以看到，尽管被求值的表达式包含种种格式上令人纠结的换行、空白字符，但是程序依然能够正确地完成解析并得出结果。进一步地，其他任何更为复杂的结构化文本，都可以利用同样的技术，生成其语法分析器，从而能够针对文本的语义进行高级操作。

上述源代码和编译结果可以点此下载。