Können reguläre Ausdrücke verwendet werden, um verschachtelte Muster zu vergleichen?

Question

Ist es möglich, einen regulären Ausdruck zu schreiben, der einem verschachtelten Muster entspricht, das eine unbekannte Anzahl von Malen vorkommt? Kann ein regulärer Ausdruck beispielsweise einer öffnenden und schließenden geschweiften Klammer entsprechen, wenn in den äußeren geschweiften Klammern eine unbekannte Anzahl von öffnenden/schließenden geschweiften Klammern vorhanden ist?

Zum Beispiel:

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

    // More { } 
} // End 

Sollte entsprechen:

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

    // More { } 
} 

Answer 1

Nein. Es ist so einfach. Ein endlicher Automat (die Datenstruktur, die einem regulären Ausdruck zugrunde liegt) hat kein Gedächtnis außer dem Zustand, in dem er sich befindet, und wenn Sie eine beliebig tiefe Verschachtelung haben, benötigen Sie einen beliebig großen Automaten, der mit dem Begriff endliche kollidiert Automat.

Sie können verschachtelte/gepaarte Elemente bis zu einer festen Tiefe zuordnen, wobei die Tiefe nur durch Ihren Speicher begrenzt wird, da der Automat sehr groß wird. In der Praxis sollten Sie jedoch einen Push-Down-Automaten verwenden, d. H. Einen Parser für eine kontextfreie Grammatik, beispielsweise LL (von oben nach unten) oder LR (von unten nach oben). Sie müssen das schlechtere Laufzeitverhalten berücksichtigen: O (n^3) gegen O (n), mit n = Länge (Eingabe).

Es gibt viele Parser-Generatoren verfügbar, zum Beispiel ANTLR für Java. Eine vorhandene Grammatik für Java (oder C) zu finden, ist ebenfalls nicht schwierig.
Weiteren Hintergrund: Automata Theory bei Wikipedia

Answer 2

Nein, Sie sind in das Reich an diesem Punkt der Context Free Grammars bekommen.

Answer 3

Nein. Sie benötigen einen vollständigen Parser für diese Art von Problem.

Answer 4

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

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

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

HTH

EDIT: Kontrolle:

• http://dev.perl.org/perl6/rfc/145.html
• Rubin Informationen: http://www.ruby-forum.com/topic/112084
• mehr Perl: http://www.perlmonks.org/?node_id=660316
• noch Perl: https://metacpan.org/pod/Text::Balanced
• perl, perl, perl: http://perl.plover.com/yak/regex/samples/slide083.html

Und noch eine Sache von Torsten Marek (die zu Recht darauf hingewiesen hatte, dass es kein Regex mehr):

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

Answer 5

Die Pumping lemma for regular languages ist der Grund, warum Sie das nicht tun können.

Der erzeugte Automat wird eine endliche Anzahl von Zuständen haben, sagen wir k, so dass eine Kette von k + 1 öffnenden Klammern irgendwo wiederholt werden muss (da der Automat die Zeichen verarbeitet). Der Teil der Zeichenkette zwischen dem gleichen Zustand kann unendlich viele Male dupliziert werden und der Automat wird den Unterschied nicht kennen.

Insbesondere, wenn es k + 1 öffnende Klammern gefolgt von k + 1 schließenden Klammern akzeptiert (was es sollte), akzeptiert es auch die gepumpte Anzahl von öffnenden Klammern gefolgt von unveränderten k + 1 schließenden Klammern (was es nicht t).

Answer 6

Korrekte reguläre Ausdrücke könnten dies nicht tun, da Sie den Bereich regulärer Sprachen verlassen würden, um in den kontextfreien Sprachen zu landen.

Nichtsdestoweniger sind die Pakete "regulärer Ausdruck", die viele Sprachen anbieten, strenger.

Zum Beispiel haben Lua reguläre Ausdrücke den "" Erkenner, der mit ausgeglichenen Klammern übereinstimmt. In Ihrem Fall würden Sie „%b{}“

Ein weiteres entwickeltes Werkzeug ähnlich wie sed verwenden ist gema, wo Sie ausgewogene geschweiften Klammern sehr leicht mit {#} übereinstimmen.

Also, abhängig von den Werkzeugen, die Sie zur Verfügung haben, kann Ihr "regulärer Ausdruck" (im weiteren Sinne) in der Lage sein, verschachtelte Klammern zu finden.

Answer 7

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

Answer 8

Ja, wenn es .NET RegEx-Engine ist. Die .Net-Engine unterstützt Finite-State-Maschinen, die mit einem externen Stack ausgestattet sind. siehe details

Answer 9

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

Answer 10

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

Answer 11

Das rekursive Matching in der PHP-Regex-Engine ist massiv schneller als das prozedurale Matching von Klammern. besonders bei längeren Saiten.

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

z.B.

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

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

gegen

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 12

Meine question+answer verwendet ist und ich mache einen Ausdruck und Meta-Ausdruck, die beliebig (endlich) Verschachtelungsebenen mithalten kann. Es ist ziemlich fug, aber was kann man sonst noch erwarten? Verwenden Sie Rückwärtsreferenzen in der Übereinstimmung, wenn Ihre Engine dies unterstützt.