DFA和NFA

根据正则表达式的匹配方式不同，将正则表达式引擎分成文本模式（Text Directed）和表达式模式(Regex Directed)两种。有时候也称为DFA（Deterministic Finite Automaton 确定有穷状态机）、NFA（Nondeterministic Finite Automaton 不确定有穷状态机）。

NFA

NFA是基于表达式做匹配的。由于NFA支持惰性、引用等特性，所以NFA的应用比较广。事实上常见的正则表达式引擎都是NFA模式的。

我们来看一下正则表达式`ab*c`在引擎内部是如何匹配字符串“abbc”的。

1. 首先使用`a`匹配字符串"abbc"。

使用`a`匹配，字符串字符“a”，匹配。

2. 使用`b*`匹配剩余字符串“bbc”。

使用`b*`匹配字符串第一个“b”，匹配。

继续使用`b*`匹配字符串第二个“b”，匹配。

继续使用`b*`匹配字符串“c”，不匹配。剩余字符串为“c”。

3. 使用`c`匹配剩余字符串“c”。

使用`c`匹配，字符串字符“c”，匹配。正则表达式匹配成功。

NFA的回溯

如果正则式出现了重复符号或选择符号，则正则表达式可能会出现多种匹配的结果，而NFA是使用回溯来实现对所有正则表达式可能出现的结果进行遍历的。

我们看一下，利用正则表达式`a.+c`查找字符串“abcd”，表达式引擎是如何查找的。

1. 子表达式`a`匹配字符“a”。剩余字符串“bcd”

2. 子表达式`.+`可以匹配剩余字符串"bcd"，一直到字符串结束。剩余字符串为空。

3. 子表达式`c`匹配字符串结束，不匹配。促发上一个子表达式回溯。

4. 上一个子表达式`.+`退回一个字符“d”，即匹配字符串“bc”。剩余字符串“d”。

5. 子表达式`c`匹配剩余字符串“d”，不匹配。再次促发上一个匹配回溯。

6. 上一个子表达式`.+`再退回一个字符“c”，即匹配字符串“b”。剩余字符串“cd”。

7. 子表达式`c`匹配剩余字符串“cd”，匹配“c”。字符串匹配成功。

DFA

DFA是基于文本的匹配引擎。由于DFA没有回溯等操作，所以DFA的速度较之于NFA要快。

我们来看一下正则表达式`ab*c`是如何匹配字符串“abbc”的。

1. 首先使用`a`匹配字符串"abbc"。

使用`a`匹配，字符串字符“a”，匹配。剩余字符串为“bbc”。

2. 使用`b*`匹配剩余字符串“bbc”。

使用`b*`作为空字符匹配空字符，匹配。这个结果备选，剩余字符串为“bbc”.

继续使用`b*`匹配字符串第一个“b”，匹配。这个结果备选，剩余字符串为“bc”。

继续使用`b*`匹配字符串第二个“b”，匹配。这个结果备选，剩余字符串为“c”。

继续使用`b*`匹配字符串“c”，不匹配。这个结果不使用。

3. 使用`c`匹配剩余字符串“bbc”、“bc”或“c”。

使用`c`匹配，字符串字符“bbc”，不匹配。这个结果不使用。

使用`c`匹配，字符串字符“bc”，不匹配。这个结果不使用。

使用`c`匹配，字符串字符“c”，匹配。正则表达式匹配成功。

DFA的最长匹配

如果正则式出现了重复符号或选择符号，则正则表达式可能会出现多种匹配的结果，在DFA中，会选择其中最长的匹配结果。

例如，用正则表达式`HashMap|LinkedHashMap`匹配字符串“LinkedHashMap”。两个子表达式`HashMap`和`LinkedHashMap`都可以匹配。DFA会选择最长的匹配"LinkedHashMap"。