为什么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。

每次失败都会返回一步来检查是否存在匹配。这为正则表达式引擎创建了一系列步骤和可能性。