精通正则表达式_精通正则表达式 第4版_精通正则表达式 mobi

这一篇就重点讲解正则表达式的核心——正则引擎。

1、正则引擎

正则引擎主要可以分为基本不同的两大类：一种是DFA（确定型有穷自动机），另一种是NFA（不确定型有穷自动机）。DFA和NFA都有很长的历史，不过NFA的历史更长一些。使用NFA的工具包括.NET、PHP、Ruby、Perl、Python、GNU Emacs、ed、sec、vi、grep的多数版本，甚至还有某些版本的egrep和awk。而采用DFA的工具主要有egrep、awk、lex和flex。也有一些系统采用了混合引擎，它们会根据任务的不同选择合适的引擎（甚至对同一表达式中的不同部分采用不同的引擎，以求得功能与速度之间的平衡）

NFA和DFA都发展了很多年了，产生了许多不必要的变体，结果，现在的情况比较复杂。POSIX标准的出台，就是为了规范这种现象，POSIX标准清楚地规定了引擎中应该支持的元字符和特性。精通正则表达式除开表面细节不谈，DFA已经符合新的标准，但是NFA风格的结果却与此不一，所以NFA需要修改才能符合标准。这样一来，正则引擎可以粗略地分为三类：DFA；传统型NFA；POSIX NFA。

我们来看使用`to(nite|knight|night)`来匹配文本‘…tonight…’的一种办法。正则表达式从我们需要检查的字符串的首位（这里的位置不是指某个字符的位置，而是指两个相邻字符的中间位置）开始，每次检查一部分（由引擎查看表达式的一部分），同时检查“当前文本”（此位置后面的字符）是否匹配表达式的当前部分。如果是，则继续表达式的下一部分，如果不是，那么正则引擎向后移动一个字符的位置，继续匹配，如此继续，直到表达式的所有部分都能匹配，即整个表达式能够匹配成功。在此例子中，由于表达式的第一个元素是`t`，正则引擎将会从需要匹配的字符串的首位开始重复尝试匹配，直到在目标字符中找到‘t’为止。之后就检查紧随其后的字符是否能由`o`匹配，如果能，就检查下面的元素。下面是`nite`或者`knight`或者`night`。引擎会依次尝试这3种可能。尝试`nite`的过程与之前一样：“尝试匹配`n`，然后是`i`，然后是`t`，最后是`e`”。如果这种尝试失败，引擎就会尝试另一种可能，如此继续下去，直到匹配成功或是报告失败。表达式的控制权在不同的元素之间转换，所以我们可以称它为“表达式主导”。

从它们匹配的逻辑上我们不难发现：一般情况下，文本主导的DFA引擎要快一些。正则表达式主导的NFA引擎，因为需要对同样的文本尝试不同的子表达式匹配，可能会浪费时间。在NFA的匹配过程中，目标文本的某个字符可能会被正则表达式反复检测很多遍（每一个字符被检测的次数不确定，所以NFA叫做不确定型有穷自动机）。精通正则表达式相反，DFA引擎在匹配过程中目标文本中的每个字符只会最多检查一遍（每个字符被检测的次数相对确定，所以DFA叫做确定型有穷自动机）。由于DFA取得一个结果可能有上百种途径，但是因为DFA能够同时记录它们，选择哪一个表达式并无区别，也就是说你改变写法对于效率是没有影响的。而NFA是表达式主导，改变表达式的编写方式可能会节省很多功夫。

所以后面我们讲解的知识都是涉及的NFA的。

2、回溯

现在应该知道回溯其实就是引擎在匹配字符串的过程中出现多选的情况，当其中一种选择无法匹配时再次选择另种的过程叫做回溯。其实我们在优化正则表达式的时候就是考虑的尽量减少回溯的次数。

2.1回溯匹配优先和忽略优先

《精通正则表达式》这本书里面叫做匹配优先和忽略优先，网上有很叫做贪婪模式和非贪婪模式，反正都一样，叫法无所谓。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-22527-1.html