Reguläre Ausdrücke verstehen

Reguläre Ausdrücke haben den Ruf, ein kryptischer Zeichensalat zu sein: ^[\w.%+-]+@[\w.-]+\.[a-zA-Z]{2,}$ wirkt auf viele wie eine zufällige Aneinanderreihung von Sonderzeichen. Dieser Ruf ist unverdient. Ein regulärer Ausdruck ist eine sehr präzise Notation, und wer das dahinterliegende Modell kennt, liest solche Muster nicht mehr Zeichen für Zeichen, sondern als Beschreibung einer Maschine.

Dieser Beitrag beschreibt reguläre Ausdrücke als das, was sie theoretisch sind: eine kompakte Beschreibung eines endlichen Automaten. Aus diesem Modell folgen fast alle praktischen Eigenheiten, von Greedy und Lazy bis zu katastrophaler Laufzeit. Eine reine Syntaxreferenz mit den einzelnen Bausteinen gibt es bereits in einem früheren Beitrag; hier geht es um das Verständnis dahinter.

Kein Zeichensalat: Was ein Ausdruck wirklich beschreibt

Eine formale Sprache ist schlicht eine Menge von Zeichenketten über einem Alphabet. Das Alphabet kann {a, b} sein, die Menge der ASCII-Zeichen oder Unicode. Die Sprache ist dann eine (oft unendliche) Auswahl daraus: etwa „alle Strings, die mit a beginnen und mit b enden“.

Ein regulärer Ausdruck ist eine endliche, kompakte Notation für genau eine solche Menge. Das Muster entscheidet für jeden möglichen String eine einzige Frage: gehört er dazu oder nicht? ^ab*$ beschreibt die Sprache {a, ab, abb, abbb, ...}. Das Muster ist die Beschreibung, die Sprache ist das Beschriebene. Diese Unterscheidung ist das Fundament für alles Weitere.

Die Grundbausteine

Die Syntax besteht aus wenigen Kategorien. Literale wie a matchen sich selbst. Zeichenklassen wie [a-z], \d oder . matchen eines aus einer Menge von Zeichen. Quantoren (*, +, ?, {m,n}) geben an, wie oft sich das Vorangehende wiederholt. Alternation (a|b) erlaubt eine Auswahl. Gruppen (...) klammern Teilausdrücke und fangen optional den gematchten Teilstring. Anker (^, $, \b) schließlich prüfen eine Position, ohne ein Zeichen zu konsumieren.

Diese Aufteilung wirkt beliebig, ist es aber nicht. Jeder dieser Bausteine entspricht einer Operation auf Automaten.

Das mentale Modell: der endliche Automat

Stellen wir uns eine einfache Maschine vor. Sie hat eine endliche Zahl von Zuständen, einen Startzustand und einige akzeptierende Zustände. Sie liest den Eingabestring Zeichen für Zeichen. Jedes gelesene Zeichen löst einen Zustandsübergang aus. Endet der String in einem akzeptierenden Zustand, gehört er zur Sprache, das Muster matcht.

Genau das ist ein endlicher Automat. Die Bausteine übersetzen sich direkt in seine Struktur: Ein Literal oder eine Zeichenklasse ist ein einzelner Übergang. Konkatenation hängt Zustände hintereinander. Alternation ist eine Verzweigung. Ein Quantor wie * ist eine Schleife, die zum vorherigen Zustand zurückführt. Anker sind Nullbreiten-Bedingungen, die eine Position prüfen, aber keinen Übergang über ein Zeichen erzwingen.

Man unterscheidet zwei Varianten. Ein DFA (deterministischer endlicher Automat) hat pro Zustand und Zeichen genau einen Übergang. Er muss nie raten und läuft in linearer Zeit $O(n)$ über die Eingabelänge $n$. Ein NFA (nichtdeterministischer endlicher Automat) darf mehrere mögliche Übergänge pro Zeichen haben und muss die „richtige“ Verzweigung sozusagen erraten. Für den Menschen ist der NFA oft die natürlichere Übersetzung eines Musters, weil Alternation und Quantoren direkt zu Verzweigungen werden.

Ein bisschen Theorie: warum das alles dasselbe ist

Der zentrale Satz heißt Kleenes Theorem, und er ist erstaunlich aufräumend: Reguläre Ausdrücke, NFA und DFA beschreiben exakt dieselbe Klasse von Sprachen, die regulären Sprachen. Alle drei lassen sich ineinander umwandeln. Die Thompson-Konstruktion baut aus einem regulären Ausdruck mechanisch einen NFA, und die Potenzmengenkonstruktion macht aus jedem NFA einen äquivalenten DFA.

Das erklärt die lineare Laufzeit. Hat man erst einmal einen DFA, kostet das Durchlaufen der Eingabe nur einen Schritt pro Zeichen. Wichtig ist hier eine saubere Trennung: Die Zahl der Zustände eines DFA kann bei der Umwandlung exponentiell wachsen, das Aufbauen des Automaten kann also teuer sein. Die Laufzeit auf der Eingabe bleibt davon unberührt linear. Diese beiden Aussagen werden gern verwechselt.

Ein wichtiger Vorbehalt betrifft die Zusatzfeatures moderner Engines, und hier lohnt sich Genauigkeit, weil zwei sehr unterschiedliche Dinge oft in einen Topf geworfen werden. Lookaround (Lookahead und Lookbehind) erhöht die Ausdrucksmächtigkeit theoretisch nicht: Ein Ausdruck mit Lookaround, aber ohne Rückwärtsreferenzen, beschreibt weiterhin genau eine reguläre Sprache und lässt sich prinzipiell zu einem endlichen Automaten kompilieren. Praktisch erschwert Lookaround allerdings die einfache Übersetzung in einen DFA, weshalb viele Engines es über Backtracking umsetzen. Rückwärtsreferenzen (\1) sind der eigentliche Bruch: Mit ihnen verlässt man die Klasse der regulären Sprachen, und das Matching wird im Allgemeinen sogar NP-hart. Der Begriff „regulärer Ausdruck“ ist in der Praxis also weiter gefasst als in der Theorie, aber die Grenze verläuft an den Backreferences, nicht am Lookaround.

Greedy vs. Lazy, und warum das kein Zufall ist

Backtracking-Engines simulieren den NFA durch Ausprobieren: Sie folgen einem Pfad und setzen bei einer Sackgasse zurück. Aus diesem Suchverfahren folgt der Unterschied zwischen gierig und faul. Ein greedy Quantor (*, +) versucht zuerst so viel wie möglich zu matchen und gibt bei Bedarf zeichenweise zurück. Ein lazy Quantor (*?, +?) versucht zuerst das Minimum und dehnt sich nur bei Bedarf aus.

Für die reine Ja/Nein-Frage der Zugehörigkeit ist das meist egal: Ob ein String matcht, ändert sich dadurch in aller Regel nicht. Sichtbar wird der Unterschied erst dabei, welche Teilstrings die Gruppen fangen. Der Klassiker ist das Matchen eines HTML-Tags: <.*> gegen <a><b> matcht gierig den gesamten String bis zum letzten >, während <.*?> faul nur <a> fängt. Wer diesen Unterschied verinnerlicht hat, vermeidet eine der häufigsten Fehlerquellen im Alltag.

Praktische Fallstricke

Es gibt zwei Engine-Familien. Backtracking-Engines (PCRE, die verbreitete Perl-kompatible Regex-Bibliothek, sowie Python re, Java, JavaScript, .NET) unterstützen Rückwärtsreferenzen und Lookaround, können aber im schlechtesten Fall exponentiell langsam werden. Automaten-basierte Engines wie RE2 oder die Rust-regex-Bibliothek garantieren lineare Laufzeit, verzichten dafür aber auf Backreferences. Die Einteilung ist allerdings keine feste Zuordnung pro Werkzeug: grep etwa bietet im Standardmodus (BRE, also mit Basic Regular Expressions) sehr wohl Rückwärtsreferenzen (\1) und fällt dafür intern auf ein Backtracking-Verfahren zurück; die Garantie linearer Laufzeit gilt nur für den DFA-Pfad ohne Backreferences. Entscheidend ist also, welchen Sprachumfang man tatsächlich nutzt, nicht allein der Name des Programms.

Daraus folgt das gefürchtete katastrophale Backtracking (ReDoS). Verschachtelte oder überlappende Quantoren wie (a+)+$ erzeugen bei nicht-matchender Eingabe exponentiell viele Rücksetz-Pfade. Ein solches Muster gegen aaaaaaaaaaaaaaaa! kann eine Backtracking-Engine praktisch aufhängen. Bei Eingaben von Nutzer:innen ist das eine echte Sicherheitslücke. Rein automaten-basierte Ausführung ist davon nicht betroffen, weil sie gar nicht zurücksetzt.

Der dritte Stolperstein ist das Escaping. Metazeichen wie ., *, +, (, [ müssen mit Backslash entwertet werden, wenn sie wörtlich gemeint sind: \. matcht einen Punkt. Zwei Details werden oft übersehen. Der Punkt . matcht standardmäßig nicht den Zeilenumbruch. Und innerhalb einer Zeichenklasse [...] gelten eigene Regeln, dort ist . meist schon ein Literal und braucht kein Escaping.

Wann RegEx, und wann ein echter Parser

Reguläre Sprachen haben eine prinzipielle Grenze. Sie können nicht beliebig tief verschachtelte, balancierte Strukturen zählen. Das Pumping-Lemma zeigt formal, dass etwa die Sprache $\{a^n b^n \mid n \geq 0\}$ nicht regulär ist: Ein endlicher Automat hat nur endlich viele Zustände und kann sich nicht merken, wie viele a er gesehen hat.

Deshalb lassen sich HTML, JSON oder allgemein geklammerte Ausdrücke prinzipiell nicht mit klassischer RegEx parsen. Das ist keine Frage des richtigen Tricks, sondern eine Grenze der Werkzeugklasse. Für balancierte Strukturen braucht es einen echten Parser auf Basis einer kontextfreien Grammatik. RegEx ist dagegen das richtige Werkzeug für flache, lokale, lexikalische Muster: Tokenisierung, Formatvalidierung, Suchen und Ersetzen.

Ein Wort zum Email-Beispiel aus der Syntaxreferenz: Es ist ein didaktisches Muster, keine vollständige Validierung. Eine wirklich RFC-5322-konforme Email-Erkennung mit RegEx ist notorisch unpraktikabel. Für den Alltag reicht ein pragmatisches Muster, für Korrektheit versendet man am besten eine Bestätigungsmail.

Ausprobieren

Wer ein Gefühl dafür entwickeln will, wie sich Änderungen am Muster auf die gematchten Strings auswirken, probiert das am besten interaktiv aus. Auf der Projektseite liegt dafür ein kleiner RegEx-Builder, mit dem sich Muster direkt gegen Testeingaben prüfen lassen.

Fazit

Ein regulärer Ausdruck ist eine kompakte Beschreibung eines endlichen Automaten, der eine Eingabe Zeichen für Zeichen abläuft und am Ende genau eine Frage beantwortet: gehört dieser String zur beschriebenen Sprache oder nicht? Aus diesem Modell folgen die lineare Laufzeit automaten-basierter Ausführung, das Verhalten von Greedy und Lazy, das Risiko katastrophalen Backtrackings und die harte Grenze bei verschachtelten Strukturen. Wer das Modell im Kopf hat, sieht im Muster keinen Zeichensalat mehr, sondern eine Maschine.