在 C 中用节点类型的不同结构表示 AST

Question

我有很多看起来像这样的结构：

typedef struct ast_function_node
{        
    int node_type;
    ast_node* arguments;
    symbol* sym;
} ast_function_node;

typedef struct ast_while_node
{
    int node_type;
    ast_node* condition;
    ast_node* while_branch;
} ast_while_node;

typedef struct ast_assignment_node
{
    int node_type;
    symbol* sym;
    ast_node* value;
} ast_assignment_node;

typedef struct ast_number_node
{
    int node_type;
    double value;
} ast_number_node;

typedef struct ast_string_node 
{
    int node_type;
    char* value;
} ast_string_node;

etc...

还有一个基础结构：

typedef struct // Basic AST node
{
  int node_type;
  struct ast_node* left;
  struct ast_node* right;
} ast_node;

我可以很容易地填充这个 AST，但是当涉及到遍历它时，我陷入了类型转换的困境。如果我想访问每个节点，查看它的类型然后相应地做一些事情，最好的方法是什么？当然，仅仅将它投射到 ast_node 的基节点是不行的。

Answer 1

我在 C 中执行此操作的方法是将 struct 与 union 成员一起使用：

typedef struct ast_function
{        
    ast_node* arguments;
    symbol* sym;
} ast_function;

typedef struct ast_while
{
    ast_node* condition;
    ast_node* while_branch;
} ast_while;

typedef struct ast_assignment
{
    symbol* sym;
    ast_node* value;
} ast_assignment;

/* Etc. */

typedef struct ast_node {
  int node_type;
  /* See anonymous unions in any C reference */
  union {
    ast_function   function_data;
    ast_while      while_data;
    ast_assignment assignment_data;
    /* Etc. */
  };
}

那么你根本不需要强制转换：

switch (node->node_type) {
  case AST_FUNCTION:
    handle_function(&node->function_data); 
    break;
  /* Etc. */
}

如果您将 node_type 设为 enum 而不是 int，如果您在 switch 语句中遗漏了一个可能性，编译器将能够警告您。

在 C 中用节点类型的不同结构表示 AST

Representing an AST in C with different structs for types of nodes

parsing

abstract-syntax-tree

bison

flex-lexer

yacc