C编译器AST中表达式类型表示方案咨询：是否有标准实现方式？

在C编译器的AST实现中，**带标签的联合体（Tagged Union）**是最主流、最高效的标准方案，完全能替代你考虑的链表实现（链表本身不适合AST这种树形结构，且内存冗余确实很高）。下面是具体的实现思路和替代方案：

一、带标签的联合体（Tagged Union） #

这是C语言里处理异构树形结构的经典手法，核心是用一个枚举标记节点类型，搭配联合体存储不同表达式的具体数据：

// 枚举所有表达式类型
typedef enum {
    EXPR_BINARY,   // 二元运算：a + b, c * d
    EXPR_UNARY,    // 一元运算：-x, !flag
    EXPR_LITERAL,  // 字面量：123, "hello"
    EXPR_VAR,      // 变量引用：foo, bar
    EXPR_ASSIGN    // 赋值表达式：x = 5
} ExprType;

// 前置声明具体表达式结构
typedef struct Expr Expr;
typedef struct BinaryExpr BinaryExpr;
typedef struct UnaryExpr UnaryExpr;
typedef struct LiteralExpr LiteralExpr;

// 核心AST表达式节点：标签+联合体
struct Expr {
    ExprType type;
    union {
        BinaryExpr* binary;
        UnaryExpr* unary;
        LiteralExpr* literal;
        char* var_name;          // 变量引用直接存名字，不用额外结构体
        struct {                 // 赋值表达式直接内嵌结构
            char* var;
            Expr* value;
        } assign;
    } data;
};

// 具体表达式的结构定义
struct BinaryExpr {
    char op;          // 运算符：+, -, *, /
    Expr* left;
    Expr* right;
};

struct UnaryExpr {
    char op;          // 运算符：-, !
    Expr* operand;
};

struct LiteralExpr {
    enum { LIT_INT, LIT_STR } lit_type;
    union {
        int int_val;
        char* str_val;
    } val;
};

这种方式的优势：

• 内存紧凑：每个节点只存储必要的类型标签和对应数据，没有链表的指针冗余
• 类型安全：通过标签可以明确判断节点类型，避免非法访问
• 适配AST树形结构：轻松支持多子节点的表达式（比如二元运算的左右操作数）

二、模拟面向对象的多态结构体 #

如果需要更灵活的扩展（比如后续添加新表达式类型时，不用修改核心Expr结构体），可以用基结构体+函数指针表的方式模拟多态：

// 基结构体：所有表达式节点的公共部分
typedef struct Expr Expr;
typedef void (*ExprFreeFunc)(Expr*);
typedef void (*ExprPrintFunc)(Expr*);

struct Expr {
    ExprType type;
    ExprFreeFunc free;
    ExprPrintFunc print;
};

// 具体表达式结构体，嵌入基结构体
typedef struct BinaryExpr {
    Expr base;
    char op;
    Expr* left;
    Expr* right;
} BinaryExpr;

// 实现具体的操作函数
void BinaryExprFree(Expr* expr) {
    BinaryExpr* bin = (BinaryExpr*)expr;
    bin->left->free(bin->left);
    bin->right->free(bin->right);
    free(bin);
}

// 创建节点时初始化函数指针
Expr* CreateBinaryExpr(char op, Expr* left, Expr* right) {
    BinaryExpr* bin = malloc(sizeof(BinaryExpr));
    bin->base.type = EXPR_BINARY;
    bin->base.free = BinaryExprFree;
    bin->op = op;
    bin->left = left;
    bin->right = right;
    return (Expr*)bin;
}

这种方式适合大型编译器项目，扩展新表达式类型时只需要定义新结构体和对应函数，不用修改核心的Expr结构。

为什么链表不适合AST？ #

链表是线性结构，只能表达顺序关系，但AST是树形结构，每个表达式节点可能有多个子节点（比如二元运算需要左右两个操作数），链表无法直接表达这种分支关系；另外链表每个节点额外存储前后指针，内存开销比上面两种方案大很多，访问子节点的效率也更低。

额外优化建议 #

• 用内存池分配AST节点：编译器处理代码时会创建大量AST节点，用内存池批量分配可以减少内存碎片，提升分配/释放效率
• 尽量内嵌小型数据：比如变量名、简单运算符可以直接存在联合体里，不用额外动态分配结构体，进一步节省内存

内容的提问来源于stack exchange，提问作者gillo04