regular - paquete re python
Coincidencia de estructuras anidadas con expresiones regulares en Python (6)
¿Estás hablando de recursión? No está claro de su 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 la coincidencia de grupos anidados. La numeración de los grupos depende del orden en que aparece su paréntesis de apertura en el patrón.
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 característica? ¿Se puede lograr esto usando expresiones regulares con alguna solución? (Aunque parece ser el tipo de problema para el que no están diseñadas las implementaciones actuales de expresiones regulares)
Las expresiones regulares no pueden analizar 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 ser vista como una notación abreviada para una FSA).
Los motores "regex" de hoy en día soportan algunas construcciones limitadas de "anidamiento", pero desde un punto de vista técnico, ya no deberían llamarse "regulares".
No puedes hacer esto generalmente usando expresiones regulares de Python. (Las expresiones regulares de .NET se han ampliado con "grupos de equilibrio", que es lo que permite coincidencias anidadas).
Sin embargo, PyParsing es un paquete muy bueno 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:
Python no admite la recursión en expresiones regulares. Por lo tanto, los equivalentes a los grupos de balanceo de .NET o las expresiones regulares de PCRE en Perl no son inmediatamente posibles en Python.
Como usted mismo dijo: este NO es un problema que realmente deba resolver con una sola expresión regular.
Recomiendo eliminar el agrupamiento de la expresión regular, repitiendo los resultados y realizando expresiones regulares en eso.
Edición: el analizador anidado de falsetru , que he modificado ligeramente para aceptar patrones de expresiones regulares arbitrarias para especificar delimitadores y separadores de elementos, es más rápido y más simple que mi solución re.Scanner original:
import re
def parse_nested(text, left=r''[(]'', right=r''[)]'', sep=r'',''):
""" https://.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*''))
rendimientos
[''a'', [''c1::group'', [''c2::containing::HINT''], ''a few''], [''c3::words''], ''or three'']
Las estructuras anidadas no se pueden emparejar solo con expresiones regulares de Python, pero es muy fácil construir un analizador básico (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 así:
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 coincide con paréntesis anidados. Puede pasar otras expresiones regulares para que coincidan con otros patrones anidados, como corchetes, [] . Por ejemplo ,
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, el uso de pyparsing puede hacer mucho más que el código anterior. Pero para este único propósito, el NestedParser anterior es aproximadamente 5 veces más rápido para cadenas pequeñas:
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 cuerdas 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