本文共 1437 字,大约阅读时间需要 4 分钟。
-- Start
虽然支持正则表达式的工具有很多,但在这些工具的背后都是使用以下两种引擎之一来解析字符串。不同的引擎支持的元字符及工作原理是不同的,下面我们看看它们的工作原理。
我们用表达式 reg(ress|ular) 匹配文本 I love regular expressions,NFA 引擎从表达式 r 开始,检查当前表达式 r 是否和当前文本 I 匹配,如果不匹配,指针向后移一位,当前文本变为空格,再次检查当前表达式与当前文本是否匹配,如此反复尝试。如果指针移动到文本末尾时,仍然无法匹配,则报告匹配失败。如果像本例这样遇到多选分支该怎么办呢?引擎会在分支开始前保存当前指针的位置,然后依次尝试每一个分支,如果分支没有匹配成功,则指针首先回退到最近的保存位置(我们把这一过程称为回溯),然后尝试下一个分支,如果某一个分支匹配成功,则剩余的分支将不再尝试。所以有时候分支的顺序特别重要。Never ever 不要写出类似下面的表达式。
\d*|\w 此表达式的第二个分支永远也得不到尝试的机会,因为第一个分支总是能够匹配成功,考虑调换分支顺序
love|love regular 如果第一个分支能够匹配,那么第二个分支将得不到尝试的机会;如果第一个分支不能匹配,第二个分支也肯定不能匹配。考虑调换分支顺序
如果用 exp|reg|lov 来匹配上面的文本 I love regular expressions,会得到什么结果呢?如果你知道了答案,说明你看懂了上面的原理。
我们用表达式 love|love regular 匹配文本 I love regular expressions,DFA 引擎会记录当前所有可能的匹配,随着指针向右移动,不能匹配的分支被淘汰出局,最后只剩下唯一的分支。本例中匹配的是love regular,显然匹配的结果和分支的顺序没有任何关系,无论分支的顺序如何,结果总是能够匹配的分支中最长的那一个。由此可知,对于同样的表达式love|love regular,NFA 和DFA引擎会得到不同的结果,事实上,我们可以通过这个表达式来判断引擎的类型。
对于目标文本的每一个字符,DFA 引擎最多只检查一遍,而 NFA 则有可能需要回溯。显然 DFA 要更快一些,但是 DFA 也有致命伤,它不支持非贪婪量词和捕获型括号。所以目前大部分工具都是使用 NFA 作为正则引擎。
由于 NFA 具有表达式主导的特性,通过改变表达式的编写方式,我们可以对表达式进行多方面的控制,一个好的表达式能给我们带来很多收益,一个差的表达式将严重影响性能,甚至是内存溢出,而它们之间的差别就在一念之间。
--更多参见: -- 声 明:转载请注明出处 -- Last Updated on 2012-05-26 -- Written by ShangBo on 2012-05-21 -- End