The AST as a tagged union

An Abstract Syntax Tree represents the hierarchical structure of a program after parsing. In first, the AST uses the classic C pattern of a tagged union — a single struct type that can hold any node variant, with a tag field indicating which variant is active.

The shape of a node

typedef struct AST {
  Kind tag;                              // which variant is active
  union {
    struct AST_PROGRAM              AST_PROGRAM;
    struct AST_EXPRESSION_LIST      AST_EXPRESSION_LIST;
    struct AST_BINARY_EXPRESSION    AST_BINARY_EXPRESSION;
    struct AST_IDENTIFIER           AST_IDENTIFIER;
    struct AST_BOOLEAN              AST_BOOLEAN;
    struct AST_NUMBER               AST_NUMBER;
    struct AST_STRING               AST_STRING;
    struct AST_ASSIGNMENT           AST_ASSIGNMENT;
    struct AST_VARIABLE_DECLARATION AST_VARIABLE_DECLARATION;
    struct AST_UNARY                AST_UNARY;
    struct AST_CONDITIONAL          AST_CONDITIONAL;
    struct AST_BLOCK                AST_BLOCK;
    struct AST_FUNCTION             AST_FUNCTION;
    struct AST_CALL                 AST_CALL;
  } data;
} AST;

Every node is the same size in memory (the size of the largest variant — currently AST_CONDITIONAL, which holds a growable array of when arms). The tag field tells the interpreter which data member is valid to read, e.g. ast->data.AST_BINARY_EXPRESSION.left.

Why not a class hierarchy?

In object-oriented languages you would model this with a base class and subclasses for each node type. In C, the tagged union is the idiomatic equivalent — and it keeps everything in a single allocation without pointer indirection to vtables.

The compiler enforces completeness

With -Wswitch enabled (part of -Wextra, which every target builds with), the compiler warns if any switch (ast->tag) does not handle every Kind value. Adding a new tag triggers compile-time warnings in every switch that does not handle it. The compiler audits your code for you.