如何判斷正則表達式實現是否使用DFA或NFA？

我面臨的問題是，某個regex implementation是基於DFA還是NFA。如何判斷正則表達式實現是否使用DFA或NFA？

我明白這一點的出發點是什麼。也可以問：我在找什麼？什麼是基本模式和/或特徵？一個很好的解釋性鏈接或者一點比較（即使不直接用於正則表達式）也是非常好的。

來源

2011-11-25 Jan

請考慮發佈在http://cstheory.stackexchange.com/上。 –

我覺得你的行話有點倒退。 NFA有多個執行路徑的可能性，所以它們是需要回溯的。回溯不會對DFA有任何好處，因爲它只能以一種方式播放。 – phs

http://lambda.uta.edu/cse5317/notes/node9.html也可能與您的興趣相關。評估一個規則的NFA將需要算法保存一組狀態（回溯軌跡），其中DFA評估器將始終保持一個自動機狀態。 – phs

我認爲你的意思是「正則表達式實現」而不是算法（通常意義上的）。

您可以使用已知的表達式來測試已知會導致一種方法或另一種方法出現問題的表達式。同時尋找更容易在其中一個或另一箇中實現的功能（這不是一種可靠的方法 - 正則表達式引擎的開發人員可以找到新的方法來實現以前的難題）。

通常情況下，答案是閱讀文檔或查看已知參考文獻（"Mastering Regular Expressions"文檔中的許多常見情況）。最後爲什麼不問作者？

來源

2011-11-25 11:03:55 Richard

我會接受這個答案，因爲有明顯的建議要問作者。我甚至都沒有想過:) Pete Kirkham的回答也非常有價值。 – Jan

如果是黑匣子，那麼給它一些輸入，並用病理案例測量它的時間特徵，參照圖表in this discussion of NFS vs backtracking regex implementations。（注意NFS圖是微秒而不是秒）。另外，如果它是一個純粹的NFA，那麼它不會有一些不規則的特徵，它們是一些「正則表達式」解析器，它們需要回溯。

或者，查看RxParser類的文檔;文檔似乎在Web上不可用，並且需要吱吱聲運行時才能瀏覽。

來源

2011-11-25 13:12:29

如何判斷正則表達式實現是否使用DFA或NFA？

回答

相關問題