Regulärer Ausdruck

Reguläre Ausdrücke (Abk. RegExp oder Regex, engl. regular expressions) dienen der Beschreibung von (Unter-)Mengen von Zeichenketten mit Hilfe syntaktischer Regeln. Sie finden vor allen in der Softwareentwicklung Verwendung; für fast alle Programmiersprachen existieren Implementierungen.

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\epsilon$ (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 kann ein Punkt auch ein Newline (Zeilenumbruch) enthalten, die meisten Implementierungen sehen jedoch 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:

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

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

^*	Alphanumerische Zeichen: und [:digit:.
^*	Buchstaben: und [:upper:.
^*	Leerzeichen und Tabulator.
^*	Steuerzeichen. Im ASCII-Kode sind das die Zeichen 00 bis 1F, und 7F (DEL).
^*	Ziffern: 0, 1, 2,... bis 9.
^*	Graphische Zeichen: und [:punct:.
^*	Kleine Buchstaben: a bis z.
^*	Druckbare Zeichen: [:punct: und Leerzeichen.
^*	! " # $ % & ' ( ) * + , - . / : ; < = > ? @ \ ^ _ ` { > } ~ .
^*	Whitespace: tab, newline, vertical tab, form feed, carriage return, and space.
^*	Großbuchstaben: A bis Z.
^*	Hexadezimale Ziffern: 0 bis 9, A bis F, a bis f.

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 ^*
\D : keine Ziffer ^*
\w : ein Buchstabe, eine Ziffer oder der Unterstrich ^*
\W : kein Buchstabe, keine Zahl und kein Unterstrich ^*
\s : Whitespace, meistens \f\n\r\t\v
\S : alle Zeichen außer Whitespace ^*

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.
+ : 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.
^*+ dagegen erlaubt ein "a", "b", "aa", "baab" etc.
^*{2,5} trifft auf jede Zeichenfolge zu, die an irgendeiner Stelle zwei, drei, vier oder fünf Ziffern in Folge enthält, z. B. "12", "12345", "123123223" oder "abc12xyz"; nicht jedoch trifft der Ausdruck z. B. auf die Zeichenfolgen "0", "1.1" und "a1a1" zu.

Gieriges Verhalten

Normalerweise wird von einem regulären Ausdruck mit Quantor die größtmögliche passende Zeichenkette gematcht, 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 "non-greedy" (also "nicht gierig") deklarieren. Hierfür wird dem Quantor ein Fragezeichen ? nachgestellt. Der entstehende Ausdruck führt bei herkömmlichen RegEx-Implementierung zu einer Fehlermeldung.

Beispiel:

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

Die Implementierung von genügsamen ("non-greedy") Quantoren ist vergleichsweise aufwändig, weshalb nicht alle RegEx-Parser diese unterstützen.

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 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

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 Abarbeiten/Matchen des Ausdrucks in Schritten und vieles mehr
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 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)

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

Reguläre Sprachen, reguläre Ausdrücke
Regex-Kurs für Anfänger mit Übungen
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 - Beschreibung in SELFHTML
Perl - Syntax regulärer Ausdrücke (englisch)
PHP - Reguläre Ausdrücke
C - Die GNU-Regex-Bibliothek (Quellcode, enthält Dokumentation)
Java - Javadoc für java.util.regex.Pattern (englisch)

Programmierung | Programmiersprachelement | Compilerbau | Theoretische Informatik

Gourt Home::Gourt :: Regulärer Ausdruck