Darstellung eines abstrakten Syntaxbaums in C

Ich implementiere einen Compiler für eine einfache Spielzeugsprache in C. Ich habe einen funktionierenden Scanner und Parser und einen vernünftigen Hintergrund zur konzeptionellen Funktion/Konstruktion eines AST. Meine Frage bezieht sich auf die spezifische Art und Weise, wie ein AST in C dargestellt wird. Ich bin in verschiedenen Texten/Ressourcen online ziemlich häufig auf drei Stile gestoßen:

Eine Struktur pro Knotentyp.

Dies hat einen Basisknoten “Klasse” (Struktur), der das erste Feld in allen untergeordneten Strukturen ist. Der Basisknoten enthält eine Aufzählung, die den Typ des Knotens speichert (Konstante, binärer Operator, Zuweisung usw.). Der Zugriff auf Mitglieder der Struktur erfolgt über einen Satz von Makros, mit einem Satz pro Struktur. Es sieht in etwa so aus:

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;

Eine Struktur pro Knotenlayout.

Dies scheint größtenteils das gleiche wie das obige Layout zu sein, außer dass es anstelle von ast_node_add und ast_node_assign ein ast_node_binary hätte, um beide darzustellen, da das Layout der beiden Strukturen dasselbe ist und sie sich nur durch den Inhalt von base->class unterscheiden . Der Vorteil scheint ein einheitlicherer Satz von Makros zu sein (LEFT(node) für alle Knoten mit einem linken und rechten statt einem Makropaar pro), aber der Nachteil scheint, dass die C-Typprüfung nicht so nützlich ist (es gäbe zum Beispiel keine Möglichkeit, ein ast_node_assign zu erkennen, wo es nur ein ast_node_add geben sollte).

Eine Struktur insgesamt, mit einer Vereinigung, um verschiedene Arten von Knotendaten zu speichern.

Eine bessere Erklärung dafür, als ich geben kann, kann gefunden werden hier. Mit den Typen aus dem vorherigen Beispiel würde es so aussehen:

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

Ich neige dazu, die dritte Option am meisten zu mögen, weil sie das rekursive Durchlaufen viel einfacher macht (da viel Pointer-Casting zugunsten der Vereinigung vermieden wird), aber es nutzt auch nicht die Überprüfung des C-Typs. Die erste Option scheint insofern die gefährlichste zu sein, als sie auf Zeiger auf Strukturen angewiesen ist, die umgewandelt werden, um auf das Mitglied eines beliebigen Knotens zuzugreifen (sogar verschiedene Mitglieder desselben Knotens, die unterschiedliche Zugriffsfälle erfordern (Basis vs. links)), aber diese Umwandlungen sind Typ überprüft, so dass das strittig sein könnte. Die zweite Option scheint mir die schlechteste aus beiden Welten zu sein, obwohl ich vielleicht etwas vermisse.

Welches dieser drei Schemata ist das beste und warum? Gibt es eine bessere vierte Option, auf die ich noch nicht gestoßen bin? Ich gehe davon aus, dass keiner von ihnen eine Einheitslösung ist. Wenn es also darauf ankommt, ist die Sprache, die ich implementiere, eine statisch typisierte imperative Sprache, fast eine kleine Teilmenge von C.

Eine spezielle Frage habe ich zum dritten (Union) Layout. Wenn ich nur das Wertfeld verwende, gibt es nach dem Wert einen leeren Platz, um die Möglichkeit zu berücksichtigen, dass in op geschrieben wird?

Sie können jede dieser Arbeiten machen.

Ich bevorzuge das Union-Layout, weil dann alle Knoten “das gleiche” Layout haben.

[You may find it useful to have a “child sublist” option, e.g., and arbitarily big, dynamic array of children, instead of having left- or right-leaning lists.]

Sie werden feststellen, dass dieses Problem nicht dasjenige ist, das das Erstellen Ihres Compilers schwierig macht. Vielmehr geht es darum, Symboltabellen zu haben, verschiedene Arten von Analysen durchzuführen, eine IR auf Maschinenebene auszuwählen, einen Codegenerator zu erstellen und Codeoptimierungen durchzuführen. Dann triffst du auf echte User und entdeckst, was du wirklich falsch gemacht hast :-}

Ich würde einen auswählen und damit laufen, damit Sie die Möglichkeit haben, sich den anderen Themen zu nähern.