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

Question

我似乎记得DotNet中的正则表达式有一个特殊的机制，允许嵌套结构的正确匹配，如“((a ((c) b)) (d) e)”中的分组。

什么是这个功能的python等值？这可以通过使用正则表达式来解决吗？ （虽然它似乎是目前的正则表达式的实现不是为那种问题设计的）

Answer 1

你不能通常使用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

Answer 2

我建议从正则表达式本身去除嵌套，循环遍历结果并对其执行正则表达式。

Answer 3

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

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

Answer 4

你说的是递归吗？你的问题并不清楚。举例：

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') 

这显示了嵌套组的匹配。组的编号取决于模式中其左括号出现的顺序。

Answer 5

正则表达式不能解析嵌套结构。根据定义，嵌套结构不是常规的。它们不能用正则语法构造，并且它们不能被有限状态自动机解析（正则表达式可以被看作是FSA的简写符号）。

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

Answer 6

编辑：falsetru's nested parser，我已经略作修改，以接受任意正则表达式模式，以指定分隔符和项目分隔符，比我原来的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嵌套括号匹配。您可以传递其他正则表达式来匹配其他嵌套模式，例如括号[]。 For example，

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 

和更快的放大字符串周围28X：

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