创建带有C优化错误的egrep命令克隆

Question

我正在开发一个 C 程序，使用 KMP (Knuth-Morris-Pratt) 算法实现类似正则表达式的模式匹配。但是，我遇到了一个问题，即程序产生不正确的输出，即使我期望根据提供的输入进行匹配。

这是我的代码：

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

// Match any character ('.')
int match_any(char c) {
    return c != '\0'; // '.' matches any character except the end of string.
}

// Recursive function to evaluate pattern with '*' (star operator)
int match_star(const char* text, const char* pattern, char prev_char) {
    // Try zero repetitions first (move directly to the next pattern)
    if (regex_match(text, pattern)) {
        return 1;
    }

    // Try one or more repetitions of the previous character
    while (*text && (*text == prev_char || prev_char == '.')) {
        text++;
        if (regex_match(text, pattern)) {
            return 1;
        }
    }

    return 0;
}

// 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 *text == '\0'; // End of pattern and text match

    // Handle grouped sub-patterns inside parentheses
    if (*pattern == '(') {
        const char* end = strchr(pattern, ')');
        if (!end) return 0; // Invalid pattern (no closing parenthesis)

        // Extract and process the sub-pattern inside the parentheses
        char subpattern[1024];
        strncpy(subpattern, pattern + 1, end - pattern - 1);
        subpattern[end - pattern - 1] = '\0';

        if (!regex_match(text, subpattern)) return 0;

        // Continue matching after the parentheses
        return regex_match(text, end + 1);
    }

    // Handle alternation (|)
    if (strchr(pattern, '|')) {
        const char* alt_pos = strchr(pattern, '|');
        char left[1024], right[1024];

        // Split around '|'
        strncpy(left, pattern, alt_pos - pattern);
        left[alt_pos - pattern] = '\0';
        strcpy(right, alt_pos + 1);

        // Check both sides of the alternative
        return regex_match(text, left) || regex_match(text, right);
    }

    // Handle repetition (*) for the previous character
    if (*(pattern + 1) == '*') {
        return match_star(text, pattern + 2, *pattern);
    }

    // Handle '.' (any character) case
    if (*pattern == '.') {
        if (*text == '\0') return 0; // No match at the end of the string
        return regex_match(text + 1, pattern + 1);
    }

    // Direct character match
    if (*text == *pattern) {
        return regex_match(text + 1, pattern + 1);
    }

    // No match
    return 0;
}

// Function to search for the pattern in each line of a file
void search_in_file(const char* pattern, const char* filename) {
    FILE* file = fopen(filename, "r");
    if (!file) {
        printf("Error: Could not open file %s\n", filename);
        exit(1);
    }

    char line[1024];
    int line_number = 1;

    while (fgets(line, sizeof(line), file)) {
        line[strcspn(line, "\n")] = '\0'; // Remove newline character
        // Debug print to ensure we are reading lines properly
        printf("Checking line %d: %s\n", line_number, line);
        if (regex_match(line, pattern)) {
            printf("Match found on line %d: %s\n", line_number, line);
        }
        line_number++;
    }

    fclose(file);
}

int main(int argc, char* argv[]) {
    if (argc < 3) {
        printf("Usage: %s <filename> <pattern>\n", argv[0]);
        return 1;
    }

    const char* filename = argv[1];
    const char* pattern = argv[2];

    search_in_file(pattern, filename);

    return 0;
}

输入文件（input.txt）：

hello world
he*llo
abc123
a.b.c
alpha and omega
aaabbbccc
12345

我正在使用以下命令运行程序： daarkmp.exe 输入.txt“a*b” 我在输出中得到什么： 我添加了调试打印语句来跟踪正在读取的行和正在匹配的模式，但仍然没有输出。 我验证了我的输入文件格式正确且可访问。 有谁知道为什么我的模式匹配逻辑可能不起作用？在 C 语言的正则表达式实现中是否存在我应该检查的常见陷阱？

Answer 1

abc

中

abc123

第 3 行的匹配一开始似乎工作正常。前三个字符匹配，留下空模式不匹配

123

。代码

if (*pattern == '\0') return *text == '\0'; // End of pattern and text match

似乎是说空模式（或到目前为止所有内容都已匹配的模式）只能匹配空字符串。

将代码与常见的 RegEx 样式进行比较，代码似乎在模式的末尾放置了隐式的

$

（即字符串结尾）。我想知道它是否也可以工作，就好像在模式的开头有一个隐式的

^

（即字符串的开头）。