regex - online - ¿Se pueden usar expresiones regulares para hacer coincidir patrones anidados?

regex replace()

Question

¿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 apertura y cierre cuando hay un número desconocido de llaves abiertas / cerradas anidadas dentro de las llaves externas?

Por ejemplo:

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

  // More { }
} // End

Debe coincidir

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

  // More { }
}

Answer 1

SÍ

... asumiendo que hay un número máximo de anidamientos en los que estaría dispuesto a pasar.

Dejame explicar.

tiene razón en que una expresión regular no puede verificar patrones anidados como este, PERO es posible definir un patrón regex anidado que le permita capturar estructuras anidadas como esta hasta una profundidad máxima . EBNF-style uno para capturar comentarios de EBNF-style ( 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 los /(+/*+ y /*+/)+ con { y } y reemplazando todo lo que esté en medio con un simple [^{}] :

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

( Aquí está el enlace para probarlo).

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

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

Para encontrar bloques triple-anidados, 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 de forma recursiva 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. 😉)

Answer 2

El lema de bombeo para los 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 k + 1 llaves de apertura está obligada a tener un estado repetido en algún lugar (ya que 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 de cierre de frases (que no debería).

Answer 3

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 cuerdas más largas.

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

p.ej

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

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

contra

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;
}

Answer 4

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

Answer 5

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

Sin embargo, los paquetes de "expresiones regulares" que ofrecen muchos idiomas son estrictamente más poderosos.

Por ejemplo, las expresiones regulares de Lua tienen el reconocedor " %b() " que coincidirá con el paréntesis equilibrado. En tu caso usarías " %b{} "

Otra herramienta sofisticada similar a sed es gema , en la que unirás las llaves equilibradas muy fácilmente con {#} .

Por lo tanto, dependiendo de las herramientas que tenga a su disposición, su "expresión regular" (en un sentido más amplio) puede ser capaz de coincidir entre paréntesis anidados.

Answer 6

Mi question+answer está relacionada y hago una expresión y una metaexpresión que pueden coincidir con niveles arbitrarios (finitos) de anidación. Es bastante feo, pero ¿qué más puedes esperar? Utilice referencias inversas en la coincidencia si su motor lo admite.

Answer 7

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

Answer 8

No. Es así de 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 más información: Teoría de autómatas en Wikipedia.

Answer 9

No. Necesita un analizador completo para este tipo de problema.

Answer 10

Probablemente funcione 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:

• http://dev.perl.org/perl6/rfc/145.html
• Información de ruby: http://www.ruby-forum.com/topic/112084
• más perl: http://www.perlmonks.org/?node_id=660316
• aún más perl: https://metacpan.org/pod/Text::Balanced
• perl, perl, perl: http://perl.plover.com/yak/regex/samples/slide083.html

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

• http://coding.derkeiler.com/Archive/Perl/comp.lang.perl.misc/2008-03/msg01047.html

Answer 11

Sí, si es .NET RegEx-engine. El motor .Net es compatible con la máquina de estados finitos que se suministra con una pila externa. ver details

Answer 12

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

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

Answer 13

como mencionó zsolt, algunos motores de expresiones regulares son compatibles con la recursión; por supuesto, estos suelen ser los que utilizan un algoritmo de seguimiento por lo que no será particularmente eficiente. ejemplo: /(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm