Können reguläre Ausdrücke verwendet werden verschachtelte Muster übereinstimmen? [Duplikat]

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

  •  02-07-2019
  •  | 
  •  

Frage

    

Diese Frage bereits eine Antwort hier:

         

Ist es möglich, einen regulären Ausdruck zu schreiben, die ein verschachteltes Muster übereinstimmt, die eine unbekannte Anzahl von Malen auftritt? Zum Beispiel kann eine Öffnungs- und Schließ Klammer übereinstimmen ein regulärer Ausdruck, wenn eine unbekannte Anzahl von Öffnungs- / Schließ Klammern sind innerhalb der äußeren Klammern verschachtelt?

Zum Beispiel: 

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

  // More { }
} // End

Sollte übereinstimmen: 

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

  // More { }
}
War es hilfreich?

Lösung

Nein. So einfach ist das. Ein endlicher Automat (die die Datenstruktur einen regulären Ausdruck zugrunde liegt) nicht Speicher abgesehen von dem Zustand, in es ist, und wenn Sie beliebig tiefe Verschachtelung haben, müssen Sie einen beliebig großen Automaten, die mit dem Begriff einer kollidiert endlicher Automat.

Sie können bis zu einer festgelegten Tiefe verschachtelt / gepaart Elemente Spiel, wo die Tiefe nur von Ihrem Speicher begrenzt ist, da der Automat sehr groß wird. In der Praxis jedoch, sollten Sie einen Pushdown-Automaten, das heißt einen Parser für eine kontextfreie Grammatik, zum Beispiel LL (top-down) oder LR (bottom-up) verwenden. Sie haben das schlechtere Laufzeitverhalten zu berücksichtigen: O (n ^ 3) gegenüber O (n), mit n = Länge (Eingang)

.

Es gibt viele Parser-Generatoren avialable, zum Beispiel ANTLR für Java. Das Finden einer bestehenden Grammatik für Java (oder C) ist auch nicht schwer.
Weitere Hintergrund: Automata Theory bei Wikipedia

Andere Tipps

Verwenden von regulären Ausdrücken für verschachtelte Muster zu überprüfen, ist sehr einfach. 

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

Wahrscheinlich Perl-Lösung arbeiten, wenn die Zeichenfolge in einer Zeile: 

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

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

HTH

EDIT: überprüfen:

Und noch eine Sache von Torsten Marek (die zu Recht darauf hingewiesen hatte, dass es nicht ein regulärer Ausdruck ist mehr) :

Ja, wenn es .NET RegEx-Engine ist. .NET-Engine unterstützt finiten Zustandsmaschine mit einem externen Stapel zugeführt. finden Sie unter Details

Pumping Lemma für reguläre Sprachen ist der Grund, warum Sie nicht das tun kann.

Der erzeugte Automat wird eine endliche Anzahl von Zuständen haben, sagen k, so dass eine Reihe von k + 1 Öffnung Zahnspange ist verpflichtet, einen Zustand irgendwo haben wiederholt (wie der Automat die Zeichen verarbeitet). Der Teil des Strings zwischen dem gleichen Zustand kann unendlich oft dupliziert werden und der Automat wird den Unterschied nicht kennen.

Insbesondere dann, wenn es k + 1 Öffnung Klammern gefolgt von k + 1 Schließen Klammer akzeptiert (was es soll) es wird auch die gepumpte Anzahl von Öffnungs Klammern durch unverändert k + 1 Schließen Brases gefolgt akzeptieren (was sollte es nicht ).

Die richtigen Reguläre Ausdrücke wären es nicht in der Lage sein zu tun, wie Sie in das Reich der Regular Sprachen verlassen würden in den Context Free Sprachen Gebiete zu landen.

Dennoch ist die „regulärer Ausdruck“ Pakete, die viele Sprachen anbieten, sind streng leistungsfähiger.

Zum Beispiel Lua reguläre Ausdrücke haben die „%b()“ Erkenner, die ausgewogene Klammer übereinstimmen. In Ihrem Fall würden Sie "%b{}"

verwenden

Eine andere hoch entwickelte Tool ähnlich wie sed ist gema , wo Sie ausgewogene geschweiften Klammern sehr leicht mit {#} übereinstimmen.

So, abhängig von den Tool, die Sie zu Ihrer Verfügung, um Ihren „regulärer Ausdruck“ haben (im weiteren Sinne) kann möglicherweise verschachtelte Klammern entsprechen.

Mit der rekursiven Matching in den PHP-Regex-Engine schneller massiv als prozedurale Abstimmung von Klammern. vor allem bei längeren Strings.

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

z. 

$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

... unter der Annahme, dass es eine maximale Anzahl von Verschachtelungen ist man glücklich sein würde bei zu stoppen.

Lassen Sie mich erklären.

@ torsten-marek richtig, dass ein regulärer Ausdruck nicht für verschachtelte Muster wie diese überprüfen kann, ABER ist es möglich, definieren ein verschachtelter RegexMuster, die Sie verschachtelte Strukturen wie diese bis zu einem gewissen maximalen Tiefe erfassen können. I eine erstellt zu erfassen EBNF-Stil Kommentare ( versuchen sie es hier out), wie: 

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

Die Regex (für einzelne eingehende Kommentare) ist die folgende: 

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

Dies leicht für Ihre Zwecke angepasst werden könnte, indem die \(+\*+ und \*+\)+ mit { und } ersetzen und alles dazwischen mit einem einfachen [^{}] ersetzen: 

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

( Hier ist der Link dass auszuprobieren.)

So verschachteln, erlauben nur dieses Muster innerhalb des Blocks selbst: 

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

Triple-verschachtelte Blöcke zu finden, verwenden: 

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

Ein klares Muster entstanden. Um Kommentare zu einer Tiefe von N verschachtelt, verwenden Sie einfach die Regex: 

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

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

könnte ein Skript geschrieben werden, um rekursiv diese reguläre Ausdrücke zu erzeugen, aber das ist über den Rahmen dessen, was ich brauche dies für. (Dies ist für den Leser als Übung.

als zsolt erwähnt, einige Regex-Engines unterstützen Rekursion - natürlich diese sind in der Regel diejenigen, die einen Backtracking-Algorithmus verwenden, so dass es nicht besonders effizient sein wird. Beispiel: /(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm

Nein, Sie werden immer in den Bereich der Context Free Grammatiken an diesem Punkt .

Dies scheint zu funktionieren: /(\{(?:\{.*\}|[^\{])*\})/m

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top