Python

正则表达式中的递归模式

发布于 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。

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

显然，我冒着被以下人员击落的风险：

不要用正则表达式解析html
用pyparse做到这一点
编写适当的词法分析器和解析器，例如使用ply

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

关注者

被浏览

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

知识点

Python

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

去下载看看

正则表达式中的递归模式

说明：