Patrón recursivo en expresiones regulares

Esto está muy relacionado con la expresión regular para que coincida con los corchetes externos. Sin embargo, ¿quiero saber específicamente 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 visto algunas afirmaciones de que los patrones recursivos se pueden usar para igualar paréntesis equilibrados, pero no hay ejemplos que usen el paquete regex de python (Nota: no es compatible con el patrón recursivo, necesita usar regex).

Una afirmación es que la syntax es b(?:m|(?R))*e donde:

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


Quiero extraer coincidencias para las llaves externas en lo siguiente:

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

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

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

(En mi ejemplo, estaba usando finditer (sobre objetos coincidentes), vea aquí ).

Así que esperaba que lo 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 confundido por [] o error: too much backtracking .

¿Es posible extraer objetos coincidentes 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 un analizador adecuados, por ejemplo, utilizando capas

Quiero enfatizar que se trata de cómo usar el patrón recursivo (que si mi comprensión es correcta, nos lleva fuera del análisis del lenguaje regular, ¡por lo que en realidad puede ser posible!). Si se puede hacer, esta debería ser una solución más limpia.

El patrón es:

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

Puedes ver 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 paréntesis. 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 de expresiones regulares retrocederá el grupo atómico por grupo atómico en lugar de carácter por carácter. Para llevar a casa este punto, puedes 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 función 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 (de forma predeterminada) registra (en previsión) todas las posiciones de seguimiento de 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 el comienzo del grupo). Entonces, cuando se produce el mecanismo de retroceso, el último carácter “a” no se puede devolver. Solo se puede devolver todo el grupo.

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

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

Pude hacer esto sin problemas con la syntax de b(?:m|(?R))*e :

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

Manifestación


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