正則表達式：確定兩個正則表達式是否可以匹配相同的輸入？

我想知道兩個已知的正則表達式之間是否存在衝突，以允許用戶構造互斥的正則表達式列表。正則表達式：確定兩個正則表達式是否可以匹配相同的輸入？

例如，我們知道，下面的正則表達式有很大的不同，但它們都匹配xy50：

'^xy1\d' 
'[^\d]\d2$'

是否有可能來確定，使用計算機算法，如果兩個正則表達式能有這樣的衝突？怎麼樣？

來源

2010-08-04 Tom

我有一個偷偷摸摸的懷疑，這個問題相當於停機問題。 – 2010-08-04 22:15:40

@Seamus Campbell：極好的一點！這是停止問題的氣味嗎？如果不是，那麼它如何實施？ – Tom 2010-08-04 22:17:45

對此的另一種思考方式是...... 爲什麼不添加到用戶的正則表達式中，從而使正則表達式相互排斥？也就是說最後確定它與前一個不一樣這有幫助嗎？ – MikeG 2010-08-04 22:20:36

這裏沒有涉及停機問題。您只需要計算非空的交點^xy1\d和[^\d]\d2$。

我不能給你一個在這裏的算法，但這裏有一個方法的兩個討論產生交集，而不訴諸一個DFA的建設：

然後是RAGEL

http://www.complang.org/ragel/

它也可以計算正則表達式的交集。

更新：我剛剛用OP的正則表達式嘗試過Ragel。 Ragel可以從生成的狀態機中爲graphviz生成一個「點」文件，這非常棒。在OP的正則表達式的交集看起來像這樣在Ragel語法：

('xy1' digit any*) & (any* ^digit digit '2')

，並具有以下狀態機：

雖然空交集：

('xy1' digit any*) & ('q' any* ^digit digit '2')

樣子這個：

因此，如果都失敗，那麼你仍然可以通過比較生成的「點」文件來讓Ragel計算交集並檢查它是否輸出空狀態機。

來源

2010-08-04 22:29:52

+1表示工作的例子！ – 2010-08-05 00:21:10

有點遲，要添加這個，但一個簡單的證明是這樣工作的：在將第二個的相交補碼與第一個相加之後，可以通過嘗試所有字母組合來測試它是否爲非空字母表中的字符數量與您FSM中的狀態數量相同。其餘部分僅僅是抽水引理，因爲FSM中的狀態數量是抽水限制的簡單上限。 – Whoopska 2011-07-30 19:56:09

@Whoopska：這聽起來不像一個非常有效的方法... – 2014-07-10 11:12:12

這個問題可以重申爲「兩種或更多規則表達式描述的語言是否具有非空的相交」？

如果你限制的問題純正則表達式（無反向引用，前瞻，回顧後，或其他功能，使識別上下文無關的或更復雜的語言），問題是至少可判定的。常規語言在十字路口下關閉，並且有一種算法將兩個正則表達式作爲輸入，並在有限時間內生成識別交叉點的DFA。

每個正則表達式都可以轉換爲非確定型有限自動機，然後轉換爲確定型有限自動機。一對DFA可以被轉換爲識別交集的DFA，即。如果有從開始狀態到最終DFA的任何接受狀態的路徑，則該交集非空（使用您的術語爲「衝突」）。

不幸的是，將初始NFA 轉換爲DFA時可能會出現指數式的放大，因此在實際中，隨着輸入表達式增長的大小，問題很快就變得不可行。

如果允許純正則表達式的擴展，所有的投注都關閉 - 這樣的語言在交集之下不再關閉，所以這個構造不會在下工作。

來源

2010-08-04 22:29:50

是的我認爲這是可以解決的：與其將正則表達式視爲匹配字符串，您還可以將它們視爲生成字符串。也就是說，他們會匹配的所有字符串。假設[R]是由正則表達式R生成的字符串集合。然後給定正則表達式R和T，我們可以嘗試將T與[R]匹配。如果[R]中有一個與T匹配的字符串，則[R]與T相匹配。

應該可以將此開發爲一種算法，其中[R]按需延遲構建：其中正常的正則表達式匹配嘗試匹配輸入字符串中的下一個字符，然後前進到字符串中的下一個字符，修改後的算法將檢查對應於輸入正則表達式的FSM是否可以在當前狀態下生成匹配字符，然後前進到「全部下一個國家「同時。

來源

2010-08-04 22:34:46 michid

我不太明白。但是他們再次匹配的字符串列表可能是無限的......另外，試圖將T與[R]匹配是關鍵。你的算法需要更好地定義imho。 – jjmontes 2016-05-31 00:03:33

另一種方法是改用Dan Kogai的Perl Regexp::Optimizer。

use Regexp::Optimizer; 
    my $o = Regexp::Optimizer->new->optimize(qr/foobar|fooxar|foozap/); 
    # $re is now qr/foo(?:[bx]ar|zap)/

..首先，優化，然後丟棄所有冗餘模式。

也許Ron Savage的Regexp::Assemble可能會更有幫助。它允許將任意數量的正則表達式組裝成單個正則表達式，以匹配單個RE匹配的所有單個正則表達式。*或兩者的組合。

_{*但是，您需要了解Perl和Java或其他PCRE風味之間的一些差異。}

來源

2018-01-27 07:28:17 wp78de

正則表達式：確定兩個正則表達式是否可以匹配相同的輸入？

回答

相關問題