Regulärer Ausdruck

Reguläre Ausdrücke (Abk. RegExp oder Regex, engl. regular expression) dienen der Beschreibung einer Familie von formalen Sprachen, d. h. sie beschreiben (Unter-)Mengen von Zeichenketten. Sie gehören somit zur Theoretischen Informatik. Hier bilden sie die unterste und somit ausdrucksschwächste Stufe der Chomsky-Hierarchie (Typ-3). Es lässt sich zeigen, dass zu jedem regulären Ausdruck ein gleichwertiger endlicher Automat existiert und umgekehrt. Dieser Automat ist einfach bestimmbar. Hieraus folgt die relativ einfache Implementierbarkeit regulärer Ausdrücke.

Der Mathematiker Stephen Kleene benutzte eine Notation, die er reguläre Mengen nannte. Ken Thompson nutzte diese Notation um qed (eine Vorgängerversion des Unix-Editors ed) zu bauen und später das Werkzeug grep zu schreiben. Seither implementieren sehr viele Programme Funktionen, um reguläre Ausdrücke zum Suchen und Ersetzen von Zeichenketten zu nutzen.

Einige Programmiersprachen wie z. B. Perl unterstützen einige Erweiterungen der regulären Ausdrücke, z. B. Rückwärtsreferenzen. Hierbei handelt es sich nicht mehr um reguläre Ausdrücke im Sinne der theoretischen Informatik, denn die so erweiterten Ausdrücke gehören nicht mehr notwendigerweise zur untersten Stufe der Chomsky-Hierarchie.

Die Mächtigkeit regulärer Ausdrücke reicht aus, um die Morphologie einer natürlichen Sprache zu beschreiben.

Elemente, mit denen sich ein regulärer Ausdruck festlegen lässt

Eine häufige Anwendung regulärer Ausdrücke besteht darin, spezielle Zeichenketten in einer Menge von Zeichenketten zu finden. Die im Folgenden angegebene Beschreibung ist eine (oft benutzte) Konvention, um Konzepte wie Zeichenklasse, Quantifizierung, Verknüpfung und Zusammenfassen konkret zu realisieren. Hierbei wird ein regulärer Ausdruck aus den Zeichen des zugrunde liegenden Alphabets in Kombination mit sogenannten Metazeichen ([, ], (, ), {, }, ?, +, *, ^, $, \, .) gebildet. Alle übrigen Zeichen des Alphabets stehen für sich selbst.

Zeichenliterale

Diejenigen Zeichen, die direkt (wörtlich, literal) übereinstimmen müssen, werden auch direkt notiert. Je nach System gibt es auch Möglichkeiten, den Oktal- oder Sedezimalcode anzugeben.

Beliebiges Zeichen

Ein Punkt bedeutet, dass an seinem Platz ein (fast) beliebiges Zeichen stehen kann. Abhängig vom verwendeten Programm kann ein Punkt auch eine Newline beinhalten, die meisten Implementierungen sehen jedoch die Newline nicht als beliebiges Zeichen an.

Ein Zeichen aus einer Auswahl

Mit eckigen Klammern lässt sich eine Zeichenauswahl definieren. Der Ausdruck in eckigen Klammern steht dann für genau ein Zeichen aus dieser Auswahl (Einzeichenmuster).

Beispiele:

[Aa]	einfaches Aneinanderreihen von Zeichen, hier entweder "A" oder "a"
[egh]	eines der Zeichen "e", "g" oder "h"
[0-6]	Bindestrich für einen Bereich, hier also eine Ziffer von "0" bis "6"
[A-Za-z0-9]	ein beliebiger Buchstabe oder eine beliebige Ziffer
[^a]	ein beliebiges Zeichen außer "a"

Vordefinierte Zeichenklassen

Es gibt vordefinierte Zeichenklassen, die allerdings nicht von allen Implementationen unterstützt werden, da sie lediglich Kurzformen sind und auch durch eine Zeichenauswahl beschrieben werden können. Die wichtigsten Zeichenklassen sind:

\d : eine Zahl [0-9]
\D : keine Zahl [^0-9]
\w : ein Buchstabe, eine Zahl oder der Unterstrich [a-zA-Z_0-9]
\W : kein Buchstabe, keine Zahl und kein Unterstrich [^\w]
\s : Whitespace-Zeichen, meistens [ \f\n\r\t\v]
\S : alle Zeichen außer Whitespace-Zeichen [^\s]

Quantoren (auch Quantifizierer oder Wiederholungsfaktor, Angabe der Anzahl Wiederholungen)

Quantoren erlauben es, den vorherigen Ausdruck in verschiedener Vielfachheit in der Zeichenkette zuzulassen:

? : Der voranstehende Ausdruck ist optional, er kann einmal vorkommen, muss es aber nicht, d. h. der Ausdruck kommt null- oder einmal vor.
+ : Der voranstehende Ausdruck muss mindestens einmal vorkommen, darf aber auch mehrfach vorkommen.
* : Der voranstehende Ausdruck darf beliebig oft (auch keinmal) vorkommen.
{n} : Der voranstehende Ausdruck muss exakt n-mal vorkommen.
{min,} : Der voranstehende Ausdruck muss mindestens min-mal vorkommen.
{min,max} : Der voranstehende Ausdruck muss mindestens min-mal und darf maximal max-mal vorkommen.

Beispiele:

"a+" erlaubt ein "a" oder ein "aa" oder auch "aaaa" etc.
"[ab]+" dagegen erlaubt ein "a", "b", "aa", "baab" etc.
Ein "[0-9]{2,5}" findet "13", "28333", "123", aber nicht "0", "123123223" etc.

Gruppierung mit runden Klammern

Ausdrücke lassen sich mit runden Klammern "(" und ")" zusammenfassen: Etwa erlaubt "(abc)+" ein "abc" oder ein "abcabc" etc.

Einige Programme speichern die Gruppierung ab und ermöglichen deren Wiederverwendung im Regulären Ausdruck oder bei der Textersetzung: Ein Suchen und Ersetzen mit

AA(.*?)BB

als Regulären Suchausdruck und

\1

als Ersetzung ersetzt alle Zeichenketten, die von AA und BB eingeschlossen sind, durch den zwischen AA und BB enthaltenen Text. D. h. AA und BB und das dazwischen wird ersetzt durch das dazwischen, also fehlen AA und BB im Ergebnis. \1, \2 usw. nennt man Rückwärtsreferenzen. \1 bezieht sich auf das erste Klammerpaar, \2 auf das zweite usw.; dabei zählt man die öffnenden Klammern.

Interpreten von regulären Ausdrücken, die Rückwärtsreferenzen zulassen, entsprechen nicht mehr dem Typ 3 der Chomsky-Hierarchie. Mit dem Pumpinglemma lässt sich einfach zeigen, dass folgender regulärer Ausdruck, der feststellt, ob in einem String vor und nach der 1 die gleiche Anzahl von 0 steht, keine reguläre Sprache ist.

/^(0*)1\1$/

Alternativen

Man kann alternative Ausdrücke mit dem "|"-Symbol zulassen:

"(ABC|abc)" bedeutet "ABC" oder "abc", aber z. B. nicht "Abc".

Spezielle Zeichen

Um die oft auf Textdateien oder einzelne Zeilen bezogenen Anwendungen auf dem Computer zu unterstützen, werden in der Regel die folgenden Sonderzeichen definiert:

^ steht für den Zeilenanfang.
$ steht für das Zeilenende.
\b steht für die leere Zeichenkette am Wortanfang oder am Wortende.
\B steht für die leere Zeichenkette, die nicht den Anfang oder das Ende eines Wortes bildet.
\< steht für die leere Zeichenkette am Wortanfang.
\> steht für die leere Zeichenkette am Wortende.
\d Ziffer
\D keine Ziffer
\w Wortzeichen - ein Buchstabe, eine Zahl oder der Unterstrich [a-zA-Z_0-9]
\W kein Wortzeichen
\s Whitespace
\S kein Whitespace
. irgendein Zeichen, aber normalerweise kein Linefeed

Jedes der Metazeichen kann durch das "\"-Symbol aufgehoben werden. Beispielsweise lässt der Ausdruck "(A\*)+" die Zeichenketten "A*", "A*A*" etc. zu.

Werkzeuge

Tcl Regular Expression Visualiser
Regex-Coach - Programm, das anschaulich demonstriert, welche Auswirkungen reguläre Ausdrücke auf einen bestimmten Text haben, erlaubt Abarbeiten/Matchen des Ausdrucks in Schritten und vieles mehr
txt2regex Regex erstellen mit Hilfe eines Bash Scriptes - Einfaches erstellen von Regex

Siehe auch: Kleenesche Hülle

Literatur

Jeffrey Friedl: Reguläre Ausdrücke. O'Reilly, ISBN 3-89721-349-4. Sehr umfassendes, praxisnahes Buch, das aber auch einführende Kapitel aufweist, die für viele Arbeiten bereits ausreichen
Tony Stubblebine: Reguläre Ausdrücke - kurz und gut. O'Reilly, ISBN 3-89721-264-1
Mehran Habibi: Real World Regular Expressions with Java 1.4. Springer, ISBN 1-59059-107-0

Weblinks