Regular Expressions

Regex Balanced Groups - Stackmanipulation und die blanke Theorie

Die regulären Ausdrücke in der .net-Implementierung (wie auch in PERL, Javascript, PHP, Java, …) folgen schon lange nicht mehr den regulären Sprachen. Das geht zwar mit enormen Performanceeinbußen einher, da man dies nur noch per Backtracking statt als endlichen Automaten umsetzen kann, doch auf die Vielfalt an Möglichkeiten will man offensichtlich auch nicht verzichten.

Eine dieser Erweiterung in .net betreffen die Möglichkeit, einen Stack zu verwalten. Diese Möglichkeit wird häufig unter dem Begriff Balanced Groups geführt. Um damit schön herumspielen zu können, werden aber gleich drei verschiedene Konstrukte benötigt.

Capture Groups

Es gibt benannte (named capture group) und - so lange RegexOptions.ExplicitCapture nicht verwendet wird - auch unbenannte (unnamed capture group) Gruppierungskonstrukte. Es können zwar beide Varianten für die Stackmanipulation herangezogen werden, aufgrund der Fehleranfälligkeit gehe ich aber hier nur auf die benannten Gruppen ein.
Diese folgen dabei dem Muster:

RegexOption.IgnorePatternWhitespace
1
2
(?<name>subpattern) # bzw.
(?'name'subpattern)

Der Text, der durch subpattern gefunden wird, landet auf dem Stack (auch Slot genannt) mit dem angegebenen Namen.
Will man mehr als einen Wert auf den Stack legen, kann dies mit der Angabe des gleichen Namens oder mit Wiederholungen hinbekommen.
So lange für subpattern keine Entsprechung im Text gefunden, wird auch nichts auf den Stack gelegt.

Grob in Pseudocode übersetzt werden kann der Ausdruck mit

1
2
3
if (subpattern.IsMatch()) {
    name.push(subpattern.Text);
}

Beispiele

Mit den Ausdruck

RegexOption.IgnorePatternWhitespace
1
2
(?<test>\w)+
(?<test>\w{2})

und dem Text "Hallo" erhält man also einen Stack mit dem Namen test auf dem 4 Werten liegen.

lo
l
a
H
test

Die ersten 3 Werte stammen vom Teilausdruck (?<test>\w)+. Hierbei wird jedes einzelne Zeichen der Reihe nach auf den Stack gelegt. Der letzte Wert stammt vom hinteren Teilausdruck (?<test>\w{2}) und wird ebenfalls auf den Stack mit dem Namen test gelegt.

Mit Capture Groups kann man also Daten auf die einzelnen Stacks verteilen (push).

vom Stack entfernen

Genauso, wie man Elemente auf den Stack legen kann, kann man diese auch wieder entfernen (pop). Hierzu wird vor den Namen ein Minus-Zeichen gestellt, also

1
(?<-name>subpattern)

Der Wert wird nur entfernt, wenn der subpattern an der Stelle auch passt. Diese Bedingung darf aber auch leer sein und trifft damit immer zu - mit einer Einschränkung: wenn der Stack bereits leer ist, gilt (?<-name>) als Nicht-Treffer.

Übersetzt werden kann der Ausdruck in etwa so:

1
2
3
4
5
6
7
if (subpattern.IsMatch()) {
    if (name.Count > 0) {
        name.pop();
    } else {
        return false; // Abbruch
    }
}

Beispiel

Mit dem regulären Ausdruck

RegexOption.IgnorePatternWhitespace
1
2
3
(?<test>\w)+
(?<-test>)
(?<test>\w{2})

bekommt man beim Text "Hallo" den Stack

lo
a
H
test

zu sehen. Nachdem die einzelnen Buchstaben von Hal auf dem Stack gelegt wurden, wird der letzte davon (l) wieder entfernt und danach die letzten beiden Buchstaben (lo) auf den Stack gelegt.

Die Bedingung von (?<-test>) ist dabei leer und wird daher immer ausgeführt, wenn etwas auf dem Stack liegt. Ist nichts auf dem Stack, führt der pop-Versuch zu einem Nicht-Treffer.

Balanced Groups

Die Stack-Operationen können auch gemischt werden - die eigentlichen Balanced Groups. Hierbei handelt es sich aber nicht nur um eine verkürzte Schreibweise.

RegexOption.IgnorePatternWhitespace
1
2
3
(?<name1>
    (?<-name2>subpattern)
)

prüft, ob subpattern vorhanden ist, entfernt den obersten Eintrag des Stacks name2 und legt den gefundenen Teilstring daraufhin auf den Stack mit dem Namen name1. Die Reihenfolge der Operationen lässt sich umkehren, indem man <name1> und <-name2> vertauscht.

1
(?<name1-name2>subpattern)

funktioniert dagegen etwas anders.
Statt den durch subpattern gefundenen Teil des Textes auf den Stack name1 zu legen, wird dort der Teil des Textes, der zwischen dem obersten Eintrag von name2 und subpattern liegt hinzugefügt.

Beispiel

Wieder wird der Text "Hallo" verwendet. Mit dem regulären Ausdruck

1
2
3
4
(?<test>\w).*
(?<test>
    (?<-test>\w)
)

bekommt man den Stack

o
test

zu sehen.
Dreht man die Reihenfolge um zu

1
2
3
4
(?<test>\w).*
(?<-test>
    (?<test>\w)
)

sieht man dagegen

H
test

In diesem Fall wird zuerst der letzte Buchstabe auf den Stack gelegt, danach aber gleich wieder entfernt.

Verwendet man allerdings die gemischte Form

1
2
(?<test>\w).*
(?<test-test>\w)

erhält man den Stack

all
test

all entspricht dabei dem, was durch .* selektiert wurde.
Damit lässt sich z.B. ein Klammernpaar finden (auch verschachtelt) und der dazwischenliegende Teil auf den Stack legen.

Group Test

Mit einem Group Test kann man prüfen, ob mindestens ein Wert auf den Stack liegt und entsprechend darauf reagieren. Leider lässt sich der Inhalt nicht testen (zumindest nicht, ohne den Eingabetext entsprechend zu gestalten).

RegexOption.IgnorePatternWhitespace
1
2
3
4
(?(name)
    yes|
    no
)

Es ist also vollkommen egal, welcher Wert auf dem Stack liegt - sobald “etwas” auf dem Stack mit dem angegebenen Namen liegt, wird die yes-Subexpression verwendet, ansonsten die optionale no-Subexpression.

Auch dieser Ausdruck lässt sich in Pseudocode übersetzen:

1
2
3
4
5
if (name.Count > 0) {
    yes();
} else {
    no();
}

Falls name keiner gültigen Gruppe entspricht, wird der Teil des Ausdrucks als Subexpression gewertet (in dem Fall als Literal), d.h. es wird im Text nach den Zeichen gesucht.

Beispiel

Mit dem regulären Ausdruck

RegexOption.IgnorePatternWhitespace
1
2
3
4
5
6
7
(
    (?(test)
        (?<-test>)
    )
    (?<test>\w)
)+
(?<test>\w{2})

bekommt man beim Text "Hallo" den Stack

lo
l
test

(?(test)(?<-test>)) prüft hierbei vor dem drauflegen der einzelnen Buchstaben auf den Stack, ob etwas auf dem Stack ist und löscht das oberste Elemente falls das so ist.

Backreference

Mit dem Rückverweis kann man testen, ob als nächstes im zu prüfenden String die Buchstaben vorkommen, die als letztes auf den Stack gelegt wurden. Der “klassische” Rückverweis macht dies anhand eines Index (z.B. \1). Daneben gibt es aber auch eine benannte Variante

RegexOption.IgnorePatternWhitespace
1
2
\k<name>     # bzw. in anderer Schreibweise
\k'name'

Beispiel

RegexOption.IgnorePatternWhitespace
1
2
(?<test>.)  # legt ein Zeichen auf den Stack
\k<test>+   # findet alle weiteren vorkommen dieses einen Zeichens

\k<test> findet wirklich nur den Buchstaben, der zuvor auf den Stack gelegt wurde.
Beim Text aaargh wäre das demnach nur die Folge aaa.

Ende der Theorie - was macht man nun damit

So unscheinbar die einzelnen Konstrukte auch sein mögen. Was man hier vorfindet ist ein fast vollständiger Kellerautomat (auch pushdown automaton genannt) mit mehreren Kellerspeichern. Das “fast“ bezieht sich auf das Fehlen der Möglichkeit, den Wert der Kellerstapel direkt zu prüfen (ohne auf die Eingabe zuzugreifen)..

Beispiel

Im Wikipedia-Artikel steht ein Beispiel einer kontextfreien Sprache L = {an bn | n>0}, was soviel bedeutet, dass nach der Angabe beliebig vieler (>0) a‘s genauso viele b‘s vorhanden sein müssen (und sonst nichts), damit das Wort der Sprache entspricht. Somit gehört das Wort aabb zur Sprache L, aabbb aber nicht.
Das kann man mit regulären Ausdrücken nicht prüfen - wenn Sie denn regulär sind. Mit Hilfe der Balanced Groups funktioniert es aber.

RegexOption.IgnorePatternWhitespace
1
2
3
4
5
6
7
8
9
^                 # am Anfang der Zeile starten
(?<keller>a)+     # einzelne a's am Anfang auf den Stack legen
(?(keller)        # falls etwas auf dem Stack liegt
    (?<-keller>b) # b matchen und vom Stapel entfernen
)+
(?(keller)        # falls etwas auf dem Stack liegt
    (?!)          # abbrechen
)
$                 # Sicherstellen, dass keine weiteren Zeichen mehr vorhanden sind