http://ftp.gnu.org/gnu/bison/
安装bison需要先安装 msys下的flex

http://sourceforge.net/projects/mingw/files/MSYS/Extension/flex/
（flex-2.5.35-2-msys-1.0.13-bin.tar.lzma）

./configure --prefix=/mingw
make
make install


实际msys有现成版本
http://sourceforge.net/projects/mingw/files/MSYS/Extension/bison/bison-2.4.2-1/
（bison-2.4.2-1-msys-1.0.13-bin.tar.lzma）
                                                    
转载于:https://my.oschina.net/rechy/blog/189705

文章目录
工作原理
.y文件结构
原理
编译运行
语义 (语义值类型，语义动作)
声明部分(终结符，编码，结合律，优先级)
优先级和结合律
bison 无法处理的语法
语法与内置函数
编译选项
冲突与出错处理
冲突
出错处理
跟踪分析过程
flex & bison
原理
例子(后缀表达式的计算)：

工作原理
.y文件结构

YYSTYPE		语义值类型
%token NUM  定义终结符NUM
yyerror			必须用户自己提供
int yylex()   这个例子中使用自己编写的yylex，实际会使用flex编译的文件所提供的yylex
产生式右边为空表示 $\epsilon$
产生式后面的c语言代码称为语义动作
$$ 表示产生式左部的语义值
$1,$2,…分别表示右边第一，第二个符号的语义值
yylval 是全局变量，表示当前所识别的词形的语义值。

%{
c 语言说明部分，定义语义动作中需要的全局变量，语义值类型，以及头文件等
// 逆波兰表达式的计算
#define YYSTYPE int
#include <ctype.h>
#include<stdio.h>
void yyerror(char*);
int yylex();
%}

声明部分
定义终结符， 规定非终结符语义值类型，规定运算优先级，规定文法形态等
%token NUM

%% 
语法规则部分，定义产生式和语义动作
input:		/*empty equal to epsilon*/
	| input line
	;
line: '\n'
	|exp '\n'	{printf("\%.d\n",$1);}
	;
exp: NUM	{$$ = $1;}
	| exp exp '+' 	{$$ = $1+$2;}
	| exp exp '-'	{$$ = $1-$2;}
	| exp exp '*' 	{$$ = $1*$2;}
	| exp exp '/' 	{$$ = $1 / $2;}
	| exp 'n'	{$$ = -$1; }
	;
%%
// 附加c语言代码：
bison直接拷贝到.tab.c文件的尾部，用户再次可定义接口函数，也可由其它文件提供再链接。
int yylex(){
	int c;
	/*skip white space*/
	while((c=getchar())==' '||c=='\t')
		;
	/*process numbers*/
	if(isdigit(c)){
		ungetc(c, stdin);
		scanf("%d",&yylval);
		return NUM;
	}
	if(c==EOF) 
		return 0;
		
	return c;
}

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

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

原理

对输入.y文件中的形式文法构架LALR分析表，并生成基于该分析表的语法分析器C语言源程序.tab.c。
bison 通过 int yylex() 的返回值获得单词的编码；通过全局变量YYSTYPE yylval获得当前单词的语义值.
分析方法采用自顶向上的移进/规约法，完成规约时，yyparse()将执行bison源文件对应产生式的语义动作。
必要的语法环境：yylex()，main()， yyerror()， 其中yylex可由用户提供，也可由flex源程序提供，然后和bison源程序一起连接成可执行文件

编译运行

bision rpcalc.y
gcc -o rpcalc rpcalc.tab.c
rpcalc  （启动程序）

语义 (语义值类型，语义动作)
 语义值类型：

由于在移进、规约的时候是拷贝进栈，所以当语义值的类型是指针时，所指的地址一定不能是局部变量。安全的做法是：生命周期开始时通过动态申请内存所指的值保存，生命周期结束时释放该内存(动态内存分配)
通过%union 在声明部分讲YYSTYPE定义为C语言的union结构。

对于非终结符，通过 %type \<union 分量名> 非终结符名 来规定语义动作中以何种方式访问语义值对应的类型。
对于非终结符，使用 %token \<union 分量名> 终结符名，或者%type规定。
在语义动作中，使用$<comp_name>m访问



%union { 
	double val; /* 表达式的语义值 */ 
	SYMREC *tptr; /* 变量和函数的语义值是符号表元素指针 */ 
} 
%token<val> NUM /* 语义值的类型是双精度浮点数 */ 
%token<tptr> VAR FNCT /* 语义值的类型是符号表元素指针 */ 
%type<val> exp 

 语义值声明周期：

在语义栈中存在的时间
比如 NUM的生命周期从yylex()通过scanf("%d",&yylval)创建，然后压入语义栈中，随后规约exp:NUM {$$=$1}, NUM的语义值从栈中退出，exp的语义值压入。

 语义动作的翻译：
源文件中的
exp:  exp exp '\' 	{$$ = $1 \ $2;}

会被翻译为：

$(yyval) = (yyvsp[(1) - (3)]) / (yyvsp[(2) - (3)]);$

yyvsp 是一个栈栈顶是yyvasp[0], 越往栈底走，索引依此减1，这个例子的存储数据为：

 (栈顶)’\’ $2 $1，
 语义动作：

尾部语义动作

产生式尾部的语义动作在发现该产生式句柄时已经在栈顶形成，需要对该产生式进行规约时进行。语义动作包括计算综合属性(S属性)和产生副作用

每个产生式有一个默认动作 {$$=$1;}

产生式中间语义动作

用来解决**继承属性(L属性)**的计算







在这里插入图片描述

声明部分(终结符，编码，结合律，优先级)

bison将终结符分为两类：字符(Symbol)和单词(Token). Token需要声明，字符在产生式(语法规则)中直接用字符常量，注意加引号’  '。如 exp: exp exp + 是错的


token对终结符的编码规则

0或负数： 文件结束标记
字符单词：对应的ASCII码
error： 256
非字符单词从258开始顺序编码, 在.tab.c中可以找到具体定义




在使用单独的词法分析模块的时候，需要bison需要使用 -d 选项，这样讲token的宏定义等输出到.tab.h 文件中，这样词法分析模块可以include此头文件来使用宏定义的token。


规定结合律

%left ‘+’ ‘-’


优先级和结合律
%left '+' '-' 
%left '*' '/' 
%left UMINUS 
%% 
exp : exp '+' exp 
	| exp '-' exp 
	| exp '*' exp 
	| exp '/' exp 
	| '-' exp %prec UMINUS
	;


结合性：%left 左结合； %right 右结合；%nonassoc 不能结合；
出现在同一个%left后的单词优先级相同
优先级：出现在不同 “%left” 的终结符，其运算优先级别按照 “%left” 在源文件中出现 的先后次序由低到高排列, 即：UMINUS的优先级最高，乘法和除法次之，加法和 减法最低.
由于一元减和二元减的运算符相同，在语法中出现一元减的产生式通过%prec UNIMUS设定一元减和UMINUS具有相同的优先级.

bison 无法处理的语法
 bison语法分析器可以使用两种分析方法，一种是LALR(1), 另一种是GLR(通用的自左向右)。GLR更强大但更麻烦。

  LALR(1)不能处理的语法有：

有歧义的语法
需要向前查看超过1个记号才能确定是否匹配的语法。

语法与内置函数




变量
说明




yylval
当前终结符语义值的全局变量


YYSTYPE
语义值数据类型


编译选项




选项
说明




-d
输出文件 .tab.h


-v
输出分析表文件 name.output


-t
在输出文件(.tab.c)中设置宏YYDEBUG 为1， 从而打开分析器的调试代码，使得最后生成的分析器文件能够对分析过程进行追踪。


冲突与出错处理
冲突

输出冲突的报警信息：打开-t选项，在LALR(1)分析表文件.output文件中指出冲突所在
如果是S/R冲突，优先S
如果是RR冲突，排列在前者优先。

出错处理

如果在 bison 输入文件中没有任何提供任何出错处理，输出分析器在工作时，如果发现语法错误 (即在当前状态下面对当前的终结符不能进行任何移进或归约 操作), yyparse()在传参 “syntax error” 调用用户提供的void yyerror(char const *)函数后，返回1退出yyparse().
通常yyerror可定义如下：

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


bison 通过预留的终结符 error 提供从出错状态恢复分析的机制, 如：

$stmnts: /* empty\ string */$ $| stmnts\ \ '\backslash n'$ $| stmnts\ \  exp \ \ '\backslash n'$ $| stmnts\ \  error\ \  '\backslash n'$

在产生式右边有保留终结符 error 的规则称为错误恢复规则，输出分析器在一 个含有错误恢复规则的状态出错时，首先从分析栈中弹出语法符号直到能 将 error 移进，在栈顶形成错误恢复规则中 error 前的句型为止，如上例中在 分析exp 时出错，将弹出所有的已分析的表达式成分，将 error 压栈到项目,  此时栈中符号为：{stnmts error . ‘\n’}; 然后，跳过所有的输入直到遇到错误恢 复规则规中error的后随符号为止. 如上例中将跳过所有的输入直到’\n’ 才恢 复分析.
在错误恢复规则中可以像其他规则一样有语义动作，但是不能引用终结 符error的语义值.
在某一错误恢复规则起作用时，为了防止分析器频繁报错，输出分析器规定只 有在连续移进三个单词后才恢复报错，在错误恢复规则语义动作中，可以使用 bison 提供的 C 语言宏 “yyerrok;” 解消上述限定，即刻恢复报错机制.
在激活错误恢复规则后，当前向前查看的单词将会继续作为向前查看符号进行 分析，如果用户希望跳过该单词，可在语义动作中用 bison 提供的宏 “yyclearin;” 跳过当前单词. 但是由于该操作是在归约出错产生式时才起作用， 因此如果错误恢复规则中error 之后还有终结符，只有移进该终结符才能有语 义动作，因此 “yyclearin;” 将无任何效果. “yyclearin;” 有效当且仅当它是 在紧随error之后的动作中

跟踪分析过程
调用yyparse()前，置yydebug非零，如下的main.c
main() { 
	extern int yydebug;
	yydebug = 1;
	yyparse(); 
}

flex & bison
原理
flex 输出的单词扫描程序正是int yylex(), 为了让 bison 输出的语法分析源程序能与 flex 输出的词法分析源程序协同工作，必须保证单词编码的一致，以及 语义值数据类型的一致, 这要求在 flex 源程序中:

1 定义部分包含 bison 输出的头文件.tab.h
2 根据语法规则中的单词设计匹配单词的正规表达式，及需要过滤的白字符 (white space) 和注释, 如: ‘\n’ 如果是语义规则所需的单词，就不能冒然 过滤掉
3 在识别单词的 C 语言动作中，如果该单词有语义值，应先计算其语义值并 赋值到全局变量yylval，如果是字符单词，return yytext[0];，否 则return 单词名;
4 为了保证词法分析能处理所有的字符，对语法分析不支持的字符的的动作报错并过滤
5 bison 使用的单词名不能与 flex 中自带的宏名有冲突. 如: BEGIN不能作为 单词名, 否则return BEGIN;将调用 flex 预置的宏BEGIN, 而不能返回期望的单 词编码, 可修改单词名为SBEGIN来避免冲突.

例子(后缀表达式的计算)：
rpcacle.y:
%{
// 逆波兰表达式的计算
// #define YYSTYPE int  默认int
#include<stdio.h>

void yyerror(char*);
int yylex();
%}

%token NUM
%token ADD SUB MUL DIV
%token EOL

%% 
input:		/*empty equal to epsilon*/
	| input line
	;
line: EOL
	| exp EOL	{printf("\%d\n",$1);}
	;
exp: NUM	{$$ = $1;}
	| exp exp ADD 	{$$ = $1+$2;}
	| exp exp SUB	{$$ = $1-$2;}
	| exp exp MUL 	{$$ = $1*$2;}
	| exp exp DIV 	{$$ = $1 / $2;}
	;
%%


int main(void){ 
	int n=yyparse();
	printf("%d",n);
	return n;
}

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

rpcalc.l

%{
#include "rpcalc_fb.tab.h"

%}

%%
"+"	{ return ADD; }
"-"	{ return SUB; }
"*"	{ return MUL; }
"/"	{ return DIV; }

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

\n      { return EOL; }
"//".*  
[ \t]   { /* ignore white space */ }
.	{ printf("Mystery character %c\n", *yytext); }
%%

当我们的文法设计的有问题的时候，就需要开启bison的调试方式来检测文法错在哪里，那么如何开启bison的调试方式呢？
bison调式需要做的事情如下：
1 ）在语法文件*.y定义段开启yydebug，最终如下：
%{
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
int yydebug=1;
%}

2）在编译语法文件*.y的时候，使用-v参数，生成output文件，这个文件中的内容可以帮助我们分析语法分析过程，使用–debug参数，生成的C代码包含调试信息。

命令如下：
bison a.y -d -v --debug

-d是用来生成头文件的，与调试无关。

-v生成output文件，描述了我们创建的自动机，可以帮助我们分析调试内容。
–debug使得生成的C代码包含更多的调试信息输出

3）编译目标代码，如下：
gcc -o test lex.yy.c a.tab.c -lfl -ly

4）运行test

5）结合程序输出信息和output文件的内容，可以知道我们设计的语法错在哪里。