Java RegularExpressions上的「StackOverflowError」是否意味着優化Regex？

Pattern csvline = Pattern.compile("((([^\\\"]|\\\"\\\")+|\\\"([^\\\"]|\\\"\\\")+\\\"))*", Pattern.DOTALL);

這個表達式傳遞this online Regex test。但是，在運行時總是會拋出StackOverflowError。

經過一番研究，我找到了解決辦法是

Pattern csvline = Pattern.compile("((([^\\\"]|\\\"\\\")++|\\\"([^\\\"]|\\\"\\\")++\\\"))*", Pattern.DOTALL);

這裏我用的佔有慾量詞，而不是貪心的孩子來代替表達。在這種情況下，它也是一種優化。

我的問題是，是因爲Java不能處理很多回溯（它消耗堆棧空間，我認爲這是一個好的引擎不應該這樣），所以任何時候當你看到由正則表達式引起的StackOverflowError時，你應該考慮優化以減少回溯？

只是好奇......這個正則表達式支持像'word1，word2，'word3和word4''嗎？ – 2013-02-21 06:17:22

爲什麼你需要附加的括號？相同的正則表達式：'（（[^ \\\「] | \\\」\\\「）+ | \\\」（[^ \\\「] | \\\」\\\「）+ \ \\「）*' – pstr 2013-02-21 06:22:51

@OscarMederos是的，這只是故事的一部分。這個表達只是爲了確定當前線路是「真實」線路的一部分。如果引用字段包含換行符，則「當前」行將需要與以下行結合使用。所以該算法是在進行額外處理之前重建整條線。 – 2013-02-21 21:35:37

java throwing StackOverflowError表明匹配是通過遞歸調用在內部完成的。這很糟糕，但也有其自己的好處，因爲它表明了您的正則表達式的潛在問題。 ((A+|B))*（這是你的正則表達式的形式）：

回溯地獄是你做的有限多個匹配+內的另一個有限多個匹配*的事實引起的。

通常，如果您可以編寫一個不需要回溯且不需要堆棧的非正則表達式解決方案（如括號匹配問題），那麼您可以使用所有格量詞來編寫正則表達式（在添加額外的+之後正常量詞）執行相同的任務，因爲所有格量詞不會（允許）回溯，這與您在非正則表達式解決方案中所做的相似。

2013-02-21 06:35:53 nhahtdh

這是我上面提出的索賠的示例：http://stackoverflow.com/a/14811222/1400768。問題的關鍵在於檢查一個句子是否是整個句子的子序列，以一個詞的粒度（詞的順序必須遵循，但詞不需要構成整個句子的連續部分）。 – nhahtdh 2013-02-21 06:57:33

是的Java正則表達式引擎壞了。它使用回溯，因此它可以支持反向引用，並因此具有與所有類似perl的正則表達式引擎相同的病態指數空間/時間問題。你是對的，它可能潛在地分析表達式以確定它實際上是規則的，並使用你期望的多項式空間/時間算法。

在這種情況下，我總是建議使用級聯正則表達式，最好通過JFlex，儘管如果你堅持2或3級，手動做它們不會太痛苦。除此之外，如果您使用詞法分析器，它的可維護性和編寫和調試將更加容易。

這個想法是，你通過重複應用簡單的正則表達式來分析這一行。在你的情況下，第一個標識下一個字段的開始;第二個標識字段的結尾（捕獲內容）;第三次檢查'下一場';重複。

這些幾乎與您使用JFlex識別的3個標記幾乎相同，區別在於字段分隔符令牌非常簡單，您可能在手動執行時將其包含在「字段結束」正則表達式中。

2013-02-21 06:47:50 Recurse

回答