在C中表示抽象语法树

Question

我正在C中为一个简单的玩具语言实现一个编译器.我有一个工作的扫描器和解析器,以及关于AST的概念功能/构造的合理背景.我的问题与在C中表示AST的具体方式有关.我在网上不同的文本/资源中经常遇到三种风格:

每种类型的节点一个结构.

它有一个基节点"class"(struct),它是所有子结构中的第一个字段.基节点包含一个存储节点类型的枚举(常量,二元运算符,赋值等).使用一组宏访问结构的成员,每个结构一个集.它看起来像这样:

struct ast_node_base {
    enum {CONSTANT, ADD, SUB, ASSIGNMENT} class;
};

struct ast_node_constant {
    struct ast_node_base *base;
    int value;
};

struct ast_node_add {
    struct ast_node_base *base;
    struct ast_node_base *left;
    struct ast_node_base *right;
};

struct ast_node_assign {
    struct ast_node_base *base;
    struct ast_node_base *left;
    struct ast_node_base *right;
};

#define CLASS(node) ((ast_node_base*)node)->class;

#define ADD_LEFT(node) ((ast_node_add*)node)->left;
#define ADD_RIGHT(node) ((ast_node_add*)node)->right;

#define ASSIGN_LEFT(node) ((ast_node_assign*)node)->left;
#define ASSIGN_RIGHT(node) ((ast_node_assign*)node)->right;

每个节点布局一个结构.

这似乎与上面的布局大致相同,除了没有ast_node_add和ast_node_assign它将有一个ast_node_binary来表示两者,因为两个结构的布局是相同的,它们只是由base-> class的内容不同.这样做的好处似乎是一组更加统一的宏(左侧和右侧所有节点的LEFT(节点),而不是每对一对宏),但缺点似乎是C类型检查不会有用(例如,没有办法检测到只有ast_node_add的ast_node_assign).

一个结构总数,带有用于保存不同类型节点数据的联合.

可以在这里找到比我能给出的更好的解释.使用上一个示例中的类型,它看起来像:

struct ast_node {
  enum { CONSTANT, ADD, SUB, ASSIGNMENT } class;
  union { int                                 value;
          struct { struct ast_node* left;    
                   struct ast_node* right;  } op;
};

我倾向于最喜欢第三个选项,因为它使得递归遍历变得更容易(因为大量的指针转换被避免支持联合),但它也没有利用C类型检查.第一个选项似乎是最危险的,因为它依赖于指向结构的指针来访问任何节点的成员(甚至同一节点的不同成员需要不同的情况来访问(base vs. left)),但这些类型转换是类型的检查,这可能是没有实际意义的.我的第二个选择似乎是两个世界中最糟糕的选择,尽管我可能会遗漏一些东西.

这三种方案中哪一种最好,为什么？我还没有找到更好的第四种选择吗？ 我假设它们都不是"一刀切"的解决方案,所以如果重要的是我正在实现的语言是静态类型的命令式语言,几乎是C的一小部分.

我对第三个(联合)布局的具体问题. 如果我只使用值字段,那么值后面会有空格,以适应op被写入的可能性吗？

Answer 1

你可以做任何这些工作.

我更喜欢联合布局,因为所有节点都有"相同"的布局.

[你可能会发现有一个"子子列表"选项是有用的,例如,和任意​​大的,动态的孩子数组,而不是左倾或右倾列表.

您将发现此问题不是使编译器难以构建的问题.相反,它具有符号表,执行各种分析,选择机器级IR,构建代码生成器以及执行代码优化.然后你会遇到真正的用户,你会发现你真正做错了什么: - }

我会选择一个并运行它,这样你就有机会接近其他问题.