flex/bison系列2：实现一个简单的计算器

引言

这是一个系列文章，旨在了解如何使用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;}
;

orczhou.com