什么是正则表达式平衡组？

Question

我刚刚阅读了一个关于如何在双花括号中获取数据的问题(这个问题),然后有人提出了平衡组.我还不太确定它们是什么以及如何使用它们.

我读了平衡组定义,但解释很难理解,我仍然对我提到的问题感到困惑.

有人可以简单地解释什么是平衡组以及它们如何有用吗？

Answer 1

据我所知,平衡组是.NET正则表达式的独特之处.

旁白:重复的群体

首先,您需要知道.NET(再次,据我所知)唯一的正则表达式风格,允许您访问单个捕获组的多个捕获(不是在反向引用中,但在匹配完成后).

为了举例说明,请考虑模式

(.)+

和字符串"abcd".

在所有其他正则表达式中,捕获组1只会产生一个结果:( d注意,完全匹配当然会abcd如预期的那样).这是因为捕获组的每个新用法都会覆盖先前的捕获.

另一方面,.NET会记住它们.它在堆栈中这样做.匹配上面的正则表达式之后

Match m = new Regex(@"(.)+").Match("abcd");

你会发现的

m.Groups[1].Captures

是否CaptureCollection其元素对应于四个捕获

0: "a"
1: "b"
2: "c"
3: "d"

其中数字是指数CaptureCollection.因此,基本上每次再次使用该组时,新的捕获都会被推入堆栈.

如果我们使用命名捕获组,它会变得更有趣.因为.NET允许重复使用相同的名称,我们可以写一个正则表达式

(?<word>\w+)\W+(?<word>\w+)

将两个单词捕获到同一组中.同样,每次遇到具有特定名称的组时,捕获都会被推送到其堆栈中.所以将此正则表达式应用于输入"foo bar"和检查

m.Groups["word"].Captures

我们找到两个捕获

0: "foo"
1: "bar"

这使我们甚至可以从表达式的不同部分将事物推送到单个堆栈中.但是,这只是.NET能够跟踪其中列出的多个捕获的功能CaptureCollection.但我说,这个集合是一个堆栈.那么我们可以从中汲取 灵感吗？

输入:平衡组

事实证明我们可以.如果我们使用类似的组(?<-word>...),那么word如果子表达式...匹配,则从堆栈中弹出最后一次捕获.所以,如果我们将之前的表达式更改为

(?<word>\w+)\W+(?<-word>\w+)

然后第二组将弹出第一组的捕获,最后我们将收到一个空CaptureCollection.当然,这个例子很没用.

但是减法语法还有一个细节:如果堆栈已经为空,则组失败(无论其子模式如何).我们可以利用这种行为来计算嵌套级别 - 这就是名称平衡组来自的地方(以及它变得有趣的地方).假设我们想匹配正确括号的字符串.我们在堆栈上推动每个左括号,并为每个右括号弹出一个捕获.如果我们遇到一个关闭括号太多,它将尝试弹出一个空堆栈并导致该模式失败:

^(?:[^()]|(?<Open>[(])|(?<-Open>[)]))*$

所以我们在重复中有三种选择.第一种选择消耗所有不是括号的东西.第二个替代方案匹配(s,同时将它们推入堆栈.第三种方法匹配)s,同时从堆栈弹出元素(如果可能!).

_{注意:只是为了澄清,我们只是检查没有无法比拟的括号!这意味着根本不包含括号的字符串将匹配,因为它们在语法上仍然有效(在某些语法中,您需要使用括号匹配).如果你想确保至少一组括号,只需添加一个先行(?=.*[(])右后^.}

但这种模式并不完美(或完全正确).

结局:条件模式

还有一个问题:这不能确保堆栈在字符串末尾是空的(因此(foo(bar)是有效的)..NET(以及许多其他版本)还有一个结构可以帮助我们:条件模式.一般语法是

(?(condition)truePattern|falsePattern)

其中falsePattern是可选的 - 如果省略,则false-case将始终匹配.条件可以是模式,也可以是捕获组的名称.我会在这里关注后一种情况.如果它是捕获组的名称,则truePattern当且仅当该特定组的捕获堆栈不为空时才使用.也就是说,条件模式如(?(name)yes|no)"如果name匹配并捕获了某些东西(仍然在堆栈中)",则使用模式yes否则使用模式no".

因此,在我们上面的模式结束时(?(Open)failPattern),如果Open-stack不为空,我们可以添加一些导致整个模式失败的东西.使模式无条件失败的最简单方法是(?!)(空的否定前瞻).所以我们有最终模式:

^(?:[^()]|(?<Open>[(])|(?<-Open>[)]))*(?(Open)(?!))$

请注意,此条件语法本身与平衡组没有任何关系,但必须充分利用它们的全部功能.

从这里开始,天空就是极限.许多非常复杂的用途都是可能的,当与其他.NET-Regex功能结合使用时会有一些问题,例如可变长度的lookbehinds(我必须自己学习很难).但问题始终是:使用这些功能时,您的代码是否仍然可维护？您需要非常好地记录它,并确保每个使用它的人都知道这些功能.否则你可能会更好,只需逐个字符地手动操作字符串并计算整数中的嵌套级别.

附录:(?<A-B>...)语法是什么？

这部分的学分转到Kobi(有关详细信息,请参阅下面的答案).

现在有了上述所有内容,我们可以验证字符串是否正确括号.但是如果我们能够实际获得所有这些括号内容的(嵌套)捕获,那将会更有用.当然,我们可以记住在未清空的单独捕获堆栈中打开和关闭括号,然后在单独的步骤中根据它们的位置进行一些子串提取.

但.NET提供了一个更方便的功能:如果我们使用(?<A-B>subPattern),不仅是从堆栈B弹出捕获,B而且弹出捕获和当前组之间的所有内容都被压入堆栈A.因此,如果我们使用这样的组作为结束括号,同时从我们的堆栈中弹出嵌套级别,我们也可以将该对的内容推送到另一个堆栈:

^(?:[^()]|(?<Open>[(])|(?<Content-Open>[)]))*(?(Open)(?!))$

_{Kobi 在他的回答中提供了这个Live-Demo}

所以把所有这些东西放在一起我们可以:

• 记住任意多次捕获
• 验证嵌套结构
• 捕获每个嵌套级别

全部在一个正则表达式中.如果这不令人兴奋...;)

我在第一次了解它们时发现了一些有用的资源:

• http://blog.stevenlevithan.com/archives/balancing-groups
• 关于平衡组的MSDN
• 关于条件模式的MSDN
• http://kobikobi.wordpress.com/tag/balancing-group/(稍微学术,但有一些有趣的应用程序)

Answer 2

只是M. Buettner的优秀答案的一小部分补充:

什么是(?<A-B>)语法处理？

(?<A-B>x)与...略有不同(?<-A>(?<B>x)).它们导致相同的控制流^*,但它们捕获的方式不同.
例如,让我们看一下平衡大括号的模式:

(?:[^{}]|(?<B>{)|(?<-B>}))+(?(B)(?!))

在比赛结束时我们有一个平衡的字符串,但这就是我们所拥有的 - 我们不知道大括号在哪里,因为B堆栈是空的.引擎为我们所做的艰苦工作已经消失.
_{(关于Regex Storm的例子)}

(?<A-B>x)是解决这个问题的方法.怎么样？它不会捕捉x到$A:它抓住以前捕获的内容B和当前位置.

让我们在我们的模式中使用它:

(?:[^{}]|(?<Open>{)|(?<Content-Open>}))+(?(Open)(?!))

这将捕获到$Content的括号(和它们的位置)之间的字符串,每对沿途.
对于字符串{1 2 {3} {4 5 {6}} 7}有好多有四个捕获:3,6,4 5 {6},和1 2 {3} {4 5 {6}} 7-大大优于没有或} } } }.
_{(示例 - 单击table选项卡并查看${Content},捕获)}

事实上,它可以在没有平衡的情况下使用:(?<A>).(.(?<Content-A>).)捕获前两个字符,即使它们被组分开.
(这里更常用的是先行,但它并不总是缩放:它可能会复制你的逻辑.)

(?<A-B>)是一个强大的功能 - 它可以让您精确控制您的捕获.当你试图从你的模式中获得更多时,请记住这一点.