amarant 发表于 2016-11-01 08:58

grep 使用 NFA 为什么效率高

龙书中提到，grep为了效率，使用了 NFA 算法。
NFA 匹配正则的效率不是比 DFA 更慢吗？
这么说的原因是什么，我哪里没理解正确，请各位兄弟指教。

codechurch 发表于 2016-11-01 18:21

dfa只是正则的子集，能力太弱。

amarant 发表于 2016-11-02 16:42

回复 2# codechurch

正则直接转成NFA比较容易。我理解，每一个NFA都可以转换成DFA。在转换成DFA后，再做匹配，效率就会提高很多。
我这个思路错在哪里了？请赐教，谢谢

codechurch 发表于 2016-11-02 18:44

回复 3# amarant

并非所有nfa都可以转为dfa，正则的全集就不能转为dfa
dfa只能包括*+| 的功能
像 “{，}” 与 后向引用等等功能，都不可能做到。


amarant 发表于 2016-11-02 21:02

回复 4# codechurch

多谢

captivated 发表于 2016-11-07 18:09

回复 4# codechurch

^_^，你这说的是 Unix 传统正则语言(或者说扩展正则)。按照编译书籍上严格的正则语言定义，正则语言(就是去掉 Unix 扩展正则的)和NFA DFA等价且可以相互转换的。
你说那个引用的问题，NFA 也是不能解决的，得用递归。
不过实际上的正则库实现来说，我认为没有必要死守编译理论，非把正则识别等同于构造 NFA DFA 来实现。

cjaizss 发表于 2017-02-04 16:11

codechurch 发表于 2016-11-02 18:44
回复 3# amarant

并非所有nfa都可以转为dfa，正则的全集就不能转为dfa


{,}可以转化为DFA
而后向引用当然不可以,因为它已经不是正则语言范畴
页: [1]
查看完整版本: grep 使用 NFA 为什么效率高