Regulärer Ausdruck

In der Informatik ist ein Regulärer Ausdruck (Abk. RegExp oder Regex, engl. regular expression) eine Zeichenkette, die der Beschreibung von Mengen beziehungsweise Untermengen von Zeichenketten mit Hilfe bestimmter syntaktischer Regeln dient. Reguläre Ausdrücke finden vor allem in der Softwareentwicklung Verwendung; für fast alle Programmiersprachen existieren Implementierungen.

Allgemein gesprochen stellen reguläre Ausdrücke erstens eine Art Filterkriterium für Texte dar, in dem der Ausdruck in Form eines Musters mit dem Text abgeglichen wird. So ist es beispielsweise möglich, alle Wörter, die mit S beginnen und mit D enden zu finden, ohne die zwischenliegenden Buchstaben vorgeben zu müssen. Auf diese Art kann beispielsweise die Syntax einer Programmiersprache geprüft werden, in der der Quelltext eines Programms mit dem (dann vergleichsweise komplexen) regulären Ausdruck, der die Syntax der Programmiersprache beschreibt, abgeglichen wird - bleibt etwas im Quelltext an dem Filter hängen, so hat sich ein Syntaxfehler in den Quelltext eingeschlichen.

Zweitens lassen sich aus regulären Ausdrücken, als eine Art Schablone, auch Mengen von Wörtern erzeugen, ohne jedes Wort einzeln angeben zu müssen. So lässt sich beispielsweise ein Ausdruck angeben, der alle denkbaren Zeichenkombinationen (Wörter) erzeugt, die mit S beginnen und mit D enden.

Reguläre Ausdrücke in der theoretischen Informatik

Theoretische Grundlagen

Hinweis: In diesem Abschnitt wird die Kenntnis einiger Konzepte der Theorie der formalen Sprachen vorausgesetzt.

Reguläre Ausdrücke beschreiben eine Familie von formalen Sprachen und gehören damit 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. Die Mächtigkeit regulärer Ausdrücke reicht aus, um die Morphologie einer natürlichen Sprache zu beschreiben.

Reguläre Ausdrücke unterstützen genau drei Operationen: Alternative, Aneinanderreihung und Wiederholung. Die formelle Definition sieht folgendermaßen aus:

Syntax

${\underline {\varnothing }}$ (die leere Menge) ist ein regulärer Ausdruck.
${\underline {\varepsilon }}$ (das leere Wort) ist ein regulärer Ausdruck.
$\forall a_{i}\in \Sigma$ ist ${\underline {a_{i}}}$ (jedes Zeichen aus dem zugrundeliegenden Alphabet) ein regulärer Ausdruck.
Sind $x$ und $y$ reguläre Ausdrücke, so auch $(x\cup y)$ (Vereinigung), $(xy)$ (Konkatenation) und $x^{*}$ (Stern-Operator).
Es gibt keine weiteren regulären Ausdrücke.

Anwendung regulärer Ausdrücke

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 und Bibliotheken von Programmiersprachen Funktionen, um reguläre Ausdrücke zum Suchen und Ersetzen von Zeichenketten zu nutzen. Beispiele dafür sind die Programme sed, grep, emacs und Bibliotheken der Programmiersprachen C, Perl, Java, auch die Textverarbeitung des Office-Paketes OpenOffice.org bietet die Möglichkeit, mit regulären Ausdrücken im Text zu suchen.

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 zum Typ 3 der Chomsky-Hierarchie.

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

Die folgenden Syntaxbeschreibungen beziehen sich auf die Syntax der gängigen Regex-Implementierungen mit Erweiterungen, sie entsprechen also nur teilweise der obigen Definition aus der theoretischen Informatik.

Eine häufige Anwendung regulärer Ausdrücke besteht darin, spezielle Zeichenketten in einer Menge von Zeichenketten zu finden (matchen, von englisch "to match"). 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 Hexadezimalcode anzugeben.

Beliebiges Zeichen

. : Ein Punkt bedeutet, dass an seinem Platz ein (fast) beliebiges Zeichen stehen kann. Abhängig vom verwendeten Programm oder dessen Einstellungen kann ein Punkt auch für Newline (Zeilenumbruch) stehen. Die meisten Implementierungen sehen standardmäßig Newline nicht als beliebiges Zeichen an, jedoch kann in einigen Programmen mithilfe des sogenannten s-Modifiers (z. B. in /foo.bar/s) ebendies erreicht werden.

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:

[egh]	eines der Zeichen „e“, „g“ oder „h“
[0-6]	eine Ziffer von „0“ bis „6“ (Bindestriche sind Indikator für einen Bereich)
[A-Za-z0-9]	ein beliebiger lateinischer Buchstabe oder eine beliebige Ziffer
[^a]	ein beliebiges Zeichen außer „a“ („^“ am Anfang einer Zeichenklasse negiert selbige)

In vielen neueren Implementationen können innerhalb der eckigen Klammern nach POSIX auch Klassen angegeben werden, die selbst wiederum eckige Klammern enthalten. Sie lauten beispielsweise:

[:alnum:]	Alphanumerische Zeichen: [:alpha:] und [:digit:].
[:alpha:]	Buchstaben: [:lower:] und [:upper:].
[:blank:]	Leerzeichen und Tabulator.
[:cntrl:]	Steuerzeichen. Im ASCII sind das die Zeichen 00 bis 1F, und 7F (DEL).
[:digit:]	Ziffern: 0, 1, 2,... bis 9.
[:graph:]	Graphische Zeichen: [:alnum:] und [:punct:].
[:lower:]	Kleine Buchstaben¹: nicht notwendig nur von a bis z.
[:print:]	Druckbare Zeichen: [:alnum:], [:punct:] und Leerzeichen.
[:punct:]	Zeichen wie: ! " # $ % & ' ( ) * + , - . / : ; < = > ? @ [ \ ] ^ _ ` { \| } ~ .
[:space:]	Whitespace: Horizontaler und vertikaler Tabulator, Zeilen- und Seitenvorschub, Wagenrücklauf und Leerzeichen.
[:upper:]	Großbuchstaben¹: nicht notwendig nur von A bis Z.
[:xdigit:]	Hexadezimale Ziffern: 0 bis 9, A bis F, a bis f.

¹Was Buchstaben sind, ist im Allgemeinen locale-abhängig.[1]

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. Wichtige Zeichenklassen sind:

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

Quantoren (Angabe der Anzahl Wiederholungen)

Quantoren (auch Quantifizierer oder Wiederholungsfaktoren) 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. (Dies entspricht {0,1} )
+ : Der voranstehende Ausdruck muss mindestens einmal vorkommen, darf aber auch mehrfach vorkommen. (Dies entspricht {1,} )
* : Der voranstehende Ausdruck darf beliebig oft (auch keinmal) vorkommen. (Dies entspricht {0,} )
{n} : Der voranstehende Ausdruck muss exakt n-mal vorkommen.
{min,} : Der voranstehende Ausdruck muss mindestens min-mal vorkommen.
{,max} : Der voranstehende Ausdruck darf maximal max-mal vorkommen.
{min,max} : Der voranstehende Ausdruck muss mindestens min-mal und darf maximal max-mal vorkommen.

Die Quantoren beziehen sich dabei auf den regulären Ausdruck, jedoch nicht zwangsläufig auf die durch ihn gematchte Zeichenkette. So wird zwar z.B. durch a+ ein "a" oder auch "aaaa" gematcht, jedoch matcht [0-9]+ nicht nur sich wiederholende gleiche Ziffern, sondern auch Folgen gemischter Ziffern, z.B. "072345".

Weitere Beispiele sind:

[ab]+ passt auf "a", "b", "aa", "bbaab" etc.
[0-9]{2,5} matcht zwei, drei, vier oder fünf Ziffern in Folge, z. B. "42", "54072", jedoch nicht z. B. die Zeichenfolgen "0", "1.1" oder "a1a1".

Soll eine Zeichenkette nur aus dem gesuchten Muster bestehen (und es nicht nur enthalten), so muss in den meisten RegExp-Implementierungen explizit definiert werden, dass das Muster von Anfang (^ oder \A) bis zum Ende der Zeichenkette ($ oder \z) reichen soll, ansonsten matcht z.B. [0-9]{2,5} auch bei der Zeichenkette "1234507" die Teilzeichenkette "12345". Aus dem gleichen Grund würde bspw. a* immer matchen, da jeder String, selbst der leere "", mind. 0-mal das Zeichen "a" enthält.

Gieriges Verhalten

Normalerweise wird von einem regulären Ausdruck die größtmögliche passende Zeichenkette ausgewählt, weshalb dieses Verhalten als „gierig“ (engl.: „greedy“) bezeichnet wird. Da dieses Verhalten jedoch nicht immer so gewollt ist, lassen sich bei manchen neueren RegEx-Implementierungen Quantoren als „genügsam“ bzw. engl. „non-greedy“ (also „nicht gierig“) deklarieren. Hierfür wird dem Quantor ein Fragezeichen ? nachgestellt. Die Implementierung von genügsamen Quantoren ist vergleichsweise aufwändig, weshalb nicht alle Parser diese unterstützen. Der durch das angehängte Fragezeichen entstehende Ausdruck führt bei herkömmlichen RegEx-Implementierungen zu einer Fehlermeldung oder wird ignoriert.

Beispiel:

Angenommen es wird auf den String "ABCDEB" der reguläre Ausdruck A.*B angewendet, so würde er den kompletten String "ABCDEB" finden. Mit Hilfe des "non-greedy"-Quantors "*?" passt der neue Ausdruck, also A.*?B, nur auf die Zeichenkette "AB", bricht also die Suche nach dem ersten gefundenen "B" ab.

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 (engl. "Backreferences"). \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 Pumping-Lemma (= Pumplemma) 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".

Weitere Zeichen

Um die oft auf Zeichenketten bezogenen Anwendungen auf dem Computer zu unterstützen, werden in der Regel zusätzlich zu den bereits genannten die folgenden Zeichen definiert:

^ steht für den Zeilenanfang (nicht zu verwechseln mit „^“ bei der Zeichenauswahl mittels „[“ und „]“).
$ kann je nach Kontext für das Zeilen- oder Stringende stehen.
\ hebt gegebenenfalls die Metabedeutung des nächsten Zeichens auf. Beispielsweise lässt der Ausdruck „(A\*)+“ die Zeichenketten „A*“, „A*A*“ etc. zu und lässt sich ein Punkt, „.“, mit „\.“ suchen.
\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.

Werkzeuge

JRX - Real-time JavaScript RegExp evaluator; interpretiert eingegebene Regexps ohne Serververbindung
RegExp-Tool - Online-Tool zum Validieren und Optimieren von Regexp in freien Texten oder URLs
PCRE Evaluator - Online-Evaluations-Tool mit zusätzlichen PHP-Funktionen.
Kodos - The Python Regular Expression Debugger - frei verfügbares grafisches Tool zum Erstellen, Testen und Debuggen von regulären Ausdrücken
Tcl Regular Expression Visualiser
Regex-Coach - nichtfreies Windows- u. Linux-Programm, das anschaulich demonstriert, welche Auswirkungen reguläre Ausdrücke auf einen bestimmten Text haben, erlaubt beispielsweise das schrittweise Abarbeiten eines Ausdrucks
RegexPlor - Freeware für Mac OS X: veranschaulicht farblich markiert interaktiv die Auswirkung (match, find all, search, split, replace) eines regulären Ausdrucks
TextTransformer - ein Werkzeug, das die C++ Bibliothek Boost.Regex in POSIX-Extended Syntax benutzt, um komplette Parser zu konstruieren. Ein Dialog zum Testen von regulären Ausdrücken kann frei benutzt werden. Alle Unterausdrücke werden angezeigt und das, was durch sie jeweils erkannt wird.
txt2regex Regex erstellen mit Hilfe eines Bash Scriptes - Einfaches Erstellen von Regex
Visual REGEXP - ein freies Tcl/Tk-Programm zum Erstellen und Testen von regulären Ausdrücken (englisch)
Expresso - freies komfortables .NET-Programm zur Erstellung und zum Test von REs (englisch)
Regulärer Ausdruck Prüfer - Ein freies Online Werkzeug zum Testen von regulären Ausdrücken. (englisch)
Regexp::Compare PERL Bibliothek für den angenäherten Vergleich zwischen regulären Ausdrücken untereinander

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

Siehe auch

Wildcard
PCRE (Perl-kompatible reguläre Ausdrücke)

Weblinks

Reguläre Sprachen, reguläre Ausdrücke
Regex-Kurs für Anfänger mit Übungen
Reguläre Ausdrücke in OpenOffice.org
Regular Expression Library (englisch)
http://www.regular-expressions.info/ (englisch)
POSIX-Spezifikation für reguläre Ausdrücke (englisch)
Unicode Technical Standard #18 - Unicode Regular Expressions (englisch)

Programmiersprachenspezifisch

Perl - Syntax regulärer Ausdrücke (englisch)
Python - Beschreibung des Moduls re (englisch)
PHP - Reguläre Ausdrücke
C - Die GNU-Regex-Bibliothek (Quellcode, enthält Dokumentation)
Java - Javadoc für java.util.regex.Pattern (englisch)
Syntax regulärer Ausdrücke für Emacs und M4(Programmiersprache)