第13章用 bison 做语法分析 - 13.2 bison 示例 1 - 《自己动手写编译器》

安装完成后，新建一个文本文件，输入以下内容：

%{
#include "y.tab.h"
%}
 
%%
[0-9]+          { yylval = atoi(yytext); return T_NUM; }
[-/+*()\n]      { return yytext[0]; }
.               { return 0; /* end when meet everything else */ }
%%
 
int yywrap(void) { 
    return 1;
}

将此文件另存为。注意此文件中的 %% 、 %{ 、 %} 的前面不能有任何空格。

再新建一个文本文件，输入以下内容：

%{
#include <stdio.h>
void yyerror(const char* msg) {}
%}
 
%token T_NUM
 
%left '+' '-'
%left '*' '/'
 
%%
 
S   :   S E '\n'        { printf("ans = %d\n", $2); }
    |   /* empty */     { /* empty */ }
    ;
 
E   :   E '+' E         { $$ = $1 + $3; }
    |   E '-' E         { $$ = $1 - $3; }
    |   E '*' E         { $$ = $1 * $3; }
    |   E '/' E         { $$ = $1 / $3; }
    |   T_NUM           { $$ = $1; }
    ;
 
%%
 
int main() {
    return yyparse();
}

将此文件另存为 calc.y 。注意此文件中的 %% 、 %{ 、 %} 的前面也不能有任何空格。

将前面两个文件都放在终端的当前目录，再在终端输入：

bison -vdty calc.y

此时可以发现终端下多了三个文件： y.tab.h, y.tab.c, y.output 。

再在终端输入：

此时终端下又多了一个文件： lex.yy.c 。

最后将 y.tab.c 和 lex.yy.c 一起编译并运行一遍：

gcc -o calc y.tab.c lex.yy.c
./calc

然后在终端输入算术表达式并回车：

1+2+3
ans = 6
2*(2+7)+8
ans = 26

可以发现回车后，终端会自动输出算术表达式的结果。这个程序就是一个简单的支持加、减、乘、除以及括号的整数计算器。想象一下，如果用 C 语言手工编写一个同样功能的程序，那代码量肯定很大吧。

下面再来详细的解释一下 calc.l 和 calc.y 代码。

calc.l 文件就是一个词法分析器（或者说扫描器），在第 8 章中已经介绍了 flex 的语法。该扫描器扫描标准输入（键盘），将其分割为一个个的 token ，从其代码中可以看出，它将整数扫描为一个 T_NUM 型的 token ，而将 “-/+*()n” 这些字符扫描为一个单字符 token （其 token_type 的值就是该字符的 ASCII 码），任何其他字符都会被扫描为一个值为 0 的 token 。

再来看 calc.y 文件，这个就是 bison 的自定义语法文件，其格式和 flex 分词模式文件的格式非常相似，共分为 4 段，如下：

%{
Declarations
%}
Definitions
%%
Productions
%%
User subroutines

其中的 Declarations 段和 User subroutines 和 flex 文件中是一样的， bison 会将这些代码原样的拷贝到 y.tab.c 文件中； Definitions 段和 flex 中的功能也差不多，也是在这个段定义一些 bison 专有的变量，稍后再解释这个文件中的这个段里的代码；最重要的是 Productions 段，这里面是用户编写的语法产生式，这个文件里定义的产生式用常规的方式书写的格式如下：

bison 会将 Productions 段里的第一个产生式的左边的非终结符（本文件中为 S ）当作语法的起始符号，同时，为了保证起始符号不位于任何产生式的右边， bison 会自动添加一个符号（如 S’ ）以及一条产生式（如 S’ -> S ），而将这个新增的符号当作解析的起始符号。

产生式中的非终结符不需要预先定义， bison 会自动根据所有产生式的左边来确定哪些符号是非终结符；终结符中，单字符 token （ token type 值和字符的 ASCII 码相同）也不需要预先定义，在产生式内部直接用单引号括起来就可以了（如本文件中的 ‘n’, ‘+’, ‘-‘ 等），其他类型的 token 则需要预先在 Definitions 段中定义好，如本文件中的 token T_NUM， bison 会自动为这种 token 分配一个编号，再写到 y.tab.h 文件中去，打开该文件，可以看到如下代码：

#ifndef YYTOKENTYPE
# define YYTOKENTYPE
    enum yytokentype
    {
        T_NUM = 258
    };
#endif
/* Tokens.  */
#define T_NUM 258

因此在 calc.l 文件中包含此文件就可以使用 T_NUM 这个名称了。

可以在 Definitions 段定义符号的优先级，本文件中，定义了各运算符的优先级，如下：

%left '+' '-'
%left '*' '/'

其中的 %left 表明这些符号是左结合的。同一行的符号优先级相同，下面行的符号的优先级高于上面的。

bison 会将语法产生式以及符号优先级转化为一个 C 语言的 LALR(1) 动作表，并输出到 y.tab.c 文件中去，另外，还会将这个动作表以及语法中的相关要素以可读的文字形式输出到 y.output 文件中去，该文件中内容如下：

Grammar
    0 $accept: S $end
 
    1 S: S E '\n'
    2  | %empty
 
    3 E: E '+' E
    4  | E '-' E
    5  | E '*' E
    6  | E '/' E
    7  | T_NUM
    8  | '(' E ')'
 
......
 
State 0
 
    0 $accept: . S $end
 
    $default  reduce using rule 2 (S)
 
    S  go to state 1
 
 
State 1
 
    0 $accept: S . $end
    1 S: S . E '\n'
 
    $end   shift, and go to state 2
    T_NUM  shift, and go to state 3
    '('    shift, and go to state 4
 
    E  go to state 5

上面 state x 等表示一个状态以及该状态里面的所有形态，以及该状态的所有动作，由于采用了 LALR(1) 方法构造动作表，因此这些状态里的形态数量和用 LR(1) 法构造的有所不同。

bison 将根据自定义语法文件生成一个函数 int yyparse (void) （在 y.tab.c 文件中），该函数按 LR(1) 解析流程对词法分析得到的 token stream 进行解析，每当它需要读入下一个符号时，它就执行一次 x = yylex() ，每当它要执行一个折叠动作时，这个折叠动作所应用的产生式后面的花括号里面的 C 代码将被执行，执行完后才将相应的状态出栈。

若 token stream 是符合语法的，则解析过程中不会出错， yyparse 函数将返回 0 ，否则，该函数会在第一次出错的地方终止，并调用 yyerror 函数，然后返回 1 。

yyparse 函数不仅维持一个状态栈，它还维持一个符号属性栈，当它执行 shift 动作时，它除了将相应的状态压入状态栈之外，还会将一个类型为 YYSTYPE （默认和 int 相同）、名为 yylval 的全局变量的数值压入到属性栈内，而在 reduce 动作时，可以用 $1, $2, … $n 来引用属性栈的属性， reduce 动作不仅将相应的状态出栈，还会将同样数量的属性出栈，这些属性和 reduce 产生式的右边的符号是一一对应的，同时，用代表产生式左边的终结符，在 reduce 动作里可以设置的值，当执行 goto 动作时，除了将相应的状态入栈，还会将 $$ 入栈。

以本程序为例：

以下为 yyparse 函数的基本解析流程：

（1）将初始状态 state0 压入栈顶；
（2）执行 x = yylex() ，有两种情况：
（3）置 X = x；
（4）设栈顶状态为 I ，有以下五种情况：
（4.1） M[I, X] 为 shift I’ 动作：执行 shift I’ 操作：
（4.2） M[I, X] 为 goto I’ 动作：执行 goto I’ 操作：
将 I’ 压入栈顶，将 $$ （可能在（4.3）中被赋值）压入属性栈，转到（3）；
（4.3） M[I, X] 为 reduce A -> X1 X2 … Xn ：执行 reduce(A, n) 操作，具体步骤为：
（4.4） M[I, X] 为 ACCEPT ：执行 accept 操作，返回 0 ；
（4.5） M[I, X] 为空白：执行 deny 操作，调用 yyerror 函数，返回 1。

以上流程中：如果在第（2）步（ yylex 函数内、也就是 flex 文件的 action 中）对 yylval 赋值，那么这个值将和 yylex 返回的终结符绑定；如果在第（4.3）步中（也就是 bison 文件的 action 中）对 $$ 进行赋值，那么这个值将和此 action 的产生式的左边的非终结符绑定；而 bison 文件的 action 中，可以用 $1, $2, …, $n 来引用和此 action 的产生式右边的第 1 ~ n 个符号所绑定的值。