Mit Codemustern verschachtelte Konstrukte erkennen

(Auszug aus "Reguläre Ausdrücke" von Jeffrey E. F. Friedl)

Das Beispiel aus Verschachtelte Paare mit dynamischen regulären Ausdrücken erkennen hat uns gezeigt, wie man verschachtelte Klammern mit einem dynamischen Regex-Konstrukt erkennen kann. Das ist im Allgemeinen die einfachste Methode, aber es geht auch mit Codemustern.

Der Ansatz ist recht einfach: Wir zählen die öffnenden und die schließenden Klammern und lassen schließende nur zu, wenn noch offene hängig sind. Wir werden die Klammern in Codemustern zählen, aber zuvor betrachten wir das (noch nicht funktionsfähige) Grundgerüst des regulären Ausdrucks:

my $VerschachtelteInnereien = qr{
  (?>
    (?:
       # Weder öffnende noch schließende Klammern
        [^()]+
       # Öffnende Klammer
       |  \(
       # Schließende Klammer
       |  \)
    )*
  )
}x;

Die atomare Gruppierung dient der Effizienz und verhindert, dass aus ˹([...]+|...)*˼ ein ewiges Matching wird (siehe Zurück zur Realität), wenn $VerschachtelteInnereien in einem Ausdruck verwendet wird, der Backtracking auslösen kann. Wenn man m/^\( $VerschachtelteInnereien \)$/x auf ›(hier fehlt die schließende Klammer‹ anwenden würde, würde die Regex-Maschine lange Zeit innerhalb des Ausdrucks $VerschachtelteInnereien voranschreiten und wieder zurückkrebsen, wenn die atomare Klammer nicht die unnötigen gespeicherten Zustände verhindern würde.

Für die Zählung der Klammern gehen wir in vier Schritten vor:

  1. Zuerst muss der Zähler mit null initialisiert werden:

    (?{ local $OffeneKlammern = 0 })

  2. Wenn wir eine öffnende Klammer antreffen, inkrementieren wir den Zähler und sagen so, dass noch entsprechend viele schließende Klammern benötigt werden:

    (?{ $OffeneKlammern++ })

  3. Bei einer schließenden Klammer zählen wir herunter, aber nur, wenn die Anzahl der offenstehenden Klammern positiv ist. Wenn diese Anzahl null ist, haben wir offenbar mehr schließende Klammern als öffnende. Wir erzeugen in diesem Fall mit ˹(?!)˼ einen Fehlschlag:

    (?(?{ $OffeneKlammern }) (?{ $OffeneKlammern-- }) | (?!) )

    Hier verwenden wir ein ˹(? if then|else-Konstrukt (siehe Bedingte reguläre Ausdrücke), bei dem das Codemuster im Bedingungsteil auftritt.

  4. Am Ende der Mustersuche überprüfen wir, ob der Zähler auf Null steht. Wenn nicht, war offenbar die Anzahl der schließenden Klammern kleiner als die der öffnenden, und das ist ein Fehler:

    (?(?{ $OffeneKlammern != 0 })(?!))

Wir fügen diese Elemente in unser Gerüst ein:

my $VerschachtelteInnereien = qr{
  (?{ local $OffeneKlammern = 0 }) #  1. Zählt die offenen bzw. noch zu schließenden Klammern.
  (?> # Atomare Gruppe ist effizienter
     (?:
        # Weder öffnende noch schließende Klammern
          [^()]+
        # 2.  Öffnende Klammer
        |  \(  (?{ $OffeneKlammern++ } )
        # 3.  Schließende Klammer erlauben, wenn noch Klammern offen sind
        |  \)  (?(?{ $OffeneKlammern != 0 }) (?{ $OffeneKlammern-- }) | (?!) )
     )*
  )
  (?(?{ $OffeneKlammern != 0 })(?!)) #  4. Fehlschlag, falls am Ende noch Klammern offen sind.
}x;

Diese Regex kann jetzt anstelle von $Tiefe_N aus Verschachtelte Paare mit dynamischen regulären Ausdrücken erkennen benutzt werden.

Die Deklaration von $OffeneKlammern mit local ist nur eine Vorsichtsmaßnahme, falls diese globale Variable woanders im Programm benutzt würde. Das Problem mit dem Backtracking wie bei den local-Variablen aus dem letzten Abschnitt besteht hier nicht; die Variable tritt in einem atomaren Konstrukt auf, und damit ist garantiert, dass eine einmal erkannte Alternative nicht via Backtracking zurückgegeben wird. In diesem Fall ist die atomare Klammer nicht nur ein Effizienzgewinn, sondern sie stellt auch sicher, dass die Zählervariable $OffeneKlammern immer mit der Anzahl der tatsächlich erkannten Klammern übereinstimmt.

  

<< zurück vor >>

 

 

 

Tipp der data2type-Redaktion:
Zum Thema Reguläre Ausdrücke bieten wir auch folgende Schulungen zur Vertiefung und professionellen Fortbildung an:
   

Copyright der deutschen Ausgabe © 2008 by O’Reilly Verlag GmbH & Co. KG
Für Ihren privaten Gebrauch dürfen Sie die Online-Version ausdrucken.
Ansonsten unterliegt dieses Kapitel aus dem Buch "Reguläre Ausdrücke" denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.

O’Reilly Verlag GmbH & Co. KG, Balthasarstr. 81, 50670 Köln