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

Question

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

那么在Python中，有没有类似的功能呢？我们能不能通过一些变通的方法，用正则表达式来实现这个功能？（不过看起来现在的正则表达式实现并不是专门为这种问题设计的）

Answer 1

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

import re

def parse_nested(text, left=r'[(]', right=r'[)]', sep=r','):
    """ https://stackoverflow.com/a/17141899/190597 (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

Answer 2

正则表达式无法处理嵌套结构。根据定义，嵌套结构不是规则的。它们不能通过常规语法构建，也不能被有限状态自动机解析（可以把正则表达式看作是有限状态自动机的一种简写方式）。

现在的“正则表达式”引擎有时支持一些有限的“嵌套”结构，但从技术角度来看，这些就不应该再叫“规则”的了。

Answer 3

一般来说，使用Python的正则表达式是无法做到这一点的。（.NET的正则表达式有扩展功能，比如“平衡组”，这让它可以处理嵌套匹配。）

不过，PyParsing是一个非常不错的工具，适合处理这类问题：

from pyparsing import nestedExpr

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

输出结果是：

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

关于PyParsing的更多信息：

• http://pyparsing.wikispaces.com/Documentation