关于java:翻译正则引擎的几种分类

8次阅读

共计 1721 个字符，预计需要花费 5 分钟才能阅读完成。

原文链接 http://www.softec.lu/site/RegularExpressions/RegularExpressionEngines

正则表达式引擎是正则表达式匹配算法的根底。其有多种不同的实现，但大多数都是基于 Henry Spencer 的 NFA 引擎。

正则引擎有两个大分类，DFA 和 NFA，像 Perl、Java、.Net、PHP、Python、Ruby……等大多是工具都是用了 NFA 引擎。多数宽泛被应用的工具如 mawk 应用了 POSIX NFA 引擎（NFA 的一种变种）。以高效著称的工具采纳了更为高效的 DFA 引擎。诸如 GNU awk，GNU egrep 和 Tcl 之类的一些工具联合了 NFA / DFA 两种引擎，将两者的长处联合在一起。

基于不同类型引擎的实现的正则表达式，次要有以下几点差别。

语法
匹配内容
零宽断言(环视) 性能
捕捉性能
性能

所有的引擎都会对文本做从左向右的最长匹配，但具体细节取决于应用了何种引擎。

NFA 引擎中应用的非确定无限状态机 (Nondeterministic finite automation) 是一种由要匹配的表达式驱动的算法。这使得正则表达式像一个小的编程语言一样，可管制引擎在匹配失败时候的行为。

正则引擎从正则表达式其实地位开始，尝试正则表达式与文本的结尾进行匹配，如果匹配胜利，都后退一个配置，否则文本始终后退到下一个字符，直到匹配。如果正则表达式须要作出抉择（例如应用代替词或可选的量词），它将抉择其中之一，并记住其余抉择以及在文本中进行抉择的地位。如果在之后的解决中，匹配失败，并且还有其余可选的门路，则引擎将回溯做之前作出抉择的地位，并尝试其余的抉择。如果没有其余可用的代替计划，则匹配失败，引擎后退到下一个字符并从头开始匹配正则表达式。

如果引擎达到了正则表达式的开端并且所有内容都已匹配，则引擎就会认为匹配胜利，并最终放弃所有剩下的代替办法，甚至不再持续摸索。这里有很重要的一点：抉择不同门路的程序很重要，它决定是是否能做到最长匹配。

引擎会真正依照正则表达式进行匹配，让你抉择达到齐全匹配所需的每个步骤。你必须很审慎地通知它，首先查看哪种抉择能力达到您的冀望。你也有机会调整正则表达式，以最大水平地缩小回溯并尽早进行匹配。NFA 引擎中应用的办法的一些示例也能够帮忙你理解回溯是如何工作的。

POSIX NFA 引擎相似于传统 NFA 引擎，然而当找到胜利的匹配项时，它将会记录匹配后果，并且尝试其余可用的代替办法以查找是否能够找到更长的最右边的匹配。这打消了传统 NFA 引擎中不能保障最长最左匹配的问题。

以弗里德尔（Friedl）的书中的这个乏味的例子为例：用 one(self)?(selfsufficient)? 去匹配 oneselfsufficient，传统的 NFA 将匹配 oneself，而 POSIX NFA 将匹配oneselfsufficient，因为(self)? 有两种抉择，匹配 self 或者啥都不匹配，显然最终匹配到的更长。

DFA 引擎中应用的确定性无限自动机（Deterministic finite automaton）是一种由要搜寻的文本驱动的算法。对于搜寻到的文本中的每个字符，DFA 引擎只会查看一次。实际上，它相当于并行尝试了 NFA 中所有可能的代替办法，并将返回其中最长的匹配。

这种办法的确更高效，但也有很多毛病：

你无法控制表达式返回匹配项的形式，无论您如何结构表达式，它始终将返回最长最左匹配。
没有回溯，因而所有反复的运算符都是贪心的。原子分组和所有格修饰符也是无稽之谈。(更多详细信息，请查阅 RegularExpressionsBacktracking）
不反对零宽断言(环视)
捕捉和反向援用也不可能实现
正则表达式预编译工夫更长，占用更多内存

因为 DFA 引擎速度快，但 NFA 引擎的性能多，因而，混合 NFA / DFA 引擎试图将二者的劣势联合起来。迄今为止惟一可用的齐全混合实现是 Tcl 中应用的 Henry Spencer 引擎，它是对原始实现的齐全重写。像 GNU egrep 和 awk 只是将两个独立的引擎放一起，而后依据是否应用了 NFA 特有的性能决定应用哪个引擎。

正文完