代码之家 › 专栏 › 技术社区 › shibormot

平衡组未响应的c#regex

balancing-groups backtracking regex c#

2

shibormot · 技术社区 · 10 年前

我有以下代码:

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 则返回匹配项,一切正常。但当我改变 {end iteration items} 到 {end1 iteration items} 之后 iiiiiiiiiiiiiii 模板中的行,然后代码停止响应 matches.Dump() 线路( Dump() 是LinQPad中读取/枚举的扩展方法)

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

编辑我的目标是捕获所有顶级 <template> 如果语法有效,则进行分组,否则不捕获任何内容。我尝试了卢卡斯建议的非回溯组,但当语法有效时,现在没有捕获。

1 回复 | 直到 10 年前

1

2

Lucas Trzesniewski 10 年前

你正在经历 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 组。备选方案的最后一部分( \{ )这里是为了说明单独的开口大括号,它们不是开始/结束序列的一部分。大部分文本由 [^{]+ 在原子群内部,因此回溯不会发生。