在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