亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

Chinaunix

標(biāo)題: grep 使用 NFA 為什么效率高 [打印本頁]
作者: amarant    時(shí)間: 2016-11-01 08:58
標(biāo)題: grep 使用 NFA 為什么效率高
龍書中提到，grep為了效率，使用了 NFA 算法。
NFA 匹配正則的效率不是比 DFA 更慢嗎？
這么說的原因是什么，我哪里沒理解正確，請(qǐng)各位兄弟指教。

作者: codechurch    時(shí)間: 2016-11-01 18:21
dfa只是正則的子集，能力太弱。
作者: amarant    時(shí)間: 2016-11-02 16:42
回復(fù) 2# codechurch

正則直接轉(zhuǎn)成NFA比較容易。我理解，每一個(gè)NFA都可以轉(zhuǎn)換成DFA。在轉(zhuǎn)換成DFA后，再做匹配，效率就會(huì)提高很多。
我這個(gè)思路錯(cuò)在哪里了？請(qǐng)賜教，謝謝
作者: codechurch    時(shí)間: 2016-11-02 18:44
回復(fù) 3# amarant

并非所有nfa都可以轉(zhuǎn)為dfa，正則的全集就不能轉(zhuǎn)為dfa
dfa只能包括  *+| 的功能
像 “{，}” 與 后向引用等等功能，都不可能做到。


作者: amarant    時(shí)間: 2016-11-02 21:02
回復(fù) 4# codechurch

多謝
作者: captivated    時(shí)間: 2016-11-07 18:09
回復(fù) 4# codechurch

^_^，你這說的是 Unix 傳統(tǒng)正則語言(或者說擴(kuò)展正則)。按照編譯書籍上嚴(yán)格的正則語言定義，正則語言(就是去掉 Unix 擴(kuò)展正則的)和NFA DFA等價(jià)且可以相互轉(zhuǎn)換的。
你說那個(gè)引用的問題，NFA 也是不能解決的，得用遞歸。
不過實(shí)際上的正則庫(kù)實(shí)現(xiàn)來說，我認(rèn)為沒有必要死守編譯理論，非把正則識(shí)別等同于構(gòu)造 NFA DFA 來實(shí)現(xiàn)。

作者: cjaizss    時(shí)間: 2017-02-04 16:11
codechurch 發(fā)表于 2016-11-02 18:44
回復(fù) 3# amarant

并非所有nfa都可以轉(zhuǎn)為dfa，正則的全集就不能轉(zhuǎn)為dfa

{,}可以轉(zhuǎn)化為DFA
而后向引用當(dāng)然不可以,因?yàn)樗呀?jīng)不是正則語言范疇




歡迎光臨 Chinaunix (http://72891.cn/) Powered by Discuz! X3.2