有没有一种方法可以优化这种灾难性的正则表达式回溯案例？

Question

所以我想到了以下的正则表达式：

([^\s\\]+(?:\\.[^\s\\]*)*)(?:.*?)(\S+\.php\b)

测试链接：https://regex101.com/r/NV6Bk4/4

它匹配命令行的二进制和脚本名称。例如：

php --strict myscript.php --arg=value

在第一组和第二组中匹配php和myscript.php。

问题出在中间的部分：(?:.*?)，这导致正则表达式在大量输入时变得非常缓慢。有没有办法优化呢？由于没有模式，我想不到任何方法。

为了澄清，我要匹配的规则是：匹配任何路径到命令，可能包含转义空格。忽略后面的任何参数。匹配以.php结尾的文件，忽略其后面的任何内容。命令应该在第一组中，文件名应该在第二组中。

- Michael Böckling

---

实际上，了解实际规则更为重要。正在匹配什么以及为什么进行匹配？问题很明显：连续相邻的模式可能会匹配相同类型的字符。 - Wiktor Stribiżew

它将在Java 8中运行。 - Michael Böckling

检查 ^([^\s\\]*+(?:\\.[^\s\\]*)*).*?(\S+\.php\b)，请参见 演示。如果你的匹配从字符串的开头开始，请使用 ^，并且在第一个否定字符类中使用一种占有量词。 - Wiktor Stribiżew

看起来很有前途！有没有办法让它匹配（match()）？不幸的是，这是我必须遵守的限制。 - Michael Böckling

在末尾添加“.*”就可以了！非常感谢。 - Michael Böckling

Answer 1

您可以使用以下“修复”与Matcher#matches()一起使用：

([^\s\\]*+(?:\\.[^\s\\]*)*).*?(\S+\.php\b).*

在Java中

String regex = "([^\\s\\\\]*+(?:\\\\.[^\\s\\\\]*)*).*?(\\S+\\.php\\b).*";

请看正则表达式演示。注意，字符类之外的字面量.必须转义。如果字符串可能包含换行符，请使用Pattern.DOTALL编译模式。

正如您所看到的，.*?部分匹配任何字符，并且它之前的(?:\\.[^\s\\]*)*可以匹配任何0个或多个字符（因此，它是可选的），从左侧与.*?相邻的下一个相邻模式是[^\s\\]+，可以匹配与.*?相同的字符。这意味着，正则表达式引擎可能会回溯到第一个子模式，这就创建了许多匹配字符串的方式，通常称为灾难性回溯。

如果您使用*+贪婪限定符禁止回溯到第一个否定字符类，它将更加可靠。

在末尾添加.*以使其与.matches()一起工作，因为该方法需要完整的字符串匹配。

- Wiktor Stribiżew

---

感谢你的解释。非常出色！ - Michael Böckling