regex - 有没有办法优化这种灾难性正则表达式回溯的情况？

Question

所以我想出了以下正则表达式:

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

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

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

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

在 group(1) 和 group(2) 中匹配 php 和 myscript.php。

问题是中间的这部分:(?:.*?)，它会导致组合爆炸，减慢大输入的正则表达式。有没有办法优化这个？由于没有模式，我想不出任何东西。

澄清一下，我要匹配的规则是:匹配命令的任何路径，可能包含转义的空格。忽略它后面的任何参数。匹配以 .php 结尾的文件，忽略它后面的任何内容。命令应该在 group(1) 中，文件名应该在 group(2) 中。

Answer 1

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

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

在Java中

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

参见 regex demo .请注意，字符类之外的文字 . 必须进行转义。如果字符串可能有换行符，请使用 Pattern.DOTALL 编译模式。

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

如果您不允许使用 *+ 所有格量词回溯到第一个否定字符类，它已经可以更可靠地工作了。

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