基于抽象语法树改造的计算器实例

抽象语法树

在计算机科学中，抽象语法树（Abstract Syntax Tree，AST），或简称语法树（Syntax tree），是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。之所以说语法是“抽象”的，是因为这里的语法并不会表示出真实语法中出现的每个细节。比如，嵌套括号被隐含在树的结构中，并没有以节点的形式呈现；而类似于 if-condition-then 这样的条件跳转语句，可以使用带有三个分支的节点来表示。和抽象语法树相对的是具体语法树（通常称作分析树）。一般的，在源代码的翻译和编译过程中，语法分析器创建出分析树，然后从分析树生成AST。一旦AST被创建出来，在后续的处理过程中，比如语义分析阶段，会添加一些信息。下面是辗转相除法对应的抽象语法树

while (b != 0) {
      if (a > b)
          a = a − b;
      else
          b = b − a;
}
return a

辗转相除法抽象语法树

计算器实例

首先我们创建计算器的头文件fb3-1.h

/** 与词法分析器的解口*/
extern int yylineno; /*来自于词法分析器*/
void yyerror(char *s, ...);
int yylex();

/** ast中的节点*/
struct ast {
    int nodetype;
    struct ast *l;
    struct ast *r;
};

struct numval {
    int nodetype; /**类型k表明常量*/
    double number;
};

/** 构造ast*/
struct ast *newast(int nodetype, struct ast *l, struct ast *r);
struct ast *newnum(double d);

/** 计算ast*/
double eval (struct ast *);
/**删除和释放ast*/
void treefree(struct ast *);
/**
 * 抽象语法树由多个节点组成，每个节点都有一个节点类型。不同的节点可以有不同的域，但目前我们只有两种类型，一种是执行最多两个子节点的指针，另外一种包含一个数组。eval遍历ast，返回它所代表的表达式的值。
 *
 * */

然后我们创建Bison的语法分析规则文件fb_3_1.y

%{
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include "fb_3_1.h"
%}

/*第一部分使用%union来生命语法分析器中符号值的类型
一旦联合类型被定义，我们需要告诉bison每种语法符号使用的值类型，这通过放置在尖括号<>中的联合类型的响应成员名字来确定。
新的声明 %type把值<a>赋给exp, factor, term，当我们创建ast时会用到他们
如果你不使用记号或者非终结符的值，你并不需要为他们声明类型。
当声明中存在%union时，如果你试图使用一个没有被赋予类型的符号值，bison将会报错。
*/
%union {
    struct ast *a;
    double d;
}

%token <d> NUMBER
%token EOL
%type <a> exp factor term

%%
calclist:/*空规则*/
    | calclist exp EOL { 
        printf("=%4.4g\n", eval($2)); 
        treefree($2);
        printf("> ");
    }
    | calclist EOL { printf(">");} /*空行或注释*/
    ;

exp: factor 
   | exp '+' factor { $$ = newast('+', $1, $3);}
   | exp '-' factor { $$ = newast('-', $1, $3);}
   ;
factor: term  
   | factor '*' term { $$ = newast('*', $1, $3); }
   | factor '/' term { $$ = newast('/', $1, $3); }
   ;
term: NUMBER { $$ = newnum($1); }
    | '|' term {$$ = newast('|', $2, NULL);}
    |'(' exp ')' {$$ = $2;}
    | '-' term {$$ = newast('M', $2, NULL);}
    ;
%% 

void
yyerror(char *s, ...)
{
    va_list ap;
    va_start(ap, s);
    fprintf(stderr, "%d: error: ", yylineno);
    vfprintf(stderr, s, ap);
    fprintf(stderr, "\n");
}
int
main(int argc, char **argv)
{
    printf("> ");
    return yyparse();
}

然后我们再创建fb_3_1.funcs.c文件来具体实现抽象语法树

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include "fb_3_1.h"

struct ast *
newast(int nodetype, struct ast *l, struct ast *r)
{
    struct ast *a = malloc(sizeof(struct ast));
    if (!a) {
        printf("out of space");
        exit(0);
    }

    a->nodetype = nodetype;
    a->l = l;
    a->r = r;
    return a;
}

struct ast *
newnum(double d)
{
    struct numval *a = malloc(sizeof(struct numval));
    if (!a) {
        printf("out of space");
        exit(0);
    }

    a->nodetype = 'k';
    a->number = d;
    return (struct ast *)a;

}

double 
eval(struct ast *a)
{
    double v;

    printf("nodetype:%c\n", a->nodetype);
    if (a->nodetype == 'k') {
        printf("number:%f\n", ((struct numval *)a)->number);
    }
    switch(a->nodetype) {
        case 'k': v = ((struct numval *)a)->number;break;
        case '+': v = eval(a->l) + eval(a->r); break;
        case '-': v = eval(a->l) - eval(a->r); break;
        case '*': v = eval(a->l) * eval(a->r); break;
        case '/': v = eval(a->l) / eval(a->r); break;
        case '|': v = eval(a->l); if (v < 0) v = -v; break;
        case 'M': v = eval(a->l); break;
        default: printf("internal error: bad node %c\n", a->nodetype);
    }
    return v;
}

void
treefree(struct ast *a)
{
    switch(a->nodetype) {
        /**两颗子树*/
        case '+':
        case '-':
        case '*':
        case '/':
            treefree(a->r);
       /*一颗子树*/
        case '|':
        case 'M':
            treefree(a->l);
       /*没有子树*/
        case 'k':
            free(a);
            break;
        default: printf("internal error: bad node %c\n", a->nodetype);
    }
}

最后我们创建Makefile文件来指定编译内容，

fb_3_1: fb_3_1.l fb_3_1.y fb_3_1.h
    bison -d fb_3_1.y
    flex -o fb_3_1.lex.c fb_3_1.l
    gcc -o $@ fb_3_1.tab.c fb_3_1.lex.c fb_3_1.funcs.c
clean:
    rm -rf fb_3_1.lex.c fb_3_1 fb_3_1.tab.c fb_3_1.tab.h

在终端窗口中执行编译和测试

% make
bison -d fb_3_1.y
flex -o fb_3_1.lex.c fb_3_1.l
gcc -o fb_3_1 fb_3_1.tab.c fb_3_1.lex.c fb_3_1.funcs.c
% ./fb_3_1 
> 2 + 3
nodetype:+
nodetype:k
number:2.000000
nodetype:k
number:3.000000
=   5
> 6 * 7
nodetype:*
nodetype:k
number:6.000000
nodetype:k
number:7.000000
=  42
> 

测试结果分析

当我们在测试代码中键入2 + 3回车后，首先Flex会进行词法分析，得到3个token,'2','+',"3",然后将数据喂给Bison，Bison利用语法规则匹配到最后一条term: NUMBER { $$ = newnum($1); }，在这里会调用newnum这个函数并将返回值赋给term，读取'+'号后，因暂时无法匹配任何规则，会移进到堆栈中，然后继续读取'3'，会像‘2’一样进行类似处理返回一个数字ast，然后堆栈中的内容可以匹配上第二条

exp: factor 
        | exp '+' factor { $$ = newast('+', $1, $3);}

会进行归约处理，调用newast这个函数构造出一个新的抽象语法树，语法树的结构如下：

语法树

将新生成的语法树移进之后，发现已输入结束，可匹配上第一条规则

calclist:/*空规则*/
    | calclist exp EOL { 
        printf("=%4.4g\n", eval($2)); 
        treefree($2);
        printf("> ");
    }

此时会调用eval这个函数，并将上面得到的语法树作为参数传递到函数中去（$2的值），在eval函数中首先会匹配上'+'号

eval(struct ast *a)
{
    double v;

    printf("nodetype:%c\n", a->nodetype);
    if (a->nodetype == 'k') {
        printf("nodetype:%f\n", ((struct numval *)a)->number);
    }
    switch(a->nodetype) {
        ...
        case '+': v = eval(a->l) + eval(a->r); break;
        ...
    }
    return v;
}

然后会递归调用eval这个函数，不过传的参数分别是左子树和右子树，

double 
eval(struct ast *a)
{
    double v;

    printf("nodetype:%c\n", a->nodetype);
    if (a->nodetype == 'k') {
        printf("nodetype:%f\n", ((struct numval *)a)->number);
    }
    switch(a->nodetype) {
        case 'k': v = ((struct numval *)a)->number;break;
        ...
    }
    return v;
}

由于左右子树的类型都为k,那么直接返回其number值，分别为2和3，然后执行相加操作，得到最后的返回值5，再打印出来就得到了测试结果。

全部代码大家可以到我的github上去下载