3. bison程序的常见形式是怎样的？
词法分析器的功能是将输入流分割成一个个的记号（token），而语法分析器的功能则是找到各记号之间的关系。记号之间的关系常见的表示形式就是语法分析树。
以算术表达式1 * 2 + 3 * 4 + 5为例，其词法分析的结果可能是如下的记号序列（空格会被忽略）。
NUMBER TIMES NUMBER PLUS NUMBER TIMES PLUS NUMBER
而其语法分析的结果则表征了上述表达式的优先级顺序，如下图所示。语法分析的结果表示该表达式应该先计算1 * 2和3 * 4的值，然后将这两个结果相加，最后再将相加后的结果再加上5，最终的运算结果才是该表达式的值。
在bison中，使用BNF范式来表示一系列的语法分析规则。BNF范式是书写上下文无关文法（CFG）的标准形式。而我们常见的编程语言均是用上下文无关文法来描述的。关于BNF范式和上下文无关文法等内容请参考编译原理相关资料，这里不赘述。
在给出第一个bison程序之前，先给出一个稍微复杂点的flex程序，然后再在此基础上加入bison的内容。一个稍微复杂的flex程序如下所示。
/* flex3.l */
%{
enum yytokentype {
NUMBER = 258,
ADD,
SUB,
MUL,
DIV,
ABS,
EOL,
};
int yylval;
%}
%%
"+" { return ADD; }
"-" { return SUB; }
"*" { return MUL; }
"/" { return DIV; }
"|" { return ABS; }
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
\n { return EOL; }
[ \t] { /* 忽略空白字符 */ }
. { printf("Mystery Character %s\n", yytext); }
%%
int main(int argc, char **argv)
{
int tok;
while (tok = yylex()) {
printf("%d", tok);
if (tok == NUMBER) {
printf(" = %d\n", yylval);
} else {
printf("\n");
}
}
return 0;
}
上述程序中，我们先是定义了所有的记号类型yytokentype和一个yylval变量用于存储转换后的整数值；随后定义了模式，对于+ - * / |这五种运算符，直接返回其记号类型、对于数字[0-9]+，则是将其转换成整数值保存在yylval中并返回其记号类型等等；最后是在mian函数中循环调用yylex()，如果返回的记号类型是NUMBER，则打印其值。注意yylex()在所有记号生成完毕后，会返回值为0的EOF，使得循环结束。
为了让flex和bison协同工作，首先需要对flex3.l做一定的修改，将修改后内容保存为flex4.l，如下所示。
/
%{
#include "flex4.tab.h"
%}
%%
"+" { return ADD; }
"-" { return SUB; }
"*" { return MUL; }
"/" { return DIV; }
"|" { return ABS; }
"(" { return OP; }
")" { return CP; }
"//".* { }
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
\n { return EOL; }
[ \t] { /* 忽略空白字符 */ }
. { printf("Mystery Character %s\n", yytext); }
%%
具体改动有两点：（1）删除token类型定义，使用#include "flex4.tab.h"的方式。即token类型的定义放在bison中去做，只要将bison生成的token类型定义头文件flex4.tab.h包含进来即可；（2）删除原先的mian函数，main函数同样放在bison中完成。
综合来看，flex4.l中只包含了词法分析的内容，即模式的正则表达式和对应的动作。token类型的定义放在了bison中去完成，在flex中只引用token类型定义所在的头文件。
随后需要编写bison文件，命名为flex4.y，内容如下所示。
%{
#include
%}
/* declare tokens */
%token NUMBER
%token OP CP
%token ADD SUB MUL DIV ABS
%token EOL
%%
calclist: /* 空规则 */
| calclist exp EOL { printf("= %d\n", $2); }
;
exp: factor { $$ = $1; }
| exp ADD factor { $$ = $1 + $3; }
| exp SUB factor { $$ = $1 - $3; }
;
factor: term { $$ = $1; }
| factor MUL term { $$ = $1 * $3; }
| factor DIV term { $$ = $1 / $3; }
;
term: NUMBER { $$ = $1; }
| ABS term { $$ = $2 >= 0 ? $2 : - $2; }
| OP exp CP { $$ = $2; }
;
%%
void yyerror(char *s)
{
fprintf(stderr, "error : %s\n", s);
}
int main(int argc, char **argv)
{
yyparse();
return 0;
}
对于上述首次出现的bison程序，做如下解释说明。
（1）与flex程序类似，bison程序也类似的几个部分，分别是：
包含在%{和%}之间的声明，其功能与上述flex中的描述一致
使用%token定义的token类型，注意bison中定义的token类型的枚举值从258开始，目的是为了避免和文字字符记号产生冲突
包含在%%和%%之间的一些列BNF范式，BNF范式描述了语法规则。bison根据给定的BNF范式自动生成其对应语法规则的语法分析器
C源码部分，比如上述代码中包含了main函数，main函数中调用了语法分析的入口函数yyparse()
（2）上述代码中给定的BNF范式描述了一个简单计算器的语法规则。BNF范式具体含义以及如何编写BNF范式需要查阅编译原理相关资料，这里不赘述。