正则表达式（regular expression）是计算机科学的一个概念，很多语言都实现了它。正则表达式使用一些特定的元字符来检索、匹配以及替换符合规则的字符串。构造正则表达式语法的元字符，由普通字符、标准字符、限定字符（量词）、定位字符（边界字符）组成。详情可见下图：
image.png

    • 符号可以匹配任何字符（有可能不包括行终止符，这取决于标志的设置）
  • 使用 \ 作为转义字符，例如 . 匹配句号而 \ 匹配反斜线
  • ^ 和 $ 分别匹配一行的开头和结尾
  • 如果 X 和 Y 是正则表达式，则 XY 表示任何 X 的匹配后跟随 Y 的匹配，X|Y 表示任何 X 或 Y 的匹配
  • 可以将量词运用到表达式 X：X+（1个或多个）、X*（0个或多个）与 X?（0个或1个）
  • 默认情况下，量词要匹配能够使整个匹配成功的最大可能的重复次数。可以修改这种行为，方法是使用后缀 ？（使用勉强或吝啬匹配，也就是匹配最小的重复次数）或使用后缀 +（使用占有或贪婪匹配，也就是即使让整个匹配失败，也要匹配最大的重复次数）。例如，字符串 cab 匹配 [a-z]ab，但是不匹配 [a-z]+ab。在第一种情况中，表达式 [a-z] 只匹配字符 c，使得字符 ab 匹配该模式的剩余部分；但是贪婪版本 [a-z]+ 将匹配字符 cab，模式的剩余部分将无法匹配。
  • 我们使用群组来定义子表达式，其中群组用括号 () 括起来。例如，([+-]?)([0-9]+)

    使用

    我们可以通过一个表示正则表达式的字符串构建一个 Pattern 对象。然后从这个模式中获得一个 Matcher，并调用它的 matches 方法：
    1. Pattern pattern = Pattern.compile(patternString); 
    2. Matcher matcher = pattern.matcher(input);
    3. if (matcher.matches()) {
    4.   ...
    5. }
    为了方便使用，Pattern 直接提供了一个 matches 方法，其内部封装了上面的匹配逻辑：
    1. public static boolean matches(String regex, CharSequence input)
    如果正则表达式包含群组，那么 Matcher 对象可以通过 group 方法来抽取匹配的字符串，以及 start、end 方法来获取群组的边界：
    1. public int start(int groupIndex)
    2. public int end(int groupIndex)
    3. public String group(int groupIndex)
    4. public int groupCount()
    群组 0 是整个输入，而用于第一个实际群组的群组索引是 1。可通过调用 groupCount 方法来获得全部群组的数量。嵌套群组是按照前括号进行排序的，假设我们有下面的正则表达式：
    1. (([1-9]|1[0-2]):([0-5][0-9]))[ap]m
    和下面的输入字符串：
    1. 11:59am
    那么，Matcher 会报告下面的群组信息：
    1. 群组索引        开始        结束        字符串
    2. 0                     0            7             11:59am
    3. 1                     0          5             11:59
    4. 2                     0            2             11
    5. 3                     3            5             59

    正则表达式引擎

    正则表达式是一个用正则符号写出的公式，程序对这个公式进行语法分析，建立一个语法分析树，再根据这个分析树结合正则表达式的引擎生成执行程序（这个执行程序我们把它称作状态机，也叫状态自动机），用于字符匹配。而这里的正则表达式引擎就是一套核心算法，用于建立状态机。

目前实现正则表达式引擎的方式有两种：DFA 自动机（Deterministic Final Automaton 确定有限状态自动机）和 NFA 自动机（Non deterministic Finite Automaton 非确定有限状态自动机）。对比来看，构造 DFA 自动机的代价远大于 NFA 自动机，但 DFA 自动机的执行效率高于 NFA 自动机。

假设一个字符串的长度是 n，如果用 DFA 自动机作为正则表达式引擎，则匹配的时间复杂度为 O(n)；如果用 NFA 自动机作为正则表达式引擎，由于 NFA 自动机在匹配过程中存在大量的分支和回溯，假设 NFA 的状态数为 s，则该匹配算法的时间复杂度为 O（ns）。

1. NFA 自动机的匹配

NFA 自动机的优势是支持更多功能。例如，捕获 group、环视、占有优先量词等高级功能。这些功能都是基于子表达式独立进行匹配，因此在编程语言里，使用的正则表达式库都是基于 NFA 实现的。那么 NFA 自动机到底是怎么进行匹配的呢？我以下面的字符和表达式来举例说明。

  1. text="aabcab"
  2. regex="bc"

NFA 自动机会读取正则表达式的每一个字符，拿去和目标字符串匹配，匹配成功就换正则表达式的下一个字符，反之就继续和目标字符串的下一个字符进行匹配。

下面分解下过程。首先，读取正则表达式的第一个匹配符和字符串的第一个字符进行比较，b 对 a，不匹配；继续换字符串的下一个字符，也是 a，不匹配；继续换下一个，是 b，匹配。
image.png
然后，同理，读取正则表达式的第二个匹配符和字符串的第四个字符进行比较，c 对 c，匹配；继续读取正则表达式的下一个字符，然而后面已经没有可匹配的字符了，结束。
image.png
这就是 NFA 自动机的匹配过程，虽然在实际应用中，碰到的正则表达式都要比这复杂，但匹配方法是一样的。

2. NFA 自动机的回溯

用 NFA 自动机实现的比较复杂的正则表达式，在匹配过程中经常会引起回溯问题。大量的回溯会长时间地占用 CPU，从而带来系统性能开销。下面举例说明：

  1. text="abbc"
  2. regex="ab{1,3}c"

这个例子匹配目的比较简单。匹配以 a 开头，以 c 结尾，中间有 1-3 个 b 字符的字符串。NFA 自动机对其解析的过程是这样的：

首先，读取正则表达式第一个匹配符 a 和字符串第一个字符 a 进行比较，a 对 a，匹配。
image.png
然后，读取正则表达式第二个匹配符 b{1,3} 和字符串的第二个字符 b 进行比较，匹配。但因为 b{1,3} 表示 1-3 个 b 字符串，NFA 自动机又具有贪婪特性，所以此时不会继续读取正则表达式的下一个匹配符，而是依旧使用 b{1,3} 和字符串的第三个字符 b 进行比较，结果还是匹配。
image.png
接着继续使用 b{1,3} 和字符串的第四个字符 c 进行比较，发现不匹配了，此时就会发生回溯，已经读取的字符串第四个字符 c 将被吐出去，指针回到第三个字符 b 的位置。
image.png
那发生回溯以后，匹配过程怎么继续呢？程序会读取正则表达式的下一个匹配符 c，和字符串中的第四个字符 c 进行比较，结果匹配，结束。

3. 如何减少回溯问题？

既然回溯会给系统带来性能开销，那我们如何应对呢？如果你有仔细看上面那个案例的话，你会发现 NFA 自动机的贪婪特性就是导火索，这和正则表达式的匹配模式息息相关，一起来了解一下。

3.1 贪婪模式（Greedy）

顾名思义，就是在数量匹配中，如果单独使用 +、 ? 、* 或 {min,max} 等量词，正则表达式会匹配尽可能多的内容。例如，上边那个例子：

  1. text="abbc"
  2. regex="ab{1,3}c"

就是在贪婪模式下，NFA 自动机读取了最大的匹配范围，即匹配 3 个 b 字符。匹配发生了一次失败，就引起了一次回溯。如果匹配结果是“abbbc”，就会匹配成功。

3.2 懒惰模式（Reluctant）

在该模式下，正则表达式会尽可能少地重复匹配字符。如果匹配成功，它会继续匹配剩余的字符串。例如，在上面例子的字符后面加一个 ? 就可以开启懒惰模式。

  1. text="abc"
  2. regex="ab{1,3}?c"

匹配结果是“abc”，该模式下 NFA 自动机首先选择最小的匹配范围，即匹配 1 个 b 字符，因此也就避免了回溯问题。但懒惰模式无法完全避免回溯，下面的例子展示了懒惰模式在什么情况下会发生回溯问题。

  1. text="abbc"
  2. regex="ab{1,3}?c"

以上匹配结果依然是成功的，这又是为什么呢？我们可以通过懒惰模式的匹配过程来了解下原因。

首先，读取正则表达式第一个匹配符 a 和字符串第一个字符 a 进行比较，a 对 a，匹配。然后，读取正则表达式第二个匹配符 b{1,3} 和字符串的第二个字符 b 进行比较，匹配。
fed10b8310d8bc3873a2e94bcd848b80.webp
其次，由于懒惰模式下，正则表达式会尽可能少地重复匹配字符，匹配字符串中的下一个匹配字符 b 时就不会继续与 b{1,3} 进行匹配，从而选择放弃最大匹配 b 字符，转而匹配正则表达式中的下一个字符 c。
1022f60810980e0d9cdee7ace7c2813a.webp
此时你会发现匹配字符 b 与正则表达式中的字符 c 是不匹配的，这个时候会发生一次回溯，这次的回溯与贪婪模式中的回溯刚好相反，懒惰模式的回溯是回溯正则表达式中一个匹配字符，与上一个字符再进行匹配。如果匹配，则将匹配字符串的下一个字符和正则表达式的下一个字符。
105badb94ecd9c3ed1b9c09c3ed25cdc.webp

3.3 独占模式（Possessive）

同贪婪模式一样，独占模式一样会最大限度地匹配更多内容；但不同的是，在独占模式下，匹配失败就会结束匹配，不会发生回溯问题。

还是上边的例子，在字符后面加一个 + 就可以开启独占模式。

  1. text="abbc"
  2. regex="ab{1,3}+bc"

结果是不匹配，结束匹配，不会发生回溯问题，因为 b{1,3} 已经把两个 b 都匹配完了。

同样，独占模式也不能避免回溯的发生，我们再拿最开始的这个例子来分析下：

  1. text="abbc"
  2. regex="ab{1,3}+c"

结果是匹配的，这是因为与贪婪模式一样，独占模式一样会最大限度地匹配更多内容，即匹配完所有的 b 之后再去匹配 c，则匹配成功了。

讲到这里，你应该非常清楚了，在很多情况下使用懒惰模式和独占模式可以减少回溯的发生。

正则表达式的优化

下面总结几种正则表达式的优化方法：

1）少用贪婪模式，多用独占模式

2）减少分支选择
分支选择类型 (X|Y|Z) 的正则表达式会降低性能，如果一定要用，则需要考虑选择的顺序，将比较常用的选择项放在前面，使它们可以较快地被匹配；其次可以尝试提取共用模式，例如将 (abcd|abef) 替换为 ab(cd|ef) ，后者匹配速度较快，因为 NFA 自动机会尝试匹配 ab，如果没有找到，就不会再尝试任何选项。

3）减少捕获嵌套
捕获组是指把正则表达式中，子表达式匹配的内容保存到以数字编号或显式命名的数组中，方便后面引用。一般一个 () 就是一个捕获组，捕获组可以进行嵌套。非捕获组则是指参与匹配却不进行分组编号的捕获组，其表达式一般由（?:exp）组成。

在正则表达式中，每个捕获组都有一个编号，编号 0 代表整个匹配到的内容。我们可以看下面的例子：

  1. public static void main( String[] args ) {
  2.     String text = "<input high=\"20\" weight=\"70\">test</input>";
  3.     String reg="(<input.*?>)(.*?)(</input>)";
  4.     Pattern p = Pattern.compile(reg);
  5.     Matcher m = p.matcher(text);
  6.     while(m.find()) {
  7.         System.out.println(m.group(0));//整个匹配到的内容
  8.         System.out.println(m.group(1));//(<input.*?>)
  9.         System.out.println(m.group(2));//(.*?)
  10.         System.out.println(m.group(3));//(</input>)
  11.     }
  12. }

运行结果：

  1. <input high=\"20\" weight=\"70\">test</input>
  2. <input high=\"20\" weight=\"70\">
  3. test
  4. </input>

如果你并不需要获取某一个分组内的文本，那么就使用非捕获分组。例如，使用“(?:X)”代替“(X)”，我们再看下面的例子

public static void main( String[] args ) {
    String text = "<input high=\"20\" weight=\"70\">test</input>";
    String reg="(?:<input.*?>)(.*?)(?:</input>)";
    Pattern p = Pattern.compile(reg);
    Matcher m = p.matcher(text);
    while(m.find()) {
        System.out.println(m.group(0));//整个匹配到的内容
        System.out.println(m.group(1));//(.*?)
    }
}

运行结果：

<input high=\"20\" weight=\"70\">test</input>
test

综上可知：减少不需要获取的分组，可以提高正则表达式的性能。