正则表达式中的递归模式

Question

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

我已经看到 了一些 索赔 是递归的模式可以用来匹配平衡括号,但使用Python的没有例子正则表达式包(注:重不支持递归模式,你需要使用正则表达式).

一种说法是语法在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

我想强调这是关于如何使用递归模式(如果我的理解是正确的,将我们带到常规语言解析之外,那么实际上可能是可能的!).如果可以做到,这应该是一个更清洁的解决方案.

Answer 1

模式是:

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

Answer 2

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

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

演示

我认为你所尝试的关键是重复不会继续m,而是整个(?:m|(?R))团队.这是允许带(?R)引用的递归的原因.