Bison是一种通用解析器生成器，它将带注释的上下文无关文法转换为使用LALR（1）解析器表的确定性LR或广义LR（GLR）解析器 。作为一项实验性功能，Bison还可以生成IELR（1）或规范的LR（1）解析器表。一旦您精通Bison，就可以使用它来开发各种语言解析器，从用于简单台式计算器的语言解析器到复杂的编程语言。 Bison与Yacc向上兼容：所有正确编写的Yacc语法都应与Bison一起使用，而无需进行任何更改。熟悉Yacc的任何人都应该可以轻松使用Bison。您需要精通C或C ++编程才能使用Bison。还支持将Java作为实验功能。
Bison由三部分组成
- 定义部分
- %%
- 规则部分
- %%
- 用户附加的C语言部分
定义部分
代码部分
%{ ... %}，或%code { ... }的内容都是C代码，并将代码照搬到生成的C文件中，可以定义一些函数声明，结构体，类型等，还可以重定义一些Bison的宏，从而改变程序的规则。
声明%name
与flex %option类似，提供一定机制来控制bison默认规则。
- %pure-parser，指定希望解析器是可重入的。
- %expect 0，希望冲突数量为0
- %name-prefix="base_yy"，代表生成的函数和变量名从yy改成base_yy
- %locations，生成处理位置的代码。 语法使用特殊的'@n'标记后便会启用此模式，但是如果您的语法不使用它，则使用'％locations'可以获取更准确的语法错误消息。
- %parse-param {core_yyscan_t yyscanner}，声明一个或多个参数声明是其他yyparse参数。 在声明函数或原型时使用参数声明。 参数声明中的后一个标识符必须是参数名称。
- %lex-param {core_yyscan_t yyscanner}，指定参数声明是其他yylex参数声明。 您可以传递一个或多个这样的声明，等效于重复％lex-param。
- %union，嵌入动作返回值类型，一般为非终结符的类型定义。如：
%union
{
core_YYSTYPE core_yystype;
/* these fields must match core_YYSTYPE: */
int ival;
char *str;
const char *keyword;
char chr;
bool boolean;
JoinType jtype;
DropBehavior dbehavior;
OnCommitAction oncommit;
……
……
……
InsertStmt *istmt;
VariableSetStmt *vsetstmt;
PartitionElem *partelem;
PartitionSpec *partspec;
PartitionBoundSpec *partboundspec;
RoleSpec *rolespec;
}8. %type<>，Bison构造％type用于声明非终结符。 以前我们以前没有使用％type，因为非终结符通常由定义它们的规则隐式声明。 但是必须显式声明exp，以便我们可以指定其值类型。
9. %token<>，token类型定义。在PostgreSQL中为关键字定义。
10. 优先级定义，为了避免过多的语法冲突，在这里定义一些语法优先级，从上到下优先级依次递增
%nonassoc SET /* see relation_expr_opt_alias */
%left UNION EXCEPT
%left INTERSECT
%left OR
%left AND
%right NOT
%nonassoc IS ISNULL NOTNULL /* IS sets precedence for IS NULL, etc */
%nonassoc '<' '>' '=' LESS_EQUALS GREATER_EQUALS NOT_EQUALS
%nonassoc BETWEEN IN_P LIKE ILIKE SIMILAR NOT_LA
%nonassoc ESCAPE /* ESCAPE must be just above LIKE/ILIKE/SIMILAR */
%left POSTFIXOP /* dummy for postfix Op rules */规则部分
规则分为规则/行为行和C代码行。
规则/行为
bison语法是由一系列的规则组成。每个规则由非终结符开始，然后是“:”和可能为空的符号、文字记号和动作的列表。 例如：
simple_select:
SELECT opt_all_clause opt_target_list
into_clause from_clause where_clause
group_clause having_clause window_clause
{
SelectStmt *n = makeNode(SelectStmt);
n->targetList = $3;
n->intoClause = $4;
n->fromClause = $5;
n->whereClause = $6;
n->groupClause = $7;
n->havingClause = $8;
n->windowClause = $9;
$$ = (Node *)n;
}
|
……
……
……
;- “:”左边为非终结符。
- “:”右边为规则，由一系列的终结符或非终结符构成。
- “$$”，表示simple_select。
- “$number”，表示“:”右边符号，数字为几，则表示第几个符号。
- “|”，表示或，“simple_select”其他规则。
代码段
此段落，postgresql, 定义了一些在规则段中使用的工具函数。
移进/归约
移进：bison语法分析器通过查找能够匹配当前token的规则来运作。当bison处理一个语法分析器时，他创建一组状态，每个状态都反应出一个或者多个部分分析过的规则中可能的位置。当语法分析器读取记号时，每当它读到的记号无法结束一条规则时，它将把这个记号压入一个内部堆栈，然后切换到一个新状态，这个状态能够反映出刚刚读取的记号。这种行为被称为移进。
归约：当它发现压入的所有语法符号已经可一以组成规则的右部时，他将把右部符号全部从堆栈中弹出，然后把左部语法符号压入堆栈。这种行为被称为归约。因为它通常消减了堆栈中一定数量的符号。每当bison归约一条规则时，它会执行该规则关联的用户代码。
二义性
只要是对于语言的解析，往往都会伴随二义性的问题。bison把语法翻译为成语法分析器时有可能会报告冲突。一些情况下，语法确实有歧义；也就是说。对于一个输入的字符串，存在两种可能的语法分析器，而bison无法处理这种情况。（当然也有可能是bison对于某些规则不支持的缘故）。 bison的二义性冲突分为移进/归约冲突和归约/归约冲突。 移进/归约冲突：
%%
e: 'X'
| e '+' e
;在这里，当我们输入X+X+X时，存在两种可能，（X+X）+X和X+（X+X）。移进会按照第二条规则进行，而归约会按照条规则进行，这时就会存在矛盾。 移进/归约冲突：
%%
prog: proga | progb ;
proga: 'X';
progb 'X';移进不会产生歧义，但当归约时，X既是proga又是progb，这就会造成归约/归约冲突。
工作流程
flex&bison协作方式
