flex and bison ：做个计算器

       最近看PostgreSQL源码，看到了flex。我预计后面解析sql的时候，这两个兄弟还会出来相见，所以这两天看了flex and bison的资料。
   科班出身学过编译原理的人对flex 和bison这两个兄弟一定不会陌生，对于flex 和bison兄弟俩，天生就是和编译器打交道的。   

   flex的前身是lex，lex是1975年由Mike Lesk和当时尚在AT&T实习的Eric Schmidt共同完成的基于UNIX环境的词法分析器的生成工具。这个lex很有名气，但是无奈效率太低加上有bug，让人用的很不爽。后来伯克利实验室的Vern Paxson用C重新写了lex，并命名为flex（Fast Lexical Analyzer Generator）。Linux下我们用的是这个flex的GNU版本。对于我们Ubuntu来讲安装是一如既往的方便：

1. sudo apt-get install flex

    flex到底是干啥的呢？咱就喜欢大白话，在我看来，flex就是将输入文件按照规则，切分成一段一段的。在白一点，一个文件，就好像黄豆绿豆黑豆混在一起。flex的作用就是定义好那是黄豆，哪是绿豆，黑豆，（就是专业术语中的pattern），将这些一个个摘出来，黄豆就磨豆浆（action），绿豆去做绿豆糕(action)...
   flex 处理分词，将输出切分成一段一段的token，这些tokens可以喂给Bison处理，当然了，我们完全也可以不喂给bison，直接自己处理就得了。最简单的例子就是上篇博文提到了统计字符数，单词数和行数。
   请看下面最简单的分词：

1. /* just like Unix wc */
   
2. %{
   
3.     int chars = 0;
   
4.     int words = 0;
   
5.     int lines = 0;
   
6. %}
   
7. %%
   
8. [a-zA-Z]+ { words++; chars += strlen(yytext); }
   
9. \n { chars++; lines++; }
   
10. . { chars++; }
    
11. %%
    
12. 
    
13. int main(int argc ,char* argv[])
    
14. {
    
15.     yylex();
    
16.     printf("%8d%8d%8d\n", lines, words, chars);
    
17.     return 0;
    
18. }

    上面的内容分成三个部分，第一部分声明，第二部分是规则部分，简单地说就是

1. pattern action

匹配什么模式，匹配到后做什么动作。说到pattern，我仿佛看到正则表达式笑而不语。不过这不是我们这篇文章的主题。
   第三部分是用户自定义部分，这部分代码会原封不动地拷贝到生成的.c文件中去。
   
    我们用flex处理下这个wc.l文件，可以看到生成了lex.yy.c文件。

1. root@manu:~/code/flex_bison# flex wc.l
   
2. root@manu:~/code/flex_bison# ll
   
3. ...
   
4. -rw-r--r-- 1 root root 44407 4月 6 11:38 lex.yy.c
   
5. -rw-r--r-- 1 root root   313 4月 5 13:21 wc.l

    当然了我们可以制定输出C文件的名字，使用-o选项。Whatever，我们有了C文件，用gcc及可以编译出可执行文件了，记住加上-lfl选项。

1. root@manu:~/code/flex_bison# gcc -o wc lex.yy.c -lfl
   
2. root@manu:~/code/flex_bison# ll
   
3. ...
   
4. -rw-r--r-- 1 root root 44407 4月 6 11:38 lex.yy.c
   
5. -rwxr-xr-x 1 root root 18482 4月 6 11:42 wc*
   
6. -rw-r--r-- 1 root root 313 4月 5 13:21 wc.l
   
7. root@manu:~/code/flex_bison#

    使用下我们的wc程序：

1. root@manu:~/code/flex_bison# cat /var/log/kern.log|./wc
   
2.    13731 136454 1322344
   
3. root@manu:~/code/flex_bison# cat /var/log/kern.log|wc
   
4.    13731 189620 1322344

可以看出我们的程序行数和字符数都是对的，但是单词数和标准的wc程序不同，这是因为我们对word的定义和标准的wc不同。
我们将第二部分添上：

1. [^ \t\n\r\f\v]+     { words++; chars += strlen(yytext); }

结果就和标准的wc一样了。

1. root@manu:~/code/flex_bison# cat /var/log/kern.log|/usr/bin/wc
   
2.   13731 189620 1322344
   
3. root@manu:~/code/flex_bison# cat /var/log/kern.log|./wc
   
4.   13731 189620 1322344

   不知道大家有没有激动，反正我是很激动，统计单词个数，这个函数看起来很复杂的函数，短短几行代码就搞定了。另外，不知道为什么，这个流程总让我想起Lisp的mapcar。
   我毕业那年，参加了公司的TDD的培训，培训的思想是测试驱动开发（TDD）。其中第一道题目就是编写一个基本的四则运算的计算器，输入字符串，如

1. （1+2×4/6）+3/4+|2-4|

正确的返回结果。当时我们的scope比较小，基本是10以内个位数的加减乘除，带括号，带不带绝对值我都记不的了。当时写了一个近400行的C代码，当时很有成就感。我记得波哥对我微微一笑给我说了两个词 yacc lex。当时波哥给我写bison的资料，我当时不会的东西太多，没有顾上深入的学习flex 和 bison。昨天我就想起了这个事情，一边学习flex and bison这本书，一边照着课本写了一个计算器。
    先介绍下Bison，bison的前身是传说中的yacc，yacc是由贝尔实验室的S.C.Johnson基于Knuth大神的LR分析技术，于1975～1978年写成。1987年 UC Berkeley 的Bob Corbett在BSD下重写了yacc。在后来GNU project接管了项目，添加了很多特性，形成了今天的GNU Bison。在Ubuntu下安装：

1. sudo apt-get install bison

    Bison的.y文件也是分成三个部分：三个部分也是用%%隔开
1 声明部分：所有词法单元的定义可以放在此处
2 规则部分：具体的语法和相应的动作。
3 用户自定义部分。第三部分会被bison原封不动的拷贝进生成的.C文件。
下面看下计算器的.y文件：

1. root@manu:~/code/flex_bison/calc# cat calc.y
   
2. /* simplest version of calculator */
   
3. %{
   
4. #include <stdio.h>
   
5. #define YYSTYPE double
   
6. %}
   
7.  /* declare tokens */
   
8. %token NUMBER
   
9. %token ADD SUB MUL DIV ABS OP CP
   
10. %token EOL
    
11. %%
    
12. calclist: /* nothing */
    
13.  | calclist exp EOL { printf("= %f\n", $2); }
    
14.  ;
    
15. exp: factor
    
16.  | exp ADD factor { $$ = $1 + $3; }
    
17.  | exp SUB factor { $$ = $1 - $3; }
    
18. ;
    
19. factor: term
    
20.  | factor MUL term { $$ = $1 * $3; }
    
21.  | factor DIV term { $$ = $1 / $3; }
    
22. ;
    
23. term: NUMBER
    
24.  | ABS exp ABS { $$ = $2 >= 0? $2 : - $2; }
    
25.  | OP exp CP   { $$ = $2; }
    
26. ;
    
27. %%
    
28. main(int argc, char **argv)
    
29. {
    
30.     yyparse();
    
31. }
    
32. yyerror(char *s)
    
33. {
    
34.     fprintf(stderr, "error: %s\n", s);
    
35. }

bison和flex如果协同工作，应然怎么办呢：

首先bison -d选项，将calc.y文件处理生成两个文件calc.tab.c和calc.tab.h。其中H文件包含所有词法单元的定义：

1. root@manu:~/code/flex_bison/calc# cat calc.tab.h
   
2. ....
   
3.  enum yytokentype {
   
4.      NUMBER = 258,
   
5.      ADD = 259,
   
6.      SUB = 260,
   
7.      MUL = 261,
   
8.      DIV = 262,
   
9.      ABS = 263,
   
10.      OP = 264,
    
11.      CP = 265,
    
12.      EOL = 266
    
13.    };
    
14. 
    
15. ......

我们需要在flex的l文件中添加bison生成的.h文件。我们直接看下calc.l文件

1. root@manu:~/code/flex_bison/calc# cat calc.l
   
2. %{
   #define YYSTYPE double
   #include "calc.tab.h"
   #ifdef CALC_LEX
       YYSTYPE yylval;
   #endif
   %}
   
   %%
   "+"                                  { return ADD;    } 
   "-"                                  { return SUB;    } 
   "*"                                  { return MUL;    } 
   "/"                                  { return DIV;    } 
   "("                                  { return OP;     }
   ")"                                  { return CP;     }
   "|"                                  { return ABS;    } 
   \n                                   { return EOL;    } 
   [ t]                                 { /* ignore */   } 
   ([0-9]*\.?[0-9]+|[0-9]+\.[0-9]*)     { yylval = atof(yytext); return NUMBER; } 
   
   
   %%
   
   
   #ifdef CALC_LEX  
   int main (int argc, char** argv) {
       int token;
   
   
       while (token = yylex()) {
           printf("%d", token);
   
   
           if (token == NUMBER) {
               printf(" = %f\n", yylval);
           } else {
               printf("\n");
           }
       }
   
   
       return 0;
   }
   #endif 
   

   其中ifdef CALC_LEX部分属于单元测试部分代码，熟悉python的筒子，应该不陌生。OK，我们可以看下makefile看下如何使用flex和bison合作，生成一个计算器calc：

1. root@manu:~/code/flex_bison/calc# cat Makefile
   
2. cc=gcc
   
3. calc:calc.y calc.l
   
4.     bison -d calc.y
   
5.     flex -o calc.lex.c calc.l
   
6.     cc -o $@ calc.tab.c calc.lex.c -lfl
   
7. 
   
8. calc.lex: calc.y calc.l
   
9.     bison -d calc.y
   
10.     flex -o calc.lex.c calc.l
    
11.     cc -D CALC_LEX -o $@ calc.lex.c -lfl
    
12. clean:
    
13.     rm calc.lex.c
    
14.     rm calc.tab.h
    
15.     rm calc.tab.c
    
16.     rm calc

     执行一下make，可以看到生成了calc可执行程序。我们验证calc好不好用：

1. root@manu:~/code/flex_bison/calc# ll
   
2. 总用量 156
   
3. drwxr-xr-x 2 root root  4096 4月 6 13:46 ./
   
4. drwxr-xr-x 3 root root  4096 4月 6 11:51 ../
   
5. -rwxr-xr-x 1 root root 36459 4月 6 12:38 calc*
   
6. -rw-r--r-- 1 root root   979 4月 6 12:19 calc.l
   
7. -rw-r--r-- 1 root root 45726 4月 6 12:38 calc.lex.c
   
8. -rw-r--r-- 1 root root 45991 4月 6 12:38 calc.tab.c
   
9. -rw-r--r-- 1 root root  2104 4月 6 12:38 calc.tab.h
   
10. -rw-r--r-- 1 root root   690 4月 6 12:37 calc.y
    
11. -rw-r--r-- 1 root root   282 4月 6 12:38 Makefile
    
12. root@manu:~/code/flex_bison/calc# ./calc
    
13. 1+2
    
14. = 3.000000
    
15. 3/4+2
    
16. = 2.750000
    
17. |2-4|*3-2/(1+3)
    
18. = 5.500000
19. 2.4*5/48
    = 0.250000
    
    
    
    
    

   加上makefile，一共有91行代码。 这个例子本身没有什么什么，而且计算器本身还不完善。但是这个例子给我自己的启示是，计算机发展到现在，我们的前辈创造出了大量的有价值的东西，比如这个flex 和bison，如果我们不利用，我们自己去写一个四则运算的计算器，感兴趣的筒子可以实验下，考虑括号，考虑绝对值，考虑算法优先级，代码写的会特别的蛋疼，而且扩展性不好。我们伟大的前辈帮我们抽象这个事情，很多类似的工作就变的非常的easy。我们应该站在前辈的肩上去解决问题，而不应该人人都从0开始，这样浪费了太多的时间。对于某些领域，我们需要利用前人的成果，我们首先要通过大量的学习，至少了解前人的成果。

   光荣属于前辈，光荣属于那些无数有分享精神 探索精神的前辈。

参考文献：
1 flex and bison
2 Flex/Bison Tutorial， by Aaron Myles Landwehr
3 用flex和bison做一个命令行计算器－第一次尝试
4 词法分析&语法分析  实习指导 原著:陈嘉 许畅 改编:朱晓瑞 许畅