爲什麼Python在這個正則表達式中扼殺？

Question

這看起來像一個簡單的正則表達式，沒有反向引用，沒有「任何」字符，我甚至不敢說湯姆森DFA和所有人都可以解析它。它甚至可以工作，但扼殺非常簡單的不匹配。

{\s*? 
ngx_string\("(?P<name>[a-z0-9_]+)"\)\s*?,\s*? 
(?P<where>(([A-Z0-9_]+)\s*\|?)+?)\s*?,\s*? 
(?P<bla>[^\n}]+?)\s*?,\s*? 
(?P<bla2>[^\n}]+?)\s*?,\s*? 
(?P<bla3>[^\n}]+?)\s*?,\s*? 
(?P<bla4>[^\n}]+?)\s*? 
} 

+ re.MULTILINE | re.VERBOSE 

runnable gist here

我目前正在嘗試這種關於Python 2.7.8（但py3.4鏈接的要點也失敗了;還有的linux，X86-64，Ubuntu的，PCRE靜態鏈接中的[在最少/ proc //地圖不顯示任何有趣的東西）。

這解析得好：

{ ngx_string("daemon"), 
    NGX_MAIN_CONF|NGX_DIRECT_CONF|NGX_CONF_FLAG, 
    ngx_conf_set_flag_slot, 
    0, 
    offsetof(ngx_core_conf_t, daemon), 
    NULL }, 

而這其中的樂趣停止：

{ ngx_string("off"), NGX_HTTP_REQUEST_BODY_FILE_OFF }, 
{ ngx_string("on"), NGX_HTTP_REQUEST_BODY_FILE_ON }, 

此外，越來越多的數據：

通過改變第二行此

(?P<where>(([A-Z0-9_]{1,20})\s*\|?){1,6}?)\s{0,10}?,\s{0,10}? 

，它最終完成在合理的時間，但指數炸燬仍然存在，只是可以忍受的：（？模擬器）

trying  { ngx_string("off"), NGX_HTTP_REQUEST_BODY_FILE 
Took 0.033483 s 
trying  { ngx_string("off"), NGX_HTTP_REQUEST_BODY_FILE_ 
Took 0.038528 s 
trying  { ngx_string("off"), NGX_HTTP_REQUEST_BODY_FILE_O 
Took 0.044108 s 
trying  { ngx_string("off"), NGX_HTTP_REQUEST_BODY_FILE_OF 
Took 0.053547 s 

而且，有趣的是基於JS-Python的正則表達式解析器可以吃它，喜歡它的早餐PCRE冠軍：https://www.debuggex.com/r/S__vSvp8-LGLuCLQ

哦，也許有人應該創建pathological-regex標籤：

Answer 1

問題是(([A-Z0-9_]+)\s*\|?)+?在您的原始正則表達式或(([A-Z0-9_]{1,20})\s*\|?){1,6}?在您的測試正則表達式。 {1,20}和{1,6}僅用於抑制指數回溯。

由於\s*和\|?是可選的，正則表達式可以擴展到的指數回溯(([A-Z0-9_]+))+?當輸入包含了經典的例子僅[A-Z0-9_]沒有空格或酒吧|，但沒有正則表達式的其他部分相匹配。

AAAAAAAAAAAAAA 
AAAAAAAAAAAAA A 
AAAAAAAAAAAA AA 
AAAAAAAAAAAA A A 
AAAAAAAAAAA AAA 
... 
A AAAAAAAAAAAAA 
A AAAAAAAAAAAA A 
A AAAAAAAAAAA AA 
... 
A A A A A A A A A A A A A A 

：

例如，匹配(?P<where>(([A-Z0-9_]+)\s*\|?)+?)\s*?,\s*?針對AAAAAAAAAAAAAA（,缺失）將導致發動機檢查分裂串起來的所有可能性，每一個令牌在所述外重複的不同迭代匹配仔細一看，其餘的正則表達式也存在過度的回溯問題。

以(?P<bla2>[^\n}]+?)\s*?,\s*?爲例。 [^\n}]可以匹配一個空格（或一個製表符或多個其他空格字符），因此可以使用\s。如果您的不匹配輸入包含一長串空格，這可能會導致過度的回溯。也可能存在正確性問題，因爲,也可以被[^\n}]匹配。

在附註上，Python re是一個NFA引擎，沒有任何優化來緩解指數回溯問題。

爲了減輕指數回溯：

{\s* 
ngx_string\("(?P<name>[a-z0-9_]+)"\)\s*,\s* 
(?P<where>[A-Z0-9_]+(?:\s*\|\s*[A-Z0-9_]+)*)\s*,\s* 
(?P<bla>[^\n}]+?)\s*,\s* 
(?P<bla2>[^\n}]+?)\s*,\s* 
(?P<bla3>[^\n}]+?)\s*,\s* 
(?P<bla4>[^\n}]+?)\s* 
} 

與[^\n}]過度回溯和正確性的問題仍然沒有解決。如果參數不在不同的行上，函數調用中的,可能會被錯誤地識別爲外部塊{}的一部分。

一般的解決方案需要遞歸正則表達式，因爲您可以調用函數來將其結果作爲參數傳遞，例如， offsetof(ngx_core_conf_t, daemon)，但遞歸正則表達式功能在re包中不可用。一個不太一般的解決辦法是匹配嵌套括號的一些級別，例如1級嵌套：

(?P<bla>(?:\([^)]*\)|[^,()])+),\s* 

而且整個正則表達式是：

{\s*? 
ngx_string\("(?P<name>[a-z0-9_]+)"\)\s*,\s* 
(?P<where>[A-Z0-9_]+(?:\s*\|\s*[A-Z0-9_]+)*)\s*, 
(?P<bla>(?:\([^)]*\)|[^,()])+),\s* 
(?P<bla2>(?:\([^)]*\)|[^,()])+),\s* 
(?P<bla3>(?:\([^)]*\)|[^,()])+),\s* 
(?P<bla4>(?:\([^)]*\)|[^,()])+) 
} 

DEMO

有2注意事項：

• <bla*>捕獲組將在 結束。如果你想刪除空格，則正則表達式會更長一點，和可以防止可能的過度回溯。您可以嘗試在,之前將\s*加回this demo here。
• 它假設()不是任何字符串文字的一部分。

Answer 2

(?P<where>(([A-Z0-9_]+)\s*\|?)+?) 
        ^ ^

這是你的正則表達式爆炸的地方。閱讀http://www.regular-expressions.info/catastrophic.html。

每次失敗都會返回一步來檢查是否存在匹配。這爲正則表達式引擎創建了一系列步驟和可能性。