Représentation D'une arborescence de syntaxe abstraite en C

J'implémente un compilateur pour un langage jouet simple en C. j'ai un scanner et un analyseur de travail, et un fond raisonnable sur la fonction conceptuelle/construction D'un AST. Ma question est liée à la manière spécifique de représenter un AST en C. j'ai rencontré trois styles assez fréquemment dans différents textes / ressources en ligne:

Une structure par type de nœud.

Cela a un nœud de base"class" (struct) qui est le premier champ de toutes les structures enfants. Le le nœud de base contient une énumération qui stocke le type de nœud (constante, opérateur binaire, affectation, etc.). Les membres de la structure sont accessibles à l'aide d'un ensemble de macros, avec un ensemble par structure. Il ressemble à quelque chose comme ceci:

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;

Une structure par disposition de noeud.

Cela semble être la plupart du temps la même que la mise en page ci-dessus, sauf qu'au lieu d'avoir ast_node_add et ast_node_assign, il aurait un ast_node_binary pour représenter les deux, car la mise en page des deux structures est la même et ils ne diffèrent que par le contenu de base- > class. L'avantage de cela semble être un ensemble plus uniforme de macros (left (node) pour tous les nœuds avec un left Et right au lieu d'une paire de macros par), mais l'inconvénient semble que la vérification de type C ne sera pas aussi utile(il n'y aurait aucun moyen de détecter un ast_node_assign où il ne devrait y avoir qu'un ast_node_add, par exemple).

Un total de structure, avec une union pour contenir différents types de données de nœud.

Un meilleur explication de ce que je peux donner peut être trouvé ici. En utilisant les types de l'exemple précédent, cela ressemblerait à:

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

Je suis enclin à aimer le plus la troisième option car elle rend la traversée récursive beaucoup plus facile(en ce sens que beaucoup de casting de pointeur est évité en faveur de l'union), mais elle ne profite pas non plus de la vérification de type C. La première option semble la plus dangereuse en ce sens qu'elle repose sur des pointeurs vers des structures en cours de conversion pour accéder au membre de n'importe quel nœud (même différents membres du même nœud nécessitant différents cas d'accès (base vs gauche)), mais ces casts sont vérifiés de type afin que cela puisse être discutable. La deuxième option me semble être le pire des deux mondes, bien que peut-être que je manque quelque chose.

Laquelle de ces trois régimes sont les meilleurs, et pourquoi? Y a-t-il une meilleure quatrième option que je n'ai pas encore rencontrée? je suppose qu'aucun d'entre eux n'est une solution" One size fits all", donc si cela importe, le langage que j'implémente est un langage impératif statiquement typé, presque un petit sous-ensemble de C.

Une question spécifique que j'ai sur la troisième mise en page(union). Si je n'utilise que le champ value, y aura-t-il un espace vide après la valeur à accommoder pour la possibilité d'écriture op?