Ein regulärer Ausdruck (, Abkürzung oder ) ist in der theoretischen Informatik eine Zeichenkette, die der Beschreibung von Mengen von Zeichenketten mit Hilfe bestimmter syntaktischer Regeln dient. Neben Implementierungen in vielen Programmiersprachen verarbeiten auch viele Texteditoren reguläre Ausdrücke in der Funktion „Suchen und Ersetzen“. Ein einfacher Anwendungsfall von regulären Ausdrücken sind Wildcards.
Reguläre Ausdrücke können 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.
Der Begriff des regulären Ausdrucks geht im Wesentlichen auf den Mathematiker Stephen Kleene zurück, der die ähnliche Bezeichnung reguläre Menge verwendete.
Reguläre Ausdrücke in der theoretischen Informatik Theoretische Grundlagen Reguläre Ausdrücke sind spezielle Formeln, die reguläre Sprachen beschreiben können. Diese regulären Sprachen befinden sich auf der untersten Stufe der Chomsky-Hierarchie (Typ-3). Sie werden durch reguläre Grammatiken erzeugt.
Zu jedem regulären Ausdruck existiert ein endlicher Automat, der die vom Ausdruck spezifizierte Sprache akzeptiert. Ein entsprechender (nichtdeterministischer) endlicher Automat kann mit der Thompson-KonstruktionAlfred V. Aho, Ravi Sethi, Jeffrey Ullman: Compilers: Principles, Techniques and Tools. Addison-Wesley, 1986 aus einem regulären Ausdruck konstruiert werden. Daraus folgt die relativ einfache Implementierbarkeit regulärer Ausdrücke. Umgekehrt existiert zu jedem endlichen Automaten ein regulärer Ausdruck, der die vom Automaten akzeptierte Sprache beschreibt. Ein entsprechender regulärer Ausdruck kann mit Kleenes Algorithmus aus einem nichtdeterministischen endlichen Automaten konstruiert werden. Kleenes Algorithmus erzeugt meist sehr lange reguläre Ausdrücke. Die Zustands-Elimination (deutsch eigentlich: „Zustands-Eliminierung“) liefert in der Praxis meist kürzere reguläre Ausdrücke. Im schlimmsten Fall (englisch „worst case“) liefern jedoch beide Algorithmen reguläre Ausdrücke der Länge , wobei die Anzahl der Zeichen des zugrundeliegenden Alphabets und die Anzahl der Zustände im Automaten bezeichnen.
Syntax Die Syntax definiert genau, wie reguläre Ausdrücke aussehen.
Reguläre Ausdrücke sind immer über einer vorgegebenen endlichen Zeichenmenge definiert, dem sogenannten Alphabet. Reguläre Ausdrücke basieren auf genau drei Operationen: Alternative, Verkettung und Wiederholung. Die formale Definition sieht folgendermaßen aus: (das spezielle Symbol für die leere Menge) ist ein regulärer Ausdruck. für alle ist (die Repräsentation eines Zeichens aus dem zugrunde liegenden Alphabet) ein regulärer Ausdruck. Sind und reguläre Ausdrücke, so sind auch (Alternative), (Verkettung) und (Kleenesche Hülle, Kleene-Stern) reguläre Ausdrücke.
Für Alternative wird statt auch das Symbol verwendet. Man schreibt dann . Für die Verkettung (Konkatenation) gibt es alternativ auch ein Operatorsymbol; man schreibt dann .
Man kann auch zusätzliche Konstanten und Operationen erlauben, sofern sich ihre Wirkung auch mit den oben genannten Grundregeln beschreiben ließe. So findet man in der Literatur unter anderem auch als regulären Ausdruck oder die positive Kleenesche Hülle , die als Abkürzung von betrachtet werden kann.
Gibt man eine Rangfolge der Operatoren an, kann man auf einige Klammern verzichten. Die Rangfolge ist üblicherweise Kleene-Stern vor Konkatenation vor Alternative. Statt genügt dann die Schreibweise .
Die Anzahl der verschachtelten *-Operatoren wird als Sternhöhe bezeichnet.
Semantik Die Semantik regulärer Ausdrücke definiert genau, welche formale Bedeutung die Syntax regulärer Ausdrücke hat.
Ein regulärer Ausdruck beschreibt eine formale Sprache, also eine Menge von Wörtern (Zeichenketten). Die Definition der Semantik lässt sich analog zur Syntaxdefinition beschreiben. Dabei bezeichnet die formale Sprache, die durch den regulären Ausdruck spezifiziert wird.
Das Symbol für die leere Menge spezifiziert die leere Sprache. für alle gilt Jeder Repräsentant eines Zeichens aus dem Alphabet spezifiziert die Sprache, die nur das Wort der Länge eins mit diesem Zeichen enthält. sind und reguläre Ausdrücke, so gilt:
Die Alternative zwischen zwei Ausdrücken beschreibt die Sprache, die aus der Vereinigung der zwei Sprachen entsteht, die durch die beiden Ausdrücke beschrieben werden.
Die Konkatenation zweier Ausdrücke beschreibt die Sprache, die nur die Wörter enthält, die ein Wort aus der vom ersten Ausdruck beschriebenen Sprache als Präfix haben und deren unmittelbar folgendes Rest-Suffix ein Wort aus der vom zweiten Ausdruck beschriebenen Sprache ist.
Die kleenesche Hülle eines regulären Ausdrucks beschreibt die Sprache mit jenen Wörtern, die durch Aneinanderreihen beliebiger Wörter der durch beschriebenen Sprache entstehen.
Enthält die Syntaxdefinition regulärer Ausdrücke auch die Konstante , so ist deren Bedeutung definiert als , also die Sprache, die nur das leere Wort enthält.
Das leere Wort ist ein Wort einer formalen Sprache () und somit kein regulärer Ausdruck. Die Sprache, die nur das leere Wort enthält, lässt sich aber auch ohne die Konstante durch einen regulären Ausdruck beschreiben, zum Beispiel: . Es wird jedoch nicht immer optisch zwischen einem regulären Ausdruck und der zugehörigen Sprache unterschieden, sodass man statt auch als regulären Ausdruck für die Sprache verwendet, ebenso kann die Unterscheidung zwischen und sowie zwischen und entfallen.
Beispiele Wenn das Alphabet aus den Buchstaben , und besteht, also , dann lassen sich die folgenden Sprachen mit den entsprechenden regulären Ausdrücken beschreiben: Die Sprache aller Wörter, die aus beliebig vielen oder aus beliebig vielen bestehen: Syntax: . Semantik: Die Sprache aller Wörter, die mit anfangen und mit beliebig vielen oder beliebig vielen enden: Syntax: . Semantik: Die Sprache aller Wörter, die mit anfangen und mit einer beliebigen Folge aus den Zeichen enden: Syntax: . Semantik: Die Sprache aller Wörter, die zwei Zeichen lang sind und aus den Zeichen und bestehen: Syntax: . Semantik: Die Sprache aller Wörter, die aus beliebig vielen Teilwörtern bestehen: Syntax: . Semantik:
Anwendung regulärer Ausdrücke Ken Thompson nutzte diese Notation in den 1960er Jahren, 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, awk, grep, lex, emacs, die Programmiersprachen Perl und Tcl und Standardbibliotheken der Programmiersprachen C, C++, Java, JavaScript, Python, PHP, R, Ruby und das .Net-Framework. Auch die Textverarbeitung und die Tabellenkalkulation des Office-Paketes OpenOffice.org bieten die Möglichkeit, mit regulären Ausdrücken im Text zu suchen.
Zwischen verschiedenen Regexp-Implementierungen gibt es Unterschiede in Funktionsumfang und Syntax. In Programmiersprachen haben sich überwiegend die Perl Compatible Regular Expressions (PCRE) durchgesetzt, die sich an der Umsetzung in Perl 5.0 orientieren. Daneben wird bei POSIX zwischen „grundlegenden“ regulären Ausdrücken (basic regular expressions) und „erweiterten“ regulären Ausdrücken (extended regular expressions) unterschieden.
Einige Programme, zum Beispiel der Texteditor Vim, bieten die Möglichkeit, zwischen verschiedenen Regexp-Syntaxen hin- und herzuschalten.
Reguläre Ausdrücke spielen eine wichtige Rolle bei der lexikalischen Analyse von Quelltexten, beispielsweise in Compilern oder zur Syntaxhervorhebung in Editoren. Ein lexikalischer Scanner zerlegt den Quelltext mithilfe von regulären Ausdrücken in sogenannte Tokens (Schlüsselwörter, Operatoren …). Da es sich bei den meisten Programmiersprachen um kontextfreie Sprachen handelt, sind reguläre Ausdrücke nicht mächtig genug, um deren Syntax zu beschreiben. Daher wird die bei Compilern folgende syntaktische Analyse in der Regel von einem separaten Programm, dem Parser, erledigt.
Reguläre Ausdrücke spielen auch in der Bioinformatik eine Rolle. Sie kommen in Proteindatenbanken zum Einsatz, um Proteinmotive zu beschreiben. Der reguläre Ausdruck
W-x{9,11}-[VFY]-[FYW]-x{6,7}-[GSTNE]-[GSTQCR]-[FYW]-R-S-A-P
beschreibt zum Beispiel eine Proteindomäne in PROSITE. Der obige reguläre Ausdruck besagt Folgendes: Am Anfang wähle die Aminosäure Tryptophan (Einbuchstabencode W), dann wähle 9 bis 11 Aminosäuren frei aus, dann wähle entweder V, F oder Y, dann wähle entweder F, Y oder W, dann wieder 6 bis 7 Aminosäuren frei, dann entweder G, S, T, N oder E, dann entweder G, S, T, Q, C oder R, dann F, Y oder W, dann R dann S dann A dann P.
Reguläre Ausdrücke in der Praxis Die meisten heutigen Implementierungen unterstützen Erweiterungen wie zum Beispiel Rückwärtsreferenzen (backreferences). Hierbei handelt es sich nicht mehr um reguläre Ausdrücke im Sinne der theoretischen Informatik, denn die so erweiterten Ausdrücke beschreiben nicht mehr notwendigerweise Sprachen vom Typ 3 der Chomsky-Hierarchie.
Die folgenden Syntaxbeschreibungen beziehen sich auf die Syntax der gängigen 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. 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 den Metazeichen [ ] ( ) { } | ? + - * ^ $ \ . (teilweise kontextabhängig) gebildet, bei manchen Implementierungen auch : ! < =. Die Meta-Eigenschaft eines Zeichens kann durch einen vorangestellten Rückwärtsstrich (Backslash) aufgehoben werden. 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, das Zeichen durch den Oktal- oder Hexadezimalcode (\ooo bzw. \xhh) oder die hexadezimale Unicode-Position (\uhhhh) anzugeben.
Ein Zeichen aus einer Auswahl Mit eckigen Klammern ([ und ]) lässt sich eine Zeichenauswahl definieren. Der Ausdruck in eckigen Klammern steht dann für genau ein Zeichen aus dieser Auswahl. Innerhalb dieser Zeichenklassendefinitionen haben einige Symbole andere Bedeutungen als im normalen Kontext. Teilweise ist die Bedeutung eines Symbols vom Kontext abhängig, in dem es innerhalb der Klammern auftritt.
Beispielsweise bedeutet ein Zirkumflex ^ am Anfang einer Zeichenklassendefinition, dass die Zeichenklasse negiert bzw. invertiert wird (im Sinne der Komplementbildung). Steht ein Zirkumflex jedoch irgendwo sonst in der Definition, ist es wörtlich („literally“) zu verstehen. Ebenfalls kontextabhängig ist die Bedeutung des Bindestrich-Zeichens (-). Zudem unterscheiden sich hier die Regexp-Auswerter („regex engines“) (zum Beispiel POSIX und PCRE) in einigen Punkten voneinander. Steht ein Bindestrich - zwischen zwei Zeichen in der Klassendefinition, zum Beispiel [a-g], so ist er als Bis-Strich zu verstehen, das heißt als Beschreibung eines Zeichenintervalls oder Zeichenbereichs bezüglich der ASCII-Tabelle. Das genannte Beispiel wäre äquivalent zu [abcdefg]. Am Anfang oder Ende einer Zeichenklasse stehende Bindestriche werden als das Zeichen selbst interpretiert.