Regulärer Ausdruck
Einführung
Ein Regulärer Ausdruck (kurz Regex oder Regexp von regular expression) stellt in der Programmierung ein verallgemeinertes Suchmuster für Zeichenketten dar. Damit können Inhalte dahingehend geprüft werden, ob sie bestimmten Mustern genügen. Reguläre Ausdrücke können zum Beispiel als Filterkriterien in der Textsuche verwendet werden, indem der Text mit dem Muster des regulären Ausdrucks abgeglichen wird. Dieser Vorgang wird auch Pattern Matching genannt. So ist es beispielsweise möglich, alle Wörter aus einer Wortliste herauszusuchen, die mit S beginnen und auf D enden, ohne die dazwischen liegenden Buchstaben oder deren Anzahl explizit vorgeben zu müssen. Weitere Anwendungsfälle sind die Überprüfung von Emailadressen hinischtlich syntaktisch korrektem Aufbau oder die Angabe eines Datums im richtigen Format.
Reguläre Ausdrücke werden in der Programmierung nach deutlich verschiedenen Konventionen notiert. In diesem Artikel wird das allen Notationen gemeinsame Prinzip erklärt.
Aufbau
Die Syntax von regulären Ausdrücken basiert auf einigen Grundoperationen:
Konkatenation: Wenn r und s reguläre Ausdrücke sind, dann ist rs auch ein regulärer Ausdruck, der die Konkatenation von Zeichenketten beschreibt, die r und s entsprechen. Man kann auch sagen r und s werden verkettet.
Alternative: Der Ausdruck r∣s entspricht Zeichenketten, die entweder r oder s entsprechen.
Kleene-Stern: r∗ beschreibt Null oder mehr Wiederholungen von Zeichenketten, die r entsprechen.
Basisfall: Einzelne Zeichen wie a oder b sind die einfachsten regulären Ausdrücke. Es gibt auch einen speziellen regulären Ausdruck, das leere Wort, oft mit ϵ (siehe auch ε Übergänge) oder λ bezeichnet.
Erweiterter Aufbau
Reguläre Ausdrücke verfügen in der praktischen Anwendung, beispielsweise in Programmiersprachen, weitere zusätzliche Operationen und Notationen auf, die oft unterstützt werden, um die Ausdrücke flexibler und benutzerfreundlicher zu gestalten. Einige dieser zusätzlichen Funktionen könnten sein:
Kleene-Plus (r+): Repräsentiert eine oder mehr Wiederholungen des Ausdrucks r. Dies ist im Grunde eine Kurzform für rr*.
Optionale Zeichen (r?): Dies bedeutet, dass das Muster r null- oder einmalig vorkommen kann. Es ist äquivalent zu r|ϵ.
Charakterklassen: Zum Beispiel [a-z], welches jeden Kleinbuchstaben repräsentiert, oder \d, welches in vielen modernen Regex-Dialekten für eine Ziffer steht.
Anker: Zeichen wie ^ und $ repräsentieren oft den Anfang bzw. das Ende einer Zeile oder Zeichenkette.
Gruppierung und Rückverweise: In vielen modernen Regex-Dialekten können Sie Teile eines Musters in Klammern setzen, um sie als Gruppe zu behandeln, und dann später in demselben Muster auf diese Gruppe zurückverweisen.
Vor- und Nachbedingungen (Lookahead und Lookbehind): In einigen fortgeschrittenen Regex-Dialekten können Sie Muster spezifizieren, die vor oder nach einem anderen Muster vorkommen müssen, ohne selbst Teil des Gesamtergebnisses zu sein.
In einem regulären Ausdruck können Sie das Klammerpaar {} verwenden, um die Anzahl der Wiederholungen eines vorherigen Elements zu steuern. Sie können verschiedene Optionen in das Klammerpaar schreiben, um die Anzahl der Wiederholungen anzugeben. Beachten Sie, dass Sie in den geschweiften Klammern die Mindestanzahl und gegebenenfalls die Höchstanzahl der Wiederholungen angeben können. Wenn Sie die Höchstanzahl nicht angeben, wird keine Begrenzung für die maximale Anzahl von Wiederholungen gesetzt. In einigen regulären Ausdrucksbibliotheken können Sie sogar das Komma weglassen und einfach {n} verwenden, um genau n Wiederholungen anzugeben.
Escape-Sequenzen: Zeichen wie \t (Tabulator) oder \n (neue Zeile) sowie die Möglichkeit, spezielle Zeichen durch vorangestelltes Backslash (\) zu escapen, z. B. \\ oder \*.
Theoretische Informatik
In der theoretischen Informatik ist bewiesen, dass reguläre Ausdrücke genau die regulären Sprachen beschreiben, die auch von endlichen Automaten erkannt werden können. Das bedeutet, für jeden regulären Ausdruck gibt es einen äquivalenten endlichen Automaten (genauer gesagt, einen deterministischen endlichen Automaten, DFA) und umgekehrt.
Beispiele
Einfaches Beispiel
Nehmen wir an, wir möchten alle Zeichenketten beschreiben, die mit einem "a" beginnen, gefolgt von einer beliebigen Anzahl von "b"s und enden mit einem "c" oder einem "d". Die entsprechenden regulären Ausdrücke dafür sind:
Mit einem "a" beginnen: Dies wird einfach durch den regulären Ausdruck a beschrieben.
Gefolgt von einer beliebigen Anzahl von "b"s: Die "beliebige Anzahl" kann durch den Kleene-Stern repräsentiert werden. Also wäre der reguläre Ausdruck für "beliebige Anzahl von b"s b*. Beliebig bedeutet auch, dass gar kein b verwendet werden darf.
Endet mit einem "c" oder einem "d": Für das "oder" verwenden wir die Alternative. Der reguläre Ausdruck dafür wäre c|d.
Setzt man das Ganze zusammen (Konkatenation!), erhält man den regulären Ausdruck:
ab*(c|d)
Hier sind einige Zeichenketten, die diesem regulären Ausdruck entsprechen:
ac
ad
abc
abd
abbbbc
abbbbbd
Und hier sind einige Zeichenketten, die nicht übereinstimmen:
a
bc
ab
abcd
Es ist auch interessant zu bemerken, dass für den gegebenen regulären Ausdruck ab*(c|d), ein deterministischer endlicher Automat (DFA) erstellt werden könnte, der genau diese Sprache erkennt. Dies verbindet den regulären Ausdruck mit der Theorie der endlichen Automaten.
Komplexes Beispiel
Praxis
Reguläre Ausdrücke (Regex) haben zahlreiche praktische Anwendungen in verschiedenen Bereichen der Informatik und Softwareentwicklung. Hier sind einige Bereiche, in denen reguläre Ausdrücke in der Praxis eine wichtige Rolle spielen:
Textsuche und Textverarbeitung: Dies ist eine der häufigsten Anwendungen von Regex. Texteditoren, Suchmaschinen und viele Programmiersprachen bieten Unterstützung für Regex, um Textmuster zu suchen und zu verarbeiten. Mit Regex können Sie beispielsweise alle E-Mail-Adressen in einem Textdokument finden, bestimmte Wörter in einem Text hervorheben oder Links aus HTML-Code extrahieren.
Validierung von Benutzereingaben: Regex wird oft verwendet, um sicherzustellen, dass Benutzereingaben den erwarteten Formaten entsprechen. Zum Beispiel können Sie prüfen, ob eine Eingabe eine gültige E-Mail-Adresse, Telefonnummer oder Postleitzahl ist.
Datenbereinigung und -extraktion: In der Datenanalyse werden Regex verwendet, um unstrukturierte Daten zu bereinigen und Informationen zu extrahieren. Dies ist nützlich, wenn Sie Daten aus Logdateien, Webseiten, Dokumenten oder anderen Quellen analysieren.
Syntaxhervorhebung und Codeanalyse: In Texteditoren, integrierten Entwicklungsumgebungen (IDEs) und Codeeditoren ermöglichen Regex-basierte Syntaxhervorhebung und Codeanalysen eine bessere Darstellung von Programmiersprachen und helfen bei der Identifizierung von Syntaxfehlern.
Suchen und Ersetzen: Mit regulären Ausdrücken können Sie komplexe Suchen und Ersetzen in Textdokumenten und Quellcode durchführen. Sie können Muster in Text finden und durch andere Zeichenfolgen ersetzen.
URL-Routing in Webanwendungen: In Webanwendungen und -frameworks werden Regex oft verwendet, um URLs zu analysieren und auf bestimmte Controller oder Ressourcen weiterzuleiten.
Datenaufbereitung in Datenbanken: In einigen Datenbanken und Abfragesprachen können Sie Regex verwenden, um nach Daten zu suchen und Filterbedingungen zu erstellen.
Logik in Skripten und Programmiersprachen: Reguläre Ausdrücke sind in vielen Programmiersprachen (z. B. Python, JavaScript, Perl) eingebettet und können in Skripten und Anwendungen verwendet werden, um Textverarbeitungsaufgaben zu automatisieren.
Datenvalidierung in Formularen: Beim Erstellen von Formularen in Webanwendungen können Regex verwendet werden, um sicherzustellen, dass Benutzer korrekte Informationen eingeben, wie beispielsweise Kreditkartennummern, Passwörter und mehr.
Lexikalische Analyse und Tokenisierung: In der Compilertheorie und im Übersetzerbau werden reguläre Ausdrücke häufig verwendet, um den Quellcode in lexikalische Einheiten (Tokens) zu zerlegen.
Um zu verstehen, wie in der Programmierung reguläre Ausdrücke notiert werden, wenden wir uns folgendem zu: [+-]?[0-9]+(,[0-9]+)?
Dabei fällt auf, dass es hier offensichtlich zwei Arten von Zeichen gibt: gewöhnliche Zeichen (der Fachausdruck heißt terminale Zeichen), die sich selbst bedeuten, z.B. das Komma, welches nur bedeutet, dass dort ein Komma steht, und Metazeichen, die für die Bedeutung des regulären Ausdrucks selbst eine Bedeutung haben.
Metazeichen:
die eckigen Klammern, die eine Liste von Zeichen umschließen, von denen genau eines an einer bestimmten Stelle vorkommen soll,
das Minuszeichen (aber nur wenn es innerhalb einer eckigen Klammer und dort nicht am Rand steht), das einen Bereich von Zeichen markiert, die dann nicht alle aufgelistet zu werden brauchen,
das Fragezeichen, das anzeigt, dass das letzte Zeichen oder der Inhalt der unmittelbar voranstehenden runden Klammer optional ist, d.h. einmal vorkommen kann, aber nicht muss,
das Pluszeichen, das anzeigt, dass das letzte Zeichen oder der Inhalt der unmittelbar voranstehenden runden Klammer mindestens einmal vorkommen muss aber auch mehrmals vorkommen darf,
die runde Klammer, die dafür sorgt, dass sich ein dahinter stehendes Frage- oder Pluszeichen auf einen längeren Text und nicht nur auf das letzte Zeichen bezieht, analog der Verwendung von Klammern in der Mathematik,
sowie einige Metazeichen, die in diesem kurzen Beispiel nicht vorkommen:
der Stern, der anzeigt, dass das letzte Zeichen oder der Inhalt der unmittelbar voranstehenden runden Klammer ein- oder mehrmals vorkommen kann, aber nicht muss,
der Punkt, der für genau ein ganz beliebiges Zeichen steht,
der senkrechte Strich, der Alternativen voneinander trennt, von denen mindestens eine zutreffen muss, sowie
weitere Zeichen gibt es, werden hier aber nicht aufgeführt.
Bis auf das Minuszeichen sind diese Zeichen nur dann Metazeichen, wenn sie außerhalb von eckigen Klammern stehen. Das kann man auch dazu verwenden, beispielsweise eine Klammer als terminales Zeichen zu notieren: man schreibt dann einfach[(], was, soviel heißt wie "eines der folgenden Zeichen: (". Alternativ kann man auch vor ein Metazeichen einen inversen Schrägstrich setzen, um es auf diese Weise zu maskieren, d.h. an dieser Stelle nur als terminales Zeichen zu verwenden - allerdings werden wir noch sehen, dass dieser inverse Schrägstrich manchmal auch gerade Metazeichen bezeichnet, während die Maskierung mittels eckiger Klammern solche Tücken nicht hat.
Nun wird detaillierter dargelegt, wie die ineinander verschachtelten Teilausdrücke zusammenwirken:
Das letzte Pluszeichen verlangt, dass die davorstehende Ziffer (notiert als [0-9]) mindestens einmal vorkommen muss; ebenso verlangt das Komma, dass das Komma genau einmal vorkommen muss. Das steht aber in einer runden Klammer, die mit einem Fragezeichen versehen ist, so dass doch alles optional ist. Wie passt das zusammen? Man löst solche Fragen, indem man den Ausdruck strikt in seine Bestandteile gliedert. Das Fragezeichen sagt aus, dass der Teilausdruck ,[0-9]+ optional ist. Ist im zu untersuchenden String ein Teil vorhanden, der diesem Teilausdruck entspricht, ist es recht, wenn nicht, auch. Wenn ein solcher Teilstring vorhanden ist - und nur dann - interessieren wir uns dafür, wie er aussieht: und dann gibt es Zeichen, die er zwingend enthalten muss.
Vorrangregeln
Jetzt brauchen wir nur noch die Vorrangregeln zu kennen und schon können wir nach Herzenslust reguläre Ausdrücke schreiben. Die Vorrangregeln sind:
Die eckigen Klammern binden stärker als die runden.
Stern, Pluszeichen und Fragezeichen binden stärker als Hintereinanderschreiben, d.h. ab* bedeutet a(b*) und nicht (ab)*.
Der senkrechte Strich bindet schwächer als Hintereinanderschreiben, d.h. ab|c bedeutet (ab)|c und nicht a(b|c).
Normen
Nachfolgend sind verbreitetsten Notationen für reguläre Sprachen zusammengestellt die syntaktisch von einander abweichen:
Theorie: die in der Theorie der formalen Sprachen übliche Notation
ERE: Extended Regular Expression (=erweiterter regulärer Ausdruck) gemäß X/Open CAE Specification "System Interface Definitions", Issue 4
BRE: Basic Regular Expression (=einfacher regulärer Ausdruck) gemäß dem selben Dokument
Shell: Wildcards (=Joker) nach den Konventionen von Unix-Shells
SQL: Wildcards (=Joker) nach den Konventionen von SQL-Datenbankabfragen, die ansonsten hier nicht weiter diskutiert werden.