基于KMP算法的C语言类egrep工具正则匹配异常问题排查

核心问题定位 #

你的代码存在两个关键逻辑错误，导致a*b无法匹配aaabbbccc这类行：

1. 匹配语义混淆：全匹配 vs 包含匹配 #

egrep的核心是行内包含匹配（只要行中存在任意子串符合模式即可），但你的regex_match函数实现的是全匹配（要求整个行完全和模式一致）。比如：

• 模式a*b的全匹配要求行必须是b、ab、aab这类以b结尾且前面只有a的字符串；
• 而aaabbbccc行结尾是ccc，不符合全匹配的要求，因此被判定为不匹配。

2. 前缀匹配终止条件错误 #

即使只考虑前缀匹配（模式匹配行的开头部分），原代码中regex_match的终止条件也有误：

if (*pattern == '\0') return *text == '\0'; // 全匹配终止条件

该条件要求模式匹配完成时，文本也必须完全结束。导致模式b无法匹配bbbccc（因为匹配b后文本还有剩余），进而让a*b的匹配逻辑失效。

代码修复方案 #

步骤1：修改匹配逻辑为前缀匹配 #

将regex_match的终止条件改为模式匹配完成即成功（不管文本是否还有剩余）：

// General recursive regex matching function (前缀匹配：模式匹配文本开头部分)
int regex_match(const char* text, const char* pattern) {
    // Debug print
    printf("Matching pattern '%s' with text '%s'\n", pattern, text);

    if (*pattern == '\0') return 1; // 模式匹配完成，前缀匹配成功

    // ... 其余代码保持不变 ...
}

步骤2：新增包含匹配函数 #

添加regex_search函数，遍历文本的每个位置，检查是否存在任意子串能通过前缀匹配符合模式：

// 检查文本中是否包含符合模式的子串（模拟egrep的包含匹配逻辑）
int regex_search(const char* text, const char* pattern) {
    if (*pattern == '\0') return 1; // 空模式匹配任意文本
    do {
        if (regex_match(text, pattern)) {
            return 1;
        }
    } while (*text++ != '\0');
    return 0;
}

步骤3：替换调用逻辑 #

在search_in_file中，将regex_match替换为regex_search：

if (regex_search(line, pattern)) {
    printf("Match found on line %d: %s\n", line_number, line);
}

C语言正则实现常见排查要点 #

• 匹配语义混淆：明确需求是全匹配、前缀匹配还是包含匹配，egrep类工具必须用包含匹配；
• 量词逻辑错误：*（零或多次）、+（一次或多次）的边界条件是否正确，比如零次匹配的处理、循环终止条件；
• 递归终止条件：避免全匹配的终止条件误用在包含/前缀匹配场景；
• 特殊字符处理：命令行传入的模式是否被shell解析（比如*需要用引号包裹），特殊元字符（.、*、|）的逻辑是否覆盖所有情况；
• 文本边界处理：换行符、字符串结束符\0的处理是否正确，比如fgets读取的行是否去除了换行符；
• 子模式优先级：括号分组、分支|的逻辑是否符合正则表达式的优先级规则，比如当前代码中|的处理是从左到右递归拆分，需确认是否符合预期。

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