引言
这是一个系列文章，旨在了解如何使用Flex/Lex和Yacc/Bison进行词法和语法解析。在前面，已经完成了使用Lex/flex做基础的词法解析。接着，开始这个系列的第二部分，使用flex和bison完成一个简单的计算器。
为了简化实现，将注意力放在简单flex和bison使用上，这里对计算器做了几个简化：
- 只支持加、减、乘计算，暂时不支持除法，除法可能涉及到浮点类型，故暂时忽略
- 不考虑整数溢出的问题，这里使用int类型（那么他存储与计算范围是有限的）
也就是该程序可以计算加法、减法、乘法，以及他们的任意组合，如： 3+4、 3+4*2、 3+4*2-3、 3+4*2-3*2
后续，还将考虑增加更急复杂的计算器，包括：
- 实现，带有变量的计算器程序
- 实现带来循环、带有条件判断的程序
这里先从简单的开始。
初次手写一个cal.l和cal.y
这是在vim中写出的第一遍代码，包含了词法文件cal.l和语法文件cal.y，详细如下。这其中当然是有很多错误的，之所以，依旧写出来，是为了和正确代码对比，以此看看对哪些概念理解有偏差。如果你是找一个正确例子的话，可以跳过这一段。
%{
#inlcude <stdlib.h>
%}
/* 十进制整数 */
%token INTEGER
%union {
int a;
}
/* 操作符 + - * / */
%token OPERATOR
%%
program:
program expression \n { printf("%d",$2); } // 这里就是以回车结尾，也可以考虑使用 = 结尾
|
expression:
INTEGER
| expression '+' expression {$$ = $1 + $2}
| expression '-' expression {$$ = $1 - $2}
| expression '*' expression {$$ = $1 * $2}
dec_integer:
INTEGER
{
$$ = $1.a;
}这里也有几个已知的问题，例如：运算符的优先级没有定义，也就说4+3*2可能会算成14。没错，如果眼尖的话，还发现有一些拼写错误。
接着是cal.l文件：
#inlcude <stdlib.h>
#include "y.tab.h"
%}
[:digit:]+ {
yylval.a = atoi(yytext)
RETURN INTEGER;
}当然，这里面有很多的错误。一会儿来看后面正确的内容。
修改cal.l和cal.y
- 首先，是去解决已知的问题：运算符优先级如何去解决？关于什么是优先级、什么是结合律这里不做详述，这里有一篇文章讲得比较细致，几幅图也非常直观：Precedence and Associativity of Operators in Python。虽然是不同的语言，但意思是一样的。理解这个点还是比较重要的，例如在关系型数据库中，之前有遇到过这样的案例，可以思考一下如下的表达式
t.col < 2 or t.col < 11 and t.col > 4是什么意思：
-- 猜测一下，如下的 SELECT 查询是否能够返回记录：
CREATE TABLE t(col INT);
INSERT INTO t values (1);
WHERE t.col < 2 or t.col < 11 and t.col > 4扯远了，再回到cal.y文件，优先级和结合律需要进行如下修改，以定义”*”优先级高于”+”、”-“：
%left '+' '-'
%left '*'这里的代码先后，就定义了优先级；优先级越高，定义在越在后面；left表示，左结合。
- 除了优先级，在cal.y语法规则中的定义部分，如果有字符，并没有使用引号。例如上面的cal.y的第17行的\n，是需要加上引号的，即
'\n'。
- 对于cal.y的中定义的语法规则，并没有定义返回值存储在联合体（YYSTYPE，也就是如下这里cal.y定义的唯一的那个联合体）哪个类型中。例如，没有定义”expression”这个语法规则，返回值是使用哪个值，虽然这里的联合体只定义了一个类型（即int a）。具体的，添加了如下代码：
%token <a> INTEGER
%type <a> expression完成这样的定义后，在lex的文件cal.l中，就可以对yylval进行赋值，如：yylval.a = atoi(yytext); 这时，对于yacc文件中cal.y，如果引用这个TOKEN，就可以使用$1（或者是$2、$3）来引用lex解析后的返回值，如：expression: INTEGER { $$ = $1;}。
- 于是，重新使用了独立的Token重新定义了运算符，并定义了优先级，如下：
cat cal.y
...
%token O_ADD O_MINUS O_MULTIPLY O_EQ
%left O_ADD O_MINUS
%left O_MULTIPLY
%token <a> INTEGER
%type <a> expression
...
cat cal.l
...
"=" { return O_EQ;};
"+" { return O_ADD;};
"-" { return O_MINUS;};
"*" { return O_MULTIPLY;};
...- 没有定义 yyerror 函数，程序也会编译不过去，会报如下错误：
cal.tab.c:(.text+0x53b): undefined reference to `yyerror'按照文档，可以定义一个最简单的yerror函数（参考：The Error Reporting Function yyerror），如下：
void
yyerror (char const *s)
{
fprintf (stderr, "something error: %s\n over", s);
}- 删除了无效的dec_integer规则，如果有无效的规则，也会失败
- 将[:digit:]修改为[0-9]+。至于为什么[:digit:]不生效，后面做了一些搜索。为了避免歧义，需要额外再加一层中括号，写法也就是[[:digit:]]。详细参考：Patterns@Lexical Analysis With Flex
完整的计算器程序文件cal.l cal.y
补充一个main入口函数，修改cal.l、cal.y即可。
修正后的cal.l
%{
#include "cal.tab.h"
#include <stdio.h>
%}
%option noyywrap
%%
[0-9]+ {
yylval.a = atoi(yytext);
return INTEGER;
}
"=" { return O_EQ;};
"+" { return O_ADD;};
"-" { return O_MINUS;};
"*" { return O_MULTIPLY;};
%%修正后的cal.y
%{
#include <stdlib.h>
#include <stdio.h>
int main(){
yyparse();
}
void
yyerror (char const *s)
{
fprintf (stderr, "something error: %s\n over", s);
}
%}
%union {
int a;
}
%token O_ADD O_MINUS O_MULTIPLY O_EQ
%token <a> INTEGER
%left O_ADD O_MINUS
%left O_MULTIPLY
%type <a> expression
%%
program:
|
program expression O_EQ { printf("result is : %d",$2); }
;
expression:
INTEGER { $$ = $1;}
| expression O_ADD expression {$$ = $1 + $3; }
| expression O_MINUS expression {$$ = $1 - $3; }
| expression O_MULTIPLY expression {$$ = $1 * $3;}
;编译与执行
然后，就可以生成c文件并编译可执行文件了：
lex cal.l
bison -d cal.y
gcc cal.tab.c lex.yy.c -o a.out
./a.out
4+3*2=
也可以像这样：
lex cal.l && bison -d cal.y && gcc cal.tab.c lex.yy.c -o a.out && ./a.out附带注释说明的cal.y文件
%{ // %{ ... %} 包含了完整的C语言代码
#include <stdlib.h> // 这里包含需要的头文件、入口函数main
#include <stdio.h> // 以及一个简答的yyerror函数
int main(){
yyparse();
}
void
yyerror (char const *s)
{
fprintf (stderr, "something error: %s\n over", s);
}
%}
%union { // 这是一个非常重要的联合体，用于定义
int a; // 各种不同类型的Token所返回的数据
} // 广泛的被yylex使用，并用于与.yy文件共享数据
// 也就是 YYSTYPE
%token O_ADD O_MINUS O_MULTIPLY O_EQ
%token <a> INTEGER // 这里表示INTEGER(这是一个被lex识别的token）
// INTEGER（被lex识别的token返回值为YYSTYPE.a
%left O_ADD O_MINUS // 这里定义 + -为左结合律
%left O_MULTIPLY // 这里定义 * 为左结合律，并且优先级高于 + -
%type <a> expression // 这里定义语法规则(grammer rule)expression
// 的返回值为 YYSTYPE.a
%%
program: // 这是start symbol，所有的program都需要符合该定义
|
program expression O_EQ { printf("result is : %d",$2); }
;
expression:
INTEGER { $$ = $1;}
| expression O_ADD expression {$$ = $1 + $3; }
| expression O_MINUS expression {$$ = $1 - $3; }
| expression O_MULTIPLY expression {$$ = $1 * $3;}
;
