抽象语法树的定义（c语言版）-ag真人游戏

给定抽象语法：

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

（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");
    }
}

 例如，用上述数据结构来编码程序  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);

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）第几行第几列。