python3 - python string expresiones regulares

Patrón recursivo en expresiones regulares

Question

Esto está muy relacionado con la expresión regular para que coincida con los corchetes exteriores , sin embargo, específicamente quiero saber cómo o si es posible hacer el patrón recursivo de esta expresión regular . Todavía tengo que encontrar un ejemplo de Python usando esta estrategia, así que creo que esta debería ser una pregunta útil.

He seen some claims that los patrones recursivos se pueden usar para hacer coincidir los paréntesis equilibrados, pero no hay ejemplos que usen el paquete de expresiones regulares de python (Nota: re no es compatible con el patrón recursivo, debe usar expresiones regulares).

Una seen es que la sintaxis es b(?:m|(?R))*e donde:

b es lo que comienza la construcción, m es lo que puede ocurrir en el medio de la construcción, y e es lo que puede ocurrir al final de la construcción

Quiero extraer coincidencias para las llaves externas de la siguiente manera:

"{1, {2, 3}} {4, 5}"
["1, {2, 3}", "4, 5"] # desired

Tenga en cuenta que esto es fácil de hacer lo mismo para llaves internas :

re.findall(r"{([^{}]*)}", "{1, {2, 3}} {4, 5}")
[''2, 3'', ''4, 5'']

(En mi ejemplo, yo estaba usando el buscador (sobre los objetos del partido), mira here .)

Así que esperaba que la siguiente, o alguna variación, funcionara:

regex.findall(r"{(:[^{}]*|?R)}", "{1, {2, 3}} {4, 5}")
regex.findall(r"({(:[^{}]*|?R)})", "{1, {2, 3}} {4, 5}")
regex.findall(r"({(:.*|(?R))*})", "{1, {2, 3}} {4, 5}")
regex.findall(r"({(:.*)|(?R)*})", "{1, {2, 3}} {4, 5}")
regex.findall(r"({(:[^{}])|(?R)})", "{1, {2, 3}} {4, 5}")

pero estoy arruinado por [] o error: too much backtracking .

¿Es posible extraer objetos de coincidencia para el paréntesis externo utilizando la recursión de expresiones regulares?

Obviamente, corro el riesgo de ser derribado con:

• no analizar html con expresiones regulares
• haz esto con pyparse
• escriba un lexer y analizador apropiado, por ejemplo, usando capas

Quiero enfatizar que se trata de cómo utilizar el patrón recursivo (que si mi comprensión es correcta, nos lleva fuera del análisis de lenguaje habitual, ¡así que puede ser realmente posible!). Si se puede hacer, esto debería ser una solución más limpia.

Answer 1

El patrón es:

{((?>[^{}]+|(?R))*)}

Puedes ver que esto funciona para tu ejemplo:

regex.findall("{((?>[^{}]+|(?R))*)}", "{1, {2, 3}} {4, 5}")
# [''1, {2, 3}'', ''4, 5'']

Explicación:

La parte m necesita excluir los corchetes. El uso de un grupo atómico es necesario si desea al mismo tiempo permitir un cuantificador para [^{}] y repetir el grupo sin problemas de retroceso catastrófico. Para ser más claros, si falta el último corchete de cierre, este motor regex retrocederá al grupo atómico por grupo atómico en lugar de carácter por carácter. Para llevar a casa este punto, puede hacer que el cuantificador sea posesivo así: {((?>[^{}]+|(?R))*+)} (o {((?:[^{}]+|(?R))*+)} ya que el grupo atómico no es más útil).

El grupo atómico (?>....) y el cuantificador posesivo ?+ , *+ , ++ son los dos lados de la misma característica. Esta característica prohíbe que el motor de expresiones regulares retroceda dentro del grupo de caracteres que se convierte en un "átomo" (algo que no se puede dividir en partes más pequeñas) .

Los ejemplos básicos son los siguientes dos patrones que siempre fallan para la cadena aaaaaaaaaab :

(?>a+)ab
a++ab

es decir:

regex.match("a++ab", "aaaaaaaaaab")
regex.match("(?>a+)ab", "aaaaaaaaaab")

Cuando usa (?:a+) o a+ el motor de expresiones regulares (por defecto) graba (en previsión) todas las posiciones de retroceso para todos los caracteres. Pero cuando se usa un grupo atómico o un cuantificador posesivo, estas posiciones de retroceso no se registran más (excepto en el comienzo del grupo). Entonces, cuando ocurre el mecanismo de retroceso, el último carácter "a" no puede devolverse. Solo el grupo completo puede ser devuelto.

[EDIT]: el patrón se puede escribir de una manera más eficiente si usa un subpatrón "desenrollado" para describir el contenido entre paréntesis:

{([^{}]*+(?:(?R)[^{}]*)*+)}

Answer 2

Pude hacer esto sin problema con la sintaxis b(?:m|(?R))*e :

{((?:[^{}]|(?R))*)}

Demo

Creo que la clave de lo que estabas intentando es que la repetición no continúa en m , sino en todo el grupo (?:m|(?R)) . Esto es lo que permite la recursión con la referencia (?R) .