¿Se pueden usar expresiones regulares para unir patrones anidados? [duplicar]

StackOverflow https://stackoverflow.com/questions/133601

  •  02-07-2019
  •  | 
  •  

Pregunta

    

Esta pregunta ya tiene una respuesta aquí:

         

¿Es posible escribir una expresión regular que coincida con un patrón anidado que se produce un número desconocido de veces? Por ejemplo, ¿puede una expresión regular coincidir con una llave de apertura y cierre cuando hay un número desconocido de llaves de apertura / cierre anidadas dentro de las llaves exteriores?

Por ejemplo: 

public MyMethod()
{
  if (test)
  {
    // More { }
  }

  // More { }
} // End

Debería coincidir: 

{
  if (test)
  {
    // More { }
  }

  // More { }
}
¿Fue útil?

Solución

No. Es fácil. Un autómata finito (que es la estructura de datos subyacente a una expresión regular) no tiene memoria aparte del estado en el que se encuentra, y si tiene un anidado arbitrariamente profundo, necesita un autómata arbitrariamente grande, que choca con la noción de un autómata finito.

Puede hacer coincidir elementos anidados / emparejados hasta una profundidad fija, donde la profundidad solo está limitada por su memoria, porque el autómata se vuelve muy grande. Sin embargo, en la práctica, debe usar un autómata push-down, es decir, un analizador para una gramática libre de contexto, por ejemplo, LL (arriba-abajo) o LR (abajo-arriba). Debe tener en cuenta el peor comportamiento en tiempo de ejecución: O (n ^ 3) frente a O (n), con n = longitud (entrada).

Hay muchos generadores de analizadores disponibles, por ejemplo ANTLR para Java. Encontrar una gramática existente para Java (o C) tampoco es difícil.
Para obtener más información, consulte Teoría de los autómatas en Wikipedia

Otros consejos

Usar expresiones regulares para verificar patrones anidados es muy fácil. 

'/(\((?>[^()]+|(?1))*\))/'

Probablemente esté funcionando la solución Perl, si la cadena está en una línea: 

my $NesteD ;
$NesteD = qr/ \{( [^{}] | (??{ $NesteD }) )* \} /x ;

if ( $Stringy =~ m/\b( \w+$NesteD )/x ) {
    print "Found: $1\n" ;
  }

HTH

EDITAR: comprobar:

Y una cosa más por Torsten Marek (que había señalado correctamente, que ya no es una expresión regular) :

Sí, si es .NET RegEx-engine. El motor .Net admite máquinas de estado finito suministradas con una pila externa. ver detalles

El Bombeo de lemma para idiomas regulares es la razón por la que no puedes hacer eso.

El autómata generado tendrá un número finito de estados, digamos k, por lo que una cadena de llaves de apertura k + 1 tendrá un estado repetido en alguna parte (mientras el autómata procesa los caracteres). La parte de la cadena entre el mismo estado se puede duplicar infinitamente muchas veces y el autómata no notará la diferencia.

En particular, si acepta k + 1 llaves de apertura seguidas de k + 1 llaves de cierre (que debería) también aceptará el número bombeado de llaves de apertura seguidas de k + 1 frases de cierre sin cambios (que no debería ).

Las expresiones regulares adecuadas no podrían hacerlo ya que dejarías que el ámbito de los idiomas regulares aterrizara en los territorios de los idiomas libres del contexto.

Sin embargo, la "expresión regular" los paquetes que ofrecen muchos idiomas son estrictamente más potentes.

Por ejemplo, Lua las expresiones regulares tienen el " % b () " ; Reconocedor que coincidirá con paréntesis equilibrados. En su caso, usaría " % b {} "

Otra herramienta sofisticada similar a sed es gema , donde combinará llaves rizadas equilibradas muy fácilmente con {#} .

Entonces, dependiendo de las herramientas que tenga a su disposición, su "expresión regular" (en un sentido más amplio) puede coincidir con paréntesis anidados.

El uso de la coincidencia recursiva en el motor de expresiones regulares de PHP es mucho más rápido que la coincidencia de procedimiento entre paréntesis. especialmente con cadenas más largas.

http://php.net/manual/en/regexp.reference.recursive.php

por ejemplo 

$patt = '!\( (?: (?: (?>[^()]+) | (?R) )* ) \)!x';

preg_match_all( $patt, $str, $m );

vs. 

matchBrackets( $str );

function matchBrackets ( $str, $offset = 0 ) {

    $matches = array();

    list( $opener, $closer ) = array( '(', ')' );

    // Return early if there's no match
    if ( false === ( $first_offset = strpos( $str, $opener, $offset ) ) ) {
        return $matches;
    }

    // Step through the string one character at a time storing offsets
    $paren_score = -1;
    $inside_paren = false;
    $match_start = 0;
    $offsets = array();

    for ( $index = $first_offset; $index < strlen( $str ); $index++ ) {
        $char = $str[ $index ];

        if ( $opener === $char ) {
            if ( ! $inside_paren ) {
                $paren_score = 1;
                $match_start = $index;
            }
            else {
                $paren_score++;
            }
            $inside_paren = true;
        }
        elseif ( $closer === $char ) {
            $paren_score--;
        }

        if ( 0 === $paren_score ) {
            $inside_paren = false;
            $paren_score = -1;
            $offsets[] = array( $match_start, $index + 1 );
        }
    }

    while ( $offset = array_shift( $offsets ) ) {

        list( $start, $finish ) = $offset;

        $match = substr( $str, $start, $finish - $start );
        $matches[] = $match;
    }

    return $matches;
}

SÍ

... asumiendo que hay un número máximo de anidamientos en los que te gustaría parar.

Déjame explicarte.

@ torsten-marek tiene razón en que una expresión regular no puede verificar patrones anidados como este, PERO es posible definir un patrón de expresión regular anidado que le permitirá capturar estructuras anidadas como esta hasta cierta profundidad máxima . Creé uno para capturar estilo EBNF comentarios ( pruébelo aquí ), como: 

(* This is a comment (* this is nested inside (* another level! *) hey *) yo *)

La expresión regular (para comentarios de profundidad única) es la siguiente: 

m{1} = \(+\*+(?:[^*(]|(?:\*+[^)*])|(?:\(+[^*(]))*\*+\)+

Esto podría ser fácilmente adaptado para sus propósitos reemplazando \ (+ \ * + y \ * + \) + con { y } y reemplazando todo entre un simple [^ {}] : 

p{1} = \{(?:[^{}])*\}

( Aquí está el enlace para probarlo.

Para anidar, solo permita este patrón dentro del bloque mismo: 

p{2} = \{(?:(?:p{1})|(?:[^{}]))*\}
  ...or...
p{2} = \{(?:(?:\{(?:[^{}])*\})|(?:[^{}]))*\}

Para encontrar bloques anidados triples, use: 

p{3} = \{(?:(?:p{2})|(?:[^{}]))*\}
  ...or...
p{3} = \{(?:(?:\{(?:(?:\{(?:[^{}])*\})|(?:[^{}]))*\})|(?:[^{}]))*\}

Ha surgido un patrón claro. Para encontrar comentarios anidados a una profundidad de N , simplemente use la expresión regular: 

p{N} = \{(?:(?:p{N-1})|(?:[^{}]))*\}

  where N > 1 and
  p{1} = \{(?:[^{}])*\}

Se podría escribir un script para generar recexivamente estas expresiones regulares, pero eso está más allá del alcance de lo que necesito para esto. (Esto se deja como un ejercicio para el lector. & # 128521;)

como mencionó zsolt, algunos motores regex admiten la recursividad; por supuesto, estos suelen ser los que usan un algoritmo de retroceso, por lo que no será particularmente eficiente. ejemplo: / (? > [^ {}] *) {(? > [^ {}] *) (? R) * (? > [^ {}] *)} / sm

No, te estás metiendo en el ámbito de gramáticas libres de contexto en ese punto .

Esto parece funcionar: /(\{(?:\{.*\}|[^\{font>)*\})/m

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top