如何在C语言中正确构建AST的parser_term函数？

1. 先定义AST节点结构 #

创建二元操作节点的前提是明确AST节点的类型与存储结构，这是核心基础：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 节点类型枚举
typedef enum {
    NODE_NUMBER,   // 数值节点
    NODE_BINARY_OP // 二元操作符节点
} NodeType;

// AST节点结构体
typedef struct Node {
    NodeType type;
    union {
        double number; // 数值节点存储的值
        struct {
            char op;          // 操作符（+/-/*/）
            struct Node* left;  // 左子节点
            struct Node* right; // 右子节点
        } binary;
    } value;
} Node;

2. 封装节点创建函数 #

为避免重复代码和手动分配内存的错误，封装创建不同类型节点的辅助函数：

// 创建数值节点
Node* create_number_node(double num) {
    Node* node = (Node*)malloc(sizeof(Node));
    if (!node) {
        perror("Failed to allocate node");
        exit(EXIT_FAILURE);
    }
    node->type = NODE_NUMBER;
    node->value.number = num;
    return node;
}

// 创建二元操作节点
Node* create_binary_node(char op, Node* left, Node* right) {
    Node* node = (Node*)malloc(sizeof(Node));
    if (!node) {
        perror("Failed to allocate node");
        exit(EXIT_FAILURE);
    }
    node->type = NODE_BINARY_OP;
    node->value.binary.op = op;
    node->value.binary.left = left;
    node->value.binary.right = right;
    return node;
}

3. parser_term的正确实现 #

parser_term负责解析乘法、除法这类高优先级操作，核心逻辑是：先解析一个factor，再循环检查后续是否有*或/操作符，若有则继续解析下一个factor，并将当前节点与新factor节点组合成二元操作节点：

// 假设你已实现词法分析器（Tokenizer），提供以下接口：
// - tokenizer_next(tok): 移动到下一个token
// - tok->current_token: 当前token的信息（类型、值）
// - TOKEN_OP: 操作符token类型
// - parser_factor(tok): 解析因子（数字、括号表达式等）

Node* parser_term(Tokenizer* tok) {
    // 先解析第一个factor
    Node* node = parser_factor(tok);
    if (!node) return NULL;

    // 循环处理后续的*或/操作
    while (tok->current_token.type == TOKEN_OP && 
           (tok->current_token.value[0] == '*' || tok->current_token.value[0] == '/')) {
        char op = tok->current_token.value[0];
        // 跳过当前操作符token
        tokenizer_next(tok);

        // 解析右边的factor
        Node* right_node = parser_factor(tok);
        if (!right_node) {
            // 解析失败，释放已创建的节点避免内存泄漏
            free_node(node);
            return NULL;
        }

        // 创建新的二元操作节点，替换原来的node为组合后的节点
        Node* new_node = create_binary_node(op, node, right_node);
        node = new_node;
    }

    return node;
}

4. 常见错误修正 #

（1）内存泄漏问题 #

必须实现递归释放AST节点的函数，否则会造成内存泄漏：

void free_node(Node* node) {
    if (!node) return;
    if (node->type == NODE_BINARY_OP) {
        // 先释放子节点
        free_node(node->value.binary.left);
        free_node(node->value.binary.right);
    }
    free(node);
}

（2）词法-语法衔接错误 #

• 每次处理完一个token后，必须调用tokenizer_next()移动到下一个token，否则会重复处理同一个操作符，导致死循环。
• 确保parser_factor能正确处理括号表达式（比如(1+2)），否则parser_term无法处理嵌套表达式。

（3）错误处理缺失 #

• 当解析right_node失败时，必须释放之前创建的node，否则会丢失内存引用造成泄漏。
• 内存分配失败时要做错误处理（比如malloc返回NULL时打印错误并退出）。

（4）表达式优先级错误 #

确保语法分析的层级正确：parser_expr（处理加减）调用parser_term，parser_term调用parser_factor，这样才能保证乘法/除法优先级高于加法/减法。

5. AST打印示例 #

实现递归打印AST的函数，验证解析结果是否正确：

void print_ast(Node* node) {
    if (!node) return;
    switch (node->type) {
        case NODE_NUMBER:
            printf("%.2f", node->value.number);
            break;
        case NODE_BINARY_OP:
            printf("(");
            print_ast(node->value.binary.left);
            printf(" %c ", node->value.binary.op);
            print_ast(node->value.binary.right);
            printf(")");
            break;
    }
}

比如输入2*3+4/2，解析后打印AST会输出((2.00 * 3.00) + (4.00 / 2.00))，符合优先级规则。

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