正则表达式中的递归模式

Question

正则表达式中的递归模式

pythonregexrecursive-regex

68

这与正则表达式匹配外部括号非常相关，然而我特别想知道如何或是否可能使用regex的递归模式来实现？我还没有找到使用这种策略的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 所困扰。

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

显然，我冒着以下内容被否定的风险:

不要使用正则表达式解析html
使用pyparse
编写正确的词法分析器和语法分析器，例如使用ply

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

- Andy Hayden

3

谢谢，我从未可靠地知道如何在PCRE中进行这种类型的递归。知道 (?R) 和 b(?:m|(?R))*e 是一个很棒的技巧，我以前从没看过这么明确的解释 :) - Sam

欢迎来到正则表达式函数调用的新世界。 - user557597

2个回答

10

我可以毫不费力地使用b(?:m|(?R))*e语法完成这个操作：

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

演示

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

- Sam

2

在regex101上，Python实现失败了。 - hjpotter92

12

这仅在regex软件包中提供，而不是标准库的re模块。 - Andy Hayden

2

标准的re模块中有解决方案吗？ - roocell

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Casimir et Hippolyte · Accepted Answer

这个模式是：

{((?>[^{}]+|(?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)[^{}]*)*+)}