陈颂光
全栈工程师,能够独立开发从解释器到网站和桌面/移动端应用的各类软件。
关注我的 GitHub

Bison解析器生成器概览

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

语法

语法文件形如:

%{
导言
%}
声明
%%
规则
%%
用户代码

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

导言

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

声明

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

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

  • 标识符(通常大写),须用%token声明
  • 用单引号包围的一个字符,通常用于表示字面上的该字符
  • 用双引号包围的一个字符序列,除不支持三字符转义外与C语言含义同,通常用于表示字面上的该字符串
声明 用途
%define api.value.type {类型} 指定所有符号的语义值类型
%define api.pure full 生成可重入的解析器
%union 名字 {成员声明} 声明一个联合类型,不指定名字则YYSTYPE
%require "版本" 若bison版本低于指定版本则报错退出
%token 符号 声明一个终结符,可后接有双引号形式的字面标记
%token <类型> 符号 在栈类型为联合时,声明一个有给定语义值类型的终结符,可后接有双引号形式的字面标记
%left 符号… 声明一些左结合符号
%left <类型> 符号… 在栈类型为联合时,声明一个有给定语义值类型的左结合符号
%right 符号… 声明一些右结合符号
%right <类型> 符号… 在栈类型为联合时,声明一个有给定语义值类型的右结合符号
%nonassoc 符号… 声明一些不结合符号
%nonassoc <类型> 符号… 在栈类型为联合时,声明一个有给定语义值类型的不结合符号
%precedence 符号… 声明一些有相同优先级的符号,较后的声明对应较高的优先级
%precedence <类型> 符号… 在栈类型为联合时,声明一个有给定语义值类型的有相同优先级的符号,较后的声明对应较高的优先级
%type <类型> 非终结符… 在栈类型为联合时,声明一些有特定语义值类型的非终结符
%initial-action { C代码 } 在开始解析前运行指定的C代码,其中可用$$@$引用向前看符号的初始值和位置。
%destructor { C代码 } 符号… 在不再需要指定符号(或语义值类型)的语义值时运行指定的C代码。其中$$@$分别引用有关语义值和其位置。
%printer { C代码 } 符号… 在调试模式中报告指定符号时运行指定代码,其中yyoutput$$@$分别引用输出流、有关语义值和其位置。
%expect N 预期有N个移入-归约冲突而没有归约-归约冲突,不用警告。
%expect-rr N 预期有N个归约-归约冲突(用GLR解析器),不用警告。
%start 符号 指定开始符号
%code {代码} 把给定代码原样复制到解析器
%code 位置 {代码} 把给定代码原样复制到解析器中指定位置(requires(包含头文件的位置)、provides(头文件中)、top(包含头文件的位置与解析器之间)、imports
%file-prefix "前缀" 指定输出文件名对应输入文件名前缀.y
%output "文件" 指定输出文件
%language "语言" 指定生成解析器的语言(C/C++/Java)
%name-prefix "前缀" 为外部可用名字加给定前缀而非yy
%skeleton "文件" 指定基于的骨架
%verbose 生成更多信息

规则

规则中定义语法的产生式及语义动作。规则形如:

RESULT: COMPONENTS…;

其中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。这个计算器当然功能不强,但读者应该已经知道如何为它加上更多功能。

关键词 unix yacc bison