为了账号安全,请及时绑定邮箱和手机立即绑定

正则表达式中的递归模式

/ 猿问

正则表达式中的递归模式

Cats萌萌 2019-12-21 13:14:01

这与正则表达式匹配外括号非常相关,但是,我特别想知道该正则表达式的递归模式如何或是否可行?我尚未找到使用此策略的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

我想强调一下这是关于如何使用递归模式的(如果我的理解是正确的,它将使我们脱离常规语言的分析范围,因此实际上可能!)。如果可以做到,那应该是一个更清洁的解决方案。


查看完整描述

3 回答

?
慕森王

模式是:


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

您可以看到此示例适用于您:


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

# ['1, {2, 3}', '4, 5']

说明:

m部分需要排除括号。如果您希望同时允许一个量词[^{}]并重复该基团而没有催化回溯问题,则需要使用原子基团。更明确地说,如果缺少最后一个大括号,则此regex引擎将按原子组而不是逐个字符地回溯原子组。为了说明这一点,您可以这样使量词具有所有格:({((?>[^{}]+|(?R))*+)}或{((?:[^{}]+|(?R))*+)}由于原子团不再有用)。


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


基本示例是以下两种始终失败的模式aaaaaaaaaab:


(?>a+)ab

a++ab

那是:


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

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

当您使用(?:a+)或a+正则表达式引擎时(默认情况下)记录(预先记录)所有字符的所有回溯位置。但是,当您使用原子组或所有格量词时,将不再记录这些回溯位置(组开始时除外)。因此,当发生回溯机制时,无法返回最后的“ a”字符。只有整个小组都可以退还。


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


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


查看完整回答
反对 回复 2019-12-21
?
慕哥9229398

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


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


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


查看完整回答
反对 回复 2019-12-21
?
一只斗牛犬

因为regex模块没有回溯控制动词(来自Perl和PHP)的功能,这些功能允许这样的操作:$res = preg_split('~({(?>[^{}]+|(?1))*})(*SKIP)(*FAIL)|\s+~', $str);。您所能做的就是将这种模式与findall / iter:r'({(?>[^{}]+|(?1))*})|[^\s{]+'或类似的东西一起使用。

查看完整回答
反对 回复 2019-12-21

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信