Coincidencia de estructuras anidadas con expresiones regulares en Python

Question

Me parece recordar que las expresiones regulares en DotNet tienen un mecanismo especial que permite la coincidencia correcta de las estructuras anidadas, como la agrupación en "((a ((c) b)) (d) e)".

¿Cuál es el equivalente de Python de esta función? ¿Se puede lograr esto usando expresiones regulares con alguna solución temporal? (Aunque parece ser el tipo de problema que las implementaciones actuales de regex no están diseñadas para)

Answer 1

Generalmente, no puede hacer esto utilizando expresiones regulares de Python. (Las expresiones regulares de .NET se han ampliado con "grupos de equilibrio", que es lo que permite las coincidencias anidadas.)

Sin embargo, PyParsing es un muy buen paquete para este tipo de cosas:

from pyparsing import nestedExpr 

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

La salida es:

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

Más sobre PyParsing:

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

Answer 2

Recomendaría eliminar el anidamiento de la expresión regular en sí, al recorrer los resultados y realizar expresiones regulares sobre eso.

Answer 3

Python no es compatible con la recursión en expresiones regulares. Por lo tanto, los equivalentes a los grupos de equilibrio de .NET o PCRE regex en Perl no son inmediatamente posibles en Python.

Como usted mismo dijo: esto NO es un problema que realmente debería resolver con una sola expresión regular.

Answer 4

¿Estás hablando de recursividad? No está claro por tu pregunta. Un ejemplo:

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

Esto muestra coincidencia de grupos anidados. La numeración de los grupos depende del orden en que se produce el paréntesis de apertura en el patrón.

Answer 5

Expresiones regulares no se puede parse estructuras anidadas. Las estructuras anidadas no son regulares, por definición. No pueden ser construidos por una gramática regular, y no pueden ser analizados por un autómata de estado finito (una expresión regular puede verse como una notación abreviada para una FSA).

Los motores "regex" de hoy en día admiten algunas construcciones de "anidación" limitadas, pero desde un punto de vista técnico, ya no deberían llamarse "regulares".

Answer 6

Editar:falsetru's nested parser, que he modificado ligeramente para que los patrones de expresiones regulares arbitrarias para especificar delimitadores y separador de elementos, es más rápido y más simple que mi solución original 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*')) 

produce

['a', ['c1::group', ['c2::containing::HINT'], 'a few'], ['c3::words'], 'or three'] 

---

Las estructuras anidadas no se pueden combinar con Python regex solo, pero es notablemente fácil t o construir un analizador de base (que puede manejar estructuras anidadas) usando 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()) 

Se puede utilizar la siguiente manera:

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

Por defecto NestedParser partidos paréntesis anidados. Puede pasar otras expresiones regulares para que coincidan con otros patrones anidados, como los corchetes, []. 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']]] 

---

Por supuesto, pyparsing puede hacer mucho más que el código anterior lata. Sin embargo, para este único propósito, lo anterior NestedParser es de aproximadamente 5 veces más rápido para las pequeñas cadenas:

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 

y alrededor de 28x más rápido para las cadenas más grandes:

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