NFA DFA和正則表達式轉換表

我一直在尋找一些算法，在輸入一個正則表達式或字符串，並將其轉換爲NFA，然後轉換爲DFA，這實際上會打印出轉換表相應的最終DFA。NFA DFA和正則表達式轉換表

因此，我想知道是否已經有一個算法或C或Python庫來做到這一點，或者如果您有使用算法的建議，我可以實現。

謝謝。

2013-10-20 Anoracx

正如你所寫的，你的問題有點過於寬泛/主觀回答：你問你是否應該自己編寫代碼或是否有現有的庫。 Stack Overflow中這些表單的問題在這裏並不合適。你能否更新你的問題以獲得更具體的內容，比如「如何使用庫X來解決這個問題？」或者「什麼算法在這裏最合適？」 – templatetypedef

現在，我問，如果有一個現有的庫，或者如果我應該從頭開始實施，或者（這就是爲什麼我提到湯姆森）如果有人知道我可以實現的算法。但是我修改了一些問題，我希望它更清楚。 – Anoracx

http://projectsgeek.com/2011/05/regular-expression-to-dfa-code-in-c-language.html –

我不確定這些鏈接是否可以幫助您。

第一個提供了Python中非常簡單的NFA/DFA實現，並將NFA轉換爲DFA。它不會從正則表達式生成NFA，但它不是很難做到。第二個網站對NFA和DFA進行了長時間的討論，其中包括大量代碼示例（主要以C語言編寫）以及我所知道的外部庫的鏈接。第三和第四個鏈接提供了第二篇文章作者開發的兩個regex引擎實現的源代碼，包括從正則表達式解析到NFA，然後從NFA轉換到DFA。但請注意，我沒有看過這些項目。

否則，我會提的是最真實的世界正則表達式引擎使用NFA，而不是DFA，因爲一些擴展功能，根本就不能通過DFA執行。因此，如果上面的鏈接都不能幫助你，那麼你可能會看看編譯器編譯器，因爲它們是真正使用DFA的。

來源

2013-10-24 21:47:17 jwatkins

感謝您的幫助，但不幸的是，我查看了鏈接，找不到任何算法打印出相應的最終DFA的狀態表。 – Anoracx

他們可能尚未打印轉換表，但從最終計算的DFA中提取它非常簡單...您只需遍歷每個節點，併爲其分配唯一的順序標識符。然後再次遍歷該圖，並輸出該節點id，即每個轉換的後繼節點的id可能的轉換列表。在您可能檢查的結構中計算DFA確實是更難的部分。 – jwatkins

NFA DFA和正則表達式轉換表

回答

相關問題