正则的引擎

正则引擎主要可以分为两大类：一种是DFA，一种是NFA。

• NFA表达式主导

• DFA文本主导

一般而论，DFA引擎则搜索更快一些。但是NFA以表达式为主导，更容易操纵，因此一般程序员更偏爱NFA引擎！

两种引擎各有所长，而真正的引用则取决与你的需要以及所使用的语言！

是否支持忽略优先量词和分组捕获？

• NFA 支持

• DFA 不支持

使用DFA引擎的程序主要有：

awk,egrep,flex,lex,MySQL,Procmail等；

使用传统型NFA引擎的程序主要有：

GNU Emacs,Java,ergp,less,more,.NET语言,PCRE library,Perl,PHP,Python,Ruby,sed,vi；

回溯

NFA引擎，最重要的性质就是它依次处理各个自表达式，遇到需要在两个可能成功的可能中进行选择的时候，他会选择其一同时记住另一个，以备稍后可能的需要。

回溯就像是在道路的每个分岔口留下一小堆面包屑。

如果需要在“进行尝试”和“跳过尝试”之间选择，对于匹配优先量词，引擎会优先选择“进行尝试”，而对于忽略优先量词，会选择“跳过尝试”。

距离当前最近储存的选项就是当本地失败强制回溯时返回的。使用的原则是LIFO。

回溯是NFA的灵魂。

示例

• ab.*lmn 匹配 abcdefghijklmn

• ab.*?lmn 匹配 abcdefghijklmn

• ab??c 匹配 abc