爲什麼這個正則表達式會導致我的正則表達式引擎掛起？

有沒有人有任何想法爲什麼這個正則表達式導致我的應用程序掛起？爲什麼這個正則表達式會導致我的正則表達式引擎掛起？

/^(?:((?:.+?)(?: of the)?)+) of the (?:(.+?)) (?:"(.+?)")$/

它掛起當我嘗試用它來搭配這樣的字符串：

'description of the post "This is a Post"'

但它似乎相當快，當我使用它發生在這樣一個較短的字符串匹配： 'age of the person "Bob"'

關於爲什麼會發生這種情況或我該如何解決它的任何想法？

2012-08-28 Ajedi32

不，但是關於您的系統（語言至少？）的一些信息可能會有所幫助。 – djechlin

我正在使用Ruby 1.9.3，但這個問題似乎發生在任何正則表達式引擎上。 – Ajedi32

的這是catastrophic backtracking在你的正則表達式，你的正則表達式的以下部分結果可能是罪魁禍首：

((?:.+?)(?: of the)?)+

你應該嘗試重構你的正則表達式，每當你有嵌套的重複。在這種情況下，我認爲您可以將整個部分簡化爲.+，並讓您的正則表達式以相同的方式運行。

2012-08-28 16:53:50

是的，我認爲它會是這樣的。你說得對，正則表達式的一部分就是問題。雖然在這種情況下，我認爲將該部分縮短爲「（。+）」不是一個好主意，因爲我在其中有很多其他正則表達式檢查相同的字符串我想避免含糊不清。 – Ajedi32

只要你可以避免嵌套的重複，它應該沒問題，但我肯定會建議使用註釋以避免模糊，而不是增加正則表達式的複雜性。 –

這不是說正則表達式對人類來說是模棱兩可的，我關心的是正則表達式匹配的東西沒有按照我的應用程序預期的方式進行格式化。這就是我含糊不清的意思。 – Ajedi32

這可能是因爲有太多的回溯/分組，因此需要花費很多時間來分析較大的字符串。

正如你可以在演示中看到：http://regex101.com/r/xC3dF0，系統無法解析字符串由於大量回溯

2012-08-28 16:45:23 Ankur

哦，現在這是一個有用的外觀網站。 – Ajedi32

回答