Pattern / Matcher 正则表达式引擎源码
概述
java.util.regex 是 Java 自带的正则引擎，由 Pattern（编译后的模式）与 Matcher（对具体输入执行匹配的状态机）两部分组成。Pattern 把正则字符串编译成一棵 Node 语法树，Matcher 在这棵树上做带回溯的递归匹配。
与使用 DFA（确定性有限自动机）的引擎（如 RE2）不同，Java 采用回溯型 NFA 引擎：支持反向引用、环视等 DFA 无法表达的特性，但存在最坏情况下指数级回溯的风险。
本文基于 OpenJDK 21 源码，从 Pattern.compile 的编译流程开始，依次拆解内部解析器、Node 模式树、Matcher 的匹配入口与捕获组，最后深入到 Curly / Ques / Branch 的回溯实现与 GroupRef 反向引用。
核心源码解析
① Pattern.compile(String regex) 的编译流程
java
public static Pattern compile(String regex) {
return new Pattern(regex, 0); // 默认无标志位
}
private Pattern(String p, int f) {
pattern = p;
flags = f;
if ((flags & UNICODE_CASE) != 0) // 大小写不敏感隐含 Unicode 字符类
flags |= UNICODE_CHARACTER_CLASS;
compiling = true; // 进入编译态
// ① 解析正则 → 构建 Node 树
// ② normalize() 做节点合并优化（如相邻 Slice 合并）
// ③ 预计算 capturingGroupCount / localCount
compiling = false;
compiled = true;
}编译期主要动作：
pattern()解析：调用包内pattern()方法从头解析正则字符串，返回根节点root。normalize()优化：合并相邻的字符节点为单个Slice、把可压缩的CharProperty预编译为位图（BmpCharProperty用 256 位布尔数组BitSet快速判断字符命中），减少匹配期的节点数量与判断成本。- 捕获组计数：解析过程中统计
capturingGroupCount（(开括号数量）与localCount（命名组局部编号），Matcher据此分配groups数组。
编译是一次性的，编译结果（Node 树）可被多个 Matcher 共享，因此「一次 compile、多次 matcher」是官方推荐用法。
② Pattern 内部的正则解析器
解析器由 Pattern 内部的若干游标字段驱动：
java
// Pattern 内部解析状态
private int cursor; // 当前解析位置（游标）
private Node curLocal; // 当前"局部变量"（用于命名组/引用编号）
private int capturingGroupCount; // 已遇到的捕获组数量
private int groupCount; // 总体组数量（含非捕获组）解析采用「读一个字符、构造一个节点」的手写递归下降：
peek()/read()/next()/accept(char)：游标操作。next()读取当前字符并前进，accept(ch)判断下一个字符是否为期望值（用于识别*、+、?等后缀符号）。expr()：处理|交替，收集每个分支构建Branch节点。sequence()：处理一段连续片段，把相邻字符/子表达式按序链接成链，构造Slice。atom()：解析一个原子——普通字符、.、字符类[...]、\d等预定义类（生成CharProperty）、(...)分组（压入GroupHead）、\1反向引用（生成GroupRef）。piece()：在原子之后尝试读取量词后缀*、+、?、{n,m}，构造Curly/Ques/Plus等节点。
每个解析方法返回一个 Node，子表达式通过 Node.next 指针串成链，最终 top = expr(...) 作为树根。
③ Pattern 的 Node 模式树
Node 是所有匹配节点的抽象基类，核心方法是递归匹配入口：
java
abstract static class Node {
Node next = null; // 后继节点（链式结构）
abstract boolean match(Matcher matcher, CharSequence seq, int[] groups);
}一个典型的模式 ^(\w+)-(\d+)$ 编译后的树形结构：
Start → GroupHead(1) → Slice(\w+) → GroupTail(1) → '-'(Slice)
→ GroupHead(2) → Slice(\d+) → GroupTail(2) → End主要节点类型：
| 节点 | 对应语法 | 职责 |
|---|---|---|
Start / End | ^ / $ | 位置锚定：匹配前校验 seq.isAtStart() / seq.isAtEnd() |
GroupHead / GroupTail | (...) | 捕获组：匹配成功时把起止位置写入 groups 数组 |
Slice | 连续字符 | 逐字符比较一段定长文本 |
CharProperty / BmpCharProperty | .、\d、[...] | 单个字符的谓词判断 |
Curly | *、+、{n,m} | 量词：贪婪 / 懒惰 / 占有三种模式 |
Ques | ? | 0 或 1 次匹配 |
Branch | | | 交替：依次尝试每个分支 |
GroupRef | \1 | 反向引用：与捕获组内容比较 |
Node.next 构成单链表，match 返回 false 时由上层节点决定回溯（尝试其他路径）还是失败。
④ Pattern.split(CharSequence input) 的切分实现
java
public String[] split(CharSequence input, int limit) {
int index = 0; // 当前已切分位置
boolean matchLimited = limit > 0;
ArrayList<String> matchList = new ArrayList<>();
Matcher m = matcher(input); // 复用编译好的 Pattern
while (m.find()) { // 不断寻找下一个匹配
if (!matchLimited || matchList.size() < limit - 1) {
if (index == 0 && index == m.start() && m.start() == m.end()) {
continue; // 忽略开头的空匹配
}
matchList.add(input.subSequence(index, m.start()).toString());
index = m.end(); // 推进分割点
} else if (matchList.size() == limit - 1) {
matchList.add(input.subSequence(index, input.length()).toString());
index = m.end();
}
}
if (index == 0) // 无任何匹配 → 整个字符串
return new String[] { input.toString() };
// 追加最后一段（limit 语义下的尾部处理）
if (!matchLimited || matchList.size() < limit)
matchList.add(input.subSequence(index, input.length()).toString());
int resultSize = matchList.size();
if (limit == 0) { // limit=0 丢弃末尾空串
while (resultSize > 0 && matchList.get(resultSize - 1).equals(""))
resultSize--;
}
return matchList.subList(0, resultSize).toArray(EMPTY_STRING_ARRAY);
}- 基于
Matcher.find()：split本质是"把匹配位置当作分隔符"的循环切分，subSequence(index, m.start())截取每段。 limit三语义：limit > 0至多切limit段；limit == 0丢弃尾部空串（默认行为）；limit < 0保留全部空串。- 分隔符为空匹配（如按零宽位置切分）时，
split会跳过开头的空匹配并处理相邻情况，避免产出无意义的空段。
⑤ Matcher.matches() 的全局匹配
java
public boolean matches() {
return match(from, 0, ENDANCHOR); // 锚定开头（from=0）+ 锚定末尾（ENDANCHOR）
}
public boolean lookingAt() {
return match(from, 0, ANCHORIAL); // 只锚定开头，不要求到末尾
}match(int from, int anchor, int mode) 是匹配的核心入口：
java
boolean match(int from, int anchor, int mode) {
this.hitEnd = false;
this.requireEnd = false;
from = from < 0 ? 0 : from;
this.first = from; // 记录本次匹配起点
this.oldLast = oldLast < 0 ? from : oldLast;
for (int i = 0; i < groups.length; i++)
groups[i] = -1; // 重置所有捕获组
acceptMode = mode;
boolean result = parentPattern.root.match(this, getText(), 0); // 从根节点开始递归
if (!result)
this.first = -1; // 失败标记
this.oldLast = this.last;
return result;
}matches()要求整个输入被模式覆盖：模式树的End节点在ENDANCHOR模式下校验seq.isAtEnd()，等效于「从0开始匹配且last == input.length()」。lookingAt()只要求前缀匹配，等价于「^模式匹配开头」。match会把first/last/groups全部重置，保证同一Matcher可反复匹配不同片段。
⑥ Matcher.find(int start) 的局部搜索
java
public boolean find() {
int nextSearchIndex = last; // 从上次匹配末尾继续
if (nextSearchIndex == first) nextSearchIndex++;
if (nextSearchIndex < 0) nextSearchIndex = 0;
if (nextSearchIndex > getTextLength()) return false;
return search(nextSearchIndex);
}
boolean search(int from) {
this.hitEnd = false;
this.requireEnd = false;
from = from < 0 ? 0 : from;
this.first = from;
this.oldLast = oldLast < 0 ? from : oldLast;
for (int i = from; i <= max; i++) { // max 为允许的最大起点（含前瞻需要）
// 从位置 i 以根节点尝试一次完整匹配（即 Node.match 的递归回溯）
if (parentPattern.root.match(this, getText(), i)) {
this.first = i;
this.groups[0] = first; // 整段匹配写入 group(0)
this.groups[1] = last;
return true;
}
}
this.first = -1;
return false;
}find()：从上次last位置继续搜索（last == first时空匹配要前进一位避免死循环），实现while (m.find())的连续扫描。find(int start)：reset()后从指定位置search(start)，用于显式指定搜索起点。search对每个起点尝试root.match；一次Node.match内部是整棵树的递归 + 回溯，find失败则推进起点重试，因此find最坏复杂度为「起点数 × 单次匹配代价」。
⑦ Matcher.group(int group) 的捕获组
java
public String group(int group) {
if (first < 0)
throw new IllegalStateException("No match found");
if (group < 0 || group > groupCount())
throw new IndexOutOfBoundsException("No group " + group);
if ((groups[group * 2] == -1) || (groups[group * 2 + 1] == -1))
return null; // 该组本轮未参与匹配
return getSubSequence(groups[group * 2], groups[group * 2 + 1]).toString();
}Matcher维护int[] groups：每个捕获组占用两个连续槽位，groups[g*2]存开始索引、groups[g*2+1]存结束索引（左闭右开）。groups长度在Matcher构造时按pattern.capturingGroupCount + 1分配，group(0)恒为整个匹配（由search/match写入）。- 槽位在每次匹配开始被重置为
-1，因此未参与本次匹配的分支组返回null而非异常。 groupCount()来自Pattern.groupCount()，即编译期统计的捕获组数量（非捕获组(?:...)不计入）。
⑧ Matcher.appendReplacement(StringBuffer, String) 的替换
java
public Matcher appendReplacement(StringBuffer sb, String replacement) {
if (first < 0)
throw new IllegalStateException("No match available");
sb.append(getText(), lastAppendPosition, first); // ① 追加匹配前的原文
appendEvaluated(sb, replacement); // ② 解析替换串并追加
lastAppendPosition = last; // ③ 记录已消费位置
return this;
}
private void appendEvaluated(StringBuffer buffer, String s) {
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '\\') { // 反斜杠转义
i++; // 读取下一个字符原样输出
buffer.append(s.charAt(i));
} else if (c == '$') {
// 解析 $1 / ${name}：取数字或花括号内组名 → 查 groups 数组
... buffer.append(getSubSequence(groups[g * 2], groups[g * 2 + 1]));
} else {
buffer.append(c); // 普通字符直接输出
}
}
}
public StringBuffer appendTail(StringBuffer sb) {
sb.append(getText(), lastAppendPosition, getTextLength()); // 追加剩余原文
return sb;
}lastAppendPosition：记录上一次替换已消费的文本终点，appendReplacement先补上「上次结尾 → 本次匹配起点」之间的原文。- 替换串解析：
$1、${name}展开为对应捕获组内容，\\与\$转义为字面量。 replaceAll(replacement)的完整流程就是「while (find()) appendReplacement(...)+ 末尾appendTail()」，三者组合实现全文替换。
⑨ 回溯算法在 Curly / Ques / Branch 中的实现
回溯的本质：一条匹配路径失败时，回退到最近的可选择点尝试另一条路径。在 Node 树中，可选择点就是 Curly（量词次数）、Ques（匹配 0 次还是 1 次）、Branch（选择哪个分支）。
Ques（? 量词）的两种模式：
java
boolean match(Matcher matcher, CharSequence seq, int[] groups) {
switch (type) {
case 0: // 贪婪：先匹配原子，失败再回溯为"不匹配"
if (atom.match(matcher, seq, groups))
return true;
return next.match(matcher, seq, groups); // 回溯：跳过原子
case 1: // 懒惰：先尝试"不匹配"，失败再匹配原子
if (next.match(matcher, seq, groups))
return true;
return atom.match(matcher, seq, groups); // 回溯：补上原子
}
return false;
}Curly（{n,m} / * / +）的贪婪模式核心：
java
// 贪婪：先尽量多匹配，再逐次回溯减少次数
for (int i = cmin; i < cmax; i++) {
// 尝试"到此为止 + 后继"是否可行
if (next.match(matcher, seq, groups))
return true;
if (!atom.match(matcher, seq, groups)) // 无法再多匹配一次
return false;
}
return next.match(matcher, seq, groups);- 贪婪：先匹配足量次（
cmin保底、cmax封顶），然后先试后继；后继失败才回溯"少匹配一次原子再试"。 - 懒惰（
type=1）：反过来，先试最少次数，后继失败才增加一次。 - 占有（
type=2）：匹配后不再回溯（++/*+），匹配失败直接整体失败，适合无需回溯的场景，可避免灾难性回溯。
Branch（| 交替）依次尝试：
java
boolean match(Matcher matcher, CharSequence seq, int[] groups) {
for (Node branch : branches) {
if (branch.match(matcher, seq, groups))
return true; // 第一个成功的分支胜出
}
return false; // 全部分支失败
}Curly / Ques / Branch 的 match 都是递归调用，嵌套越深递归栈越深；Matcher 的一次匹配本质上是对 Node 树做深度优先的回溯遍历。
⑩ "\1" 反向引用的 GroupRef
java
static final class GroupRef extends Node {
int groupIndex; // 引用的捕获组编号
Node next;
boolean match(Matcher matcher, CharSequence seq, int[] groups) {
int groupStart = groups[groupIndex * 2]; // 被引用组的起止
int groupEnd = groups[groupIndex * 2 + 1];
if (groupStart < 0 || groupEnd < 0)
return false; // 该组尚未捕获 → 匹配失败
// 特殊情形：反向引用位于输入开头，无法向前比较
if (seq.isAtStart()) {
if (groupStart == 0 && groupEnd == seq.length()) // 引用整个输入
return next.match(matcher, seq, groups);
if (groupStart == groupEnd) // 被引用组为空
return next.match(matcher, seq, groups);
}
// 逐字符比较：当前位置与捕获组内容必须一致
for (int i = groupStart; i < groupEnd; i++) {
if (seq.charAt(seq.index) != seq.charAt(i))
return false;
seq.index++; // 推进输入游标
}
return next.match(matcher, seq, groups); // 比较通过 → 继续后继节点
}
}seq是Matcher内部包装输入文本的可移动CharSequence（携带index游标，并提供isAtStart()/isAtEnd()判断），GroupRef通过推进seq.index消耗输入。- 比较逻辑：把「当前位置开始的子串」与「被引用捕获组的子串」逐字符比对，全部相等才算通过，这正是
(a)\1匹配连续相同子串的原理。 - 反向引用使正则不再是"正则语言"，这也是 Java 选择回溯型 NFA 引擎的核心原因之一。
总结
Java 正则引擎 = 编译（Pattern） + 回溯匹配（Matcher）：
| 阶段 | 组件 | 关键实现 |
|---|---|---|
| 编译 | Pattern.compile | 递归下降解析 pattern() → Node 树 → normalize() 节点合并优化 |
| 解析 | curLocal + cursor | expr / sequence / atom / piece 分层构造节点 |
| 匹配 | Matcher | match 重置状态后从 root 递归；find 循环推进起点重试 |
| 捕获 | groups 数组 | 每组分两个槽位存起止索引，group(0) 为整段匹配 |
| 回溯 | Curly / Ques / Branch | 深度优先尝试所有路径，失败回退到最近选择点 |
| 引用 | GroupRef | 逐字符比对捕获组内容，依赖 Matcher 内部可移动 CharSequence |
理解 Node 树与递归回溯模型后，正则的语义（量词贪婪/懒惰、交替优先级、反向引用）都能映射到具体的匹配路径；同时也解释了为什么"嵌套量词 + 复杂环视"的组合可能触发灾难性回溯——每一次 find 失败都会让引擎在 Node 树上指数级探索选择点。