慎用正则表达式

什么是正则表达式

正则表达式(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 < cmin; j++) {
    if (atom.match(matcher, i, seq)) {
      i = matcher.last;
      continue;
    }
    return false;
  }
  if (type == GREEDY)//贪婪模式
    return match0(matcher, i, j, seq);
  else if (type == LAZY)//懒惰模式
    return match1(matcher, i, j, seq);
  else//独占模式
    return match2(matcher, i, j, seq);
}

关于贪婪模式的匹配逻辑，在 match0() 方法中。

// Greedy match.
// i is the index to start matching at
// j is the number of atoms that have matched
boolean match0(Matcher matcher, int i, int j, CharSequence seq) {
  if (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 < cmax) {
      if (!atom.match(matcher, i, seq))
        break;
      if (i + k != matcher.last) {
        if (match0(matcher, matcher.last, j+1, seq))
          return true;
        break;
      }
      i += k;
      j++;
    }
    // Handle backing off if match fails
    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 < matcher.to) {
      return isSatisfiedBy(seq.charAt(i))
        && next.match(matcher, i+1, seq);
    } else {
      matcher.hitEnd = true;
      return false;
    }
  }
}

//其中 isSatisfiedBy具体代码为：
static final class Single extends BmpCharProperty {
  final int c;
  Single(int c) { this.c = c; }
  boolean isSatisfiedBy(int ch) {
    return ch == c;
  }
}

关于上述代码的逻辑，我尝试用调试截图来讲解，首先是进入 match0()方法，注意观察 i 和 j 的值，i=2表示该匹配 text 中的第三个字符了，而 j=1表示 b{1,3}已经匹配了一个 b。

进入第一个循环中，其中 atom.match(matcher, i, seq) 用来匹配 text 的第三个字符，匹配成功。因为 j=2 小于 cmax，又接着调用 atom.match(matcher, i, seq)，我们知道 text 的第四个字符和 b{1,3} 匹配失败，所以直接 break 了。

然后调用 next.match(matcher, i, seq) ，比较 text 第四个字符和 reg 的最后一个字符，匹配成功，最后返回 true。

上述关于匹配逻辑讲解比较简单，但也算是印证了上文的贪婪模式匹配流程图，

2、懒惰模式（Reluctant）

该模式指的是正则表达式会尽可能少地重复匹配字符。如果匹配成功，它会继续匹配剩余的字符串。

String regex = "ab{1,3}?c";

和贪婪模式刚好相反，第一次匹配时，选择最小的范围匹配，即 abc。

不过懒惰模式也无法避免回溯问题，比如说要匹配的文本为 abbc，第一次没有匹配成功，然后匹配范围由小变大，同样发生了回溯。

关于懒惰模式的匹配流程如下图所示，这里就不解读源码了，核心逻辑在 Curly 类的 match1()方法中，感兴趣的朋友可以动手调试一下。

懒惰模式匹配流程图

3、独占模式（Possessive）

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

在限定符后面加一个“+”，就可以开启独占模式。

关于独占模式的了解来源于极客时间专栏刘超老师的一篇文章，说下面这个案例a匹配失败后不会回溯，那是不是说独占模式就不会出现回溯问题呢？结果紧接着又给了一个案例b，说是匹配成功，而且还发生了回溯，我是有点懵圈了，这都什么和什么呀？

//案例a，下述代码匹配不成功
String text=“abbc”;
String regex = "ab{1,3}+bc";
//案例b，下述代码匹配成功，发生了回溯
String text=“abbc”;
String regex = "ab{1,3}+c";

没办法，只能从代码入手了，根据上文可知独占模式会进入 match2()方法，我们来一探究竟。

boolean match2(Matcher matcher, int i, int j, CharSequence seq) {
  for (; j < cmax; j++) {
    if (!atom.match(matcher, i, seq))
      break;
    if (i == matcher.last)
      break;
    i = matcher.last;
  }
  return next.match(matcher, i, seq);
}

相较于贪婪模式，代码逻辑确实简单了很多。我们先来调试案例a，循环里的方法还是来匹配 text 的后三个字符，匹配失败后 break，执行 next.match(matcher, i, seq)，调试时发现进入了 Slice 类中，首先我们来看一下 next 的值：

Slice 类具体代码如下：

static final class Slice extends SliceNode {
  Slice(int[] buf) {
    super(buf);
  }
  boolean match(Matcher matcher, int i, CharSequence seq) {
    int[] buf = buffer;
    int len = buf.length;
    for (int j=0; j<len; j++) {
      if ((i+j) >= matcher.to) {
        matcher.hitEnd = true;
        return false;
      }
      if (buf[j] != seq.charAt(i+j))
        return false;
    }
    return next.match(matcher, i+len, seq);
  }
}

而 buffer 的内容为[98,99]，即对应 regex 中的后两位，循环体中执行 buf[0] != seq.charAt(3)，结果直接返回 false。看起来确实没有回溯，而且第一次见到 buffer ，虽然背后的具体逻辑还不清楚，但是无疑提升了代码效率。

对了， Slice 类是通过 atom() 方法中的 newSlice(buffer, first, hasSupplementary)创建的，经过测试发现，当限定符后加上“+”后，后面如果有不小于两个的普通字符，则会产生 buffer，这里列举几个小案例：

String reg = "ab{1,3}+qcsd{1,2}+x"; //只会产生一个buffer，[q,c,s]
String reg = "ab{1,3}+qcsd{1,2}+xd"; //会产生两个buffer，[q,c,s],[x,d]

接着调试案例b，首先根据前文可知，因为“+”后只有一个字符‘c'，所以不会产生 buffer，我们看一下此时的 next 对象:

之后的匹配就比较简单了，直接判断值是否相等就可以了。

回顾一下上文的知识点，原文作者说案例b也不能避免回溯的发生，但是就我分析而言，这并不算是回溯吧。贪婪模式中的回溯代码如下：

    // Handle backing off if match fails
    while (j >= backLimit) {
      if (next.match(matcher, i, seq))
        return true;
      i -= k;
      j--;
    }

相较于独占模式来说复杂多了，当需要正则匹配的内容很长很长时，肯定是独占模式效率更高。

综上所述，独占模式相较于贪婪模式性能更好，而且个人认为独占模式没有发生回溯。

分组

如果要对多个字符进行重复怎么办呢？此时我们就要用到分组，我们可以使用小括号"()"来指定要重复的子表达式，然后对这个子表达式进行重复，例如：(abc)? 表示0个或1个 abc，这里一 个括号的表达式就表示一个分组 。

分组可以分为两种形式，捕获组和非捕获组。

关于分组的详细讲解推荐阅读：正则表达式高级用法(分组与捕获)

正则表达式的优化

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

贪婪模式会引起回溯问题，独占模式个人认为没有回溯问题，性能更好。

2、减少分支选择

分支选择类型“(X|Y|Z)”的正则表达式会降低性能，可以换用其他方式来实现，或者调整匹配顺序等。

• 就像数据库中的前缀索引一样，将出现频率高的字符放在前面，可实现快速匹配；
• 抽取共用字段放在前面，例如，将“(abcd|abef)”替换为“ab(cd|ef)”，后者匹配速度较快，因为 NFA 自动机会尝试匹配 ab，如果没有找到，就不会再尝试任何选项；
• 如果是简单的分支选择类型，我们可以用三次 index（String.indexOf()） 代替“(X|Y|Z)。

3、减少捕获组的使用

上文有提到过捕获组和非捕获组，简单来说一般一个 () 就是一个捕获组，捕获组可以进行嵌套。形如（?:exp）的表达式即为非捕获组。

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.*?>)
    System.out.println(m.group(2));//(.*?)
    System.out.println(m.group(3));//(</input>)
  }
}

执行结果为：

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

如果你只想获取 input 标签包裹的内容，则可以使用非捕获分组。

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

当然上述使用非捕获分组的方式有些多余，直接去掉不想捕获的分组的括号也可以，效果是一样的。

String reg = "<input.*?>(.*?)</input>";

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

正则表达式工具

正则表达式在线测试

玩转正则表达式！推荐一个速查、调试、验证、可视化工具

在线访问直接访问ihateregex.io/

Regulex

Regular Expression Test Page for Java

regular expressions 101

总结

正则表达式虽然小，却有着强大的匹配功能。不管是什么开发语言，都会用得到，以往只是完成正则匹配的功能，比如，注册页面手机号或邮箱的校验，但从未考虑过写的匹配语句是否存在性能问题。今天带大家从一个全新的角度来认识正则表达式，希望在未来能不用正则就不用，如果不得不用，就做好性能排查，尽量写的完美。