BNF
巴科斯范式(BNF: Backus-Naur Form 的缩写)是由 John Backus 和 Peter Naur 首先引入的用来描述计算机语言语法的符号集。
在BNF中，双引号中的字("word")代表着这些字符本身。而double_quote用来代表双引号。
在双引号外的字（有可能有下划线）代表着语法部分。
< > : 内包含的为必选项。
[ ] : 内包含的为可选项。
{ } : 内包含的为可重复0至无数次的项。
| : 表示在其左右两边任选一项，相当于"OR"的意思。
::= : 是“被定义为”的意思 或者单一的冒号
"..." : 术语符号
[...] : 选项，最多出现一次
{...} : 重复项，任意次数，包括 0 次
(...) : 分组
| : 并列选项，只能选一个
下面是是用BNF来定义的Java语言中的For语句的实例：
for (initialization; termination;
increment) {
statement(s)
}
BNF定义如下：
FOR_STATEMENT ::=
"for" "(" ( variable_declaration |
( expression ";" ) | ";" )
[ expression ] ";"
[ expression ] ";"
")" ( statement | "{" statement "}" )
BNF处理1*2 + 3*4 +5简单的算术表达式：
<exp> ::= <factor>
| <exp> + <factor>
<factor> ::= NUMBER
| <factor> * NUMBER
exp被定义为是一个factor或者factor+exp
factor被定义是NUMBER或者factor*NUMBER
例子1：
%{
#include <stdio.h>
%}
/*声明token*/
%token NUMBER
%token ADD SUB DIV MUL ABS
%token EOL
%%
calclist: /*空规则*/
| calclist exp EOL { printf("= %d
",$2); }
;
exp: factor
| exp ADD factor { $$ = $1 + $3; }
| exp SUB factor { $$ = $1 - $3; }
;
factor: term
| factor MUL term { $$ = $1 * $3; }
| factor DIV term { $$ = $1 / $3; }
;
term:NUMBER
| ABS term { $$ = $2>0 ? $2 : -$2; }
| "+" term { $$ = $2; }
;
%%
int main(int argc, char ** argv)
{
printf(">");
yyparse();
return 0;
}
yyerror(char *s)
{
fprintf(stderr,"error:%s
",s);
}
bison程序包括与flex程序相同的三个部分结构：声明部分、规则部分、C代码部分。
1、声明部分：
声明部分包含了会被原样拷贝到目标分析程序开头的C代码，同样也通过%{和%}来声明。
%token记号声明，以便于告诉bison在语法分析程序中的记号的名称。通常，记号总是使用大写。
任何没有声明为记号的语法符号必须出现在至少一条规则的左边（左边表示规则的定义）
2、规则部分：
简单的BNF定义的规则。bison使用单一的冒号而不是::=，分号被用来表示规则的结束。
在flex中每个规则之后，使用花括号括起。
bison会自动分析语法，记住每条被匹配的规则，所以动作代码只需要维护每个语法符号关联的语义值。
bison语法分析器也执行一些额外的动作，例如创建数据结构以便后续使用。
第一条规则左边的语法符号是语法起始符号(start symbol)，整个输入必须被它匹配。
每个bison规则中的语法符号都有一个语义值，目标符号（冒号左边的语法符号）的值在动作中代码用$$代替，
右边语法符号的语义值依次为$1,$2，直到这条规则的结束。当词法分析器返回记号时，记号值总是存储在yyval里，
其他语法符号的语义规则在语法分析器的规则里进行设置，例如本例子的 factor、term和exp符号的语义值就是它们所
描述的表达式值。
例子中，头两条规则定义了calclist语法符号，通过循环来读入用换行符结束的表达式并且打印结果。
calclist: /*空规则*/
| calclist exp EOL { printf("= %d
",$2); }
| calclist EOL { printf("> "); } /* blank line or a comment */
;
calclist的定义使用一种常见的双规则递归定义来实现一个序列或者列表：
第一个规则为空，不进行任何匹配
第二个规则添加一个项目到列表中，对应的动作是通过$2打印出exp的值
第三个规则实现输入空行
其余的规则实现计算器，带有操作符的规则（exp ADD factor 和ABS term）在语义值上进行相应的算术操作。
右边仅有一个语法符号的规则是组合文法，例如exp：factor，一种表达式exp就是一个因子factor。
如果一个规则缺少现实的动作，语法分析器将把$1赋予$$，这是i一个内部设定。
词法分析器程序
%option noyywrap
%{
#include "fb1-5.tab.h"
%}
%%
"+" { return ADD; }
"-" { return SUB; }
"*" { return MUL; }
"/" { return DIV; }
"|" {return ABS; }
^[-+][0-9]+ { yylval = atoi(yytext); return NUMBER;}
[0-9]+ { yylval = atoi(yytext); return NUMBER;}
{return EOL; }
[ ] {}
. { yyerror("Mystery character=%c!",*yytext);}
%%
1、由于在语法分析中声明了token，故这里使用的话，需要进行引用，在声明部分添加include文件
2、返回记号的时候，记号对应的值是存储在yylval变量中
联合编译flex和bison程序
对应的makefile文件内容为：
fb1-5: fb1-5.l fb1-5.y
bison -d fb1-5.y
flex fb1-5.l
gcc -o $@ fb1-5.tab.c lex.yy.c -lfl
bison 使用-d选项（用于定义文件）运行，创建fb1-5.tab.c和fb1-5.tab.h文件
flex创建lex.yy.c，然后将两者和flex的库文件编译在一起
测试结果
[root@typhoeus79 bison]# ./fb1-5 > > -5+10 = 5 -5*4+20 = 0
二义性文法：并不多见
语法分析为什么不写成这样？
exp:exp ADD exp
| exp SUB exp
| exp MUL exp
| exp DIV exp
| ABS exp
| NUMBER
;
原因在于优先级和二义性。
分开的term、factor和exp的语法符号可以让bison首先处理ABS，接着是MUL和DIV，然后是ADD和SUB。
通常来说，一旦一种文法有不同的优先级，语法分析器就需要为每种优先级制定一条规则。
下面的文法如何？
exp： exp ADD exp
| exp SUB exp
| factor;
factor和term部分相似
存在二义性。例如1-2+3的输入可能被分析为(1-2)+3，也可能被分析为1-(2+3)
如果一种文法是有歧义的，bison会报告冲突(conflicts)，并且标出针对给定输入哪儿会有两种不同的分析。
增加其他规则
支持小括号
词法解析中添加如下：
"(" { return OP; }
")" { return CP; }
语法解析中添加：
term:NUMBER
| ABS term { $$ = $2>0 ? $2 : -$2; }
| "+" term { $$ = $2; }
| "-" term { $$ = -$2; }
| OP exp CP { $$ = $2;}
如果想支持如下计算，应该怎么搞呢？
>(10-2)+(-10+2) = 0 >(100-2)*2 = 196 >(+10-2) = 8 >10-(-10+10) = 10
需要词法分析，重点需要区分正常的加减号以及前缀加减号
%option noyywrap
%{
#include "fb1-5.tab.h"
int flag=1;
int flag2 = 1;
%}
%%
"+" {
if(flag){
flag = 1;
//printf("ADD
");
return ADD;
}else
{
flag2 = 1;
}
}
"-" {
if(flag){
//printf("SUB
");
flag = 1;
return SUB;
}else
{
//printf("Flag=%d,Here
",flag);
flag2 = -1;
}
}
"*" { return MUL; }
"/" { return DIV; }
"(" { flag = 0;
//printf("OP
");
return OP; }
")" {
flag =1;
flag2 = 1;
//printf("CP
");
return CP; }
"|" {return ABS; }
^[-+][0-9]+ { yylval = atoi(yytext); return NUMBER;}
[0-9]+ {
if(flag)
yylval = atoi(yytext);
else{
yylval = flag2*atoi(yytext);
flag = 1;
}
//printf("NUMBER2=%d
",yylval);
return NUMBER;}
{return EOL; }
[ ] {}
. { yyerror("Mystery character=%c!",*yytext);}
%%
【参考链接】