菜鸟笔记
提升您的技术认知

抽象语法树的定义(C语言版)

给定抽象语法:

   E -> n

     | E + E

     | E * E

构造出相应的抽象语法树

抽象语法树的数据结构及相关操作

enum kind {E_INT, E_ADD, E_TIMES};
struct Exp 
{
    enum kind kind;
};
struct Exp_Int   // 对应第一个右部
{
    enum kind kind;
    int n;
};
struct Exp_Add   // 对应第二个右部
{
    enum kind kind;
    struct Exp *left;
    struct Exp *right;
};
struct Exp_Times // 对应第三个右部
{
    enum kind kind;
    struct Exp *left;
    struct Exp *right;
};

// “构造函数”的定义
struct Exp_Int *Exp_Int_new(int n)
{
    struct Exp_Int *p = malloc(sizeof(*p));
    p->kind = E_ADD;
    p->n = n;
    return p;
}

struct Exp_Add *Exp_Add_new(struct Exp *left, struct Exp *right)
{
    struct Exp_Add *p = malloc(sizeof(*p));
    p->kind = E_ADD;
    p->left = left;
    p->right = right;
    return p;
}

struct Exp_Times *Exp_Times_new(struct Exp *left, struct Exp *right)
{
    struct Exp_Times *p = malloc(sizeof(*p));
    p->kind = E_TIMES;
    p->left = left;
    p->right = right;
    return p;
}

 AST上的常用操作

(1)优美打印

void pretty_print(e)
{
    switch (e->kind)
    {
    case E_INT:
        printf("%d", e->n);
        return;
    case E_ADD:
        printf("(");
        pretty_print(e->left);
        printf(")");
        printf(" + ");
        printf("(");
        pretty_print(e->right);
        printf(")");
    case E_TIMES:
        printf("(");
        pretty_print(e->left);
        printf(")");
        printf(" * ");
        printf("(");
        pretty_print(e->right);
        printf(")");
    default:
        break;
    }
}

(2)树的规模(节点个数)

int numNodes(E e)
{
    switch (e->kind)
    {
    case E_INT: return 1;
    case E_ADD: 
    case E_TIMES:
        return 1 + numNodes(e->left)
                 + numNodes(e->right);
    default:
        error("compiler bug");
    }
}

1、手工构造 

 例如,用上述数据结构来编码程序  2 + 3 * 4

e1 = Exp_Int_new(2);
e2 = Exp_Int_new(3);
e3 = Exp_Int_new(4);
e4 = Exp_Times_new(e2, e3);
e5 = Exp_Add_new(e1, e4);

2、自动生成

LR分析中生成抽象语法树

(1)在语法动作中,加入生成语法树的代码片段(片段一般是语法树的“构造函数”)

(2)在产生式归约的时候,会自底向上构造整棵树(从叶子到根)

比如,在yacc中,我们书写以下代码

   E -> E + E    {$$ = Exp_Add_new($1, $3);}
     |  E * E    {$$ = Exp_Times_new($1, $3);}
     |  n        {$$ = Exp_Int_new($1);}

源代码信息的保留和传播

抽象语法树是编译器前端和后端的接口,程序一旦被转换成抽象语法树,则源代码即被丢弃,后续的阶段只处理抽象语法树。

所以抽象语法树必须编码足够多的源代码信息,例如它必须编码每个语法结构在源代码中的位置(文件、行号、列号等),这样,后续的检查阶段才能精准的报错,或者获取程序的执行剖面。

示例:位置信息

struct position_t
{
    char *file;
    int line;
    int column;
};
struct Exp_Add
{
    enum kind kind;
    Exp *left;
    Exp *right;
    struct position_t from;
    struct position_t to;
};

上述程序可以表示我们识别了这样一个子树的结构,并且这棵子树对应的源代码是从(from)第几行第几列到(to)第几行第几列。