c - 在 C 中表示抽象语法树

Question

我正在用 C 为一种简单的玩具语言实现一个编译器。我有一个可用的扫描器和解析器，并且对 AST 的概念函数/构造有一定的了解。我的问题与在 C 中表示 AST 的具体方式有关。我在不同的在线文本/资源中经常遇到三种样式:

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

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

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 的内容不同->类。这样做的好处似乎是一组更统一的宏(LEFT(节点)用于所有节点左右而不是一对宏)，但缺点似乎是 C 类型检查不会那么有用(例如，将无法检测到只有 ast_node_add 的 ast_node_assign)。

一个结构总计，用一个 union 来保存不同类型的节点数据。

可以找到比我能给出的更好的解释 here .使用前面示例中的类型，它看起来像:

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

我最喜欢第三个选项，因为它使递归遍历更容易(因为有利于 union 避免了很多指针转换)，但它也没有利用 C 类型检查。第一个选项似乎是最危险的，因为它依赖于指向被强制转换的结构的指针来访问任何节点的成员(甚至同一节点的不同成员需要不同的情况来访问(基本与左))，但这些强制转换是类型检查所以可能没有实际意义。对我来说，第二种选择似乎是两个世界中最糟糕的，尽管我可能遗漏了一些东西。

这三种方案中哪一种最好，为什么？有没有我还没有遇到的更好的第四个选项？我假设它们都不是“一刀切”的解决方案，所以如果重要的话，我正在实现的语言是静态类型命令语言，几乎是 C 语言的一小部分。

我有一个关于第三( union )布局的具体问题。 如果我只使用值字段，值后面是否会有空格以适应写入 op 的可能性？

Answer 1

您可以使这些工作中的任何一个工作。

我更喜欢 union 布局，因为这样所有节点都有“相同”的布局。

[您可能会发现有一个“子列表”选项很有用，例如，任意大的动态子数组，而不是左倾或右倾列表。]

您会发现这个问题并不是使您的编译器构建变得困难的问题。相反，它拥有符号表、执行各种分析、选择机器级 IR、构建代码生成器并进行代码优化。然后你会遇到真正的用户，你会发现你真正做错了什么:-}

我会选择一个并运行它，以便您有机会接近其他问题。