C語言經典正則表達式引擎實現：Kernighan & Pike 精簡版

Brian Kernighan 與 Rob Pike 在《軟件工程實踐》中呈現了一個極精簡的正則引擎，僅支援 .、*、^、$ 四種元字符，代碼不足 50 行卻涵蓋核心匹配邏輯。本文完整呈現並逐函數解析。

支援語法

完整源碼

#include <stdio.h>

int matchhere(char *, char *);
int matchstar(int c, char *regexp, char *text) {
    char *t;
    for (t = text; *t != '\0' && (*t == c || c == '.'); t++);
    do {
        if (matchhere(regexp, t)) return 1;
    } while (t-- > text);
    return 0;
}

int matchhere(char *regexp, char *text) {
    if (regexp[0] == '\0') return 1;
    if (regexp[1] == '*') return matchstar(regexp[0], regexp + 2, text);
    if (regexp[0] == '$' && regexp[1] == '\0') return *text == '\0';
    if (text[0] != '\0' && (regexp[0] == '.' || regexp[0] == text[0]))
        return matchhere(regexp + 1, text + 1);
    return 0;
}

int match(char *regexp, char *text) {
    if (regexp[0] == '^') return matchhere(regexp + 1, text);
    do {
        if (matchhere(regexp, text)) return 1;
    } while (*text++ != '\0');
    return 0;
}

int main() {
    char *regexp = ".*$";
    char *text = "123";
    if (match(regexp, text)) puts("ok");
    return 0;
}

函數職責拆解

match(regexp, text) — 入口函數

• 處理 ^ 錨點：若模式以 ^ 開頭，僅從文本開頭匹配
• 否則嘗試文本每個位置作為起點（do-while 循環）

matchhere(regexp, text) — 核心遞歸匹配

• 模式為空 → 匹配成功
• 下一字符為 * → 委派 matchstar
• 模式為 $ 且結尾 → 檢查文本是否也結尾
• 字符匹配（含 .） → 遞歸匹配剩餘
• 否則失敗

matchstar(c, regexp, text) — 星號處理

• 先向前掃描所有匹配 c 或 . 的字符
• 從最長匹配開始回溯（do-while(t-- > text)）
• 每個位置嘗試匹配剩餘模式
• 實現「貪婪匹配 + 回溯」語義

執行流程追蹤：match(".*$", "123")

1. match：模式無 ^，進入循環
2. matchhere(".*$", "123")
3. matchhere：見 .* → matchstar('.', "$", "123")
4. matchstar：掃描到結尾 t="\0"
5. 回溯嘗試：matchhere("$", "123") 失敗 → matchhere("$", "23") 失敗 → ... → matchhere("$", "") 成功
6. 返回 1，主程式印出 ok

擴展方向

• 加入 +（一次或多次）、?（零或一次）
• 加入字符類 [abc]、分組 (...)
• 編譯為 NFA/DFA 提升效能（現代引擎做法）
• 支援 UTF-8 多位元組字符

教學價值

此實現展示了遞歸下降 + 回溯的核心思想，代碼極簡卻完整，是學習正則引擎原理的最佳入門材料。