在Python中使用正则expression式匹配嵌套结构
我似乎记得DotNet中的正则expression式有一个特殊的机制，它允许嵌套结构的正确匹配，比如“ ( (a ( ( c ) b ) ) ( d ) e ) ”中的分组。
什么是这个function的Python等值？ 这可以通过使用正则expression式来解决吗？ （虽然似乎是当前正则expression式的实现不是为了devise的问题）
通常不能使用Python正则expression式来执行此操作。 （.NET正则expression式已经扩展了“平衡组”，这就是允许嵌套匹配的原因。）
不过，PyParsing对于这种types的东西来说是一个很好的包：
from pyparsing import nestedExpr data = "( (a ( ( c ) b ) ) ( d ) e )" print nestedExpr().parseString(data).asList()
输出是：
[[['a', [['c'], 'b']], ['d'], 'e']]
更多关于PyParsing：
正则expression式不能分析嵌套结构。 根据定义，嵌套结构不是常规的。 它们不能用正则语法来构造，而且不能用有限状态自动机来parsing（正则expression式可以被看作是FSA的简写符号）。
今天的“正则expression式”引擎有时支持一些有限的“嵌套”构造，但从技术angular度来看，它们不应该被称为“规则”了。
编辑：我已经略微修改，以接受任意的正则expression式模式来指定分隔符和项目分隔符，比我原来的re.Scanner解决scheme更快，更简单：
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正则expression式匹配，但使用re.Scanner构build一个基本的parsing器（可以处理嵌套结构）非常容易：
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)*(cd))")) # [[['a+b'], '*', ['c-d']]] p = NestedParser() print(p.parse("( (a ( ( c ) b ) ) ( d ) e )")) # [[['a', [['c'], 'b']], ['d'], 'e']]
默认情况下， NestedParser匹配嵌套圆括号。 您可以传递其他正则expression式来匹配其他嵌套模式，如括号[] 。 例如 ，
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可以完成比上面的代码更多的function。 但是对于这个单一的目的，上面的NestedParser比小string要快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
Python不支持在正则expression式中recursion。 所以，在Perl中，.NET平衡组或PCRE正则expression式的等价物并不是立即可能的。
就像你自己说的：这不是一个你应该用一个正则expression式解决的问题。
我build议从正则expression式本身去除嵌套，循环遍历结果并对其执行正则expression式。
你在谈论recursion吗？ 从你的问题不清楚。 一个例子：
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')
这显示了嵌套组的匹配。 组的编号取决于模式中左括号的顺序。
