正则表达式中的递归模式
这与正则表达式匹配外括号非常相关,但是,我特别想知道该
正则表达式的递归模式 如何或是否可行?
我尚未找到使用此策略的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(在match对象上),请参见
此处。)
因此,我希望以下内容或某些变体能够起作用:
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
我想强调一下这是关于 如何使用递归模式的
(如果我的理解是正确的,那么它将使我们脱离常规语言的分析范围,因此实际上可能!)。如果可以做到,那应该是一个更清洁的解决方案。
-
模式是:
{((?>[^{}]+|(?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+
regex引擎时(默认情况下)记录(预先记录)所有字符的所有回溯位置。但是,当您使用原子组或所有格量词时,将不再记录这些回溯位置(组开始时除外)。因此,当发生回溯机制时,无法返回最后的“
a”字符。只有整个小组都可以退还。[编辑]:如果您使用“展开”子模式来描述方括号之间的内容,则可以用更有效的方式编写模式:
{([^{}]*+(?:(?R)[^{}]*)*+)}