# 正则的引擎

正则引擎主要可以分为两大类：一种是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