c# 正则表达式与平衡组不响应

Question

我有以下代码：

void Main()
{
  string template = @"
aaa 
{begin iteration items} 
  bbbbbb 
  {begin iteration subitems} 
    ccccccc 
  {end iteration subitems} 
  ddddddddd 
  {begin iteration items} 
    hhhhhhhhhhhhhhhhh
  {end iteration items} 
  iiiiiiiiiiiiiiiiiiiiiiiiiiii
{end iteration items} 
eeeeeeeeeeeeeeee
{begin iteration items} 
  ffffff
{end iteration items} 
gggggggggggg
  ";

  string re = @"
\{\s*begin\s+iteration\s+items\s*}
(?<template>
  (
    (?<iteration>\{\s*begin\s+iteration\s+items\s*})
    |(?<-iteration>\{\s*end\s+iteration\s+items\s*})
    |((?!(\{\s*begin\s+iteration\s+items\s*})|(\{\s*end\s+iteration\s+items\s*})).*?)
  )*(?(iteration)(?!))
)
\{\s*end\s+iteration\s+items\s*}
  ";

  Regex r = new Regex(re, RegexOptions.IgnoreCase | RegexOptions.Singleline | RegexOptions.IgnorePatternWhitespace);
  var matches = r.Matches(template);
  matches.Dump();
}

当 template 平衡时，匹配返回，一切正常。但是当我在模板中的 iiiiiiiiiiiiiii 行之后将 {end iteration items} 更改为 {end1 iteration items} 时，代码将停止响应 matches.Dump() 行（Dump() 是 read/enumerate 在 LinQPad)

怎么了？是否可以重写 Regex 使其始终响应？

编辑我的目标是在语法有效的情况下捕获所有顶级 <template> 组，否则不捕获任何内容。我按照 Lucas 的建议尝试了非回溯组，但是当语法有效时现在没有捕获。

Answer 1

您正在经历catastrophic backtracking这里。

简而言之：带有嵌套量词的 ((something)*)* 形式的模式将触发它，因为如果不能立即找到匹配项，引擎必须尝试所有可能的组合。

可以用原子团来防范。以下应该可以解决问题：

\{\s*begin\s+iteration\s+items\s*}
(?<template>
  (?>
    (?<iteration>\{\s*begin\s+iteration\s+items\s*})
    |(?<-iteration>\{\s*end\s+iteration\s+items\s*})
    |[^{]+
    |\{
  )*(?(iteration)(?!))
)
\{\s*end\s+iteration\s+items\s*}

如果需要捕获，请使用 ((?>...)) 而不是 (?>...)。

我简化了表达式 - 使用原子组时不再需要前瞻，因为这些情况将由 iteration 组处理。备选方案的最后一部分 (\{) 在这里是为了解决单独的左大括号，它不是 begin/end 序列的一部分。大部分文本被原子组内部的 [^{]+ 消耗，因此回溯不会发生。

c# 正则表达式与平衡组不响应

c# regex with balancing groups not responding

c#

regex

backtracking

balancing-groups