Regulärer Ausdruck

Grundidee und theoretische Bedeutung

Ein regulärer Ausdruck (RegExp oder Regex) ist eine Zeichenkette, die nach festen syntaktischen Regeln Mengen von Zeichenketten beschreibt. Beim sogenannten Pattern Matching wird geprüft, ob ein Text oder ein Teil davon dem Muster entspricht. Dadurch lassen sich beispielsweise aus einer Wortliste alle Wörter auswählen, die mit S beginnen und mit D enden, ohne die Buchstaben dazwischen oder ihre Anzahl festzulegen.

In der theoretischen Informatik beschreiben reguläre Ausdrücke reguläre Sprachen. Diese gehören zur untersten Stufe der Chomsky-Hierarchie, dem Typ 3, und werden durch reguläre Grammatiken erzeugt. Zu jedem regulären Ausdruck gibt es einen endlichen Automaten, der die beschriebene Sprache akzeptiert. Aus einem regulären Ausdruck kann mit der Thompson-Konstruktion ein nichtdeterministischer endlicher Automat entstehen. Umgekehrt lässt sich aus jedem endlichen Automaten ein regulärer Ausdruck konstruieren: Kleenes Algorithmus arbeitet mit einem nichtdeterministischen endlichen Automaten, während die Zustands-Elimination in der Praxis meist kürzere Ausdrücke liefert. Im schlechtesten Fall haben beide Verfahren eine Länge von |Σ|4^{|Q|}; dabei bezeichnet |Σ| die Anzahl der Zeichen des Alphabets und |Q| die Anzahl der Zustände.

Diese theoretische Grundlage erklärt, warum reguläre Ausdrücke vergleichsweise einfach implementierbar sind. Erweiterungen moderner Programme, etwa Rückwärtsreferenzen und bestimmte Kontextbedingungen, gehen jedoch über reguläre Sprachen hinaus und beschreiben nicht mehr notwendigerweise Sprachen vom Typ 3.

Syntax und Semantik der Grundformen

Ein regulärer Ausdruck wird über einem endlichen Alphabet Σ definiert. Die klassische Syntax beruht auf drei Operationen: Alternative, Verkettung und Wiederholung.

• ∅ ist der reguläre Ausdruck für die leere Menge.
• Für jedes Zeichen a ∈ Σ ist a ein regulärer Ausdruck.
• Sind x und y reguläre Ausdrücke, dann sind auch (x|y), (xy) und (x*) reguläre Ausdrücke. Dabei steht | für die Alternative, xy für die Verkettung und x* für die Kleenesche Hülle.

Für die Alternative wird auch + verwendet, für die Verkettung kann man x · y schreiben. Zusätzlich erlaubte Schreibweisen sind ε für das leere Wort und x+ für die positive Kleenesche Hülle. x+ ist eine Abkürzung für (x(x*)). Die übliche Rangfolge lautet: Kleene-Stern vor Verkettung vor Alternative. Deshalb kann (((ab)|c)) als (ab|c) geschrieben werden. Die Anzahl verschachtelter *-Operatoren heißt Sternhöhe.

Die Semantik legt fest, welche Sprache ein Ausdruck beschreibt. Für einen Ausdruck r bezeichnet L(r) die zugehörige formale Sprache:

• L(∅) = ∅.
• L(a) = {a}; der Ausdruck a beschreibt also genau das eine Zeichen.
• L(x|y) = L(x) ∪ L(y); die Alternative bildet die Vereinigung.
• L(xy) = {αβ | α ∈ L(x) ∧ β ∈ L(y)}; die Wörter aus beiden Sprachen werden aneinandergereiht.
• L(x*) = {α₁…αₙ | n ∈ ℕ₀, α₁,…,αₙ ∈ L(x)}; beliebig viele, auch null, Wörter aus L(x) werden verkettet.

Falls ε als Ausdruck zugelassen ist, gilt L(ε) = {ε}. Das leere Wort ε ist selbst kein regulärer Ausdruck, sondern ein Wort aus Σ*. Die Sprache, die nur das leere Wort enthält, kann ohne ε etwa durch ∅* beschrieben werden.

Klassische Beispiele

Für das Alphabet Σ = {a,b,c} gelten unter anderem folgende Beschreibungen:

• a*|b* beschreibt alle Wörter, die nur aus beliebig vielen a oder nur aus beliebig vielen b bestehen.
• a(b*|c*) beschreibt Wörter, die mit a beginnen und danach beliebig viele b oder beliebig viele c enthalten.
• a(a|b|c)* beschreibt Wörter, die mit a beginnen und danach eine beliebige Folge aus a, b und c haben.
• (a|b)(a|b) beschreibt genau die zweistelligen Wörter aa, ab, ba und bb.
• (ab)* beschreibt beliebig viele Wiederholungen des Teilworts ab, also ε, ab, abab, ababab, …

In Programmen werden auch kompakte Beispiele verwendet. hello findet hello, gray|grey findet gray oder grey, gr[ae]y findet ebenfalls gray oder grey. colou?r findet color und colour. go*gle findet ggle, gogle, google und weitere Varianten mit beliebig vielen o; go+gle verlangt dagegen mindestens ein o. Der Ausdruck g(oog)+le findet google, googoogle und weitere Wiederholungen von oog.

Zeichenklassen und Wiederholungen

In praktischen Implementierungen werden wörtliche Zeichen direkt notiert. Sonderzeichen können je nach System auch als Oktalcode (\ooo), Hexadezimalcode (\xhh) oder Unicode-Position (\uhhhh) angegeben werden. Ein Backslash hebt die Metabedeutung des folgenden Zeichens auf.

Eckige Klammern definieren eine Zeichenauswahl, die genau ein Zeichen umfasst. [egh] bedeutet e, g oder h; [0-6] steht für eine Ziffer von 0 bis 6; [A-Za-z0-9] erlaubt lateinische Buchstaben und Ziffern. Ein ^ am Anfang negiert die Klasse, daher bedeutet [^a] jedes Zeichen außer a. Ein Bindestrich zwischen zwei Zeichen beschreibt einen Bereich, etwa [a-g], am Anfang oder Ende einer Klasse dagegen das Zeichen - selbst. Die genaue Behandlung einzelner Zeichen kann sich zwischen POSIX und PCRE unterscheiden.

Häufige vordefinierte Klassen sind:

• \d: eine Ziffer, meist [0-9], eventuell einschließlich weiterer Unicode-Ziffern.
• \D: ein Zeichen, das keine Ziffer ist.
• \w: Buchstabe, Ziffer oder Unterstrich; je nach Implementierung auch nichtlateinische Buchstaben.
• \W: ein Zeichen, das kein Wortzeichen ist.
• \s: Whitespace, meist Leerzeichen sowie \f, \n, \r, \t und \v.
• \S: ein Zeichen, das kein Whitespace ist.
• \p{…} und \P{…}: Zeichen, die einer Unicode-Kategorie angehören oder nicht angehören, etwa \p{L} für Buchstaben und \p{N} für Nummern.

Der Punkt . steht für ein fast beliebiges Zeichen; Zeilenumbrüche sind meist ausgenommen. Der Single-Line-Modifier s kann dies in einigen Implementierungen ändern. POSIX bietet zusätzlich Klassen wie [:digit:], [:alpha:], [:alnum:], [:space:], [:punct:], [:lower:] und [:upper:].

Quantoren bestimmen, wie oft der vorherige Ausdruck vorkommen darf: {min,max} bedeutet mindestens min- und höchstens max-mal, {n} genau n-mal, {0,max} höchstens max-mal, {min,} mindestens min-mal, ? null- oder einmal, + mindestens einmal und * beliebig oft einschließlich nullmal. [ab]+ findet beispielsweise a, b, aa oder bbaab; [0-9]{2,5} findet zwei bis fünf Ziffern, etwa 42 oder 54072.

Ohne Anfangs- und Endmarkierung wird oft nur ein Teil gefunden. Damit die gesamte Zeichenkette dem Muster entsprechen muss, werden je nach Implementierung \A oder ^ für den Anfang und \Z, \z oder $ für das Ende verwendet. Quantoren sind normalerweise gierig und suchen die längstmögliche Übereinstimmung. Ein genügsamer Quantor, etwa ?, sucht die kürzeste passende Folge: A.?B findet in ABCDEB nur AB, während A.*B die gesamte Zeichenkette findet. Eine Alternative ohne *? ist A[^B]*B.

Gruppen, Rückwärtsreferenzen und Kontextbedingungen

Runde Klammern fassen Ausdrücke zusammen. (abc)+ findet abc, abcabc und weitere Wiederholungen. Viele Implementierungen speichern die Übereinstimmung einer Gruppe. Sie kann über eine Rückwärtsreferenz wie \n oder $n erneut verwendet werden; n bezeichnet die Nummer der Gruppe, während n=0 meist die gesamte Übereinstimmung meint. Mit AA(.*?)BB als Suchausdruck und \1 als Ersetzung werden die Begrenzungen AA und BB entfernt und nur der Inhalt dazwischen eingesetzt.

Nicht erfassende Gruppen werden meist als (?:…) geschrieben. Der Ausdruck \d+(?:-\d+)* findet Zahlenfolgen mit durch Bindestriche getrennten weiteren Zahlen, ohne die letzte Zahl als Rückwärtsreferenz zu speichern. Das spart Speicher und Ausführungszeit. Rückwärtsreferenzen erweitern die Ausdrucksmacht: Ausdrücke, die sie im Suchmuster verwenden, entsprechen nicht mehr notwendigerweise regulären Sprachen. Ein Beispiel für eine Umformung ist das Datum MM/DD/YYYY: ([0-1]?[0-9])\/([0-3]?[0-9])\/([0-9]{4}) extrahiert drei Gruppen, die mit \3-\1-\2 in YYYY-MM-DD umgeordnet werden.

Possessives Matching verhindert Backtracking. Bei A.+B wird in ABCDEB keine Übereinstimmung gefunden, weil .+ bis zum Ende reicht und das letzte B nicht wieder freigeben darf. Dafür gibt es unter anderem (?>Ausdruck) sowie die possessiven Quantoren ++, *+, ?+ und {min,max}+.

Look-around assertions prüfen Kontext, ohne ihn selbst als Teil der Übereinstimmung zurückzugeben. Sport(?=verein) findet in „Ein Sportler betreibt Sport im Sportverein.“ nur das letzte Sport. Positive und negative Varianten sind (?=Ausdruck), (?!Ausdruck), (?<=Ausdruck) und (?<!Ausdruck). \s(?=EUR) findet ein Whitespace-Zeichen vor EUR, nicht aber EUR selbst.

Inline-Modifikatoren können für den gesamten folgenden Ausdruck oder nur für eine Gruppe gelten: (?Modifikatoren)Ausdruck beziehungsweise (?Modifikatoren:Ausdruck). i ignoriert Groß- und Kleinschreibung, m behandelt Zeilenanfang und -ende innerhalb mehrzeiliger Eingaben, s lässt den Punkt auch auf Zeilenumbrüche passen. Relativ seltene bedingte Ausdrücke haben die Form (?(Bedingung)wahr-Ausdruck|falsch-Ausdruck). Als Bedingung können unter anderem eine Look-around assertion oder eine Gruppennummer dienen.

Praktische Nutzung und Grenzen

Reguläre Ausdrücke werden in vielen Texteditoren, Programmen, Bibliotheken und Programmiersprachen zum Suchen und Ersetzen eingesetzt. Genannt werden unter anderem sed, awk, grep, lex, emacs, Perl, Tcl sowie Bibliotheken für C, C++, Java, JavaScript, Python, PHP, R, Ruby und das .Net-Framework. Auch Textverarbeitung und Tabellenkalkulation von OpenOffice.org unterstützen die Suche mit regulären Ausdrücken.

Die Syntax und der Funktionsumfang unterscheiden sich zwischen Implementierungen. Verbreitet sind Perl Compatible Regular Expressions (PCRE), die sich an Perl 5.0 orientieren. POSIX unterscheidet grundlegende und erweiterte reguläre Ausdrücke; Programme wie Vim können zwischen Syntaxvarianten umschalten. Weitere praktische Zeichen sind ^ für den Zeilenanfang, $ für Zeilen- oder Zeichenkettenende, \b und \B für Wortgrenzen beziehungsweise Nicht-Wortgrenzen, \< und \> für Wortanfang und Wortende sowie \n, \r, \r\n und \t für verschiedene Zeilenumbrüche und Tabulatoren.

Eine wichtige Anwendung ist die lexikalische Analyse. Ein Scanner zerlegt Quelltext mithilfe regulärer Ausdrücke in Tokens, etwa Schlüsselwörter und Operatoren. Da die meisten Programmiersprachen kontextfreie Sprachen sind, reichen reguläre Ausdrücke nicht aus, um ihre gesamte Syntax zu beschreiben; diese Aufgabe übernimmt anschließend meist ein Parser.

Auch in der Bioinformatik werden reguläre Ausdrücke verwendet, beispielsweise in Proteindatenbanken zur Beschreibung von Proteinmotiven. Der Ausdruck W-x{9,11}-[VFY]-[FYW]-x{6,7}-[GSTNE]-[GSTQCR]-[FYW]-R-S-A-P beschreibt eine Proteindomäne in PROSITE: zuerst Tryptophan W, dann 9 bis 11 beliebige Aminosäuren, danach V, F oder Y, anschließend F, Y oder W, dann 6 bis 7 beliebige Aminosäuren, danach G, S, T, N oder E, anschließend G, S, T, Q, C oder R, dann F, Y oder W und schließlich R, S, A, P.