粗略探究一下正则表达式的实现原理
转自我的个人微博
会进来看这篇分享的同学，应该已经大概知道正则表达式是什么了（以下简称 RE），而且应该多多少少有使用过，感受过 RE 的用途。所以我就直接进入正题，从 RE 的三大基本操作开始介绍。
RE 三个基本操作：选择，连接和闭包
RE 对于大部分程序员来说并不陌生，但当提到 RE 的三个基本操作的时候就没什么概念了。所谓基本操作，就是构成 RE 的基石，只要实现了这几个基本操作，理论上就可以通过这几个操作的拼接和嵌套来应付（几乎）所有的表达式。他们就是下面这三个操作：
- 选择：即取并集。符号为
|，即我们常在 RE 中看到的A|B，意为匹配A或者B中的一个 - 连接：表达式之间的连接。即我们常在 RE 中看到的
AB，意为匹配一个B出现在一个A之后的模式 - 闭包：自身连接0次或者多次。符号为
*,即我们常在 RE 中看到的A*。可能有人会疑惑为什么只有*而没有?和+，这部分同学可以带着这个问题看下去就懂了。
上述三个就是 RE 的三个基本操作，同学们可以想象一下是否“所有”的表达式都可以看成是上述三个操作的拼接和嵌套。这里“所有”打上引号是因为并非真的是所有，因为正则表达式发展至今已经不是最初的样子，技术人员为了方便不断给 RE 添加新功能，所以现在有好几个不同版本的正则表达式标准，有些新功能的实现方式并不能通过上述三个操作来实现，但是我们今天不讨论这些或巧妙或复杂的新技术排除在外，只讨论原始朴素的正则表达式。
用有限状态自动机实现 RE
现在我们知道了 RE 的三大基本操作，所以目标就是想办法实现这三种基本操作。这时候就需要用到有限状态自动机（Finite Status Automaton，FSA）这个工具了。有 ASR 或者 NLP 经验的同学应该比较熟悉自动机的概念。简单来说，FSA 就是一个规定了事物在不同状态之间达到什么条件才会转换的机制。下面我画了一个 HO 在两个不同状态之间转换的简易 FSA 示意图（不是很严谨，仅供理解）：
我们可以看到，把上述这种 FSA 写成代码流程也是比较自然的过程，只要用条件判断控制（if()）状态转换就行。那么， 怎么用 FSA 来表示 RE 的匹配过程呢？
用 FSA 表示 RE 基本操作
先从连接操作开始说起。假设我们就想匹配字符串“ab”，对应的正则表达式就是 ab。相当于用 FSA 表示如下：
如果输入字符串能从状态 0 转换到状态 2，就返回匹配成功，反之就是匹配失败，该字符串和正则表达式不匹配。
上述正则表达式 ab 相当于是 [匹配字符串 “a”] 和 [匹配字符串 “b”] 这两个子表达式进行连接操作。所以更一般的，如果我们想连接两个子表达式 A 和 B（而不是单纯的连接字符串 “a” 和 “b”），我们可以像这样表示：
其中的 表示不需要任何条件就能跳转。上面那幅图简化一下就是这样：
以此类推，两个子表达式的选择操作（A|B）就可以表示成这样：
上面这个 FSA 表示，输入的表达式只需要有一条路（通过子表达式 A 或者通过表达式 B）能从状态 0 转换到状态 1 就算匹配成功。
然后到闭包。可能还有一些同学在像为啥闭包只要讨论 * 而不管 ? 和 +，毕竟每次要用到这三个操作的时候我们一般都是一起考虑然后在这三个里面挑一个最合适的。那么我们就先从 ? 开始讨论。
A? 表示表达式 A 匹配 1 次或者 0 次。用 FSA 可以这样表示：
A+ 表示表达式 A 匹配 1 次或一次以上：
最后， A* 表示表达式 A 匹配 0 次 或 0 次以上，它的 FSA 我就不画了，可能想象力比较好的同学已经自己脑海里有图像了，一时想象不出来的同学可以自己动手画一下看看。其实就算上述两个 FSA 的结合。
至此我们已经能用 FSA 表示出正则表达式的三个基本操作，接下来我们实际应用一把，感受一下如何用 FSA 来解决实际的正则表达式。
用 FSA 实现表达式 A(B|C)*
首先，最开始的 A 用 FSA 画出来就是：
然后，回忆一下 B|C 应该长什么样:
接下来就用到了我们上面推出来的闭包 (B|C)*，这里把 (B|C) 看成一个整体就跟上一节讨论的 A* 一样，来看看跟你想的（画的）是不是一样:
最后，就只要把 A 和 (B|C)* 做一个连接操作就行：
至此，正则表达式 A(B|C)* 的有限状态机就构造完成了。不过可能大部分同学都会觉得这个图看着很别扭，好像有哪里不对，但是看上去又完全符合要求。是的，上图确实找不到任何“错误”，但是又有很多不合理的地方。眼尖的同学可能一眼就已经看出，上述状态图中的状态 1 和状态 2 完全就是等价的嘛，3，4也是。确实如此，上述设计虽然不回导致字符串的异常匹配，但是匹配效率上还有很大的可提升空间。
接下来我们就讨论 FSA 的优化过程。
从 NFA 到 DFA
我们还是从表达式 a(b|c)* 开始讨论，注意我这里没有用大写的字母 ABC 来表示子表达式，因为子表示会把表达式内部的状态给隐藏掉，所以我这里举的例子就是直接用小写得字母 abc 来表示他们的原始含义，即单纯的匹配“字母 a 后面接0个或多个 b 再接0个或多个 c ”的字符串。对应的 FSA 如下所示，跟上一节最后的图很像，只是这个图里没有子表达式，都是一个个的状态加转换条件。还有下图中我加了个长得不一样的状态 5，像这种样式的状态我们称之为接受态或终止态，一旦达到这种状态意味着匹配成功，前面我都没有加是因为对前面讲的内容没有影响，但是接受态在后面 FSA 的优化过程中很关键，请大家留个心眼。
注意观察上述示意图，我们可以看到两个特征：
- 图中有很多可任意跳转的边，即 epsilon 边
- 给一个跳转条件，可以跳转到的状态是不确定的。
上述第一点显而易见。第二点稍微解释一下，我举个例子，假设现在状态 0，且满足条件 a，然后它能跳转到状态 1、4、5 中的一个，就是说它最终跳转到哪个状态是不能确定的。对于这种自动状态机，我们就叫它“非确定性有限状态自动机（Non-deterministic Finite Automaton, NFA）”。
想要优化它需要用到“子集构造算法”。 该算法的专业定义如下，不过不结合实例看这个定义基本是看不懂的，所以后面我直接用上述例子（a(b|c)*）演示一遍。
子集构造算法：从将初始状态划分为一个初始状态子集开始,构造状态子集(经过零个或多个空字符串ε转移到的状态和已在子集中的状态都是构造的新的状态子集),存在c属于字母表Σ,经过一个c的转移(必须有c的转移),能够使得从状态子集 i转移到状态子集 j, 则在DFA中有在c的输入下从状态子集 i 转移到状态子集 j 的转移.直到最后不再有新的状态子集出现.根据状态子集的转移依次构造DFA.
先构建初始状态子集（定义见上），说白了就是从初始状态 0 出发，可以通过 0 条或多条 边能到达的所有状态的集合（这就是子集的概念，后面每一步都会用到）。上述例子中我们看到，状态 0 通过
边哪里都去不了，所以初始状态子集只有状态 0 一个元素。我们构造这么一个表格，来方便看出各个状态子集通过不同的边能到达的状态集合。
可以看到，通过初始状态“零”通过边 a，能够到达的状态有状态 1、4、5，而通过边 b 和 c 都不能到达任何状态。所以我们又得到了一个状态子集 {1, 4, 5}。
重复上述过程，知道没有新的状态产生。最后我们得到这样的表格。
如此，我们得到了 4 种新状态以及他们之间的转换关系。因此我们可以构建新的 FSA。
再看 NFA 的两个特征：
- 图中有很多可任意跳转的边，即 epsilon 边
- 给一个跳转条件，可以跳转到的状态是不确定的。
对比上述这个新的 FSA，是不是上述两条都已经不满足了。我们称这种新的 FSA 为 “确定性有限状态自动机（Deterministic Finite Automaton, DFA）” 。我们可以自己拿例子过一遍这个自动机，验证它是否满足 a(b|c)*。这里可能令人不解的点是：这个图怎么有三个接受态。。。？没错，FSA 并没有规定接受态只能有一个，只要能转移到任何一个接受态，此次匹配就算成功。“那。。。凭什么状态一、二、三可以是接受态呢？”。这就要看上面那个表格了，原来的 NFA 中的接受态是状态 5，因此只要包含了原状态 5的状态子集在 DFA 中也是接受态。
从 DFA 到 DFA
可能有人觉得上述优化后的 DFA 已经足够简洁，没有优化的空间了。事实是它还能优化的跟简洁，达到更快的匹配效率。这种优化方法被称为等价状态集合划分。照例，先给定义。
等价状态集合划分：一开始只有两个状态集,一个接受（终止）状态集合,一个非接受（非终止）状态集合.对于每一个状态集合Sp,如果存在c属于字母表Σ,使得Sp中的状态转移到不同的状态集合(包括没有转移的空状态集合),则拆分Sp,使得拆分后的状态集合中的每一个状态不可能转移到不同的状态集合.其中状态集合之间的转移构成最小化DFA中的转移.
我们继续还是已上述的例子来演示（虽然这不是个好例子）。
第一步就是分两个状态集，判断标准是该状态是否为接受态。因此我们把状态零（只有它不是接受态）单独分为一个状态集 Sp，而状态一、二、三分为另一个状态集 Sp
。
然后，判断是否存在边 c 连接了不同的状态集，如果有的话，把相关的状态单独分出来。但是我们这个例子中没有这种边（所以我说这不是个很好的例子，同学们感兴趣的话可以自己找别的例子试一试），因此不需要任何迭代。所以我们最终得到的 FSA 示意图长这样。
是不是出乎意料的简洁，但是带入例子验证之后确实是逻辑合理的。
这个最终优化出来的 FSA 我们称之为 “最小确定性有限状态自动机（Minimal deterministic Finite Automaton, DFA°）”。
总结
至此，我们的正则表达式探索之旅也接近尾声了。我们可以看到，NFA 构造起来最简单，但是也是构造出来的状态机冗余操作很多，匹配的时候甚至需要用到回溯（因为它的不确定性）；而 DFA° 构造过程很长，需要一步一步推出来，但是构造好之后，推理过程也是前面两种 FSA 难以比拟的。目前常用的 RE 引擎基本都是 DFA 和 DFA° 两种混用的解决方案，根据具体的使用场景来定具体的实现方式。
