使用 Regex 解析 C 风格的注释，避免回溯

Question

我想匹配 JavaScript 文件中的所有块注释和多行注释（这些是 C 样式注释）。我有一个很好用的模式。但是，它会产生一些回溯，这会显着降低速度，尤其是在处理较大的文件时。

模式：\/\*(?:.|[\r\n])*?\*\/|(?:\/\/.*)

示例：https://www.regex101.com/r/pR6eH6/2

如何避免回溯？

Answer 1

由于交替，你有大量的回溯。您可以考虑使用字符 class [\s\S] 来代替 (?:.|[\r\n])，从而显着提高性能：

\/\*[\s\S]*?\*\/|\/\/.*

见demo

在Python中，你也可以使用re.S/re.DOTALL修饰符使.匹配换行符（注意单行注释模式应该是然后匹配 \/\/[^\r\n]*):

/\*.*?\*/|//[^\r\n]*

见another demo

但是，因为*? 惰性量词也会造成类似于贪婪量词的开销，你应该考虑为 C style multiline comments - /\*[^*]*\*+(?:[^/*][^*]*\*+)*/ 使用更优化的模式，整个正则表达式现在看起来像：

/\*[^*]*\*+(?:[^/*][^*]*\*+)*/|//.*

见yet another demo

详情:

/\* - 一个/*
[^*]* - *
\*+ - 一个或多个星号
(?:[^/*][^*]*\*+)* - 零个或多个序列：
- [^/*] - / 和 *
- [^*]* - *
- \*+ - 1+ 个星号
/ - / 符号
| - 或
//.* - // 和除换行符以外的任何 0+ 个字符。

只是想注意，在 Python 中，你不需要转义 / （在 JS 中，你不需要在使用 RegExp 声明正则表达式时转义 /构造函数）。

注意：最后一个模式不允许简单地捕获 /* 和 */ 中的内容，但是因为该模式比其他模式更稳定，即使您需要使用尾随 * - /\*([^*]*\*+(?:[^/*][^*]*\*+)*)/|//(.*) 捕获内容，我也建议使用它 - 然后您需要从 .group(1).[= 中删除最后一个字符49=]

Answer 2

你可以用你的图案做什么？

您的实际模式是：

 \/\*(?:.|[\r\n])*?\*\/|(?:\/\/.*)

或没有无用的反斜杠和组：

/\*(?:.|[\r\n])*?\*/|//.*

正如 stribizhev 所解释的那样，(?:.|[^\r\n])*? 可以使用 DOTALL 模式以更简单的方式编写，即：.*? 或不使用 [\s\S] 代替点。

但是，如果将主交替的两个分支（多行注释分支和单行注释分支）共有的第一个字符 / 考虑在内，您可以做得更好：

/(?:\*[\s\S]*?\*/|/.*)

这次改动的两个好处：

以交替开始一个模式不是一个好主意，必须尽可能避免，因为正则表达式引擎必须为每个位置测试交替的两个分支（在最坏的情况下）字符串。所以在你的情况下（只有两个分支），你可以认为正则表达式引擎工作是 X2。如果您将第一个字符（或更多标记，如果可能）放在因子中，则字符串中大部分不感兴趣的位置会更快地被丢弃（不以 / 开头的位置），因为只有一个当第一个字符不是正确字符时分支测试。
当您以文字字符串开始模式时，正则表达式引擎能够使用更快的算法直接找到字符串中模式可能成功的位置（文字字符串出现的位置).在您的情况下，使用此优化将使您的模式更快。

您可以改进的其他事情：非贪婪量词

非贪婪量词本质上很慢（与贪婪量词相比），因为每次它取一个字符时，它都必须测试模式结束是否成功（直到模式结束成功） .换句话说，当回溯机制出现时，非贪婪量词可能比贪婪量词更糟糕（回溯机制和量词如何工作是最重要的（最？）要理解的事情之一，花时间了解它） .

您可以以更有效的方式重写子模式 \*[\s\S]*?\*/：

\*[^*]*\*+(?:[^*/][^*]*\*+)*/

详情：

\*    # literal asterisk
[^*]* # zero or more character that are not an asterisk
\*+   # one or more asterisks: this one will match either the last asterisk(s)
      # before the closing slash or asterisk(s) inside the comment.

(?:[^*/][^*]*\*+)* # In case there are asterisks(s) inside the comment, this
                   # optional group ensures the next character isn't a slash: [^*/]
                   # and reach the next asterisk(s): [^*]*\*+
/    # a literal slash

这个子模式更长但更有效，因为它只使用贪婪量词，并且回溯步骤减少到最少。

现在的模式是：

/(?:\*[^*]*\*+(?:[^*/][^*]*\*+)*/|/.*)

并且只需要约 950 步（而不是约 12500 步）即可找到您的示例字符串的 63 次出现。

demo

使用 Regex 解析 C 风格的注释，避免回溯

Parse C-Style Comments with Regex, avoid Backtracking

javascript

python

regex

backtracking