Bison解析器生成器概览

Bison是GNU的一个LALR(1)（实际上甚至支持任何每个串只有有限种的解析方式的上下文无关语法）解析器生成器，与yacc兼容。只要写出语法和，Bison支持生成C/C++/Java的解析器代码。

语法文件形如：

其中可用C语言风格的注释。

导言中可声明类型和变量或是其它代码，例如包含头文件、声明词法分析器 yylex 和错误处理器 yyerror 还有其它全局变量。它们会被放到输出文件的较前位置。

声明中声明语法符号及其语义值类型、运算符优先级等等。

符号名由字母、下划线、句号、非开首的数字和横线组成。终结符有三种方式表示：

标识符（通常大写），须用


    %token

声明

用单引号包围的一个字符，通常用于表示字面上的该字符

用双引号包围的一个字符序列，除不支持三字符转义外与C语言含义同，通常用于表示字面上的该字符串


   %code 位置 {代码}

把给定代码原样复制到解析器中指定位置（


   requires

（包含头文件的位置）、


   provides

（头文件中）、

top

（包含头文件的位置与解析器之间）、


   imports

）


   %file-prefix "前缀"

指定输出文件名对应输入文件名


   前缀.y


   %output "文件"

指定输出文件


   %language "语言"

指定生成解析器的语言（C/C++/Java）


   %name-prefix "前缀"

为外部可用名字加给定前缀而非yy


   %skeleton "文件"

指定基于的骨架


   %verbose

生成更多信息

其中 RESULT 为非终结符， COMPONENTS 为一些终结或非终结符或语义动作。其中空白只作为分隔符。语义动作形如 {C STATEMENTS} ，只要里面的C代码花括号平衡（不考虑三字符转义），其中可用 $$ 引用 RESULT 或当前中间动作的语义值、用 $N 引用第N个（从1开始）分量的语义值（只能引用前面的，动作的语义值要用 $<类型>N 引用）。在分量后加 [名字] 可给分量一个名字，然后可用此 名字 或 [名字] 代替数字引用其语义值（如果规则中某符号只出现一次，也直接可用符号名）。可以用 @N 引用分量N的位置，用 @$ 引用目标的位置，用 yylloc 引用向前看符号位置。没有动作的规则默认动作为 $$ = $1 。

生成 RESULT 的多条规则可以分开写，也可以写在一起如：

RESULT:
  RULE1-COMPONENTS…
| RULE2-COMPONENTS…
如果容许RESULT匹配空字符串，可以干脆在规则中不写分量，如semicolon.opt: | ";";，但视觉上往往得不到注意，所以也可写%empty作占位符。
语法规则可以互递归，在左递归与右递归之间最好用左递归，因为LR归约由右到左进行，左递归省栈空间。
语义动作通常在规则最后，有动作在中间的规则都可化为一系列动作在后的规则。如
target: A {动作} B;
subtarget: A {动作};
target: subtarget B;
。值得一提的是，插入中间动作可能引致冲突。
用户代码中可以有任意代码，通常有导言中声明的函数实现，会原样被复制到输出。
以下我们实现一个简单的计算器，首先写个flex文件：
#include <stdlib.h>
#include "calc.tab.h"
DIGIT	[0-9]
PUNCT	[-+*/)(\n]
{DIGIT}+	yylval=atoi(yytext);return TOK_NUMBER;
{PUNCT}	return yytext[0];
再写个bison文件：
#include <stdio.h>
int yylex (void);
void yyerror(char *message);
%define api.value.type {int}
%token	TOK_NUMBER
%left '+' '-'
%left '*' '/'
%start	statement
statement:	%empty
			| statement expression '\n' {printf("%d\n",$2);};
expression:	TOK_NUMBER {$$=$1;}
			| '(' expression ')' {$$=$2;}
			| expression '+' expression {$$=$1+$3;}
			| expression '-' expression {$$=$1-$3;}
			| expression '*' expression {$$=$1*$3;}
			| expression '/' expression {$$=$1/$3;};
int main(){
	yyparse();
void yyerror(char * message){
	fputs(message,stderr);
然后写个makefile：
calc.out: lex.yy.c calc.tab.c
	gcc $+ -lfl -o $@
lex.yy.c: calc.lex calc.tab.h
	flex $<
calc.tab.h calc.tab.c: calc.y
	bison --defines $<
clean:
	rm lex.yy.c *.out
现在，只要make一下就会生成我们要的可执行文件calc.out。这个计算器当然功能不强，但读者应该已经知道如何为它加上更多功能。