`

深入入门正则表达式(java) - 匹配原理 - 1 - 引擎分类与普适原则

 
阅读更多

本节第一部分主要介绍正则引擎的分类,由于java属于NFA,所以只重点介绍此类。其余类型简要或不做介绍。

 

分类的内容全部来自《精通正则表达式》v3

 

 

 

引擎类型 程序
DFA awk(大多数版本)、egrep(大多数版本)、flex、lex、MySQL、Procmail
传统NFA GNU Emacs、Java、grep(大多数版本)、less、more、.NET语言、PCRE library、Perl、PHP(所有三套正则库)、Python、Ruby、sed(大多数版本)、vi
POSIX NFA mawk、Mortice Kern Systems'utilities、GNU Emacs(明确指定时使用)
DFA/NFA混合 GNU awk、GNU grep/egrep、Tcl

 

 

 

NFA(非确定型有穷自动机):表达式主导

 

正则:“to(nite|knight|night)”

 

目标文本:“tonight”

 

正则表达式从“t”开始,每次检查一部分(由引擎查看表达式的一部分),同时检查当前文本是否匹配表达式的当前部分。如果是,则继续表达式的下一部分,直到表达式的所有部分都能匹配。

 

此例中第一个元素是“t”,它会重复尝试,在目标字符串中找到“t”为止,然后检查“o”,过程与此一致。然后是“(nite|knight|night)”部分,表达式会一次尝试,直到宣告匹配成功或失败才会停止。 表达式中的控制权在不同元素之间转换,所以作者称其为“表达式主导”

 

所以正则:“nfa|nfa not”,目标字符串:“nfa not”中,也只是匹配“nfa”而已,而不会完整的匹配。

 

 

 

DFA (确定型有穷自动机) :文本主导

 

DFA引擎在扫描字符串时,会记录“当前有效”的所有匹配可能。

 

还是最初的例子,引擎移动到“t”时,它会在当前处理匹配可能中添加一个潜在的可能

 

接下来扫描的每个字符,都会更新当前的可能匹配序列。继续扫描两个字符之后的情况如上图。分支“knight”被排除。

 

书中作者称其问文本主导,是因为扫描每个字符的时候都对引擎进行了控制

 

 

 

 

 

测试引擎类型

 

1.如果支持忽略优先量词,那么基本就是传统NFA。DFA不支持忽略优先量词,POSIX NFA中也没有意义。

 

2.DFA不支持捕获型括号和回溯。在这两种混合类型的引擎中,如果没有使用捕获型括号,就会使用DFA

 

ps:在RegexBuddy中似乎只有传统NFA,起码做1的验证时结果是这样的,所以DFA和混合型引擎在这就不做验证了,本文也主要针对java,所以这里指着重介绍和java相关内容

 

 

 

 

 

两条普适原则(来自 《精通正则表达式》 v3)

 

1.优先匹配最左面(最靠开头)的匹配结果

 

注意:此原则并没有规定优先匹配结果的长度,而只是规定在所有可能的匹配结果中,优先选择最左边的(可能有)。

 

作者关于此原则的解释:匹配先从需要查找的字符串的起始位置尝试匹配。这里的“尝试匹配”的意思是:在当前位置测试整个正则表达式能匹配的每个可 能。如果在当前位置测试了所有的可能之后找不到匹配结果,就需要从字符的第二个字符之前的位置开始重新尝试……只有在尝试过所有的起始位置(直到字符串的 最后一个字符)都找不到匹配结果的情况下,才会报告失败。

 

下面给出一个例子:

 

目标字符串“This is a cat.”

 

我想匹配字符“is”,我的正则为“is”

结果如下(图1):

这里找到了两个结果,根据原则1,最先找到的是“this”中的“is”,而并没有找到“is”这个单词。这也很容易理解。下面我们看看RegexBuddy中debug的过程

这里怎么会有这么多字符,目标字符串实际只有13个字符,那么多出来的那些都是哪来的呢?

我觉得,RegexBuddy是把字符与字符之间的位置也算为一个character。再来看看图1

我之所以把每一个字符都装在表格里,就是让大家看的清楚。这里,每一个竖线(其实是不存在的)也作为一个character,我觉得这样是有道理的,比如零宽断言,它的匹配就是在某一个竖线的位置。我们不妨用“^”测试一下,看看debug的结果。

当正则以“字符串起始位置锚点”开头,引擎就会知道如果能匹配,那么肯定是从字符串开头,所以不需要做更多的尝试。

 

ps:这和RegexBuddy上面的debug结果似乎是矛盾的。确实是这样,不知道是不是其一个bug,起码v3.5.4是这样的

 

RegexBuddy暂时是不支持字符组的集合操作的,不知这算功能缺失还是算个bug

 

 

 

 

 

2.标准的量词(*,+,?,{m,n})是匹配优先的

 

目标字符串:“copyright 2003”

 

正则:“.*”,那么匹配的结果为全部字符

正则:“.*[0-9]*”,这个时候,由于量词是匹配优先的,所以“.*”会匹配整个字符串,而后面的“[0-9]*”怎什么也匹配不到 ,这并不影响最终结果,因为“*”表示0个也可以,我们可以添加一组括号来验证这个结果,如下图显示的一样

我们现在将正则改成这样:“.*[0-9]+”,这时候“.*”也会先把字符串全部匹配,之后是“[0-9]+”这个部分,发现它要求至少匹配到一 个数字才行,所以它会强迫“.*”吐出它之前匹配到的内容给自己使用,当“.*”吐出字符“3”之后,“[0-9]+”成功匹配,至此匹配结束,不再进行 其他尝试。

我们来debug看看这一过程:

书中作者总结为:先来先服务。我觉得,也就是说,多个匹配优先量词时,如果目标字符串“不能无法同时满足其需求”,那么写在前面的量词会得到尽量多的字符,后面的量词会像“类似”忽略优先量词一样进行匹配 - 给点就行。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics