Reguläre Ausdrücke verstehen und anwenden

Stell dir vor, du suchst in vielen Zeichenketten nach einer bestimmten Form. Ein einzelnes Wort wie abc ist bereits ein einfaches Muster: Es trifft die genaue Zeichenfolge abc, auch als Teil einer längeren Zeichenkette.

Ein Regex besteht aus zwei Arten von Zeichen:

• Literale stehen für sich selbst. Im Muster Tag müssen T, a und g in dieser Reihenfolge vorkommen.
• Metazeichen haben eine besondere Funktion. Dazu gehören beispielsweise ., *, +, ?, |, (, ), [ und ].

Das Muster ab*c verlangt ein a, danach beliebig viele b und anschließend ein c. Es passt daher zu ac, abc und abbbbc.

Eine Zeichenklasse beschreibt genau ein Zeichen aus einer Auswahl. [abc] trifft also ein a, ein b oder ein c.

Bereiche verkürzen eine Auswahl:

• [0-9] steht für eine Ziffer von 0 bis 9.
• [a-c] steht für a, b oder c.
• [A-Za-z] steht für einen der ausdrücklich angegebenen Groß- oder Kleinbuchstaben.
• [^u] steht für ein einzelnes Zeichen außer u.

Der Punkt . ist in vielen Dialekten ein Platzhalter für fast jedes Einzelzeichen. Ob er auch einen Zeilenumbruch erfasst, hängt vom verwendeten Modus ab.

Ein Quantor bestimmt, wie oft das unmittelbar vorherige Element vorkommen darf:

• *: null oder mehr Wiederholungen
• +: eine oder mehr Wiederholungen
• ?: null oder eine Wiederholung
• {n}: genau n Wiederholungen
• {n,m}: mindestens n, höchstens m Wiederholungen
• {n,}: mindestens n Wiederholungen

Klammern verändern, worauf ein Quantor wirkt. (ab)+ wiederholt den vollständigen Block ab; das Muster passt beispielsweise zu ab und abab. Ohne Klammern würde ab+ nur das b wiederholen.

Viele Suchfunktionen melden bereits einen Treffer, wenn nur ein Teil des Textes passt. [0-9]{2,5} findet in 1234507 beispielsweise die Teilzeichenkette 12345.

Soll die gesamte Zeichenkette aus zwei bis fünf Ziffern bestehen, werden in vielen Dialekten Anfang und Ende markiert:

^[0-9]{2,5}$

^ bezeichnet gewöhnlich den Anfang und $ das Ende der untersuchten Zeichenkette oder Zeile. Die genaue Bedeutung kann sich durch den Mehrzeilenmodus ändern. Manche Programmierschnittstellen bieten deshalb eine eigene Ganzstring-Prüfung an.

Ein Sonderzeichen muss geschützt werden, wenn du es als gewöhnliches Zeichen suchst. Der Punkt bedeutet normalerweise „beliebiges Zeichen“. \. verlangt dagegen einen echten Punkt. Das Muster 11\.10\.2019 passt deshalb zum Datum mit Punkten, aber nicht zu 11a10b2019.

Der senkrechte Strich | trennt praktische Alternativen. Baum|Blume passt zu Baum oder Blume.

Klammern fassen mehrere Elemente zusammen. (Sonn|Frei)tag passt zu Sonntag oder Freitag. Ohne passende Gruppierung könnte die Alternative einen größeren Bereich erfassen als beabsichtigt.

Gruppen können in vielen Engines außerdem den gefundenen Text speichern. Eine solche Capturing-Gruppe lässt sich später beim Ersetzen oder über eine Rückwärtsreferenz wiederverwenden. Benötigst du den gespeicherten Teil nicht, unterstützen viele Dialekte eine nicht erfassende Gruppe wie (?:ab).

Gierig und zurückhaltend suchen

Quantoren sind gewöhnlich gierig: Sie erfassen zunächst so viel wie möglich, solange der Rest des Musters noch passen kann.

Zurückhaltende und possessive Quantoren, Capturing, Rückwärtsreferenzen und Look-arounds sind Erweiterungen praktischer Engines. Ihre genaue Schreibweise und Unterstützung unterscheiden sich.

In der theoretischen Informatik beschreibt ein regulärer Ausdruck nicht nur Fundstellen in einem Text, sondern eine formale Sprache.

Die Grundbausteine theoretischer regulärer Ausdrücke sind:

• ∅: die leere Sprache, die kein Wort enthält
• ε: das leere Wort, also ein Wort der Länge null
• ein Alphabetzeichen wie a
• Alternative beziehungsweise Vereinigung
• Konkatenation, also Aneinanderfügen
• Kleene-Stern *, also beliebig viele Wiederholungen einschließlich null

Für die Alternative wird theoretisch je nach Notation | oder + verwendet. Das ist eine wichtige Verwechslungsgefahr: In vielen praktischen Regex-Dialekten bedeutet + stattdessen „mindestens eine Wiederholung“.

Vom Ausdruck zum endlichen Automaten

Ein endlicher Automat besitzt endlich viele Zustände. Er liest ein Wort Zeichen für Zeichen, wechselt dabei den Zustand und entscheidet am Ende, ob das Wort akzeptiert wird.

Theoretische reguläre Ausdrücke und endliche Automaten sind gleich mächtig: Zu jedem regulären Ausdruck gibt es einen endlichen Automaten mit derselben Sprache, und zu jedem endlichen Automaten gibt es einen passenden regulären Ausdruck.

Betrachte die Sprache aller Binärwörter, die auf 1 enden. Ein Ausdruck dafür ist (0|1)*1.

Ein deterministischer Automat benötigt dafür zwei Zustände:

Nach jeder gelesenen 1 steht der Automat in q1, nach jeder 0 in q0. Deshalb akzeptiert er genau die nichtleeren Wörter, deren letztes Zeichen 1 ist. 1, 01 und 101 werden akzeptiert; ε, 0 und 110 werden abgelehnt.

Für die systematische Umwandlung eines Ausdrucks in einen Automaten kann eine Konstruktion mit ε-Übergängen verwendet werden. In der Gegenrichtung lassen sich Zustände eliminieren oder Pfade schrittweise durch Ausdrücke beschreiben.

Praktische Regex-Dialekte teilen viele Grundideen, sind aber nicht vollständig einheitlich. Unterschiede betreffen unter anderem Zeichenklassen, Anker, Unicode, Zeilenmodi, Capturing, Look-behind und die Schreibweise von Ersetzungen.

Gehe deshalb in fünf Schritten vor:

1. Formuliere genau, welche Zeichenketten passen sollen.
2. Zerlege die Bedingung in feste Zeichen, Auswahl, Reihenfolge und Wiederholungen.
3. Entscheide zwischen Teiltreffer und Ganzstring-Prüfung.
4. Bilde das Muster und erkläre jeden Teil.
5. Teste passende, unpassende und grenzwertige Eingaben im vorgesehenen Dialekt.

Komplexe Engine-Erweiterungen können über klassische reguläre Sprachen hinausgehen. Besonders Rückwärtsreferenzen vergleichen einen Treffer mit zuvor gespeichertem Text. Ein praktischer „Regex“ ist daher nicht immer ein regulärer Ausdruck im strengen theoretischen Sinn.

Wenn du alle drei Antworten begründen kannst, kannst du Regex-Bausteine nicht nur erkennen, sondern zu einer gewünschten Zeichenmenge zusammensetzen und mit passenden Gegenbeispielen prüfen.