Verschachtelte Konstrukte erkennen

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

Microsoft hat dem Regex-Paket in .NET eine sehr interessante Erweiterung hinzugefügt, mit der man beliebige verschachtelte Konstrukte erkennen kann – etwas, was mit regulären Ausdrücken eigentlich nicht möglich ist. Die Erweiterung ist nicht ganz einfach zu verstehen und wird hier dennoch nur kurz beschrieben.

Am einfachsten illustrieren wir die Erweiterung mit einem Beispiel:

Dim R As Regex = New Regex(" \(                    " & _
                           "   (?>                 " & _
                           "       [^()]+          " & _
                           "     |                 " & _
                           "       \( (?<TIEFE>)   " & _
                           "     |                 " & _
                           "       \) (?<-TIEFE>)  " & _
                           "   )*                  " & _
                           "   (?(TIEFE)(?!))      " & _
                           " \)                    ",  _
       RegexOptions.IgnorePatternWhitespace)

Diese Regex erkennt das erste geschlossene, äußerste Klammerpaar, auch wenn es weitere, beliebig verschachtelte Klammerpaare enthält, also beispielsweise den unterstrichenen Teil von ›vorher (nixda (oja (hier) isjagut) nachher‹. Die erste öffnende Klammer wird nicht erkannt, weil die schließende Klammer dazu fehlt.

Ich beschreibe nur ganz kurz, wie das vor sich geht:

  1. Bei jedem gefundenen ›(‹ wird mit der benannten Klammer ˹(?<TIEFE>)˼ die Verschachtelungstiefe der Regex-Maschine um eins erhöht (die Tiefe, die über die Klammer ganz am Anfang der Regex hinausgeht).
  2. Bei jedem gefundenen ›)‹ bewirkt das neue Konstrukt ˹(?<-TIEFE>)˼, dass von der entsprechenden Variable wieder eins subtrahiert wird.
  3. Mit ˹(?(TIEFE)(?!))˼ wird sichergestellt, dass diese Variable den Wert null hat, wenn die Regex-Maschine das literale ˹\)˼ am Ende erreicht.

Das funktioniert deshalb, weil im Backtrack-Stack der Regex-Maschine nachgeführt wird, wie viele Gruppen erfolgreich erkannt wurden. ˹(?<TIEFE>)˼ ist lediglich eine benannte Version von ˹()˼, das natürlich immer passt. Weil diese Klammer direkt nach dem ˹\(˼ kommt, kann diese erfolgreich erkannte Gruppe als Zählervariable für die öffnenden Klammern benutzt werden.

Die Anzahl der erkannten ›TIEFE‹-Gruppen (und damit der öffnenden Klammern) ist also im Backtrack-Stack gespeichert. Von dieser implizit gespeicherten Verschachtelungstiefe würden wir gern eins subtrahieren, wenn eine schließende Klammer gefunden wird. Genau das bewirkt das spezielle Konstrukt ˹(?<-TIEFE>)˼. Damit wird die letzte erkannte ˹(?<TIEFE>)˼-Gruppe vom Stack genommen. Wenn der Backtrack-Stack keine solche Gruppe enthält, passt auch ˹(?<-TIEFE>)˼ nicht, und es wird ein Fehlschlag zurückgegeben. So wird verhindert, dass überschüssige schließende Klammern erkannt werden.

Das Konstrukt ˹(?(TIEFE)(?!))˼ am Ende ist ein normaler bedingter Klammerausdruck, der dem Unterausdruck ˹(?!)˼ entspricht, wenn die ›TIEFE‹-Gruppe noch existiert. Sie existiert nur dann, wenn nicht genügend schließende Klammern gefunden wurden und damit nicht alle Verschachtelungsebenen mit ˹(?<-TIEFE>)˼ zu null subtrahiert wurden. Wenn dieser Fall eintritt, gehen die Klammern offenbar nicht auf, und wir erzeugen mit dem leeren negativen Lookahead ˹(?!)˼ einen Fehlschlag.

Puh! Auf diese Weise kann man mit den regulären Ausdrücken von .NET verschachtelte Konstrukte erkennen.

  

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