上一节粗略介绍了回溯，它是NFA特有的功能，DFA不需要回溯，也就不需要保存状态再反复尝试。这样看来，NFA不是更慢吗？但是当前我们所使用的大多数工具中的正则引擎都选用了NFA，这是为什么？
NFA确实更慢，但NFA也有自己的优势：如果正则表达式比较复杂，构建NFA的时间比DFA的时间更短（举例来说，如果你的正则表达式使用了多选分支，那么完全可以直接对每个多选分支构建简单的NFA，再把它们并列起来就可以了；相比之下，构建整个表达式的DFA就复杂多了）。
同时，现代NFA也提供了更多的优化措施，比如之前提到的a(bb)+a的匹配，优化过的NFA可以“并行尝试”，其匹配过程如图所示，这样的速度就快多了。
[图片上传失败...(image-91d320-1545311241772)]
更重要的是，NFA的匹配性质决定了它必须在匹配过程中保存可能的状态，需要“停下来四处看看”，也能够“回顾一路走来的历程”；相比之下，DFA不会两次测试同一个字符，所以不需要保存状态，因此，NFA具有许多DFA无法提供的功能：比如捕获型括号、反向引用、环视功能、忽略优先量词...
如果需要用到这些功能，一定不要选择使用DFA引擎的工具。当谈一般来说，用户并不需要关心引擎是DFA或NFA，毕竟它们是位于“幕后”的，需要关注的只是是否提供了希望实现功能用到的API。
而且，现代的一些工具中，为兼顾效率和功能，同时包含了DFA和NFA两种引擎，如果发现正则表达式中没有专属于NFA的功能，则使用DFA，否则使用NFA。表8-1中列出了各种常用工具使用的正则引擎。
表8-1 常用工具所使用的正则引擎
| 引擎类型 | 程序 |
|---|---|
| DFA | awk（大多数版本）、egrep（大多数版本）、flex、lex、MySql、Procmail |
| NFA | GNU Emacs、java、grep、less、more、.net、python、ruby、php、sed |
细分起来，NFA又分为传统型NFA（Traditional NFA）和POSIX NFA两种。两者点主要区别在于，如果多选分枝中点多个分支都能匹配，传统型NFA优先选择左侧点分枝，而POSIX NFA一定要选择最长的分支。比如用表达式(jeff|jeffrey)匹配字符串jeffrey，POSIX NFA的结果是jeffrey，传统型NFA的结果是jeff——如果调换多选分支的顺序，写成(jeffrey|jeff)，POSIX NFA的结果不变，而传统型NFA的结果变为jeffrey。
问题看起来很复杂，具体使用却比较简单：POSIX NFA的应用很少，主要用于Linux/Unix下的工具（所以它们中的很多并不支持捕获分组），本书中介绍的编程语言基本都采用传统型NFA引擎，遇到多选分支时优先采用最左侧的分支。
网友评论