正则表达式中的递归模式

发布于 2021-01-29 15:08:41

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

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


显然,我冒着被以下人员击落的风险:

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

关注者
0
被浏览
98
1 个回答
  • 面试哥
    面试哥 2021-01-29
    为面试而生,有面试问题,就找面试哥。

    模式是:

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


知识点
面圈网VIP题库

面圈网VIP题库全新上线,海量真题题库资源。 90大类考试,超10万份考试真题开放下载啦

去下载看看