正則表達式算法

給定一個子字符串，是否有一種方法可以生成所有可能的正則表達式（對於最小限制性的限制最多），以匹配給定字符串的子字符串？正則表達式算法

例如，假設您有一個子字符串「orange」和一個字符串「apple banana orange grape」。我如何得到一個匹配「橙色」的正則表達式列表（我知道會有很多，希望有一個庫可以爲我做這個）。

2010-09-18 StackOverflowNewbie

有很多「很多」，有任何目標字符串的正則表達式無限數量。一個簡單的例子是：「橙色」，「。*橙色」，「。*橙色。*」，「。*。*橙色。*。*」等等。你應該澄清你的問題，請解釋你的最終目標是什麼。 – 2010-09-18 12:39:41

即使'（任何可能的正則表達式）？橙色（任何possibe正則表達式）？' – 2010-09-18 12:45:51

這與詢問「給定一些運行時要求，是否有一種方法可以生成所有可能的程序（效率最低至效率最低）匹配給定輸入的要求相同？」答案是是的，有一個的方式這樣做，但結果的數量是無限的，只受限於合理的內存和語言實現的限制，所以你需要對什麼構成一個有效的「程序」用於你的目的，以便將其縮減爲一個有限集合。

例如，你可以限制自己特定的語法，排序，代表有問題的正則表達式語言的一個子集，並僅生成正則表達式匹配的語法：

 
Regex  ::= StartAnchor? Anything? (Substring | Anything) Anything? EndAnchor? 

StartAnchor ::= "^" 

Anything ::= ".*" 
       | "(.*)" 

Substring ::= "orange" 
       | "(orange)" 

EndAnchor ::= "$"

遞歸採取的所有路徑這個語法（即每個分支由?和|表示）生成所有目標正則表達式。當然，這個答案故意沒有說這樣做是否是一個好主意，或者根本不需要...

來源

2010-09-18 13:19:15

'這基本上與詢問「.....」'相同嗎？這不是一回事，也不可行。如果我誤解了你，請解釋你的意思。 – 2014-01-12 10:29:47

正則表達式算法

回答

相關問題