简介

正则表达式，是计算机科学史上闪闪发光的优秀理论：有好的理论，好的代码，好的程序，应用广泛。

70 年代末，正则表达式已经成为 unix 的关键特性，并且拥有大量以正则表达式为主要功能的优秀程序： ed, sed, grep, egrep, awk, lex。如今，正则表达式在程序设计中被广泛使用。

本文介绍正则表达式的理论和实现，以及我们如何使用它。

理论基础：计算理论的基石

正则表达式不仅仅是一种字符串处理工具，它在计算机科学理论（计算理论）中占据着核心地位。

乔姆斯基体系 (Chomsky Hierarchy)

在形式语言理论中，诺姆·乔姆斯基将语言分为四个层级。正则表达式描述的是正则语言 (Regular Language)，这是乔姆斯基体系中第 3 型语言，也是最简单、限制最强、但计算最高效的一类语言。

层级	语言类型	自动机模型	典型应用
0	递归可枚举语言	图灵机 (Turing Machine)	通用计算
1	上下文有关语言	线性有界自动机	自然语言处理
2	上下文无关语言	下推自动机 (Pushdown Automaton)	编程语言语法 (AST)
3	正则语言	有限自动机 (Finite Automaton)	词法分析, 文本搜索

为什么说它是“好的理论”？

一个优秀的理论通常具备：简洁性、表达力强、且计算上可控。正则表达式完美符合这些特征：

等价性 (Equivalence)：

正则表达式、非确定性有限自动机 (NFA) 和确定性有限自动机 (DFA) 三者在表达能力上是完全等价的。这意味着我们可以用人类易读的正则语法来写规则，然后自动转换为机器执行最高效的 DFA 代码。
封闭性 (Closure Properties)：

正则语言在并集、交集、补集、连接、闭包等运算下都是封闭的。这意味着你可以随意组合两个正则表达式，其结果依然是一个正则表达式，依然可以用有限自动机处理。
可判定性 (Decidability)：

对于正则语言，很多关键问题都是可判定的（有算法能在有限时间内给出 Yes/No）：
- 成员性：字符串 $s$ 是否符合规则 $R$？ (匹配问题)
- 空性：规则 $R$ 是否匹配不到任何字符串？
- 等价性：规则 $R_1$ 和 $R_2$ 是否描述了同一个集合？
相比之下，对于上下文无关语言（如编程语言语法），“等价性”就是不可判定的。对于图灵完备的系统，连“是否停机”都是不可判定的。
效率保证：

因为等价于 DFA，正则表达式的匹配可以在线性时间 $O(n)$ 内完成，且只需要常数空间的内存（不考虑输出捕获）。这使得它成为处理海量数据的理想选择。

正则表达式

正则表达式（Regular Expression）是用一个字符串来描述一个集合的规则。例如 a*b 描述了 “b”, “ab”, “aab”, “aaab”… 这样一个无穷集合。

在计算机科学中，正则表达式等价于有限自动机（Finite Automaton）。任何一个正则表达式都可以转换为一个等价的非确定性有限自动机（NFA），而 NFA 又可以转换为确定性有限自动机（DFA）。

基本运算

正则表达式有三种基本的运算：

连接 (Concatenation): ab 表示先匹配 a 再匹配 b。
并集 (Union): a|b 表示匹配 a 或者 b。
闭包 (Kleene Star): a* 表示匹配 0 个或多个 a。

其它常见的符号如 +, ?, [] 都可以由这三种基本运算推导出来：

a+ 等价于 aa*
a? 等价于 a|ε (ε 表示空串)

常用语法速查 (PCRE)

虽然理论上只需要连接、并集和闭包，但在实际工程中（如 Perl, Python, Java, Go, JavaScript），我们通常使用更丰富的语法（PCRE 标准或其变体）来简化编写。

类别	符号	说明	示例
字符类	`.`	匹配除换行符外的任意字符	`a.c` 匹配 “abc”, “a@c”
	`[abc]`	字符集合，匹配方括号内的任意字符	`[a-z]` 匹配小写字母
	`[^abc]`	否定字符集合	`[^0-9]` 匹配非数字
	`\d` / `\D`	数字 / 非数字	等价于 `[0-9]`
	`\w` / `\W`	单词字符 (字母数字下划线) / 非单词字符	`\w+` 匹配变量名
	`\s` / `\S`	空白字符 (空格, Tab, 换行) / 非空白	`\s+` 匹配缩进
量词	`*`	0 次或多次	`a*`
	`+`	1 次或多次	`a+`
	`?`	0 次或 1 次	`https?`
	`{n}`	恰好 n 次	`\d{4}`
	`{n,}`	至少 n 次	`\d{2,}`
	`{n,m}`	n 到 m 次	`\d{4,6}`
边界	`^`	行首	`^Start`
	`$`	行尾	`End$`
	`\b`	单词边界	`\bcat\b` 匹配 “cat” 但不匹配 “category”
分组	`(...)`	捕获组，可以用 `\1` 引用	`(ab)+`
	`(?:...)`	非捕获组，只分组不捕获	`(?:ab)+`
	`\|`	或 (Alternation)	`cat\|dog`
转义	`\`	转义特殊字符	`\.` 匹配点号本身

简单组合示例

正则表达式	说明	匹配示例
`^\s*$`	空行 (包含只有空格的行)	`""`, `" "`, `"\t"`
`\d{4}-\d{2}-\d{2}`	简单日期格式	`2023-12-31`
`[a-zA-Z_]\w*`	变量名 (字母/下划线开头)	`my_var`, `_init`, `i`
`\b(int\|void)\b`	关键字 (使用单词边界)	`int` (不匹配 `print`)

NFA 构建 (Thompson 算法)

Ken Thompson 在 1968 年提出了一种算法，可以将正则表达式直接转换为 NFA。这个算法非常直观，它基于对上述三种基本运算的递归构造。

1. 单个字符

对于单个字符 a，构造一个简单的 NFA：

2. 连接 (Concatenation) `st`

对于正则表达式 st，我们将 s 的 NFA 的结束状态与 t 的 NFA 的开始状态合并（或者通过 ε 边连接）。

3. 并集 (Union) `s|t`

对于 s|t，我们创建一个新的开始状态和结束状态。

新开始状态通过 ε 边连接到 s 和 t 的开始状态。
s 和 t 的结束状态通过 ε 边连接到新结束状态。

4. 闭包 (Kleene Star) `s*`

对于 s*，我们需要支持重复匹配和 0 次匹配。

重复：s 的结束状态有一条 ε 边回到 s 的开始状态。
0 次：新开始状态有一条 ε 边直接跳到新结束状态。

NFA 模拟执行

构建好 NFA 后，如何用它来匹配字符串呢？ NFA 的特点是，在某一时刻，它可能处于多个状态。

例如对于 a|b，初始时通过 ε 边，自动机同时处于 s 的开始状态和 t 的开始状态。当我们读入字符 ‘a’ 时，所有处于活动状态的节点，如果有一条 ‘a’ 的边，就转移到下一个状态。

算法流程：

初始集合 $S = \{start\_node\}$。
计算 $S$ 的 ε-闭包 (Epsilon Closure)：即从 $S$ 中的状态出发，只走 ε 边能到达的所有状态的集合。
读入下一个字符 $c$。
对于 $S$ 中的每个状态，如果能通过 $c$ 转移，则将目标状态加入新集合 $Next$。
令 $S = \text{epsilon\_closure}(Next)$。
重复步骤 3-5，直到字符串读完。
如果最终集合 $S$ 中包含结束状态，则匹配成功。

代码实现 (C++)

下面是一个简单的正则引擎实现，支持 |, *, () 和连接。

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <set>

using namespace std;

// NFA 状态节点
struct State {
    int id;
    int c; // 匹配字符，256 表示 split (epsilon), 257 表示 match
    State *out;
    State *out1;
    int lastlist; // 用于防止搜索时重复访问

    State(int c, State *out, State *out1) : c(c), out(out), out1(out1), lastlist(0) {
        static int id_cnt = 0;
        id = ++id_cnt;
    }
};

// NFA 片段
struct Frag {
    State *start;
    vector<State**> out; // 未连接的输出指针列表
};

// 辅助函数：创建状态
State* state(int c, State *out, State *out1) {
    return new State(c, out, out1);
}

// 辅助函数：连接指针列表
void patch(vector<State**> &l, State *s) {
    for (auto p : l) {
        *p = s;
    }
}

// 辅助函数：合并指针列表
vector<State**> append(const vector<State**> &l1, const vector<State**> &l2) {
    vector<State**> res = l1;
    res.insert(res.end(), l2.begin(), l2.end());
    return res;
}

// 将中缀正则转后缀 (Shunting-yard 简化版)
// 这里为了演示简单，假设输入已经是预处理好的，或者手动构造 NFA
// 实际实现通常需要一个 Parser

// 我们直接实现一个简单的后缀表达式构建器
Frag post2nfa(string postfix) {
    stack<Frag> stack;
    for (char c : postfix) {
        switch (c) {
        case '.': { // 连接
            Frag e2 = stack.top(); stack.pop();
            Frag e1 = stack.top(); stack.pop();
            patch(e1.out, e2.start);
            stack.push({e1.start, e2.out});
            break;
        }
        case '|': { // 并集
            Frag e2 = stack.top(); stack.pop();
            Frag e1 = stack.top(); stack.pop();
            State *s = state(256, e1.start, e2.start);
            stack.push({s, append(e1.out, e2.out)});
            break;
        }
        case '*': { // 闭包
            Frag e = stack.top(); stack.pop();
            State *s = state(256, e.start, nullptr); // split
            patch(e.out, s);
            stack.push({s, {&s->out1}});
            break;
        }
        default: { // 字符
            State *s = state(c, nullptr, nullptr);
            stack.push({s, {&s->out}});
            break;
        }
        }
    }
    Frag e = stack.top(); stack.pop();
    State *match = state(257, nullptr, nullptr);
    patch(e.out, match);
    return e;
}

// NFA 模拟
int listid = 0;
void addstate(vector<State*> &l, State *s) {
    if (s == nullptr || s->lastlist == listid) return;
    s->lastlist = listid;
    if (s->c == 256) { // split (epsilon)
        addstate(l, s->out);
        addstate(l, s->out1);
    } else {
        l.push_back(s);
    }
}

bool match(State *start, string s) {
    vector<State*> cList, nList;
    listid++;
    addstate(cList, start);
    
    for (char c : s) {
        listid++;
        nList.clear();
        for (State *st : cList) {
            if (st->c == c) {
                addstate(nList, st->out);
            }
        }
        cList = nList;
    }
    
    for (State *st : cList) {
        if (st->c == 257) return true;
    }
    return false;
}

int main() {
    // 构造 a(b|c)*d
    // 后缀表达式: abc|*.d.
    string postfix = "abc|*.d.";
    Frag nfa = post2nfa(postfix);
    
    cout << "Match abbbd: " << match(nfa.start, "abbbd") << endl;
    cout << "Match acd: " << match(nfa.start, "acd") << endl;
    cout << "Match ad: " << match(nfa.start, "ad") << endl;
    cout << "Match abd: " << match(nfa.start, "abd") << endl;
    cout << "Match abx: " << match(nfa.start, "abx") << endl;
    
    return 0;
}

NFA 转 DFA (子集构造法)

虽然 NFA 可以直接用于匹配，但它在运行时需要维护一个状态集合，并且频繁计算 $\epsilon$-闭包，这会带来性能开销。

如果我们能在编译阶段就把这些“状态集合”预先计算好，生成一个新的自动机，那么运行时只需要查表跳转，速度将大幅提升。这个过程就是 NFA 到 DFA 的转换，通常使用 子集构造法 (Subset Construction)。

原理：状态集合即新状态

DFA 的每一个状态，实际上对应的是 NFA 的一个状态集合。因为 NFA 在某一时刻可能处于 $\{s_1, s_2, s_3\}$ 中的任意一个状态，对于 DFA 来说，$\{s_1, s_2, s_3\}$ 这一整个集合就是一个确定的状态。

算法流程：

初始状态：计算 NFA 起始节点的 $\epsilon$-闭包，作为 DFA 的起始状态 $A$。
状态转移：对于 DFA 的每一个状态（即 NFA 的状态集合 $S$）和每一个输入字符 $c$：
- 找出 $S$ 中所有节点经过 $c$ 能到达的 NFA 节点集合 $T$。
- 计算 $T$ 的 $\epsilon$-闭包，得到新的集合 $U$。
- 如果 $U$ 是一个新的集合，就把它标记为 DFA 的一个新状态。
- 在 DFA 中添加一条从 $S$ 到 $U$ 的边，标记为 $c$。
重复：直到没有新的 DFA 状态产生。
结束状态：如果一个 DFA 状态代表的集合中包含 NFA 的结束节点，则该 DFA 状态为结束状态。

为什么 DFA 更快？

消除运行时计算：NFA 匹配时，每读一个字符都要进行集合运算（并集、闭包）。DFA 匹配时，这些运算在编译期已经做完了。
O(1) 状态转移：DFA 的运行逻辑极其简单：current_state = transition_table[current_state][char]。这只是一个简单的数组索引操作。
线性时间复杂度：
- NFA 匹配复杂度：$O(m \times n)$，其中 $m$ 是正则长度（状态数），$n$ 是文本长度。
- DFA 匹配复杂度：$O(n)$。速度与正则表达式的复杂程度无关！

加速效果与实例

加速多少？

在简单正则上，DFA 可能比 NFA 快 2-5 倍。但在复杂正则（特别是带有大量分支和循环）上，NFA 的状态集合会很大，DFA 的优势可以是 10 倍甚至 100 倍。更重要的是，DFA 保证了最坏情况下的性能，不会因为构造了恶意的正则表达式而导致 ReDoS（正则表达式拒绝服务攻击）。

典型实例：

grep / awk / lex：这些经典的 Unix 文本处理工具默认使用 DFA 引擎，因此处理海量日志时速度极快。
RE2 (Google)：Go 语言的标准正则库。它坚持使用自动机理论（DFA/NFA 混合），放弃了反向引用等特性，换取了绝对的 $O(n)$ 性能保证，被广泛用于高性能服务器。
Rust regex：同样基于自动机，大量使用了 DFA 优化（如 Lazy DFA）。
Hyperscan (Intel)：高性能正则匹配库，底层大量使用 DFA 和 SIMD 指令加速，用于网络包过滤（防火墙、IDS）。

DFA 完整代码实现

下面是一个基于子集构造法的 DFA 编译器实现。它将 NFA 转换为 DFA 状态转移表。

#include <map>
#include <algorithm>

// DFA 状态
struct DState {
    map<int, DState*> next; // 转移表: 字符 -> 下一个状态
    bool is_match;          // 是否为接受状态
    
    DState() : is_match(false) {}
};

// 辅助：比较两个 NFA 状态集合是否相同
// 这里的 set<State*> 是有序的，可以直接比较
typedef set<State*> StateSet;

// 全局缓存：NFA 状态集合 -> DFA 状态的映射
map<StateSet, DState*> dstate_cache;

// 计算 NFA 状态集合的 epsilon 闭包
StateSet epsilon_closure(const StateSet& start_states) {
    StateSet closure = start_states;
    stack<State*> worklist;
    for (State* s : start_states) worklist.push(s);
    
    while (!worklist.empty()) {
        State* s = worklist.top(); worklist.pop();
        
        // 检查 s 的 epsilon 边 (c == 256)
        if (s->c == 256) {
            if (s->out && closure.find(s->out) == closure.end()) {
                closure.insert(s->out);
                worklist.push(s->out);
            }
            if (s->out1 && closure.find(s->out1) == closure.end()) {
                closure.insert(s->out1);
                worklist.push(s->out1);
            }
        }
    }
    return closure;
}

// 获取或创建 DFA 状态
DState* get_dstate(StateSet states) {
    // 1. 计算闭包
    states = epsilon_closure(states);
    
    // 2. 查表，如果已存在则返回
    if (dstate_cache.count(states)) {
        return dstate_cache[states];
    }
    
    // 3. 创建新状态
    DState* d = new DState();
    dstate_cache[states] = d;
    
    // 检查是否包含 NFA 的接受状态 (257)
    for (State* s : states) {
        if (s->c == 257) {
            d->is_match = true;
            break;
        }
    }
    return d;
}

// 编译 NFA -> DFA
DState* compile_dfa(State* nfa_start) {
    dstate_cache.clear();
    
    // 初始状态
    StateSet start_set;
    start_set.insert(nfa_start);
    DState* dfa_start = get_dstate(start_set);
    
    // 待处理的 DFA 状态队列
    stack<DState*> worklist;
    worklist.push(dfa_start);
    
    // 已处理过的 DFA 状态集合 (避免重复处理)
    set<DState*> visited;
    visited.insert(dfa_start);
    
    while (!worklist.empty()) {
        DState* d = worklist.top(); worklist.pop();
        
        // 反向查找 d 对应的 NFA 状态集合 (为了演示简单，这里需要从 cache 中反查，
        // 实际实现中 DState 结构体里应该存一下对应的 StateSet)
        StateSet current_nfa_states;
        for (auto& pair : dstate_cache) {
            if (pair.second == d) {
                current_nfa_states = pair.first;
                break;
            }
        }
        
        // 找出所有可能的转移字符
        // 遍历当前集合中所有 NFA 节点，看它们能接受什么字符
        map<int, StateSet> transitions;
        for (State* s : current_nfa_states) {
            if (s->c < 256) { // 实际字符
                transitions[s->c].insert(s->out);
            }
        }
        
        // 对每个字符构建 DFA 边
        for (auto& pair : transitions) {
            int char_code = pair.first;
            StateSet next_nfa_states = pair.second;
            
            DState* next_dstate = get_dstate(next_nfa_states);
            d->next[char_code] = next_dstate;
            
            if (visited.find(next_dstate) == visited.end()) {
                visited.insert(next_dstate);
                worklist.push(next_dstate);
            }
        }
    }
    
    return dfa_start;
}

// DFA 匹配执行
bool dfa_match(DState* start, string s) {
    DState* curr = start;
    for (char c : s) {
        if (curr->next.count(c)) {
            curr = curr->next[c];
        } else {
            return false; // 无路可走，匹配失败
        }
    }
    return curr->is_match;
}

int main_dfa() {
    // 构造 a(b|c)*d
    string postfix = "abc|*.d.";
    Frag nfa = post2nfa(postfix);
    
    // 编译
    DState* dfa = compile_dfa(nfa.start);
    
    // 执行
    cout << "DFA Match abbbd: " << dfa_match(dfa, "abbbd") << endl;
    cout << "DFA Match acd: " << dfa_match(dfa, "acd") << endl;
    cout << "DFA Match ad: " << dfa_match(dfa, "ad") << endl;
    
    return 0;
}

DFA 与 NFA 的对比

特性	NFA	DFA
构建速度	快 $O(m)$	慢 $O(2^m)$ (最坏情况)
匹配速度	较慢 $O(mn)$	快 $O(n)$
内存占用	小	可能非常大

NFA 引擎：Perl, Python, Java, Ruby 等大多数语言的正则库。支持反向引用等高级特性，但可能出现回溯导致的性能问题（ReDoS）。
DFA 引擎：awk, egrep, lex。速度极快，但不支持反向引用等特性。

Go 语言的 regexp 库使用的是 RE2 算法，它是一种混合方法，保证了 $O(n)$ 的线性时间复杂度，避免了回溯爆炸。

RE2 算法与高性能正则

在工业界，正则表达式引擎的性能至关重要。传统的正则引擎（如 PCRE, Python re, Java Pattern）大多基于回溯（Backtracking）算法。虽然支持丰富的功能（如反向引用），但在某些情况下会出现指数级的时间复杂度，导致 ReDoS（正则表达式拒绝服务攻击）。

Google 的 RE2 算法正是为了解决这个问题而诞生的。它由 Russ Cox 开发，被 Go 语言标准库采用。

回溯引擎的缺陷 (The Problem)

回溯引擎本质上是一个深度优先搜索（DFS）。考虑正则表达式 a?a?a?aaa 匹配字符串 aaaaa。如果是 (a?){n}a{n} 匹配 a^{n}，回溯引擎的复杂度是 $O(2^n)$。

例如，对于正则 (x+x+)+y 匹配 xxxxxxxxxxxx... (没有 y)，回溯引擎会尝试所有的分割组合，导致死循环般的卡顿。

RE2 的原理 (The Solution)

RE2 的核心原则是：保证线性时间复杂度 $O(n)$，其中 $n$ 是输入文本的长度。它放弃了对“反向引用 (Backreferences)”和“零宽断言 (Lookaround)”等无法用有限自动机高效实现的功能的支持。

RE2 的实现策略是混合的：

预编译：将正则解析为 NFA。
执行策略：
- Bit-state hashing: 对于小模式串，使用位图记录状态。
- NFA Simulation: 使用 Thompson NFA 模拟（即前文提到的维护当前状态集合），复杂度 $O(nm)$。
- Lazy DFA: 这是 RE2 最快的部分。它不预先生成整个 DFA（因为状态可能爆炸），而是在匹配过程中按需生成 DFA 状态，并缓存起来。
- One-pass NFA: 对于需要提取子匹配（Capturing Groups）的情况，RE2 无法简单使用 DFA，而是使用一种优化的 NFA 模拟，同时记录路径信息。

Lazy DFA (惰性 DFA)

全量构建 DFA 可能会导致状态数量指数级膨胀（$2^m$）。 RE2 维护一个有限大小的 DFA 状态缓存。

匹配开始时，缓存为空。
每读入一个字符，计算目标状态。
如果目标状态已经在缓存中，直接跳转。
如果不在，利用 NFA 计算出目标状态集合，存入缓存。
如果缓存满了，直接清空或丢弃部分，或者回退到 NFA 模拟。

这种方式结合了 DFA 的速度（大部分时间查表 $O(1)$）和 NFA 的空间安全性。

核心代码逻辑演示

RE2 的实际代码非常复杂（C++），包含内存管理和各种优化。这里展示其核心的 Lock-step NFA Simulation 思想，这是它区别于回溯引擎的关键。

// 这是一个简化的 Go 语言描述，展示 RE2 如何避免回溯
// 假设我们已经有了 NFA 图

type State struct {
    char int // 匹配字符
    out  *State
    out1 *State // 用于 split
}

func Match(start *State, text string) bool {
    // 当前活跃的状态集合
    // 使用 map 或 dense array 去重
    clist := make(map[*State]bool)
    nlist := make(map[*State]bool)
    
    addState(clist, start) // 初始状态及其 epsilon 闭包
    
    for _, char := range text {
        // 这一步是关键：同时推演所有可能的状态
        // 而不是像回溯引擎那样一条路走到黑
        nlist = make(map[*State]bool)
        
        for s := range clist {
            if s.char == char {
                addState(nlist, s.out)
            }
        }
        
        clist = nlist
        if len(clist) == 0 {
            return false // 提前结束
        }
    }
    
    // 检查是否包含接受状态
    for s := range clist {
        if s.char == MatchState {
            return true
        }
    }
    return false
}

// 辅助：添加状态并处理 epsilon 转换
func addState(l map[*State]bool, s *State) {
    if s == nil || l[s] {
        return
    }
    if s.char == Split { // Epsilon
        addState(l, s.out)
        addState(l, s.out1)
        return
    }
    l[s] = true
}

总结

特性	PCRE / Python / Java	RE2 / Go / Rust
实现原理	递归回溯 (Backtracking)	有限自动机 (Automata)
时间复杂度	最坏 $O(2^n)$ (指数级)	保证 $O(n)$ (线性)
功能支持	强 (反向引用, 复杂断言)	中 (不支持反向引用)
安全性	易受 ReDoS 攻击	安全
适用场景	文本编辑, 脚本处理	高并发服务, 安全网关

常见正则表达式实例

理解了原理之后，我们来看几个实际开发中常用的正则表达式例子。

1. 电子邮箱 (Email)

^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$

^ 和 $: 匹配整个字符串的开始和结束。
[a-zA-Z0-9._%+-]+: 用户名部分，允许字母、数字和一些特殊符号，至少出现一次。
@: 必须包含 @ 符号。
[a-zA-Z0-9.-]+: 域名主体。
\.: 匹配点号。
[a-zA-Z]{2,}: 顶级域名（如 com, org, cn），至少 2 个字母。

2. IPv4 地址

^(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)$

这是一个比较严谨的匹配，考虑了数字范围 0-255。

(?:...): 非捕获组，只分组不捕获。
25[0-5]: 匹配 250-255。
2[0-4][0-9]: 匹配 200-249。
[01]?[0-9][0-9]?: 匹配 0-199 (包括 0-9, 00-99)。
{3}: 前面三段加点号重复 3 次。

3. 日期 (YYYY-MM-DD)

^\d{4}-(?:0[1-9]|1[0-2])-(?:0[1-9]|[12]\d|3[01])$

\d{4}: 4 位年份。
0[1-9]|1[0-2]: 月份 01-12。
0[1-9]|[12]\d|3[01]: 日期 01-31。

4. 手机号码 (中国大陆)

^1[3-9]\d{9}$

1: 以 1 开头。
[3-9]: 第二位通常是 3-9。
\d{9}: 后面跟着 9 位数字。

5. 简单的 HTML 标签

<([a-z]+)([^<]+)*(?:>(.*)<\/\1>|\s+\/>)

([a-z]+): 捕获标签名 (如 div, span)。
(?:>(.*)<\/\1>|\s+\/>): 匹配闭合标签 >...</div> 或自闭合标签 />。
\1: 反向引用第一个捕获组（标签名），确保首尾标签一致。 (注意：RE2 等纯自动机引擎不支持 \1 反向引用，这个例子仅适用于支持回溯的引擎)

正则表达式的能力边界

虽然正则表达式非常强大，但它并不是万能的。在计算理论中，正则表达式对应的是有限自动机 (Finite Automaton)。顾名思义，它的核心限制在于“有限”的内存（状态）。

哪些可以匹配？ (正则语言)

只要一个问题只需要有限的内存来记录当前的状态，它通常就可以用正则表达式解决。

固定模式：如关键词查找 hello。
有限的重复：如 a{5} (5个a)。
不确定的重复：如 a* (任意个a)。
有限的选择：如 a|b。
有限长度的上下文：如“后面跟着数字的字母”。

哪些不能匹配？ (非正则语言)

如果一个问题需要无限的内存（或者说，内存的大小与输入长度相关），那么它就超出了正则表达式的能力范围。

最典型的例子是：任意深度的嵌套结构。

配对的括号：$L = \{ a^n b^n \mid n \ge 1 \}$，即 ab, aabb, aaabbb…
- 为了匹配这个，机器需要“记住”读了多少个 a，以便检查后面是否有相同数量的 b。
- 因为 $n$ 可以是无穷大，有限自动机没有足够的“状态”来计数。
- 注：这是上下文无关语言 (Context-Free Language) 的范畴，需要下推自动机 (Pushdown Automaton, 带栈的自动机)。
回文串：$L = \{ w w^R \mid w \in \{a,b\}^* \}$，如 abba, baab。
- 同样需要记忆前半段的内容，长度不限，有限状态机无法做到。
算术表达式：如 ((1+2)*3)，因为涉及任意深度的括号嵌套。
HTML/XML 解析：虽然可以用正则匹配简单的 <div>...</div>，但无法处理嵌套的 <div><div>...</div></div>。

判断标准：泵引理 (Pumping Lemma)

如何从理论上严格证明一个语言不是正则语言？我们使用泵引理。

定理描述：

如果语言 $L$ 是正则语言，那么存在一个常数 $p$（泵长度），使得 $L$ 中任何长度至少为 $p$ 的字符串 $s$ 都可以被分割成三部分 $s = xyz$，满足：

$|y| > 0$ （中间部分不为空）
$|xy| \le p$ （前两部分长度不超过 $p$）
对于任意 $k \ge 0$，字符串 $xy^k z$ 仍属于 $L$ （中间部分 $y$ 可以重复任意次——即“泵出”——结果仍在语言中）。

直观理解 (鸽巢原理)：

想象一个有限自动机（DFA）有 $p$ 个状态。如果你给它一个长度为 $p$（或更长）的字符串，它在处理过程中必须经过 $p+1$ 次状态转移（包括起始状态）。根据鸽巢原理，既然只有 $p$ 个状态，但走了 $p+1$ 步，那么必然至少有一个状态被访问了两次。

这就意味着路径中出现了一个环 (Loop)。

我们可以把字符串 $s$ 的路径分为三段：

$x$：从起始状态走到第一次进入该重复状态的路径。
$y$：从该重复状态出发，转了一圈又回到该状态的路径（即“环”）。
$z$：从该重复状态继续走到结束状态的路径。

因为 $y$ 是一个环，我们可以选择：

不走这个环 ($k=0$, 也就是 $xz$)
走一次 ($k=1$, 也就是 $xyz$)
走多次 ($k=2, 3...$, 也就是 $xyyz, xyyyz...$)

无论走多少次，自动机最终都会到达同一个接受状态。这就是“泵出”的含义。

证明实例：$L = \{ a^n b^n \}$ 不是正则语言

为了证明 $L = \{ a^n b^n \mid n \ge 0 \}$（即 $n$ 个 $a$ 后面跟着 $n$ 个 $b$）不是正则语言，我们使用反证法。

1. 假设与取值

步骤：假设 $L$ 是正则语言。根据泵引理，必然存在一个泵长度 $p$。

解释：这就好比说，如果这个语言能被一个有限状态机识别，那么这个机器一定有 $p$ 个状态。

步骤：我们构造一个特定的字符串 $s = a^p b^p$。

解释：这个字符串显然属于 $L$（$a$ 和 $b$ 数量相等），而且它的长度 $2p$ 肯定大于 $p$。我们选这个字符串是为了“刁难”这个自动机。

2. 分割字符串

步骤：根据引理，字符串 $s$ 必然可以被分割成三部分 $s = xyz$，并且满足两个关键条件： 1. $|xy| \le p$ （前两部分长度不超过 $p$） 2. $|y| > 0$ （中间部分 $y$ 不能为空）

解释：我们的字符串 $s$ 长这样： \[ \underbrace{a a \dots a}_{p \text{个}} \underbrace{b b \dots b}_{p \text{个}} \]

因为限制了 $|xy| \le p$，这意味着 $x$和 $y$ 完全落在前 $p$ 个字符的范围内。而前 $p$ 个字符全都是 $a$。结论：$y$ 必然完全由 $a$ 组成。

3. “泵出”产生矛盾 (Pumping)

步骤：根据引理，如果我们把中间部分 $y$ 重复一次（即 $xy^2z$），得到的新字符串也应该属于 $L$。

具体演示：设 $y$ 的长度为 $k$（$k \ge 1$）。因为 $y$ 全是 $a$，所以 $y = a^k$。

原字符串 $s = xyz$：包含 $p$ 个 $a$ 和 $p$ 个 $b$。
泵出后的字符串 $s' = x y y z$：
- 我们在中间多插入了一个 $y$。
- 因为 $y$ 全是 $a$，所以 $a$ 的数量增加了 $k$ 个。
- $b$ 的部分完全在 $z$ 里，没有变动。
- 结果：$s'$ 包含 $p+k$ 个 $a$ 和 $p$ 个 $b$。

4. 结论

步骤：检查 $s'$ 是否属于 $L$。

解释： $L$ 的定义要求 $a$ 和 $b$ 的数量必须严格相等。但在 $s'$ 中，$a$ 的数量 ($p+k$) 显然不等于 $b$ 的数量 ($p$)，因为 $k \ge 1$。所以 $s' \notin L$。

这与泵引理的结论（$s'$ 必须属于 $L$）矛盾！因此，最开始的假设（$L$ 是正则语言）是错误的。

💡 举个具体的数字例子

如果上面的符号太抽象，我们设泵长度 $p = 3$。

构造字符串：选 $s = a^3 b^3 = \text{aaabbb}$。
尝试分割：我们要把 $\text{aaabbb}$ 分成 $x, y, z$，且 $|xy| \le 3$，$|y| \ge 1$。因为 $|xy| \le 3$，所以 $x$ and $y$ 只能在前 3 个字符 aaa 里面切。

情况 A：$x=\epsilon, y=a, z=aabbb$
- $y$ 是 a。
- 泵出（重复 $y$）：$x \cdot y \cdot y \cdot z = \epsilon \cdot a \cdot a \cdot aabbb = \text{aaaabbb}$。
- 结果：4 个 $a$，3 个 $b$。不匹配！
情况 B：$x=a, y=aa, z=bbb$
- $y$ 是 aa。
- 泵出：$x \cdot y \cdot y \cdot z = a \cdot aa \cdot aa \cdot bbb = \text{aaaaabbb}$。
- 结果：5 个 $a$，3 个 $b$。不匹配！

无论怎么切，只要 $y$ 在前 $p$ 个字符里（全是 $a$），重复 $y$ 就会导致 $a$ 变多，$b$ 不变，从而破坏数量平衡。这就是为什么有限自动机无法识别 $a^n b^n$ —— 它数不清 $a$ 有多少个，也就无法确保后面有相同数量的 $b$。

结论

能用正则：词法分析（Token识别）、简单的格式校验（邮箱、日期）、扁平的文本搜索。
不能用正则：语法分析（解析代码结构）、处理嵌套括号、解析 HTML/XML/JSON。

对于嵌套结构，请使用解析器 (Parser)，不要试图用正则表达式去“强行”匹配。

特性	NFA	DFA
构建速度	快 \(O(m)\)	慢 \(O(2^m)\) (最坏情况)
匹配速度	较慢 \(O(mn)\)	快 \(O(n)\)
内存占用	小	可能非常大

目录

简介