c# - 不匹配时正则表达式灾难性回溯

Question

我正在 https://regex101.com/ 中测试我的正则表达式在进行任何编码之前。

正则表达式:

\[(.*?)\]((?:.\s*)*?)\[\/\1\]

示例字符串:

[tag1]Test's Text Test Text Test Text Test Text.

Test Text Test Text Test "Text Test Text" Test Text Test Text.

Test Text? Test Text Test Text Test Text Test Text Test Text Test Text.

Test Text, Test Text Test Text Test Text Test Text Test Text Test Text Test Text.[/tag1]

[tag2]Test's Text Test Text Test Text Test Text.

Test Text Test Text Test "Text Test Text" Test Text Test Text.

Test Text? Test Text Test Text Test Text Test Text Test Text Test Text.

Test Text, Test Text Test Text Test Text Test Text Test Text Test Text Test Text.[/tag2]

....

....

我试图在一些长字符串中捕获 2 组。第一个是方括号内的文本，第二个是标签内的文本。

上面的正则表达式和字符串在正则表达式匹配时没有任何问题。如果匹配，每次匹配的步数仅为 1000+。但是，如果开始和结束标记不匹配，就会发生灾难性的回溯，并且匹配在 126.000+ 步中完成并停止寻找其他匹配字符串。

我知道，要防止回溯问题就是避免使用带有“+”或“*”的嵌套结构，但我似乎不知道有什么更好的方法来做到这一点。

也许有人可以提供或建议比我更好的正则表达式？

Answer 1

前言

首先，使用适当的测试环境。如果您在 .NET 中使用正则表达式，请不要在不支持 .NET 正则表达式的正则表达式测试器上测试它。

Regex101.com 不支持 .NET 正则表达式!

您的正则表达式模式不会对您在 RegexStorm.net 发布的字符串造成任何灾难性回溯.

根本原因

好的，正则表达式模式非常糟糕且效率低下。为什么？ (?:.\s*)*?(包含在一些更大的模式中，本身是独立的，这不会有问题)，匹配任何后跟零个或多个字符(因此，可选) 空格，所有重复 0 次或多次，但尽可能少。所以，. 和\s* 都可以匹配同一个字符串。当您将其包装在一个组中并添加量词时，正则表达式引擎尝试的可能匹配组合的总数呈指数增长。

增强模式

增强不是很明显，但许多人会提供类似 Federico 给出的解决方案:使用惰性点匹配模式。因此，(?s)\[([^]]*)](.*?)\[/\1] ( demo ) 看起来是一个可行的解决方案。它在 RegexHero.net 处每秒产生 7,843 次迭代.

使用展开循环方法，我们可以根据输入将正则表达式性能提高 n 倍。在这里，我们可以将 .*? 子模式写成任何字符，但 [ 和任何 [ 后面没有跟 /\1] 到 \[/\1]。这可以用否定字符类和 1 个量化组内的前瞻来编写(它甚至不需要任何修饰符或标志):

\[([^]]*)]([^[]*(?:\[(?!/\1])[^[]*)*)\[/\1]

参见 this RegexStorm demo .此正则表达式模式每秒产生 114,225 次迭代。这是因为 [tag1] 和 [/tag1] 之间根本没有 [，如果字符串包含很多 [ 或仅由 [ 组成(这在现实生活中不应该发生)。

测试

这是 RegexHero 测试:

您的原始正则表达式在该站点上仅产生 5,094 个 ips。