生成正則表達式的所有可能匹配

給定一個正則表達式，我想生成該正則表達式匹配的字符串集合。重要的是要注意，這個集合不會是無限的，因爲每個字符串都會有最大長度。是否有任何已知的算法可以做到這一點？是否有任何研究論文可以閱讀，以深入瞭解這個問題？生成正則表達式的所有可能匹配

謝謝。

p.s.這種問題在理論上的cs堆疊交換中會更適合嗎？

2011-07-10 Sam

好了，我們不能投票搬到理論CS，所以你可以標記你的問題，並要求國防部。 – BoltClock

所有可能的字符串都對應於狀態機中以匹配結束的所有可能路徑。但是，這就像是問，給我所有可能的程序長度有限，這與我的程序輸出相匹配。 – gtrak

當你說每個字符串的「最大長度」，你的意思是你的正則表達式不包含任何+或*運算符？ –

在Perl的世界裏，我們有CPAN一個模塊，做到了這一點 - >Regexp::Genex

2011-07-10 21:38:47 average

謝謝。我可以繼續使用該模塊。你是否知道討論如何實現這樣一個模塊的資源？我很好奇它是如何優雅/高效地實現的。 – Sam

只需檢查其源代碼。直觀地說，一個正則表達式是一個自動機，所以一個圖。生成匹配字符串的所有字符串將意味着查找所有路徑，從「開始」節點開始並結束於自動機的「接受」節點，因此它只是表示圖形中的路徑枚舉。 – average

回答