所有的context-free language都可以用BNF表达,所有用BNF表达的语言都可以有bison解析。
nonterminal symbol,在bison中是一个identifier,用小写表示。
terminal symbol,也被叫做token type,通常用大写。
例子
stmt: RETURN expr ’;’ ;
如果一个rule提到了叫interger const的terminal symbol,那么意味着任何整数常量都是语法上合法的。x+4和x+1在语法上是等价的。
但是精确的值有是非常重要的。因此,bison中的每个token都有token type和semantic value。
token type是grammar中定义的terminal symbol,例如INTEGER,IDENTIFIER,或者','。token type决定了所有的东西:它可以出现在哪里,它和其它token如何组合。grammar rule只知道token的类型,不知道token的其它任何东西。
semantic value包含一个token除了type之外的所有信息,如一个整数的值,一个标识符的名字。
每个grouping也可以有semantic value,比如表达式有一个值。
一个grammar rule可以有一个action,由c语句组成。每次parser识别一个rule,action都被执行。
大多数时间,action的目的是计算整个结构的semantic value。
例如:
expr: expr ’+’ expr { $$ = $1 + $3; } ;
有时需要提前读取下一个token,才能确定rule的匹配。
如果你在bison declarations包含 %glr-parser,结果是一个Generalized LR (GLR) parser。
每个token有关联的位置。用@$,@1等表示。
bison的输出一个是实现parser的C源码文件。这个parser叫做bison parser。源文件叫做bison parser implementation file。
使用bison设计真实的语言的步骤:
1 指定bison认识的语法
2 写一个lexical analyzer来处理输入,并产生tokens
3 写一个控制函数来调用bison产生的parser。
4 写一个error-reporting routines
最终编译的过程:
5 执行bison来产生parser。
6 编译bison的输出,已经其它源码文件
7 链接目标文件成一个最终的输出。
bison语法文件的通用格式如下:
1 2 3 4 5 6 7 8 9 10 | %{ Prologue %} Bison declarations %% Grammar rules %% Epilogue |
%% %{ %}用来分开sections。
prologue是c语言代码,用来定义action用到类型,定义变量。可以使用预处理,可以使用#include。声明lexical analyzer的接口yylex,以及error printer接口yyerror等。
bison declarations用来声明terminal和nonterminal symbol的名字。描述运算符的优先级,各种符号的semantic values的数据类型。
grammar rules定义了如何构造nonterminal symbol,
epilogue用来包含你想要的任何代码。