bison 读入一个 CFG 文法的文件，在程序内经过计算，输出一个 parser generator 的 c 文件；也就是说 Bison 适合上下文无关文法，采用 LALR Parser (LALR语法分析器)。

简介

在实现时，bison 会创建一组状态，每个状态用来表示规则中的一个可能位置，同时还会维护一个堆栈，这个堆栈叫做分析器堆栈 (parser stack)。每次读入一个终结符 (token)，它会将该终结符及其语意值一起压入堆栈，把一个 token 压入堆栈通常叫做移进 (shifting)。

当已经移进的后 n 个终结符可以与一个左侧的文法规则相匹配时，这个 n 各终结符会被根据那个规则结合起来，同时将这 n 个终结符出栈，左侧的符号如栈，这叫做归约 (reduction)。

如果可以将 bison+flex 混合使用，当语法分析需要输入标记 (token) 时，就会调用 yylex() ，然后匹配规则，如果找到则返回。

文件格式

两个文件的格式基本类似，分成三部分，都是通过 %% 进行分割，如下所示。

... definitions ...
%%
... rules ...
%%
... subroutines ...

其中：A) definitions 定义模式、C语言变量、以及包含c头文件等；B) rules 部分用户定义模式对应的动作；C) subroutines 部分用于定义 C 函数等。

示例

读取 Hi Bye 并输出相关的内容。

/* hello.l */
%{
        #include "hello.tab.h"
        int yyerror(char *errormsg);
        int yyparse(void);
%}

%%

("hi"|"Hi")"\n"       { return HI;  }
("Bye"|"bye")"\n"     { return BYE; }
[-[]+.,><]            { return yytext[0]; }
.                     { yyerror("Unknow char");  }

%%
int main(void)
{
        yyparse();
        return 0;
}

int yywrap(void)
{
        return 0;
}

int yyerror(char *errormsg)
{
        fprintf(stderr, "%s\n", errormsg);
        exit(1);
}

/* hello.y */
%{
        #include <stdio.h>
        #include <stdlib.h>
        int yylex(void);
        int yyerror(const char *s);
%}


%token HI BYE

%%
program:
        hi bye
        ;

hi:
        HI     { printf("Hello World\n");   }
        ;
bye:
        BYE    { printf("Bye Now\n"); exit(0); }
        ;

# Makefile
all:
        flex --outfile=hello.yy.c hello.l
        bison -d --output=hello.tab.c hello.y
        gcc hello.tab.c hello.yy.c -o hello

clean:
        rm *.tab.c *.tab.h *.yy.c -f hello

可以直接执行 hello ，然后输入 Hi Bye 加上回车即可。

规则

定了语法的产生以及语义的动作，一般规则为 Result: Components {...};，其中 Result 为非终结符，Components 可以是终结符、非终结符、语义动作。

在 {...} 中，通过 C 语言实现语义的动作，$$ 表示 Result 的

value:
	VARIABLE
        | NUMBER
expression:
          value '+' value
        | value '-' value

这意味着表达式可以是几种格式中的任意一种；例如，一个变量、一个加号或者一个数字都可以是一个表达式。

yacc 中定义了很多的符号，详细的可以查看 Bison Symbols 中的介绍，如下简单介绍常见的符号定义：

%start foobar
  修改默认的开始规则，例如从foobar规则开始解析，默认从第一条规则开始
%token TOKEN1 TOKEN2 TOKEN3 ...
  通常用来指定从 flex 解析获取的符号类型，如上，可以是终结符或者标记。
%left，%right，%nonassoc
  类似于终结符，不过同时具有某种优先级和结核性，分别表示左结合、右结合、不结合 (也就是终结符不能连续出现，
     例如<，此时不允许出现a<b<c这类句子)。
  优先级与其定义的顺序相关，先定义的优先级低，最后定义的优先级最高，同时定义的优先级相同。
     例如，如上程序关于计算器中优先级的定义。

终结符 VS. 非终结符

通过 Flex 生成的符号称为终结符 (Terminals) 或者标记 (Tokens)，从它们装配而来的内容称为非终结符 (Non-Terminals)。

所以，在上述的例子中，NUMBER 是一个终结符；value 是一个非终结符，它通过装配终结符而创建出来的。

Token VS. Type

Bison 会调用 Flex 的 yylex() 来获得标志 (Token)，其中与标志对应的值由 Lex 放在变量 yylval 中，而 yylval 的类型由 YYSTYPE 决定，默认是 int 。

也就是说，在 Bison 调用 yylex() 返回类型后，同时需要将对应的值通过 yylval 将值从 Flex 传递到 Bison 中。

%union

如果有多个值类型，则需要通过 %union 列举出所有的类型，此时 yylval 的类型就是上述的 union 结构体。

需要为每个符号定义相对的类型，其中终结符使用 %token，非终结符使用 %type 来定义。

%union {
	long value;
}
%token <value>  NUMBER
%type <value>   expression

这样，当 Bison 解析器得到 Flex 返回的 NUMBER 记号时，它可以变量 yylval 中名为 value 的成员已经被赋值；这只是一个约定，同时需要在 Flex 中添加如下内容。

[0-9]+  { yylval.value = atol(yytext); return NUMBER; }

上述通过 %type 声明了 expression 为非终结符，同时还使用了 union yylval 中的 value 成员；另外，NUMBER 为终结符。

注意，在不同的 Token 返回时，不要将值赋值到错误的对象。

使用

在 Bison 的规则中，可以通过符号名引用表达式的组成部分，其中返回值为 $$ ，其它分别为 $1 到 $N 。

expression:
	NUMBER '+' NUMBER { $$ = $1 + $3; }

注意，其中 $2 对应的是 + 号，只作为一个占位符，实际上没有任何意义。

在介绍原理的时候，会保存一个栈分析栈，实际上还通过 yyvsp 保存了对应的值，这也就是通过 $N 转换保存的值。

其它

%error-verbose 显示详细的错误信息。

冲突

在解析语法的过程中，意味着可以选择多个分支，yacc 会根据规则选择默认的分支，但是，冲突意味着某些地方可能会出现异常。

Yacc 属于 LR 解析器，类似于一个有限的状态机，有所不同的是，Yacc 同时会有一个栈保存终止符，可以 pop 也可以 push ，这也就是为什么能支持上下文无关的语法。

递进规约

简单来说，Yacc 就是不断的执行递进和规约，每次都是不断地匹配语法右侧规则。

所谓的递进 (Shitf) 就是不断地读取符号，并添加到栈中；当最上层的栈满足某个语法规则时 (如 A->x y z) ，那么就会执行规约 (Reduce) 操作，也就是将 x y z 弹出，将 A 压入。

也就是说，递进是在等待满足条件的语法；而规约则是已经找到了。

总共有两种类型的冲突：A) Shift-Reduce；B) Reduce-Reduce；如果要查看具体的冲突，可以通过 -v 参数输出调试信息，也就是 y.output 文件。

Shift-Reduce

此时解析器需要判断是执行 Shift 还是执行 Reduce ，默认是前者。

例如，有如下的语法规则。

S -> 0 S 0
S -> e     /* epsilon */

对应到 Bison 的代码为

%%
S : '0' S '0'
  | /* epsilon */
  ;

然后，通过如下方式编译。

$ bison -d -v hello.y
hello.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]

Reduce-Reduce

当执行规约时面临着两个 Reduce 的选择，默认选择第一个。

其它

字符串解析

通过如下方式可以设置使用内存字符串而非文件：

YY_BUFFER_STATE yy_scan_string(const char *str);
YY_BUFFER_STATE yy_scan_bytes(const char *bytes, int len);

这里会返回一个 YY_BUFFER_STATE 类型，在使用完之后，需要通过 yy_delete_buffer() 删除，也就是在通过 yylex() 解析前会先复制一份数据，然后解析时会修改缓存。

如果不希望复制，那么可以使用如下函数。

YY_BUFFER_STATE yy_scan_buffer(char *base, yy_size_t size)

下面是一个简单的示例：

int main() {
	yy_scan_string("a test string");
	yylex();
}

变量

$$ $1 $2 ... 定义了默认的参数，示例如下：

exp:
| exp '+' exp     { $$ = $1 + $3; }

exp[result]:
| exp[left] '+' exp[right]  { $result = $left + $right; }

示例程序

实现一个简单的计算器程序，能进行加、减、乘、除、幂运算，需要注意优先级。

calc.l 文件。

%{
    #include "calc.tab.h"
    #include <stdlib.h>
    void yyerror(char *);
%}

%%

[a-z]       {
                yylval = *yytext - 'a';
                return VARIABLE;
                }

[0-9]+      {
                yylval = atoi(yytext);
                return INTEGER;
            }

[-+()=/*\n]     { return *yytext; }

[ \t]   ;       /* skip whitespace */

.               yyerror("Unknown character");

%%

int yywrap(void)
{
	return 1;
}

calc.y 文件。

%{
	#include <stdio.h>
	void yyerror(char *);
	int yylex(void);
	int sym[26];
%}

%token INTEGER VARIABLE
%left '+' '-'
%left '*' '/'

%%

program:
	program statement '\n'
	| /* NULL */
	;

statement:
	expression                      { printf("%d\n", $1); }
	| VARIABLE '=' expression       { sym[$1] = $3; }
	;

expression:
	INTEGER
	| VARIABLE                      { $$ = sym[$1]; }
	| expression '+' expression     { $$ = $1 + $3; }
	| expression '-' expression     { $$ = $1 - $3; }
	| expression '*' expression     { $$ = $1 * $3; }
	| expression '/' expression     { $$ = $1 / $3; }
	| '(' expression ')'            { $$ = $2; }
	;

%%

void yyerror(char *s)
{
	fprintf(stderr, "%s\n", s);
}

int main(void)
{
	yy_scan_string("1+1\n");
	yyparse();
}

all:
	bison -d calc.y
	flex -o calc.lex.c calc.l
	gcc calc.lex.c calc.tab.h calc.tab.c -o calc -lm

clean:
	rm -f calc.lex.c calc.tab.c calc.tab.h calc test

参考

Guido van Rossum Python 作者的 Blog ，初篇介绍了很多关于解析器的内容。
Lex and YACC HOWTO 关于 Lex 和 Yacc 的详细介绍，可以作为入门。
龙书中的相关介绍，很多不错的资源，包括了 PDF 以及源码。

Bison 简介

简介 #

文件格式 #

示例 #

规则 #

终结符 VS. 非终结符 #

Token VS. Type #

%union #

使用 #

其它 #

冲突 #

递进 规约 #

Shift-Reduce #

Reduce-Reduce #