Klammern zählen: Reicht ein regulärer Ausdruck?
Im Kurs „Formale Sprachen“ soll ein Konfigurationsformat geprüft werden. Eine Regel sieht so aus: regel { bedingung { aktion } }. Blöcke dürfen beliebig tief verschachtelt werden, und jedes { muss ein passendes } haben. Ein Schüler schlägt den regulären Ausdruck ^\{.*\}$ vor und argumentiert, damit seien alle ungültigen Eingaben erkannt. Im Test akzeptiert der Ausdruck die Eingabe { { } } } – zwei öffnende, drei schließende Klammern – obwohl sie ungültig ist. Bei einer Eingabe mit 500 Verschachtelungsebenen stürzt anschließend das Programm ab, das die Struktur mit einer rekursiven Funktion auswertet. Die Lehrkraft möchte wissen, ob man das Problem „einfach mit einem besseren regulären Ausdruck“ lösen kann, und wie ein sauberer Aufbau aus Lexer und Parser aussehen würde. Der Schüler hält entgegen, moderne Regex-Engines könnten doch rekursiv matchen.
1. Widerlegen Sie die Behauptung, ein regulärer Ausdruck könne alle ungültigen Eingaben erkennen: mit dem Gegenbeispiel und mit einer Skizze des Pumping-Lemmas für reguläre Sprachen.
Read the worked answer
Gegenbeispiel: ^\{.*\}$ verlangt nur, dass die Zeichenkette mit { beginnt und mit } endet. { { } } } erfüllt das, obwohl die Klammern nicht ausbalanciert sind. Ein weiterer Schwachpunkt: . matcht standardmäßig kein Zeilenende, mehrzeilige Konfigurationen werden also selbst bei korrekter Klammerung abgelehnt.
Pumping-Lemma: Sei L die Menge der ausbalancierten Klammerwörter und L regulär. Dann gibt es eine Pumping-Länge n. Wähle w = {^n }^n, es gilt |w| ≥ n. Nach dem Lemma ist w = xyz mit |xy| ≤ n, |y| ≥ 1, und x y^i z ∈ L für alle i ≥ 0. Wegen |xy| ≤ n liegt y vollständig im Präfix aus öffnenden Klammern, besteht also nur aus {. Für i = 2 enthält x y² z mehr öffnende als schließende Klammern und ist damit nicht in L – Widerspruch. Also ist L nicht regulär.
Anschaulich: Ein endlicher Automat hat endlich viele Zustände und kann sich nicht merken, ob 17 oder 500 Klammern offen sind. Er müsste für jede Tiefe einen eigenen Zustand haben. Formal zeigt das auch der Satz von Myhill-Nerode: Die Wörter {^i liegen paarweise in verschiedenen Äquivalenzklassen, es gibt also unendlich viele.
Ein „besserer regulärer Ausdruck“ kann das prinzipiell nicht leisten, weil die Grenze nicht in der Schreibweise, sondern in der Sprachklasse liegt.
2. Geben Sie einen deterministischen Prüfalgorithmus an, beweisen Sie seine Korrektheit über eine Invariante und erläutern Sie Zeit- und Speicherbedarf sowie die Grenzen des Verfahrens.
Read the worked answer
zaehler = 0
für jedes Zeichen c der Eingabe:
wenn c == '{': zaehler = zaehler + 1
wenn c == '}': zaehler = zaehler - 1
wenn zaehler < 0: Fehler (zu viele schließende)
am Ende: gültig genau dann, wenn zaehler == 0
Invariante: Nach dem Lesen eines Präfixes p gilt: Wenn p noch nie negativ war, ist zaehler die Anzahl der in p noch nicht geschlossenen öffnenden Klammern. Induktion über die Präfixlänge: Für das leere Präfix ist der Zähler 0; jedes { erhöht die Zahl der offenen Klammern um eins, jedes } schließt die zuletzt geöffnete und verringert sie um eins. Daraus folgt: Ein negatives Zwischenergebnis bedeutet, dass ein } ohne offenes { auftritt; ein Endstand 0 bedeutet, dass jede geöffnete Klammer geschlossen wurde. Beide Richtungen zusammen ergeben die Korrektheit – auch die zweite ist nötig: Ohne die Negativprüfung würde }{ mit Endstand 0 fälschlich akzeptiert.
Aufwand: ein Durchlauf, O(n) Zeit; eine ganze Zahl, O(1) Speicher. Das ist besser als der rekursive Ansatz, dessen Speicher O(Tiefe) ist und der bei 500 Ebenen den Aufrufstack sprengt.
Grenzen: Das Verfahren funktioniert nur, weil es genau eine Klammerart gibt. Bei (), [] und {} muss man sich die Reihenfolge merken; dann braucht man einen echten Stack, also einen Kellerautomaten. Der Zähler ist der Spezialfall davon.
3. Wo ist der reguläre Ausdruck trotzdem sinnvoll einzusetzen? Beschreiben Sie den Aufbau aus Lexer und Parser und beurteilen Sie das Argument „moderne Regex-Engines können rekursiv matchen“.
Read the worked answer
Sinnvoll ist der reguläre Ausdruck auf der Token-Ebene. Der Lexer erkennt mit kleinen, klar umrissenen Mustern: Schlüsselwort regel, Identifier [A-Za-z_][A-Za-z0-9_]*, Klammer, Semikolon, Zahl. Diese Sprachen sind regulär, und ein DFA oder ein entsprechendes Muster ist dafür das richtige Werkzeug – schnell, deklarativ, leicht testbar. Der Parser arbeitet danach auf der Tokenfolge und prüft die Struktur mit dem Zähler bzw. bei mehreren Klammerarten mit einem Stack. Diese Trennung ist auch didaktisch wertvoll: Sie zeigt, dass „passt das Zeichen“ und „passt die Struktur“ zwei verschiedene Fragen sind.
Zu den rekursiven Regex-Engines: PCRE und einige andere erlauben rekursive Unterausdrücke oder Balancing Groups. Damit lässt sich das Problem lösen – aber dann nutzt man kein reguläres Konstrukt mehr, sondern im Kern einen Kellerautomaten, der in einer Regex-Syntax versteckt ist. Folgen: Das Muster ist nicht mehr portabel (Python re, Java und POSIX unterscheiden sich), das Verhalten bei tiefer Rekursion ist engine-abhängig (Stack-Overflow oder Backtracking-Explosion), und die Sprache ist nicht mehr regulär, was das Pumping-Lemma-Argument nicht entkräftet, sondern bestätigt. Für ein Prüfprogramm ist ein expliziter Parser transparenter und besser testbar.