檢測正則表達式是否呈指數形式

Question

這個article表明回溯時存在一些正則表達式O（2^n）。 示例爲(x+x+)+y。 當試圖匹配像xxxx ... p這樣的字符串時，它會先回溯一段時間，然後找出它無法匹配的地方。

有沒有辦法檢測這樣的正則表達式？

感謝

Answer 1

如果你的正則表達式引擎公開運行時的指數行爲（X + X +）+ Y，那麼它是破因爲DFA或NFA能夠識別在線性時間內這種格局：

echo "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" | egrep "(x+x+)+y" 
echo "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxy" | egrep "(x+x+)+y" 

都立即回答。

事實上，也有隻在真正需要回溯少數情況下（如反向引用）（主要是因爲向引用一個正則表達式是不在語言理論意義上的正則表達式了）。一個有能力的實現應該只在給出這些角落案例時切換回溯。在公平性方面，DFA也有一個陰暗面，因爲一些正則表達式具有指數大小的要求，但是大小限制比時間限制更容易實施，而且巨大的DFA在輸入上線性運行，所以它比一個更好的討價還價一個小型backtracker窒息了幾個X的。

你應該真的閱讀拉斯考克斯出色的系列文章中有關正則表達式的實現（和回溯的病態行爲）：http://swtch.com/~rsc/regexp/

要回答你的問題有關可判定：不能。因爲沒有一個 backgracking正則表達式。每種實現都有自己的策略來處理在某些情況下算法的指數級增長，並且不包含其他策略。一條規則可能適合這裏，對於那裏來說是災難性的。

UPDATE：

例如，一個實施方式可以包含一個優化器，其可以用代數變換執行它們之前以簡化的正則表達式：(x+x+)+y是相同的一個xxx*y，其不應該是任何backtracker的問題。但同樣的優化器不會識別下一個表達式，並且問題再次出現。這裏有人描述瞭如何製作這傻瓜Perl的優化器regexpr：

http://perlgeek.de/blog-en/perl-tips/in-search-of-an-exponetial-regexp.html

Answer 2

不，我不這麼認爲，但您可以使用這些準則：如果它包含兩個量詞是開放式的，在高端

• 和它們嵌套則可能是 O（2^n）。
• 如果它不包含兩個這樣的量詞，那麼我認爲它不能是O（2^n）。

量詞可能導致此有：*，+和{k,}。

另請注意，評估正則表達式的最壞情況複雜度可能與典型字符串的複雜度非常不同，並且複雜程度取決於特定的正則表達式引擎。

Answer 3

沒有反向引用的任何正則表達式可以在線性時間相匹配，儘管許多正則表達式引擎赫然出現在現實世界中不那樣做， （至少有很多插入編程語言運行時環境的正則表達式引擎支持反向引用，並且在沒有反向引用時不會切換到更高效的執行模式）。

有沒有簡單的方法來找出多少時間與反向引用的正則表達式將消耗。

Answer 4

您可以使用正則表達式解析器來檢測和拒絕嵌套重複，其對應的star height爲1.我剛剛使用npm的正則表達式解析器編寫了a module to compute and reject start heights of >1。

$ node safe.js '(x+x+)+y' 
false 
$ node safe.js '(beep|boop)*' 
true 
$ node safe.js '(a+){10}' 
false 
$ node safe.js '\blocation\s*:[^:\n]+\b(Oakland|San Francisco)\b' 
true