logo标签列表

在Python中使用正则表达式匹配嵌套结构

pythonregexrecursive-regex
19

我记得DotNet中的正则表达式有一种特殊机制，可以正确匹配嵌套结构，比如在“( (a ( ( c ) b ) ) ( d ) e )”中的分组。

那么Python中有没有相应的功能？是否可以使用一些变通方法来实现这个功能呢？（虽然似乎当前的正则表达式实现并没有为此类问题而设计）

6个回答
22

正则表达式无法解析嵌套结构。按照定义，嵌套结构不是正则的。它们不能由正则语法构造，也不能被有限状态自动机解析（正则表达式可以看作是有限状态自动机的简写符号）。

今天的“regex”引擎有时支持一些有限的“嵌套”结构，但从技术角度来看，它们不应再被称为“正则表达式”了。

7
这是一条重要信息，点赞。需要注意的是，添加嵌套支持并不是无害的。真正的正则表达式引擎很酷的一点是，在处理时不需要额外的内存，除了用来存储状态机的常量和记住当前状态的变量。另一个好处是运行速度，我认为与输入长度成线性关系。添加嵌套支持会破坏这两个优势。 - harms
1
@harms：Python的正则表达式已经是非正则的（它们支持反向引用），并且可以演示指数行为re.match(r'(A+)*B', 'A'*n)。R = r'[^()]*' \n for _ in range(expr.count('(')): R = f'(?:{R}|\({R}\))+\n re.fullmatch(R, expr)。这里有一个O(n**2)的算法：is_prime = lambda n: not re.fullmatch(r'1?|(11+?)\1+', '1'*n)。虽然添加递归支持会使正则表达式成为比现在更大的问题（但“我们都是自愿的成年人”）。 - jfs
21
你通常无法使用Python正则表达式来完成这个任务。（.NET正则表达式已经扩展了“平衡组”，这就是允许嵌套匹配的原因。）但是，PyParsing是用于此类任务非常好的软件包：
from pyparsing import nestedExpr

data = "( (a ( ( c ) b ) ) ( d ) e )"
print nestedExpr().parseString(data).asList()

输出结果为：

[[['a', [['c'], 'b']], ['d'], 'e']]

关于 PyParsing 的更多信息：

1
Pyparsing不再托管在wikispaces.com上。请访问https://github.com/pyparsing/pyparsing。 - PaulMcG
15

编辑：falsetru的嵌套解析器，我稍微修改了一下，使其可以接受任意的正则表达式模式来指定分隔符和项分隔符，比我的原始re.Scanner解决方案更快更简单:

import re

def parse_nested(text, left=r'[(]', right=r'[)]', sep=r','):
    """ https://dev59.com/CmQn5IYBdhLWcg3wCzik#17141899 (falsetru) """
    pat = r'({}|{}|{})'.format(left, right, sep)
    tokens = re.split(pat, text)
    stack = [[]]
    for x in tokens:
        if not x or re.match(sep, x):
            continue
        if re.match(left, x):
            # Nest a new list inside the current list
            current = []
            stack[-1].append(current)
            stack.append(current)
        elif re.match(right, x):
            stack.pop()
            if not stack:
                raise ValueError('error: opening bracket is missing')
        else:
            stack[-1].append(x)
    if len(stack) > 1:
        print(stack)
        raise ValueError('error: closing bracket is missing')
    return stack.pop()

text = "a {{c1::group {{c2::containing::HINT}} a few}} {{c3::words}} or three"

print(parse_nested(text, r'\s*{{', r'}}\s*'))
产出。
['a', ['c1::group', ['c2::containing::HINT'], 'a few'], ['c3::words'], 'or three']

仅使用 Python 正则表达式无法匹配嵌套结构，但使用 re.Scanner 构建基本解析器（可以处理嵌套结构）非常容易：

import re

class Node(list):
    def __init__(self, parent=None):
        self.parent = parent

class NestedParser(object):
    def __init__(self, left='\(', right='\)'):
        self.scanner = re.Scanner([
            (left, self.left),
            (right, self.right),
            (r"\s+", None),
            (".+?(?=(%s|%s|$))" % (right, left), self.other),
        ])
        self.result = Node()
        self.current = self.result

    def parse(self, content):
        self.scanner.scan(content)
        return self.result

    def left(self, scanner, token):
        new = Node(self.current)
        self.current.append(new)
        self.current = new

    def right(self, scanner, token):
        self.current = self.current.parent

    def other(self, scanner, token):
        self.current.append(token.strip())

它可以这样使用：

p = NestedParser()
print(p.parse("((a+b)*(c-d))"))
# [[['a+b'], '*', ['c-d']]]

p = NestedParser()
print(p.parse("( (a ( ( c ) b ) ) ( d ) e )"))
# [[['a', [['c'], 'b']], ['d'], 'e']]

默认情况下，NestedParser 匹配嵌套括号。您可以传递其他正则表达式来匹配其他嵌套模式，例如方括号 []。 例如，

p = NestedParser('\[', '\]')
result = (p.parse("Lorem ipsum dolor sit amet [@a xxx yyy [@b xxx yyy [@c xxx yyy]]] lorem ipsum sit amet"))
# ['Lorem ipsum dolor sit amet', ['@a xxx yyy', ['@b xxx yyy', ['@c xxx yyy']]],
# 'lorem ipsum sit amet']

p = NestedParser('<foo>', '</foo>')
print(p.parse("<foo>BAR<foo>BAZ</foo></foo>"))
# [['BAR', ['BAZ']]]
当然，pyparsing 可以实现的远不止上述代码所示的功能。但是对于这个单一的目的，上述的NestedParser对于小字符串来说大约快了5倍：
In [27]: import pyparsing as pp

In [28]: data = "( (a ( ( c ) b ) ) ( d ) e )"    

In [32]: %timeit pp.nestedExpr().parseString(data).asList()
1000 loops, best of 3: 1.09 ms per loop

In [33]: %timeit NestedParser().parse(data)
1000 loops, best of 3: 234 us per loop

对于更长的字符串，速度约快28倍：

In [44]: %timeit pp.nestedExpr().parseString('({})'.format(data*10000)).asList()
1 loops, best of 3: 8.27 s per loop

In [45]: %timeit NestedParser().parse('({})'.format(data*10000))
1 loops, best of 3: 297 ms per loop
这是一个很棒的提示！甚至没听说过re.Scanner。这将完全回答我昨天的问题。如果它没有被关闭，我会选择这个答案……再次感谢您让我知道！ - hetsch
我和原帖的作者一样遇到了同样的问题，但你的解决方案有一个方面让我无法使用它：似乎它从结果的末尾删除了所有空格字符。如何才能使列出的任何字符串末尾的空格保留下来？ - DocBuckets
@DocBuckets：你能给一个输入和期望输出的例子吗？只有字符串末尾的空格需要保留吗，还是任何地方都需要保留？最后一个闭合括号后面是否有空格？ - unutbu
@unutbu 我正在解析以下字符串：`string = "a {{c1::group {{c2::containing::HINT}} a few}} {{c3::words}} or three"`使用上面的NestedParser代码和{{，}}作为我的分隔符。该代码不会保留例如"group "和"{{c2 ::"之间的空格。 - DocBuckets
@DocBuckets：我已编辑我的答案，展示了一种替代方法，它（我认为）可以按预期解析“string”。 - unutbu
显示剩余2条评论
3

Python不支持正则表达式中的递归。因此，在Python中无法立即实现.NET的平衡组或Perl中的PCRE正则表达式。

就像你自己所说的一样：这不是你应该用单个正则表达式解决的问题。

PCRE支持使用(?R)指令等递归模式。Python可能支持旧版PCRE，但不支持更新版本。http://en.wikipedia.org/wiki/Perl_Compatible_Regular_Expressions - Il-Bhima
1
我建议从正则表达式本身中删除嵌套，循环遍历结果并对其执行正则表达式。
0
你是在谈论递归吗？从你的问题中并不清楚。这里有一个例子：
ActivePython 2.6.1.1 (ActiveState Software Inc.) based on
Python 2.6.1 (r261:67515, Dec  5 2008, 13:58:38) [MSC v.1500 32 bit (Intel)] on
win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import re
>>> p = re.compile(r"((\w+((\d+)[.;]))(\s+)\d)")
>>> m = p.match("Fred99. \t9")
>>> m
<_sre.SRE_Match object at 0x00454F80>
>>> m.groups()
('Fred99. \t9', 'Fred99.', '9.', '9', ' \t')

这展示了嵌套组的匹配。组的编号取决于它们在模式中开括号出现的顺序。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接