为什么Python会被这个正则表达式噎住？

Question

这看起来像一个简单的正则表达式，没有反引用，没有“any”字符，我甚至敢说它可以被Thomson 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

我目前正在Python2.7.8上尝试这一点（但是链接的gist在py3.4上也失败了；另外linux、x86-64、Ubuntu、PCRE在[least/proc//maps中静态链接也没有显示任何有趣的内容）。你知道吗

这很好地解释了：

{ 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 regex（仿真器？）解析器可以把它当作PCRE冠军的早餐来吃：https://www.debuggex.com/r/S__vSvp8-LGLuCLQ

哦，也许有人应该创建一个病理正则表达式标签：|

Answer 1

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

这就是你的正则表达式爆炸。读http://www.regular-expressions.info/catastrophic.html。你知道吗

每次失败时，它都会返回一步以检查是否存在错误匹配。这个正在为regex引擎创建大量的步骤和可能性。你知道吗