Le espressioni regolari possono essere utilizzate per abbinare modelli nidificati? [duplicare]

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

  •  02-07-2019
  •  | 
  •  

Domanda

    

Questa domanda ha già una risposta qui:

         

È possibile scrivere un'espressione regolare che corrisponde a un modello nidificato che si verifica un numero sconosciuto di volte? Ad esempio, un'espressione regolare può abbinare una parentesi graffa di apertura e chiusura quando vi è un numero sconosciuto di parentesi graffe aperte / chiuse nidificate all'interno delle parentesi graffe esterne?

Ad esempio: 

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

  // More { }
} // End

Dovrebbe corrispondere: 

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

  // More { }
}
È stato utile?

Soluzione

No. È così facile Un automa finito (che è la struttura dei dati alla base di un'espressione regolare) non ha memoria a parte lo stato in cui si trova, e se si ha un annidamento arbitrariamente profondo, è necessario un automa arbitrariamente grande, che si scontra con la nozione di automa finito

Puoi abbinare elementi nidificati / accoppiati fino a una profondità fissa, dove la profondità è limitata solo dalla tua memoria, perché l'automa diventa molto grande. In pratica, tuttavia, è necessario utilizzare un automa push-down, ovvero un parser per una grammatica senza contesto, ad esempio LL (top-down) o LR (bottom-up). Devi tenere conto del peggior comportamento in fase di runtime: O (n ^ 3) vs. O (n), con n = lunghezza (input).

Esistono numerosi generatori di parser disponibili, ad esempio ANTLR per Java. Anche trovare una grammatica esistente per Java (o C) non è difficile.
Per ulteriori informazioni: Teoria degli automi su Wikipedia

Altri suggerimenti

L'uso delle espressioni regolari per verificare la presenza di schemi nidificati è molto semplice. 

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

Probabilmente funzionante soluzione Perl, se la stringa è su una riga: 

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

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

HTH

MODIFICA: verifica:

E un'altra cosa di Torsten Marek (che aveva sottolineato correttamente, che non è più una regex) :

Sì, se si tratta di .NET RegEx-engine. Il motore .Net supporta una macchina a stati finiti fornita con uno stack esterno. vedi dettagli

Il Lemma di pompaggio per le lingue normali è il motivo per cui non puoi farlo.

L'automa generato avrà un numero finito di stati, diciamo k, quindi una stringa di parentesi graffe k + 1 è destinata ad avere uno stato ripetuto da qualche parte (mentre l'automa elabora i caratteri). La parte della stringa tra lo stesso stato può essere duplicata all'infinito molte volte e l'automa non conoscerà la differenza.

In particolare, se accetta k + 1 parentesi graffe di apertura seguite da k + 1 parentesi graffe di chiusura (che dovrebbe) accetterà anche il numero pompato di parentesi graffe di apertura seguite da k + 1 parentesi chiuse invariate (che non dovrebbe ).

Le espressioni regolari appropriate non sarebbero in grado di farlo poiché lasceresti il ??regno delle lingue regolari per approdare nei territori delle lingue libere dal contesto.

Tuttavia l'espressione " espressione regolare " i pacchetti che offrono molte lingue sono strettamente più potenti.

Ad esempio, Lua le espressioni regolari hanno " % b () " ; riconoscitore che corrisponderà alla parentesi bilanciata. Nel tuo caso useresti " % b {} "

Un altro strumento sofisticato simile a sed è gema , dove abbinerai molto facilmente parentesi graffe bilanciate con {#} .

Quindi, a seconda degli strumenti che hai a disposizione, la tua "espressione regolare" (in senso lato) potrebbe essere in grado di abbinare la parentesi nidificata.

L'uso della corrispondenza ricorsiva nel motore regex di PHP è enormemente più veloce della corrispondenza procedurale delle parentesi. specialmente con stringhe più lunghe.

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

per es. 

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

YES

... supponendo che ci sia un numero massimo di annidamenti in cui saresti felice di fermarti.

Lasciami spiegare.

@ torsten-marek ha ragione sul fatto che un'espressione regolare non può verificare la presenza di schemi nidificati come questo, MA è possibile definire un modello di regex nidificato che ti permetterà di catturare strutture nidificate come questa fino a una profondità massima . Ne ho creato uno per catturare i commenti in stile EBNF ( provalo qui ), come: 

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

La regex (per commenti a profondità singola) è la seguente: 

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

Questo potrebbe essere facilmente adattato ai tuoi scopi sostituendo \ (+ \ * + e \ * + \) + con { e } e sostituendo tutto quello che c'è in mezzo con un semplice [^ {}] : 

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

( Ecco il link per provarlo.)

Per nidificare, basta consentire questo modello all'interno del blocco stesso: 

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

Per trovare blocchi a triplo annidamento, utilizzare: 

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

È emerso un modello chiaro. Per trovare commenti nidificati a una profondità di N , usa semplicemente regex: 

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

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

Uno script potrebbe essere scritto per generare ricorsivamente queste regex, ma questo va oltre lo scopo di ciò di cui ho bisogno. (Questo è lasciato come esercizio per il lettore. & # 128521;)

come menzionato zsolt, alcuni motori regex supportano la ricorsione - ovviamente, questi sono in genere quelli che usano un algoritmo di backtracking, quindi non sarà particolarmente efficiente. esempio: / (? > [^ {}] *) {(? > [^ {}] *) (? R) * (? > [^ {}] *)} / sm

No, stai entrando nel regno di Context Free Grammars a quel punto .

Sembra che funzioni: /(\{(?:\{.*\}|[^\{[)*\})/m

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top