在C中表示抽象语法树

我正在C中为一个简单的玩具语言实现一个编译器。我有一个工作的扫描器和解析器,以及AST的概念function/构造的合理背景。 我的问题与在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被写入的可能性吗?

你可以做任何这些工作。

我更喜欢联合布局,因为所有节点都具有“相同”的布局。

[你可能会发现拥有一个“子子列表”选项很有用,例如,和任意​​大的,动态的孩子arrays,而不是左倾或右倾列表。

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

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

艾拉·巴克斯特给了你一个简单而前瞻性的答案 ,特别值得注意的是你将要遇到的问题,所以我将重点关注这个问题:

有没有更好的第四种选择我尚未遇到过?

您正在使用命令式语言编写编译器,并且在设计AST中节点概念的数据结构时遇到问题。 在诸如ML,OCaml,Haskell等function语言的世界中,F#将使用Tagged联合来在一个数据结构中保存所有不同的节点类型,这基本上就是您创建的。

我不认为OP会切换到这个问题的函数式语言,但如果其他人经常处理树,那么他们可能会发现学习函数式语言并将其用于与树有关的问题是有价值的。