63

这与正则表达式匹配外括号非常相关，但是，我特别想知道如何或是否可以执行此正则表达式的递归模式？我还没有找到使用这种策略的 python 示例，所以认为这应该是一个有用的问题！

我已经看到 一些 声称 可以使用递归模式来匹配平衡括号，但没有使用 python 的regex包的示例（注意：re不支持递归模式，您需要使用 regex）。

一种说法是语法是b(?:m|(?R))*e：

b是什么开始构造，m是什么可以发生在构造的中间，e是什么可以发生在构造的末尾

我想在以下内容中提取外大括号的匹配项：

"{1, {2, 3}} {4, 5}"
["1, {2, 3}", "4, 5"]  # desired

请注意，这很容易对内大括号执行相同的操作：

re.findall(r"{([^{}]*)}", "{1, {2, 3}} {4, 5}")
['2, 3', '4, 5']

（在我的示例中，我使用的是 finditer（过度匹配对象），请参见此处。）

因此，我希望以下内容或某些变体可以起作用：

regex.findall(r"{(:[^{}]*|?R)}", "{1, {2, 3}} {4, 5}")
regex.findall(r"({(:[^{}]*|?R)})", "{1, {2, 3}} {4, 5}")
regex.findall(r"({(:.*|(?R))*})", "{1, {2, 3}} {4, 5}")
regex.findall(r"({(:.*)|(?R)*})", "{1, {2, 3}} {4, 5}")
regex.findall(r"({(:[^{}])|(?R)})", "{1, {2, 3}} {4, 5}")

但我被 [] 或error: too much backtracking.

是否可以使用正则表达式的递归提取外括号的匹配对象？

显然，我冒着被击落的风险：

我想强调这是关于如何使用递归模式（如果我的理解是正确的，它会将我们带到常规语言解析之外，所以实际上可能是可能的！）。如果可以做到，这应该是一个更清洁的解决方案。

4

2 回答 2

59

模式是：

{((?>[^{}]+|(?R))*)}

您可以看到这适用于您的示例：

regex.findall("{((?>[^{}]+|(?R))*)}", "{1, {2, 3}} {4, 5}")
# ['1, {2, 3}', '4, 5']

解释：

m 部分需要排除括号。如果您希望同时允许一个量词[^{}]并重复该组而没有灾难性的回溯问题，则需要使用原子组。更清楚地说，如果最后一个右花括号丢失，则此正则表达式引擎将逐个原子组而不是逐个字符回溯原子组。为了强调这一点，您可以像这样使量词具有所有格：（{((?>[^{}]+|(?R))*+)}或者{((?:[^{}]+|(?R))*+)}因为原子组不再有用）。

原子组(?>....)和所有格量词?+, *+,++是同一特征的两侧。此功能禁止正则表达式引擎在成为“原子”的字符组内回溯（您不能将其分成较小的部分）。

基本示例是以下两种对于字符串总是失败的模式aaaaaaaaaab：

(?>a+)ab
a++ab

那是：

regex.match("a++ab", "aaaaaaaaaab")
regex.match("(?>a+)ab", "aaaaaaaaaab")

当您使用(?:a+)或a+正则表达式引擎（默认情况下）记录（预先）所有字符的所有回溯位置时。但是当你使用原子组或所有格量词时，不再记录这些回溯位置（除了组的开头）。因此，当回溯机制发生时，最后一个“a”字符无法返回。只能归还整个群体。

[编辑]：如果您使用“展开”子模式来描述括号之间的内容，则可以以更有效的方式编写模式：

{([^{}]*+(?:(?R)[^{}]*)*+)}
于 2014-10-15T15:15:31.463 回答
10

我能够做到这一点，b(?:m|(?R))*e语法没有问题：

{((?:[^{}]|(?R))*)}

演示

我认为您尝试的关键是重复不会继续m，而是整个(?:m|(?R))组。这就是允许使用(?R)引用进行递归的原因。

于 2014-10-15T15:17:38.470 回答