在某些情况下，使用递归回溯的正则表达式实现可能会表现出指数运行时间。
我正在尝试为 PCRE 引擎找到这样一个病态的正则表达式。
我已经尝试了几个正则表达式，已知它们对于 Perl 正则表达式（例如这个）是指数的，但在我的测试中，它们都没有表现出 PCRE 的指数运行时间。
问问题
291 次
1 回答
3
在您的测试中，是否所有的正则表达式都会失败？当他们确实失败时，你有没有找到确切的原因？也许匹配失败是因为正则表达式引擎检测到过多的回溯。我不知道这是否会发生，但尝试一个应该成功的正则表达式，比如这个：
(?i)lorem(?:.|\s)*pri\.
使用 RegexBuddy，我将该正则表达式应用于下面文本的第一段，并按预期突出显示了整个段落。当我删除段落末尾的句点时，突出显示消失了，调试器说它已经放弃了一百万次操作。这并不奇怪，但是当我把句号放回去并添加第二段时，它仍然失败了——再次回溯太多。
Lorem ipsum tritani impedit civibus ei pri，legimus antiopam no sed，quo id everti forensibus maiestatis。Vim 广告智能后果。Te dicam 阻碍事件测量。Usu prompta alterum contentiones no, ut esse fabellas splendide pri。
Ne utroque nominavi moderatius qui, ius at suas velit nihil, vidit blandit facilisi pri ut。Ad vel offendit reprehendunt, mea ex quem ipsum complectitur。Veri cetero feugait cu usu，在 dolor corpora adolescens vim 中，在坐 voluptua placerat sadipscing。Minim admodum constituam eos ut, vix ut movet causae tractatos, in pro dicat dicta dolores。Impetus praesent eum no.
于 2012-04-15T14:14:31.623 回答