1

我有一个正则表达式，它解析 Razor 模板语言的一个（非常小的）子集。最近，我在正则表达式中添加了一些规则，这大大减慢了它的执行速度。我想知道：是否有某些已知的正则表达式结构很慢？是否对我正在使用的模式进行了重组以保持可读性并提高性能？注意：我已确认此性能影响发生在编译后。

这是模式：

new Regex(
              @"  (?<escape> \@\@ )"
            + @"| (?<comment> \@\* ( ([^\*]\@) | (\*[^\@]) | . )* \*\@ )"
            + @"| (?<using> \@using \s+ (?<namespace> [\w\.]+ ) (\s*;)? )"

            // captures expressions of the form "foreach (var [var] in [expression]) { <text>" 
/* ---> */      + @"| (?<foreach> \@foreach \s* \( \s* var \s+ (?<var> \w+ ) \s+ in \s+ (?<expressionValue> [\w\.]+ ) \s* \) \s* \{ \s* <text> )"

            // captures expressions of the form "if ([expression]) { <text>" 
/* ---> */      + @"| (?<if> \@if \s* \( \s* (?<expressionValue> [\w\.]+ ) \s* \) \s* \{ \s* <text> )"  

            // captures the close of a razor text block
            + @"| (?<endBlock> </text> \s* \} )"

            // an expression of the form @([(int)] a.b.c)
            + @"| (?<parenAtExpression> \@\( \s* (?<castToInt> \(int\)\s* )? (?<expressionValue> [\w\.]+ ) \s* \) )"
            + @"| (?<atExpression> \@ (?<expressionValue> [\w\.]+ ) )"
/* ---> */      + @"| (?<literal> ([^\@<]+|[^\@]) )",
            RegexOptions.IgnorePatternWhitespace | RegexOptions.Multiline | RegexOptions.ExplicitCapture | RegexOptions.Compiled);

/* ---> */ 表示导致减速的新“规则”。

4

2 回答 2

1

由于您没有锚定表达式，因此引擎必须在字符串的每个位置检查每个替代子模式，然后才能确定它找不到匹配项。这总是很耗时，但如何才能减少呢？

一些想法：

我不喜欢第二行试图匹配注释的子模式，我认为它不能正常工作。

我可以看到您尝试对( ([^\*]\@) | (\*[^\@]) | . )*-allow@和*评论执行什么操作，只要它们没有分别位于前面*或后面@。但是由于组的*量词和第三个选项.，子模式会很高兴地匹配*@，因此使其他选项变得多余。

并假设您尝试匹配的 Razor 子集不允许多行注释，我建议第二行

+ @"| (?<comment> @\*.*?\*@ )"

即懒惰地匹配任何字符（但换行符），直到*@遇到第一个。您正在使用RegexOptions.ExplicitCapture仅捕获命名组的含义，因此缺少()应该不是问题。

我也不喜欢([^\@<]+|[^\@])最后一行中的子模式，它等同于([^\@<]+|<). [^\@<]+除非遇到 a @or ，否则将贪婪地匹配到字符串的末尾<。

我没有看到任何相邻的子模式会匹配相同的文本，这是过度回溯的常见罪魁祸首，但\s*由于它们的贪婪和灵活性，包括不匹配和换行符，所有这些似乎都是可疑的。也许您可以将一些 更改为\s*您[ \t]*知道不想匹配换行符的位置，例如，可能在if.

我注意到 nhahtdh 建议您使用原子分组来防止引擎回溯到先前匹配的内容，这当然值得尝试，因为几乎可以肯定，当引擎无法再找到导致匹配的匹配时会导致过度回溯减速。

您想通过该RegexOptions.Multiline选项实现什么？你看起来没有使用^，否则$它不会有任何效果。

的转义@是不必要的。

于 2013-03-13T19:39:20.970 回答
0

正如其他人所提到的，您可以通过删除不必要的转义来提高可读性（例如在字符类内部转义@或转义字符\；例如，使用[^*]代替[^\*]）。

以下是一些提高性能的想法：

订购您的不同选择，以便最有可能的选择首先出现。

正则表达式引擎将尝试按照它们出现在正则表达式中的顺序匹配每个备选方案。如果您将更有可能的选项放在前面，那么引擎将不必浪费时间尝试在大多数情况下与不太可能的替代方案进行匹配。

删除不必要的回溯

不是您的“使用”替代方案的结束：@"| (?<using> \@using \s+ (?<namespace> [\w\.]+ ) (\s*;)? )"

如果由于某种原因您有大量空白，但;在 using 行的末尾没有关闭，则正则表达式引擎必须回溯每个空白字符，直到它最终确定它不能匹配(\s*;)。在您的情况下，(\s*;)?可以替换为\s*;?以防止在这些情况下回溯。

此外，您可以使用原子组(?>...)来防止通过量词（例如*和 +）进行回溯。当您找不到匹配项时，这确实有助于提高性能。例如，您的“foreach”替代方案包含\s* \( \s*. 如果找到 text "foreach var..."，“foreach”替代方案将贪婪地匹配 之后的所有空格foreach，然后在找不到开头时失败(。然后它将一次回溯一个空白字符，并尝试(在前一个位置匹配，直到它确认它不能匹配该行。如果匹配，使用原子组(?>\s*)\(将导致正则表达式引擎不会通过 \s* 回溯，从而允许正则表达式更快地失败。

但是在使用它们时要小心，因为在错误的地方使用它们可能会导致意外失败（例如，'(?>,*);由于贪婪地.*匹配所有字符（包括;），并且原子分组(?>......)阻止正则表达式引擎，因此永远不会匹配任何内容从回溯一个字符以匹配结尾;）。

在您的一些替代方案上“展开循环”，例如您的“评论”替代方案（如果您计划为字符串添加替代方案也很有用）。

例如：@"| (?<comment> \@\* ( ([^\*]\@) | (\*[^\@]) | . )* \*\@ )"

可以换成@"| (?<comment> @\* [^*]* (\*+[^@][^*]*)* \*+@ )"

新的正则表达式归结为：

  1. @\*: 查找评论的开头@*
  2. [^*]*：阅读所有“普通字符”（任何不是*因为可能表示评论结束的内容）
  3. (\*+[^@][^*]*)*: 在评论中包含任何非终结符 *
    • (\*+[^@]：如果我们找到 a *，请确保*s 的任何字符串都不以 a 结尾@
    • [^*]*：返回阅读所有“普通字符”
    • )*: 如果我们找到另一个，则循环回到开头*
  4. \*+@：最后，抓住评论的结尾，*@小心包含任何额外的内容*

您可以从 Jeffrey Friedl 的Mastering Regular Expressions (3rd Edition)中找到更多关于提高正则表达式性能的想法。

于 2013-12-12T15:46:45.140 回答