如何从PackCC中获取所有匹配规则？动态次数匹配问题求解

核心思路 #

PackCC对expr*这类重复匹配的规则不会自动保存所有匹配结果，需要在子规则的动作中实时收集AST节点，最后在父规则里统一处理这个节点集合。

具体实现步骤 #

1. 定义存储结构与上下文 #

用C的链表或动态数组存储匹配到的expr节点，通过PackCC的上下文传递这个集合（避免全局变量污染）：

// 先定义AST节点和链表结构
typedef struct ExprNode ExprNode;
typedef struct ExprList {
    ExprNode* node;
    struct ExprList* next;
} ExprList;

// 在语法开头声明上下文变量
%context {
    ExprList* expr_list;
}

2. 在子规则中收集节点 #

修改expr规则的动作，每次匹配到表达式就将其AST节点加入链表：

expr <- /* 你的expr规则定义 */ {
    // 创建新链表节点并插入头部
    ExprList* new_item = malloc(sizeof(ExprList));
    new_item->node = $$; // $$是expr生成的AST节点
    new_item->next = ctx->expr_list;
    ctx->expr_list = new_item;
}

3. 在父规则中处理节点集合 #

在application的动作里，将链表转换为AST的子节点列表，之后清理临时链表：

application <- '(' e:expr* ')' {
    // 反转链表（因为头插法导致顺序颠倒），生成应用节点
    $$ = create_application_node(reverse_expr_list(ctx->expr_list));
    // 释放链表的临时结构（保留AST节点本身）
    free_expr_list_nodes(ctx->expr_list);
    ctx->expr_list = NULL;
}
/ '{' e:expr* '}' { /* 复制上述处理逻辑 */ }
/ '[' e:expr* ']' { /* 复制上述处理逻辑 */ }

辅助函数示例 #

需要实现链表反转和临时节点释放的辅助函数：

ExprList* reverse_expr_list(ExprList* list) {
    ExprList* prev = NULL;
    ExprList* curr = list;
    while (curr) {
        ExprList* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

void free_expr_list_nodes(ExprList* list) {
    while (list) {
        ExprList* temp = list;
        list = list->next;
        free(temp);
    }
}

替代方案：使用动态数组 #

如果链表操作繁琐，可改用动态数组存储：

// 上下文声明
%context {
    ExprNode** expr_array;
    size_t expr_count;
    size_t expr_capacity;
}

// expr规则的收集动作
expr <- /* 你的expr规则定义 */ {
    // 动态扩容数组
    if (ctx->expr_count >= ctx->expr_capacity) {
        ctx->expr_capacity = ctx->expr_capacity == 0 ? 4 : ctx->expr_capacity * 2;
        ctx->expr_array = realloc(ctx->expr_array, sizeof(ExprNode*) * ctx->expr_capacity);
    }
    ctx->expr_array[ctx->expr_count++] = $$;
}

// application规则的处理动作
application <- '(' e:expr* ')' {
    $$ = create_application_node(ctx->expr_array, ctx->expr_count);
    // 重置数组状态，避免内存泄漏
    free(ctx->expr_array);
    ctx->expr_array = NULL;
    ctx->expr_count = 0;
    ctx->expr_capacity = 0;
}

注意事项 #

• 必须在父规则动作中清理临时存储结构，否则会引发内存泄漏，还会干扰后续匹配。
• 若语法中有多个重复匹配规则，需为每个规则分配独立的存储变量，防止互相干扰。

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