什么是正则表达式
正则表达式(Regular Expression)是一种文本模式，使用一些特定的字符来检索、匹配以及替换符合规则的字符串。
构造正则表达式语法的字符，由普通字符、特殊字符（称为"元字符"）、限定字符（量词）、定位字符（边界字符）组成。
关于这些字符的介绍，推荐阅读 正则表达式 - 语法 和 正则表达式 - 元字符。
正则表达式引擎
正则表达式是一个用正则符号写出的公式，程序对这个公式进行语法分析，建立一个语法分析树，再根据这个分析树结合正则表达式的引擎生成执行程序（这个执行程序我们把它称作状态机，也叫状态自动机），用于字符匹配。
而这里的正则表达式引擎就是一套核心算法，用于建立状态机。
目前实现正则表达式引擎的方式有两种：DFA 自动机（Deterministic Final Automaton 确定有限状态自动机）和 NFA 自动机（Non deterministic Finite Automaton 非确定有限状态自动机）。关于 DFA 和 NFA 的详细讲解，感兴趣的朋友可以去阅读《编译原理（龙书）》。
对比来看，构造 DFA 自动机的代价远大于 NFA 自动机，但 DFA 自动机的执行效率高于 NFA 自动机。
假设一个字符串的长度是 n，如果用 DFA 自动机作为正则表达式引擎，则匹配的时间复杂度为 O(n)；如果用 NFA 自动机作为正则表达式引擎，由于 NFA 自动机在匹配过程中存在大量的分支和回溯，假设 NFA 的状态数为 s，则该匹配算法的时间复杂度为 O（ns）。
关于这个状态数，我们通过一个案例进行解释：
String reg = "ab{1,3}d";
比如说上述匹配规则，状态数就是3，对应不同的匹配格式，即 abd、abbd、abbbd。
NFA 自动机的优势是支持更多功能。例如，捕获 group、环视、占有优先量词等高级功能。这些功能都是基于子表达式独立进行匹配，因此在编程语言里，使用的正则表达式库都是基于 NFA 实现的。
关于捕获 group，这里就要提及正则匹配中的分组概念，分组可以分为两种形式，捕获组和非捕获组。后续会介绍这两者之间的区别，这里我们只介绍一下分组，以及如何捕获分组。
String reg = "((d+)([a-z]))s+";
上述正则表达式总共包含了四个分组，按照默认的从左到右的匹配方式。
- group(0) 代表了匹配项本身，也就是整个整个表达式 ((d+)([a-z]))s+
- group(1) 代表了子表达式项 ((d+)([a-z]))
- group(2) 代表了子表达式项 (d+)
- group(3) 代表了子表达式项 ([a-z])
可以看出 group(0)代表整个表达式，之所以这样命名捕获组，是因为在匹配中，保存了与这些组匹配的输入序列的每个子序列。捕获的子序列稍后可以通过 Back 引用（反向引用） 在表达式中使用，也可以在匹配操作完成后从匹配器检索。
NFA 自动机的回溯
我们学习算法时应该都听过回溯法，回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。 经典的八皇后问题就是回溯法的案例。
NFA 自动机匹配模式默认为贪婪模式，即正则表达式中的限定符会匹配尽可能多的内容，不撞南墙不回头，回头就带来了回溯问题。
假设有这样一段代码需要进行正则匹配：
String text=“abbc”;
String regex=“ab{1,3}c”;
匹配过程如下图所示：
上图匹配过程比较简单，如果遇到复杂的正则表达式，则可能会回溯多次。
匹配模式
上面提到了贪婪模式，正则表达式另外还有两张匹配模式。
1、贪婪模式（Greedy）
限定符用来指定正则表达式的一个给定组件必须要出现多少次才能满足匹配。有 ***** 或 + 或 ? 或 {n} 或 {n,} 或 {n,m} 共6种。
正则表达式中存在上述限定符，则会匹配尽可能多的内容，如下案例所示：
String regex = "ab{1,3}c";
关于贪婪模式，可以参照上面的匹配流程图，NFA 自动机会读取到最大的匹配范围，失败后才会进行回溯。
这里说一下我学习时的第一想法，当时自己认为第一次匹配时，选择最大的范围匹配，即 abbbc。首次匹配不成功，匹配范围由大变小，会试探着继续匹配。
上述想法让我在学习独占模式时困惑不已，我都搞不懂独占模式和贪婪模式的区别，尤其是针对下面这个案例：
String text=“abbc”
String regex=“ab{1,3}+bc”
// 结果是不匹配
为此我想要搞清楚正则匹配到底走了多少步，上文的贪婪模式匹配流程图只是参考网上画的，那么有什么依据支撑该观点。为此我做了以下努力：
1、首先我在网上查找在线正则匹配网站，最好可以解释匹配过程有多少 step，不过没有找到合适的，我在后文放了几个还不错的正则匹配工具，后续使用可以参考一下。
2、既然找不到合适的工具，那么只有一条出路，看代码，代码是不会骗人的，看代码中的匹配逻辑，加以调试，希望能够有所收获。
习惯使用 Java，所以我们就从 Java 代码入手吧，以下是测试代码：
public static void matchTest() {
String text = "abbc";
String reg = "ab{1,3}c";
Pattern p = Pattern.compile(reg);
Matcher m = p.matcher(text);
System.out.println(m.find());
}
关于 Pattern 和 Matcher 源码的学习，可以借鉴一下这两篇文章：java源码解析之Regex正则(一) 和 Pattern和Matcher.find源码解读
通过上述两篇文章，可以帮助我们克服一下读源码的压力，有一点头绪，你瞅 Pattern 文件中有接近 6000行代码，恐怕还没开始就直接劝退了。
贪婪模式匹配逻辑源码分析
下面我也不浪费篇幅来串流程了，毕竟本意也不是讲源码，只关注核心部分即可。共分为以下几大步骤：
1、读取 reg 中的内容，封装到 Node 的实现类中，Node 有很多子类，我最初接触到的子类为 Curly 类，其中包括 atom、type、cmin 和 cmax 这四个属性。这里简单介绍一下这个四个属性，atom 类似于树节点，每个节点的值对应 reg 中的普通字符，然后执行下一个节点。type 用来区分匹配模式，贪婪模式在代码中用 0表示，cmin 指的是 1，cmax 指的是 3。专门截了一张图，方便大家理解我刚才说的内容，如下所示：
98 即字符 b 对应的 ASCII 码。
2、直接讲 b{1,3} 的匹配逻辑，核心代码位于 Curly 类的 match 方法。
boolean match(Matcher matcher, int i, CharSequence seq) {
int j;
for (j = 0; j = cmax) {
// We have matched the maximum... continue with the rest of
// the regular expression
return next.match(matcher, i, seq);
}
int backLimit = j;
while (atom.match(matcher, i, seq)) {
// k is the length of this match
int k = matcher.last - i;
if (k == 0) // Zero length match
break;
// Move up index and number matched
i = matcher.last;
j++;
// We are greedy so match as many as we can
while (j = backLimit) {
if (next.match(matcher, i, seq))
return true;
i -= k;
j--;
}
return false;
}
return next.match(matcher, i, seq);
}
关于字符的匹配，具体逻辑为：
private static abstract class BmpCharProperty extends CharProperty {
boolean match(Matcher matcher, int i, CharSequence seq) {
if (i
