不使用递归或平衡组,是否可能使用正则表达式匹配嵌套的括号?

35
问题: 在不支持递归和平衡组的正则表达式中匹配任意嵌套的括号组,例如Java的java.util.regex,即在以下内容中匹配三个外部组:

(F(i(r(s)t))) ((S)(e)((c)(o))(n)d) (((((((Third)))))))

这个练习是纯粹的学术性质,因为我们都知道正则表达式不应该用来匹配这些东西,就像棉签不能用来清洁耳朵。

Stack Overflow鼓励自问自答,所以我决定创建这篇文章,分享我最近发现的一个技巧。


如果你知道Java不支持递归,为什么还要问这个问题呢?“因为我们都知道正则表达式不应该用来匹配这些东西”这个说法完全是胡说八道。 - user557597
5
@sln,我提出了问题并回答了它 - 请向下滚动。那个声明是讽刺用来预先挡住那些总是会回复说正则表达式不是这个任务的正确工具的人。不幸的是,我的帖子未能引发积极、深入的讨论,就像你和其他人的回应所展示的那样。 - jaytea
2
我正在检查你的正则表达式。它在Perl中有效。我正在尝试在boost regex中做一个等效的,但是它不会在事实之前执行未定义的反向引用。这可能是因为它正在使用伪堆栈,我将找出原因。到目前为止,我做了这个 (?(DEFINE)(?<G2>.*)(?<G1>.*\)(?!.*\k<G2>).*))(?=\()(?:(?=.*?\((?!.*?\k<G1>)(?&G1))(?=.*?\)(?!.*?\k<G2>)(?&G2)).)+?.*?(?=\k<G1>)[^(]*(?=\k<G2>$) 但是它没有找到任何东西。 - user557597
是的,不幸的是我认为你说得对:boost不支持前向引用。你有发现什么吗? - jaytea
2
就你观察到的换行行为而言,这是可以预料的。我们需要所有那些 .* 部分来潜在地匹配行终止符,以便该方法能够正确处理多行。我可以通过在示例中将每个 . 更改为 [\s\S](并将 \2$ 更改为 \2\z 以取代 'm' 修改器)来强制执行此操作,但我选择尽可能保持简单,因为已经相当难以理解了。 - jaytea
显示剩余5条评论
2个回答

51

确实!使用前向引用是可能的:

(?=\()(?:(?=.*?\((?!.*?\1)(.*\)(?!.*\2).*))(?=.*?\)(?!.*?\2)(.*)).)+?.*?(?=\1)[^(]*(?=\2$)

证明

Et voila; 就是这样。这里匹配了从开头到结尾的一个完整的嵌套括号组。每个匹配必须捕获和保存两个子字符串; 这对您没有用。只需专注于主匹配的结果即可。

不,深度没有限制。不,其中没有隐藏递归结构。只是普通的正向零宽断言,再加上一些向前引用。如果您使用的语言不支持向前引用(我指的是你,JavaScript),那我很抱歉。我真的很抱歉。我希望我可以帮助您,但我又不是什么奇迹创造者。

那很棒,但我也想匹配内部组!

好的,问题来了。我们之所以能够匹配这些外部组,是因为它们是非重叠的。一旦我们希望匹配的内容开始重叠,我们就必须稍微调整策略。我们仍然可以检查主题中正确平衡的括号组。但是,我们需要像这样使用捕获组来保存它们:

(?=\()(?=((?:(?=.*?\((?!.*?\2)(.*\)(?!.*\3).*))(?=.*?\)(?!.*?\3)(.*)).)+?.*?(?=\2)[^(]*(?=\3$))) 

这个表达式与之前的表达式完全相同,只是我用前瞻包装了大部分内容以避免消耗字符,添加了一个捕获组,并调整了反向引用索引,使其与新的友好组匹配。现在的表达式在下一个括号组之前的位置匹配,并将感兴趣的子字符串保存为\1。

那么...这到底是如何工作的?

很高兴你问了。一般方法非常简单:一边迭代字符,一边匹配下一个'('和')'的出现,每次都捕获剩余的字符串,以便在下一次迭代中恢复搜索的位置。让我一步步来解释:

注释 组成部分 描述
(?=\() 确保在进行任何重要工作之前先跟随'('
(?: 开始使用用于迭代字符串的组,因此以下先行断言会重复匹配。
处理'(' (?= 这个先行断言处理找到下一个'('
.*?\((?!.*?\1) 匹配到下一个不跟随\1的'('。下面,你会看到\1会被填充为最后一个匹配的'('之后的整个字符串部分。因此,(?!.*?\1)确保我们不再次匹配相同的'('
(.*\)(?!.*\2).*) 使用剩余的字符串填充\1。同时,检查是否至少还有另一个')'的出现。这是PCRE补丁,用于克服先行断言中捕获组中的一个错误。
)
处理') (?= 这个先行断言处理找到下一个')
.*?\)(?!.*?\2) 匹配到下一个不跟随\2的')'。就像之前的'('匹配一样,这迫使匹配一个之前未匹配的')'。
(.*) 使用剩余的字符串填充\2。这里没有适用上述提到的错误,所以简单的表达式就足够了。
)
. 消耗一个字符,以便该组可以继续匹配。安全起见,因为下一个'('或')'的任何出现都不可能存在于新匹配点之前。
)+? 尽可能少地匹配,直到找到平衡的

5
(但它非常脆弱)(为什么?)(因为:“a)你可能已经引用了括号! :)”)(“那不公平:(”) - AJNeufeld
3
嘿,这只是为了你而设的 :) https://regex101.com/r/Dfao1h/1 - jaytea
2
@AJNeufeld 小疏忽,这里: https://regex101.com/r/Dfao1h/4。我有点难过,人们似乎错过了这篇文章的重点 :( 别告诉我还有“b)”?哈哈 - jaytea
7
@AJNeufeld,我之前听取了您的意见,但现在我认为您在白费力气。处理字符转义和带引号的字符串是对我的示例非常基本的扩展,并且已经做过很多次了。这就是我说你没有理解这篇文章要点的原因。我的目的是介绍一些以前没有做过的东西,而不是介绍一些声称适用于所有情况的东西。许多人在我之前发布了类似的演示,并获得了更多的积极反馈。这就是为什么我认为我的帖子适合发布在这里的原因。 - jaytea
@Denis 错了,恐怕是必要的验证部分。如果\2 = ""(当最后一个匹配的 ')' 在字符串末尾时会发生这种情况),(?=\2) 将在每个位置上匹配。因此它将匹配 "(()" 中的 "(",这是不可取的。请参见:https://regex101.com/r/rKytow/2我的正则表达式已经具备了跨多行匹配的能力;您只需要使用 's' 修饰符来强制 '.' 匹配行终止符即可。请参见:https://regex101.com/r/rKytow/3 - jaytea
显示剩余6条评论

6

简介

输入更正

首先,您的输入不正确,因为有一个多余的括号(如下所示)

(F(i(r(s)t))) ((S)(e)((c)(o))n)d) (((((((Third)))))))
                                ^

对于包含或排除额外括号的适当修改,可以得到以下字符串之一:

删除额外的括号

(F(i(r(s)t))) ((S)(e)((c)(o))n)d (((((((Third)))))))
                                ^

添加额外的括号以匹配多余的关闭括号

((F(i(r(s)t))) ((S)(e)((c)(o))n)d) (((((((Third)))))))
^

正则表达式的能力

第二点,只有支持递归功能的正则表达式才能真正实现匹配开/闭括号(如在OP的解决方案中看到的,它匹配了错误输入中的额外括号)。

这意味着对于目前不支持递归的正则表达式(如Java、Python、JavaScript等),在正则表达式中使用递归(或模拟递归)是不可能的


输入

考虑到原始输入实际上是无效的,我们将使用以下输入进行测试。

(F(i(r(s)t))) ((S)(e)((c)(o))n)d) (((((((Third)))))))
(F(i(r(s)t))) ((S)(e)((c)(o))n)d (((((((Third)))))))
((F(i(r(s)t))) ((S)(e)((c)(o))n)d) (((((((Third)))))))

使用这些输入进行测试应该会产生以下结果:

  1. 无效(不匹配)
  2. 有效(匹配)
  3. 有效(匹配)

代码

有多种方法可以匹配嵌套组。下面提供的解决方案都依赖于支持递归功能的正则表达式版本(例如 PCRE)。

在此处查看使用的正则表达式

使用 DEFINE 块

(?(DEFINE)
  (?<value>[^()\r\n]+)
  (?<groupVal>(?&group)|(?&value))
  (?<group>(?&value)*\((?&groupVal)\)(?&groupVal)*)
)
^(?&group)$

注意: 这个正则表达式使用了标志gmx

不使用DEFINE块

在此处查看使用该正则的例子

^(?<group>
  (?<value>[^()\r\n]+)*
  \((?<groupVal>(?&group)|(?&value))\)
  (?&groupVal)*
)$

注意: 此正则表达式使用标志 gmx

不使用 x 修改器(一行式)

点击此处查看使用该正则表达式的案例

^(?<group>(?<value>[^()\r\n]+)*\((?<groupVal>(?&group)|(?&value))\)(?&groupVal)*)$

不使用命名(组和引用)

点击此处查看使用的正则表达式

^(([^()\r\n]+)*\(((?1)|(?2))\)(?3)*)$

注意: 这是我能想到的最简短的方法。


解释

我将解释最后一个正则表达式,因为它是所有其他正则表达式的简化和最小示例。

  • ^ 断言在行首
  • (([^()\r\n]+)*\(((?1)|(?2))\)(?3)*) 捕获以下内容到捕获组1
    • ([^()\r\n]+)* 将以下内容捕获到捕获组2中,任意次数
      • [^()\r\n]+ 匹配任何不在集合()\r\n中的字符,一次或多次
    • \( 匹配左括号字符(
    • ((?1)|(?2)) 捕获以下内容到捕获组3
      • (?1) 递归第一个子模式(1)
      • (?2) 递归第二个子模式(2)
    • \) 匹配右括号字符)
    • (?3)* 递归第三个子模式(3)任意次数
  • $ 断言在行尾

3
谢谢您的发布并指出问题!我没有给您点反对,但我怀疑是因为您的建议使用了递归,这并不是新颖的内容,也不是此讨论的重点。顺便说一下,具有前向引用的解决方案还可以,只是输入不正确。表达式仍然正确地匹配完整、正确平衡的圆括号组(省略了额外的“)”),这正如它应该做的那样。要验证一行是否含有正确平衡的圆括号组,您可以使用此链接:https://regex101.com/r/Dfao1h/2 - jaytea
2
是的,我很抱歉那个是匆忙制作的!这是已经更正过的链接:https://regex101.com/r/Dfao1h/3 - 我保证它是可行的,并且我敦促您仔细阅读我的帖子中表达式的分解并理解方法。我相信您会明白它如何以及为什么起作用。答案中的表达式匹配一个完整的组,而我刚才提供的则是验证(这显然更加棘手)。 - jaytea
@jaytea 最后一个确实有效。您应该更新您的答案,将该正则表达式包含在内,而不是当前包含的那个。 - ctwheels
1
我只是想展示这个概念最简单的变体,即“匹配一个组”而不是“验证一个组”或“匹配可能带引号内容的组”(就像其他评论中所述)等。 - jaytea

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接