抽象語法樹

在計算機科學中，抽象語法樹（Abstract Syntax Tree，AST），或簡稱語法樹（Syntax tree），是源代碼語法結構的一種抽象表示。它以樹狀的形式表現(xiàn)編程語言的語法結構，樹上的每個節(jié)點都表示源代碼中的一種結構。之所以說語法是“抽象”的，是因為這里的語法并不會表示出真實語法中出現(xiàn)的每個細節(jié)。比如，嵌套括號被隱含在樹的結構中，并沒有以節(jié)點的形式呈現(xiàn)；而類似于 if-condition-then 這樣的條件跳轉(zhuǎn)語句，可以使用帶有三個分支的節(jié)點來表示。和抽象語法樹相對的是具體語法樹（通常稱作分析樹）。一般的，在源代碼的翻譯和編譯過程中，語法分析器創(chuàng)建出分析樹，然后從分析樹生成AST。一旦AST被創(chuàng)建出來，在后續(xù)的處理過程中，比如語義分析階段，會添加一些信息。下面是輾轉(zhuǎn)相除法對應的抽象語法樹

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

輾轉(zhuǎn)相除法抽象語法樹

計算器實例

首先我們創(chuàng)建計算器的頭文件fb3-1.h

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

/** ast中的節(jié)點*/
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 *);
/**
 * 抽象語法樹由多個節(jié)點組成，每個節(jié)點都有一個節(jié)點類型。不同的節(jié)點可以有不同的域，但目前我們只有兩種類型，一種是執(zhí)行最多兩個子節(jié)點的指針，另外一種包含一個數(shù)組。eval遍歷ast，返回它所代表的表達式的值。
 *
 * */

然后我們創(chuàng)建Bison的語法分析規(guī)則文件fb_3_1.y

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

/*第一部分使用%union來生命語法分析器中符號值的類型
一旦聯(lián)合類型被定義，我們需要告訴bison每種語法符號使用的值類型，這通過放置在尖括號<>中的聯(lián)合類型的響應成員名字來確定。
新的聲明 %type把值<a>賦給exp, factor, term，當我們創(chuàng)建ast時會用到他們
如果你不使用記號或者非終結符的值，你并不需要為他們聲明類型。
當聲明中存在%union時，如果你試圖使用一個沒有被賦予類型的符號值，bison將會報錯。
*/
%union {
    struct ast *a;
    double d;
}

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

%%
calclist:/*空規(guī)則*/
    | 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();
}

然后我們再創(chuàng)建fb_3_1.funcs.c文件來具體實現(xiàn)抽象語法樹

#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);
    }
}

最后我們創(chuàng)建Makefile文件來指定編譯內(nèi)容，

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

在終端窗口中執(zhí)行編譯和測試

% 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",然后將數(shù)據(jù)喂給Bison，Bison利用語法規(guī)則匹配到最后一條term: NUMBER { $$ = newnum($1); }，在這里會調(diào)用newnum這個函數(shù)并將返回值賦給term，讀取'+'號后，因暫時無法匹配任何規(guī)則，會移進到堆棧中，然后繼續(xù)讀取'3'，會像‘2’一樣進行類似處理返回一個數(shù)字ast，然后堆棧中的內(nèi)容可以匹配上第二條

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

會進行歸約處理，調(diào)用newast這個函數(shù)構造出一個新的抽象語法樹，語法樹的結構如下：

語法樹

將新生成的語法樹移進之后，發(fā)現(xiàn)已輸入結束，可匹配上第一條規(guī)則

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

此時會調(diào)用eval這個函數(shù)，并將上面得到的語法樹作為參數(shù)傳遞到函數(shù)中去（$2的值），在eval函數(shù)中首先會匹配上'+'號

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;
}

然后會遞歸調(diào)用eval這個函數(shù)，不過傳的參數(shù)分別是左子樹和右子樹，

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，然后執(zhí)行相加操作，得到最后的返回值5，再打印出來就得到了測試結果。

全部代碼大家可以到我的github上去下載