用flex和bison做一个命令行计算器－第二次尝试

上次大半夜用flex和bison做了个命令行计算器玩，这回我将这个计算器进行了一番改造，使它变成了使用抽象语法树的方式，并且有一个更友好一些的shell。

我的目标是实现一个脚本语言，所以自定义函数是必不可少，如果不把语法解析结果存储起来而是简单的一边解析一边运算，那就没办法实现自定义函数了，所以引入抽象语法树是必须的。

并且使用抽象语法树的好处很多。现实的例子是：我在目前的游戏项目中自定义的通讯协议描述语法在解析时就是先解析成抽象语法树，然后使用这份抽象语法树生成对应的Erlang代码和ActionScript代码，并且在制作协议调试工具的时候还可以抽象语法树来做通信数据的可视化显示。

今天我们可以利用抽象语法树动态执行来做一个解析型语言，明天我们可以把抽象语法树转译成汇编做成一个编译型语言，或者转译成llvm的前端代码快速得到一个现成的jit。想起这些可能性就足以让人激动不已，不过千里之行始于足下，光想不做是没用的，还是实实在在码code吧 :)

下面是文法描述文档（calc.l）:


%{ 
    #include "calc_ast.h";
    #include "calc.tab.h";
 
    #ifdef CALC_LEX 
        YYSTYPE yylval;
        int calc_eof;
    #else 
        extern int calc_eof;
    #endif 
%} 
 
%% 
"+"                         { return ADD;  } 
"-"                         { return SUB;  } 
"*"                         { return MUL;  } 
"/"                         { return DIV;  } 
"%"                         { return MOD;  } 
"|"                         { return ABS;  } 
"("                         { return OP;   } 
")"                         { return CP;   } 
";"                         { return EOS;  } 
n                          { return EOL;  } 
[ rt]                     { /* ignore */ } 
([0-9]+.?[0-9]*|.[0-9]+)  { yylval.d = atof(yytext); return NUM; } 
.                           { return UNKNOW; } 
 
<<EOF>>                     { calc_eof = 1; return 0; } 
%% 
 
#ifdef CALC_LEX 
int main (int argc, char** argv) {
    int token;
 
    while (token = yylex()) {
        switch (token) {
            case ADD:       printf("ADDn");                break;
            case SUB:       printf("SUBn");                break;
            case MUL:       printf("MULn");                break;
            case DIV:       printf("DIVn");                break;
            case MOD:       printf("MODn");                break;
            case ABS:       printf("ABSn");                break;
            case OP:        printf("OPn");                 break;
            case CP:        printf("CPn");                 break;
            case EOS:       printf("EOSn");                break;
            case EOL:       printf("EOLn");                break;
            case NUM:       printf("NUM = %fn", yylval.d); break;
            case UNKNOW:    printf("UNKNOWn");             break;
        }
    }
 
    return 0;
}
#endif

文法描述文档跟上次的比较没太大变化，只是完善了调试用的输出（调试文法解析的时候运行./calc.lex）

下面是解析器的代码（calc.y）：


%{ 
    #include <stdio.h> 
    #include <stdlib.h> 
 
    #include "calc_ast.h" 
 
    calc_ast* calc_result;
    int calc_eof = 0;
%} 
 
%union { 
    calc_ast *a;
    double d;
} 
 
%token <d> NUM
%token ADD SUB MUL DIV MOD ABS OP CP
%token EOS EOL UNKNOW
 
%type <a> exp factor term
 
%% 
seg: 
   | exp EOS        { calc_result = $1; YYACCEPT; } 
   | exp EOL        { calc_result = $1; YYACCEPT; } 
   ; 
 
exp: factor 
   | exp ADD factor { $$ = calc_ast_new_node(AST_ADD, $1, $3); } 
   | exp SUB factor { $$ = calc_ast_new_node(AST_SUB, $1, $3); } 
   ; 
 
factor: term 
      | ADD term        { $$ = calc_ast_new_node(AST_ABS, $2, NULL); } 
      | SUB term        { $$ = calc_ast_new_node(AST_NEG, $2, NULL); } 
      | factor MUL term { $$ = calc_ast_new_node(AST_MUL, $1, $3); } 
      | factor DIV term { $$ = calc_ast_new_node(AST_DIV, $1, $3); } 
      | factor MOD term { $$ = calc_ast_new_node(AST_MOD, $1, $3); } 
      ; 
 
term: NUM           { $$ = calc_ast_new_num($1); } 
    | ABS exp ABS   { $$ = calc_ast_new_node(AST_ABS, $2, NULL); } 
    | OP exp CP     { $$ = $2; } 
    ; 
%% 
 
int main (int argc, char** argv) {
    int i = 1;
 
    printf("Calc V0.1 from: http://unbe.cnnn");
 
    for (;;) {
        fprintf(stdout, "%d> ", i);
 
        if (!yyparse() && !calc_eof) {
            printf("%fn", calc_ast_eval(calc_result));
            calc_ast_free(calc_result);
            i ++;
        } else if (calc_eof) {
            break;
        } else {
            rewind(stdin);
            yyrestart(stdin);
        }
    }
    return 0;
}
 
yyerror (char *s) {
    fprintf(stderr, "error: %sn", s);
}

与前一次的相比有以下几点变化：1－为了提供一个友好的shell对main函数做了升级；2－全面使用抽象语法树（AST）；3－使用了%union和%type语法。

%union语法用于定义bison的YYSTYPE，前一次试验中的YYSTYPE被定义为double，这次定义成了一个联合体。通过%type <d>和%token <a>分别定义了解析到NUM和exp term等语法结构时候的$$的数据类型。

下面是抽象语法树相关代码的头文件（calc_ast.h）：


#ifndef _CALC_AST_H_ 
#define _CALC_AST_H_ 
 
#include <stdio.h> 
#include <stdlib.h> 
 
enum calc_ast_type {
    AST_ADD,
    AST_SUB,
    AST_MUL,
    AST_DIV,
    AST_MOD,
    AST_ABS,
    AST_NEG,
    AST_NUM
};
 
typedef struct calc_ast_s calc_ast;
 
struct calc_ast_s {
    int         type;
    calc_ast*   left;
    calc_ast*   right;
    void*       value;
};
 
typedef struct calc_ast_num_s calc_ast_num;
 
struct calc_ast_num_s {
    int     type;
    double  value;
};
 
 
calc_ast* calc_ast_new_node(int type, calc_ast* left, calc_ast* right);
 
calc_ast* calc_ast_new_num(double value);
 
double calc_ast_eval(calc_ast* ast);
 
void calc_ast_free(calc_ast* ast);
 
#endif

下面是抽象语法树的实现代码（calc_ast.c）：


#include "calc_ast.h" 
 
calc_ast* calc_ast_new_node(int type, calc_ast* left, calc_ast* right) {
    calc_ast* node = malloc(sizeof(calc_ast));
 
    if (!node) {
        fprintf(stderr, "out of memory!n");
        exit(1);
    }
 
    node->type = type;
    node->left = left;
    node->right = right;
 
    return node;
}
 
calc_ast* calc_ast_new_num(double value) {
    calc_ast_num* num = malloc(sizeof(calc_ast_num));
 
    if (!num) {
        fprintf(stderr, "out of memory!n");
        exit(1);
    }
 
    num->type = AST_NUM;
    num->value = value;
 
    return (calc_ast*)num;
}
 
double calc_ast_eval(calc_ast* node) {
    double result;
 
    switch (node->type) {
        case AST_ADD:
            result = calc_ast_eval(node->left) + calc_ast_eval(node->right);
            break;
        case AST_SUB:
            result = calc_ast_eval(node->left) - calc_ast_eval(node->right);
            break;
        case AST_MUL:
            result = calc_ast_eval(node->left) * calc_ast_eval(node->right);
            break;
        case AST_DIV:
            result = calc_ast_eval(node->left) / calc_ast_eval(node->right);
            break;
        case AST_MOD:
            //result = calc_ast_eval(node->left) % calc_ast_eval(node->right); 
            break;
        case AST_ABS:
            result = calc_ast_eval(node->left);
            result = result > 0 ? result : -result;
            break;
        case AST_NUM:
            result = ((calc_ast_num*)node)->value;
            break;
        default:
            fprintf(stderr, "internal error: bad node %dn", node->type);
    }
 
    return result;
}
 
void calc_ast_free(calc_ast* node) {
    switch (node->type) {
        case AST_ADD:
        case AST_SUB:
        case AST_MUL:
        case AST_DIV:
        case AST_MOD:
            calc_ast_free(node->right);
        case AST_ABS:
            calc_ast_free(node->left);
        case AST_NUM:
            free(node);
            break;
    }
}

因为我用的数值类型是double，在直接用%做模运算会报语法错误，所以这个版本先注释掉模运算的代码了。对于calc_ast_num到calc_ast的强制转换我觉得特别扭，但是用void*也好不到哪里去。。。先能用再说吧

下面是Makfile：


calc: calc.lex
    cc -o $@ calc_ast.c calc.tab.c calc.lex.c -lfl 
 
calc.lex: calc.y calc.l calc_ast.h calc_ast.c
    bison -d calc.y 
    flex -o calc.lex.c calc.l 
    cc -D CALC_LEX -o $@ calc_ast.c calc.lex.c -lfl 
 
clean: 
    rm calc 
    rm calc.lex 
    rm calc.lex.c 
    rm calc.tab.h 
    rm calc.tab.c

make出来以后会有两个可执行文件，一个是calc.lex，用来测试文法解析的，另一个是calc，计算器的可执行文件。运行起来是一个类似erlang shell的界面，从上面的语法描述文档可以看出来语法上跟go一样支持分号结束语句也支持换行符结束语句，所以在shell里面就可以一行一行执行了。

接下我还会继续完善这个命令行计算器，近期Road Map如下：

1－添加变量声明和函数声明的支持

2－添加判断、分支、循环语句的支持

3－像erlang一样的可以计算任意大的数值

OK，打完手工，祝大家玩得愉快 :)