如有错误，望君指正。
1，bison简介
参考wiki所知，bison是一个GNU自由软件，用于自动生成语法分析器。根据自定义的语法规则，你可以分析大部分语言的语法，小到桌面计算器，大到复杂的编程语言。想要全面了解bison各个部分，参考bison官方文档http://www.gnu.org/software/bison/manual/bison.html
2，基础知识
2.1 GLR 分析器
bison确定性LR(1)算法在某一特定语法规则点上，不能决定这一步是归约还是移近。例如：
expr: id | id ‘+’ id;
这样在第一个id的时候，不知道是归约还是移近’+’。这就是众所周知的reduce/rduce和shift/reduce冲突。因为语法改成LR(1)比较复杂，所以GLR分析器运用而生。它大概的原理是，当遇到冲突的时候，那么几条路都会试着走，试着走是不执行动作。如果只有一条路走通了，那么就执行动作，舍弃其它路子；如果都没有走通，那么就报语法错误；如果多余一条都走通，把相同规约合并，bison可能根据动作优先级来执行，也可能都会执行。
2.2 终结符、非终结符
终结符也就是token，从yylex返回的类型，也是语法树结构的叶子节点。一般用大写字母表示。非终结符用于编写语法规则，也是语法树结构的非叶子节点，一般用小写字母表示。
2.3 语法树
讲语法结构抽象成树形表示。
例如：1+2*3
表达成树形结构为：
3，语法结构
%{
Prologue
%}
Bison declarations
%%
Grammar rules
%%
Epilogue
‘%{‘和’%}’之间是c/c++语言的头文件、全局变量、类型定义的地方，还需要在这里定义词法分析器yylex和错误打印函数yyerror。
‘%}’和’%%’之间是bison声明区间。在这里你需要定义你之后要用到的终结符、非终结符的类型，操作符的优先级。
‘%%’和’%%’之间是bison语法规则定义。后文会结合例子来讲解。
第二个’%%’之后是c/c++代码，需要定义Prologue区域的函数，或者其它代码，生成的c/c++文件会完全拷贝这部分代码。
4，事例
课程（链接）自带的linux已经安装好了bison，如果你用自己的linux版本，那么需要yum或apt-get来安装。
4.1 简单计算器
一个最简单的计算器，只有整数的加减法。介绍完整的一个bison文件的各个部分。
calculation.y代码：https://github.com/YellowWang/bison/blob/master/calculation/calculation.y
Prologue代码：
%{
//#define YYSTYPE double
#include <ctype.h>
#include <stdio.h>
int yylex (void);
void yyerror (char const *);
%}
你可以发现我注释掉了YYSTYPE的定义，YYSTYPE指定所有token的语义值类型，如果没有定义，那么默认为int。这个例子是整数计算器，所以就用默认值。#include引用c头文件。声明yylex和yyerror函数，这两个函数是必须的，因为c语言需要在用到这个函数之前需要提前声明。yylex函数分解token，返回每个token的类型。yyerror函数输出错误信息。
bison声明代码：
%}
%token NUM
%left ‘+’ ‘-‘
%%
声明一个终结符NUM。
设置’+’和’-‘是左结合的。例如：a+b-c，左结合下优先a+b，结果再-c。右结合则优先b-c。
语法规则代码：
%%
input:
/* empty */
| input line
;
line:
‘
‘
| expr ‘
‘ { printf (“%d
“, $1); }
;
expr:
NUM { $$ = $1; }
| expr ‘+’ expr { $$ = $1 + $3; }
| expr ‘-‘ expr { $$ = $1 – $3; }
;
%%
‘/*’与’*/’之间是注释，’|’是或的意思。我们先看第一段代码：
input:
/* empty */
| input line
;
这段的意思是：一个完整的input，要么是空（什么也没有），要么就是这个input后面跟着一个line。所以input可以推出形如”input line line…”这样的结构。也就说这是一个左递归结构。
第一个规则为空，是因为’:’和’|’中间什么也没有（注释和空白符不算）。input和line都是非终结符。这个完整的规则后需要加’;’来代表此规则定义结束。
line:
‘
‘
| expr ‘
‘ { printf (“%d
“, $1); }
;
这段的意思是：一个完整的line，要么是’
‘换行符，要么是expr后加一个’
‘换行符。expr是非终结符。line是由两个规则组成，每个规则后面如果有动作，那么用一对大括号包围。动作是c/c++代码。如第二个规则的动作的意思是：如果line推出expr ‘
‘，那么把expr的值打印出来。$1代表的是expr的语义值。语义在这里是整数。$后数字分表代表这个规则的第几项。如$2就代表’
‘，不过$2是没有意义的。$$代表line的语义值，这里仅仅是打印出expr的值。
expr:
NUM { $$ = $1; }
| expr ‘+’ expr { $$ = $1 + $3; }
| expr ‘-‘ expr { $$ = $1 – $3; }
;
这段的意思是：一个完整的expr，要么是终结符NUM，要么是expr 加上 expr，要么是expr 减去 expr。当expr是一个整数NUM，那么把这个整数赋值给expr。当expr推出expr ‘+’ expr，那么把加法的结果给$$。因为expr是非终结符，所以expr推导直到NUM为止。减法类似。这是一个递归结构，例如这样一个语句：1+3-2。根据规则expr->NUM先归约expr+3-2，然后规约’+’，继续归约终结符为expr+expr-2。因为左结合，根据expr->expr + expr，得expr-2。继续归约终结符的expr-expr，最后结果为expr，归约结束。
%%
int yylex (void)
{
int c;
/* Skip white space. */
while ((c = getchar ()) == ‘ ‘ || c == ‘ ‘)
continue;
/* Process numbers. */
if (c == ‘.’ || isdigit (c))
{
ungetc (c, stdin);
scanf (“%d”, &yylval);
return NUM;
}
/* Return end-of-input. */
if (c == EOF)
return 0;
/* Return a single char. */
return c;
}
/* Called by yyparse on error. */
void yyerror (char const *s)
{
fprintf (stderr, “%s
“, s);
}
int main (void)
{
return yyparse ();
}
yylex函数读取输入，如果是数字，就赋值到yylval。因为刚才定义的数字的语义类型为int，所以yylval就是int型。bison的语法规则里用到的形如$1的语义值，就是在yylex函数里赋值的。yylex略去非数字部分，直到文件结尾结束。
yyerror函数直接输出bison默认错误字符串”syntax error”。你可以根据错误类型自定义错误提示。当错误提示返回后，你需要从错误中恢复，这在下面的例子中讲到。这个例子没有做恢复处理，所以一旦有语法错误，就直接退出程序。
main函数直接调用yyparse进行语法分析过程。
编译、运行：
编译bison语法文件，输入命令：bison calculation.y
没有报错的话，生成文件：calculation.tab.c
编译c文件，输入命令：gcc calculation.tab.c
没有错误的话，生成可执行文件：a.out
运行，输入命令：./a.out
输入：1+1
输出：2
输入：1+2-1-2
输出：0
输入：1++2
输出：syntax error
程序退出
4.2 计算器2.0版本
加强版本。支持浮点数运算，加入乘除法，加入指数运算。介绍操作符优先级等。
calculation2.0.y代码：https://github.com/YellowWang/bison/blob/master/calculation2.0/calculation2.0.y
Prologue代码：
%{
#define YYSTYPE double
#include <ctype.h>
#include <stdio.h>
#include <math.h>
int yylex (void);
void yyerror (char const *);
%}
定义YYSTYPE为double，默认所有终结符、非终结符的语义类型为double类型。
bison声明代码：
%token NUM
%left ‘+’ ‘-‘
%left ‘*’ ‘/’
%right NEG
%right ‘^’
%token定义NUM为终结符，此处和上例一样。
%left是左结合，%right就是右结合，后面跟着操作符，用空格隔开。定义在下方的操作符比上方的操作符优先级更高。一行定义内的操作符之间的优先级是一样的。由此得出，乘除优先级大于加减，NEG是非，优先级大于乘除，指数运算大于之前所有。
语法规则部分代码：
expr:
NUM { $$ = $1; }
| expr ‘+’ expr { $$ = $1 + $3; }
| expr ‘-‘ expr { $$ = $1 – $3; }
| expr ‘*’ expr { $$ = $1 * $3; }
| expr ‘/’ expr { $$ = $1 / $3; }
| ‘(‘ expr ‘)’ { $$ = $2; }
| expr ‘^’ expr { $$ = pow($1, $3); }
| ‘-‘ expr %prec NEG { $$ = -$2; };
;
加减乘除值之前写法差不多。有'(”)’的，语义值为括号里面的值。指数乘法用到c数学库pow函数。下来我们来看看这条规则
‘-‘ expr %prec NEG { $$ = -$2; };
在bison里，一个操作符不能定义两个不同的优先级，所以’-‘已经用作减法的优先级，就不能再用来做负号的优先级。为了解决这个问题，在bison里，先定义操作符NEG的优先级，然后通过 %prec NEG来指定’-‘在这个规则为NEG相同的优先级。那么如1–1结果为2。
编译的时候需要链接数学库（gcc calculation2.0.tab.c -lm），不然提示pow未定义。
运行：
输入：(-1+3)*5-2^3
输出：2.00000
4.3 计算器3.0版本
终极版本。除了含有之前版本的功能外，加入大小判断、if语句、while语句、赋值语句，有简单语言的雏形。
calculation3.0.y代码：https://github.com/YellowWang/bison/blob/master/calculation3.0/calculation3.0.y
bison声明代码：
%union{
Expressions* expressions;
Expression* expression;
char name[32];
double num;
}
%token ASSIGN 258
%token<num> DOUBLE_CONST 259
%token<name> IDENTIFIER 260
%token IF 261 THEN 262 ELSE 263 FI 264
%token WHILE 265 LOOP 266 POOL 267
%right ASSIGN
%nonassoc ‘<‘
%left ‘+’ ‘-‘
%left ‘*’ ‘/’
%right NEG
%right ‘^’
%type<expression> expr
%type<expressions> exprs
%type<expressions> exprs_no
可以发现这次比较复杂，我们逐一讲解。
%union{
Expressions* expressions;
Expression* expression;
char name[32];
double num;
}
我们之前的例子，所有的终结符、非终结符的语义类型都是一样的，或整型或浮点型。不过这个例子，会有多种语义类型。%union后大括号里面，每种类型是一个c方式的类型定义。这里有四种类型，分别是Expressions*，Expression*，char[32]，double。因为name是32字节，所以变量名不能超过这个大小。先不用管这些是什么，做什么用，等我接下来慢慢道来。
%token ASSIGN 258
%token<num> DOUBLE_CONST 259
%token<name> IDENTIFIER 260
%token IF 261 THEN 262 ELSE 263 FI 264
%token WHILE 265 LOOP 266 POOL 267
%type<expression> expr
%type<expressions> exprs
%type<expressions> exprs_no
%token定义终结符。后面跟着数字代表终结符的编号。%token ASSIGN 258 表示ASSIGN终结符的编号为258。bison会转化成#define ASSIGN 258。这个和yylex函数返回的类型和编号要保持一致（也可以不指定编号，有的话更方便和lex的宏对应）。终结符的类型通过”%token<类型名> 终结符”这样的格式来确定。所以DOUBLE_CONST的类型名是num，也就是double类型。IDENTIFIER的类型名是name。关键字终结符不需要类型，所以属于默认类型，也就是YYSTYPE所定义的类型int。
%type是指定非终结符的类型，用法和%token一样，不过不需要指定编号。我们可以发现expr是expression类型。这里expr的意思是一个表达式，exprs和exprs_no是多个表达式集合。
%nonassoc ‘<‘
%left ‘+’ ‘-‘
%left ‘*’ ‘/’
%right NEG
%right ‘^’
这次多了一个新玩意%nonassoc，意思是后面的操作符是没有结合性的，所以只能是a<b，而不能为a<b<c，这样bison就无法分辨先是a<b还是b<c。
语法规则代码：
input:
/* empty */
| exprs
;
一个完整的输入input是由空或exprs组成。
exprs:
error { $$ = 0;}
| exprs error
| expr ‘;’
{
$$ = t_single_exprs($1);
Execute($1);
}
| exprs expr ‘;’
{
$$ = t_append_exprs($1, $2);
Execute($2);
}
;
我们先略过error不看。exprs是由expr ‘;’或 exprs expr ‘;’组成。也就是说一个表达式集合，是由一个或多个表达式后跟’;’组成。$$ = t_single_exprs($1);动作的意思是创建只有一个表达式expr的表达式集，赋值给exprs。$$ = t_append_exprs($1, $2);动作的意思是把表达式expr加入到exprs集合里。Execute($1);的意思是执行这个表达式。这里执行的意思是计算这个表达式的语义值，输出结果。动作的详细代码稍后解析。
expr:
IDENTIFIER { $$ = t_id($1); }
| DOUBLE_CONST { $$ = t_num($1);}
| expr ‘+’ expr { $$ = t_plus($1, $3); }
| expr ‘-‘ expr { $$ = t_sub($1, $3); }
| expr ‘*’ expr { $$ = t_mul($1, $3); }
| expr ‘/’ expr { $$ = t_div($1, $3); }
| ‘(‘ expr ‘)’ { $$ = $2;}
| ‘{‘ exprs_no ‘}’ { $$ = t_block($2);}
| expr ‘<‘ expr { $$ = t_less($1, $3); }
| expr ‘=’ expr { $$ = t_eq($1, $3); }
| IDENTIFIER ASSIGN expr { $$ = t_assign($1, $3); }
| IF expr THEN expr ELSE expr FI { $$ = t_if($2, $4, $6); }
| WHILE expr LOOP expr POOL { $$ = t_while($2, $4); }
;
一个expr表达式可以是一个IDENTIFIER变量，或是一个浮点数。加减乘除括号和之前例子一样。所有的动作将在稍后讲述。
‘{‘ exprs_no ‘}’ { $$ = t_block($2);}是类似cool语言的一个语法规则：一个表达式可以推出大括号包围的表达式集合。这个集合类似之前的exprs，区别是exprs_no不需要立即执行表达式的值。因为可能条件判断不符合，所以这段代码就不能执行。
expr ‘<‘ expr { $$ = t_less($1, $3); }是比较，如果第一项小于第三项，那么结果为1，否则结果为0。
expr ‘=’ expr { $$ = t_eq($1, $3); }如果第一项等于第三项，那么结果为1，否则为0。（注：此’=’没有赋值的意思。）
IDENTIFIER ASSIGN expr { $$ = t_assign($1, $3); } 赋值语句。表达式可以给一个变量赋值，类似cool语言的语法规则，形如：abc <- 1+1。（ASSIGN就是'<-‘符号，通过flex定义，稍后会讲到）
IF expr THEN expr ELSE expr FI { $$ = t_if($2, $4, $6); }条件语句。如果第二项成立，那么就进行第四项，否则进行第六项，以FI结尾。
WHILE expr LOOP expr POOL { $$ = t_while($2, $4); }循环语句。如果第二项成立，那么就执行第四项，接着检测第二项，如此反复，直到推出循环。
exprs_no:
expr ‘;’
{
$$ = t_single_exprs($1);
}
| exprs_no expr ‘;’
{
$$ = t_append_exprs($1, $2);
}
;
exprs_no和exprs的语法是一样，只是动作少了执行。
现在再来看看错误处理：
exprs:
error { $$ = 0;}
| exprs error
如果在某一个规则下匹配不出结果，那么就用error来代替。这个规则的意思是：一个完整的表达式集，要么是一个错误表达式，要么是一个完整表达式跟着一个错误。
实践运行：
输入：1 <- 1;
输出：syntax error
输入：1**;
输出：syntax error
如果不进行处理，那么程序会直接退出。
bison的语法文件到此结束，是不是觉得少了yylex函数定义？这次的词法分析比较复杂，所以用了之前课程学到的flex词法分析器。
cal.flex代码：https://github.com/YellowWang/bison/blob/master/calculation3.0/cal.flex
词法分析器需要提供token的类型，和每个类型的语义值。我们来看看flex文件代码。
token定义部分代码：
#define ASSIGN 258
#define DOUBLE_CONST 259
#define IDENTIFIER 260
#define IF 261
#define THEN 262
#define ELSE 263
#define FI 264
#define WHILE 265
#define LOOP 266
#define POOL 267
typedef union YYSTYPE
{
Expressions* expressions;
Expression* expression;
char name[32];
double num;
}YYSTYPE;
extern YYSTYPE yylval;
是不是可以发现这里的终结符的编号和bison里面定义是一致的，出差错了的话就对应不上，导致语法分析错乱。
YYSTYPE内的4个类型需要和bison %union里面定义的内容是一致的（在flex没有用到的类型可以不写，不过保持一致比较好查错）。
extern YYSTYPE yylval;调用flex的内置变量yylval，之后要设置需要的token的语义值。
flex定义段代码：
DIGIT_INT [0-9]+
DIGIT_DOUBLE [0-9]*.[0-9]+
NOTATION ;|{|}|(|)|+|-|*|/|<|=
ASSIGN <-
BLANK f|| | |v
NEWLINE
IF (?i:if)
ELSE (?i:else)
WHILE (?i:while)
THEN (?i:then)
FI (?i:fi)
LOOP (?i:loop)
POOL (?i:pool)
IDENTFIER [a-zA-Z][a-zA-Z0-9_]*
数字分为整型和浮点数。符号和空白、换行和之前例子一样。关键字如if、else等都是大小写皆可。
flex规则段代码：
{DIGIT_INT} {/*ECHO;*/
yylval.num = atof(yytext);
return DOUBLE_CONST;}
{DIGIT_DOUBLE} {/*ECHO;*/
yylval.num = atof(yytext);
return DOUBLE_CONST;}
{NOTATION} { /*ECHO*/; return yytext[0];}
{BLANK} { /*ECHO*/; }
{NEWLINE} { /*ECHO*/; }
{ASSIGN} {/*ECHO*/; return ASSIGN;}
{IF} {/*ECHO;*/ return IF;}
{ELSE} {/*ECHO;*/ return ELSE;}
{WHILE} {/*ECHO;*/ return WHILE;}
{THEN} {/*ECHO;*/ return THEN;}
{FI} {/*ECHO;*/ return FI;}
{LOOP} {/*ECHO;*/ return LOOP;}
{POOL} {/*ECHO;*/ return POOL;}
{IDENTFIER} {/*ECHO*/; strcpy(yylval.name, yytext);
return IDENTIFIER; }
.
如果是数字，那么就转为double型，赋值给语义值。操作符直接返回字符，关键字返回相应的类型。IDENTIFIER变量名赋值给语义name。
flex文件到此结束，生成的c文件有yylex函数提供给bison。
程序运行，
输入：a <- 1;
输出：1.00
输入：a <- a + 1;
输出：2.00
输入：a;
输出：2.00
在这个程序里，变量的值是一直保存的。不过没有局部变量的含义，你可以认为全部都是全局变量。下面介绍一下做法。
symtab.c代码：https://github.com/YellowWang/bison/blob/master/calculation3.0/symtab.c
全局变量定义代码：
EXPR_DATA g_symbols[100];
int g_symnum;
EXPR_DATA是结构体，有两个成员，一个是符号变量名，一个是double型数值。这里定义一个全局符号和数值的对应表g_symbols，简单起见，最多只能保存100个变量。g_symnum保存当前不同变量的数目。
这个文件还有两个函数定义：
void SetValue(char* name, double num);
double GetValue(char* name);
SetValue是设置某一个变量的数值；Getvalue得到某一变量的数值。
之前的bison语法文件里的动作一笔带过，这里要详细讲一下。
exprtree.cpp代码：https://github.com/YellowWang/bison/blob/master/calculation3.0/exprtree.cpp
这段代码用到了c++的类，每一种表达式都有一个类对应，如：expr ‘+’ expr，对应Expr_plus类；WHILE expr LOOP expr POOL对应Expr_while类等等。这些类都继承自一个表达式基类Expression，也就是bison语法文件 %union里的类型之一。基类Expression有一个虚函数为execute，意为执行，也就是执行这个表达式的结果。所以每种表达式子类都必须实现这个接口，其实也就是实现这种表达式的语义，返回结果数值。用类的方式组织的主要原因是继承的结构类似语法树，可能更方便的对应起来。
举个例子：在bison语法文件里，这条规则WHILE expr LOOP expr POOL { $$ = t_while($2, $4); }，t_while代码：
Expression* t_while(Expression* con, Expression* e)
{
return new Expr_while(con, e);
}
注：此处new之后并没有释放，所以这是一个内存泄露版本。可以在表达式执行后进行释放。
t_while函数创建并返回一个while表达式类，接受两个参数，一个是条件表达式，一个是循环体表达式。我们来看下这个类：
class Expr_while : public Expression
{
public:
Expr_while(Expression* con, Expression* e)
{
m_con = con;
m_e = e;
}
virtual double execute()
{
if (!m_con || !m_e)
return 0;
double ace = m_con->execute();
while (!float_eq(ace, 0))
{
m_e->execute();
ace = m_con->execute();
}
return 0;
}
protected:
Expression* m_con;
Expression* m_e;
};
在函数execute里，首先要判断是否指针是有效的，因为如果某一步语法错误的话，这个指针就被赋值为空（NULL）。然后先执行条件表达式，如果非0，那么就执行循环体，然后再执行条件表达式，如此往复。这和c语言的循环方式一样。
我们再来看看加法的表达式类：
class Expr_plus : public Expression
{
public:
Expr_plus(Expression* e1, Expression* e2)
{
m_e1 = e1;
m_e2 = e2;
}
virtual double execute()
{
if (!m_e1 || !m_e2)
return 0;
double num1 = m_e1->execute();
double num2 = m_e2->execute();
return num1 + num2;
}
protected:
Expression* m_e1;
Expression* m_e2;
};
加法execute函数里面，大意就是分别执行两个加数的表达式，把两个返回结果数值加起来返回。
最后看一下赋值表达式代码：
class Expr_assign : public Expression
{
public:
Expr_assign(char* name, Expression* e)
{
m_name[0]=0;
if (name)
strcpy(m_name, name);
m_e = e;
}
virtual double execute()
{
if (m_name[0]==0 || !m_e)
return 0;
double ace = m_e->execute();
SetValue(m_name, ace);
return ace;
}
protected:
char m_name[32];
Expression* m_e;
};
在execute函数里，先计算表达式的值，然后把这个值保存在全局符号表里。
剩下的表达式类和以上例子差不多，大家可以自己去github上看看。
最终全部编译和运行：
因为有很多文件组织一起，所以就写了一个Makefile，现在编译只要输入make clean命令，清除生成文件，然后再输入make进行编译。关键的编译命令如下：
flex cal.flex
bison calculation3.0.y
$(CC) -c $(CCARG) symtab.c
$(CC) -c $(CCARG) exprtree.cpp
$(CC) -c $(CCARG) lex.yy.c
$(CC) -c $(CCARG) calculation3.0.tab.c
$(CC) -o cal $(CCARG) $(OBJ)
$(CC)代表g++，$(CCARG)代表-g，包含调试信息。最后把所有.o目标文件链接成可执行程序cal。运行：
输入：./cal
基本运算测试：
输入：a <- 2*(5+2)-17/3;
输出：8.33
条件语句测试：
输入：if a < 10 then b <- 1 else b <- 2 fi;
输出：0.00
条件语句的执行结果并不需要返回什么有意义的值，所以为0。
输入：b;
输出：1.00
循环语句测试：
输入：a <- 10;
输入：b <- 1;
输入：while 0 < a loop { b <- b * a; a <- a – 1; } pool;
输入：b;
输出：3628800.00
测试结束。
5，一些bison的要点
5.1 不是所有规则都必须要有动作
如果某个规则没有动作，那么默认动作为$$=$1;
exp: NUM /*{ $$=$1;}*/
5.2 使用左递归
任何一种推导序列可以用左递归或右递归，但是应该用左递归。因为左递归可以保证有限的堆栈空间，而右递归会根据元素个数成比例的占用bison栈空间。因为在规则在应用前，所有元素必须先移动到栈上。
5.3 bison位置信息
出现语法错误的时候，bison需要给用户返回错误信息和错误发生的行列数。这个错误的位置是有yylex来提供。本文没有讲到，具体可以参阅官方文档ltcalc例子。
6，课程作业简介
做过第一次大作业，就很方便上手这次也就是第二个大作业。关于这次作业的说明和难点、调试等，将在下一篇介绍。
支付宝扫一扫
微信扫一扫
最新评论