Regulärer Ausdruck

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Regex)
Wechseln zu: Navigation, Suche

Ein regulärer Ausdruck (englisch regular expression, Abkürzung: RegExp oder Regex) ist in der theoretischen Informatik eine Zeichenkette, die der Beschreibung von Mengen von Zeichenketten mit Hilfe bestimmter syntaktischer Regeln dient. Reguläre Ausdrücke finden vor allem in der Softwareentwicklung Verwendung. Neben Implementierungen in vielen Programmiersprachen verfügen auch viele Texteditoren über 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 dazwischenliegenden 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. Dieser benutzte eine fast identische Notation, die er „reguläre Mengen“ nannte.[1]

Reguläre Ausdrücke in der theoretischen Informatik[Bearbeiten]

Theoretische Grundlagen[Bearbeiten]

Reguläre Ausdrücke beschreiben eine Familie von formalen Sprachen und gehören damit zur theoretischen Informatik. Diese Sprachen, die regulären Sprachen, befinden sich auf der untersten und somit ausdrucksschwächsten Stufe der Chomsky-Hierarchie (nämlich Typ-3). Sie werden erzeugt durch reguläre Grammatiken.

Zu jedem regulären Ausdruck existiert ein endlicher Automat, der die vom Ausdruck spezifizierte Sprache akzeptiert. Diese endlichen Automaten können ausgehend von regulären Ausdrücken 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.

Syntax[Bearbeiten]

Die Syntax definiert genau, wie reguläre Ausdrücke aussehen.

Reguläre Ausdrücke sind immer über einem vorgegebenen Zeichenvorrat \Sigma definiert, dem sogenannten Alphabet. Reguläre Ausdrücke basieren auf genau drei Operationen: Alternative, Verkettung und Wiederholung. Die formale Definition sieht folgendermaßen aus:

  1. \varnothing (das spezielle Symbol für die leere Menge) ist ein regulärer Ausdruck.
  2. für alle a_i \in \Sigma ist \mathbf{a}_i (die Repräsentation eines Zeichens aus dem zugrunde liegenden Alphabet) ein regulärer Ausdruck.
  3. Sind x und y reguläre Ausdrücke, so sind auch (x | y) (Alternative), (xy) (Verkettung) und (x^*) (Kleenesche Hülle, Kleene-Stern) reguläre Ausdrücke.

Für Alternative wird statt | auch das Symbol + verwendet. Man schreibt dann (x+y). Für die Verkettung (Konkatenation) gibt es alternativ auch ein Operatorsymbol; man schreibt dann (x \cdot y).

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 \epsilon als regulären Ausdruck[2] oder die positive Kleenesche Hülle x^+, die als Abkürzung von (x(x^*)) 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 (((ab) | c)^*) genügt dann die Schreibweise (ab | c)^*.

Die Anzahl der verschachtelten *-Operatoren wird als Sternhöhe bezeichnet.

Semantik[Bearbeiten]

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 \mathcal{L}(regex) die formale Sprache, die durch den regulären Ausdruck regex spezifiziert wird.

  1. \mathcal{L}(\varnothing) = \emptyset
    Das spezielle Symbol für die leere Menge spezifiziert die leere Sprache.
  2. für alle a_i \in \Sigma gilt \mathcal{L}(\mathbf{a}_i)=\{a_i\}
    Jeder Repräsentant eines Zeichens aus dem Alphabet spezifiziert die Sprache, die nur dieses Zeichen enthält.
  3. sind x und y reguläre Ausdrücke, so gilt:
    • \mathcal{L}(x | y)=\mathcal{L}(x) \cup \mathcal{L}(y)
    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.
    • \mathcal{L}(xy)=\{\alpha\beta\; \vert\; \alpha \in \mathcal{L}(x) \land \beta \in \mathcal{L}(y)\}
    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.
    • \mathcal{L}(x^*) = \cup_{i\geq 0}\; \mathcal{L}^i(x)
    Die kleenesche Hülle regulärer Ausdrücke beschreibt die kleenesche Hülle der durch x beschriebenen Sprache.

Enthält die Syntaxdefinition regulärer Ausdrücke auch die Konstante \epsilon, so ist deren Bedeutung definiert als \mathcal{L}(\epsilon)=\{\varepsilon\}, also die Sprache, die nur das leere Wort \varepsilon enthält.

Das leere Wort ist ein Wort einer formalen Sprache (\varepsilon \in \Sigma^*) und somit kein regulärer Ausdruck. Die Sprache, die nur das leere Wort enthält, lässt sich aber auch ohne die Konstante \epsilon durch einen regulären Ausdruck beschreiben, zum Beispiel: \varnothing^*. Es wird jedoch nicht immer optisch zwischen einem regulären Ausdruck und der zugehörigen Sprache unterschieden, sodass man statt \mathbf{a} auch a als regulären Ausdruck für die Sprache \{a\} verwendet, ebenso kann die Unterscheidung zwischen \varnothing und \emptyset sowie zwischen \epsilon und \varepsilon entfallen.

Beispiele[Bearbeiten]

Wenn das Alphabet aus den Buchstaben a, b und c besteht, also \Sigma =\{a,b,c\}, dann lassen sich die folgenden Sprachen mit den entsprechenden regulären Ausdrücken beschreiben:

  • Die Sprache aller Wörter, die aus beliebig vielen a oder beliebig vielen b besteht:
    Syntax: regex = \mathbf{a}^* | \mathbf{b}^*. Semantik: \mathcal{L}(regex)=\{a\}^* \cup \{b\}^*
  • Die Sprache aller Wörter, die mit a anfangen:
    Syntax: regex = \mathbf{a}(\mathbf{a}|\mathbf{b}|\mathbf{c})^*. Semantik: \mathcal{L}(regex)=\{a\beta \;\vert\; \beta \in \Sigma^*\}
  • Die Sprache aller Wörter, die mit a anfangen und enden und dazwischen nur aus c bestehen (oder nichts dazwischen liegt):
    Syntax: \mathbf{a}\mathbf{c}^*\mathbf{a}. Semantik: \mathcal{L}(regex)=\{a\beta a \;\vert\; \beta \in \{c\}^*\}
  • Die Sprache aller Wörter, die aus zwei Zeichen bestehen, aber kein c enthalten:
    Syntax: (\mathbf{a}|\mathbf{b}) (\mathbf{a}|\mathbf{b}). Semantik: \mathcal{L}(regex)=\{\alpha\beta \;\vert\; \alpha,\beta \in \{a,b\}\}

Anwendung regulärer Ausdrücke[Bearbeiten]

Ken Thompson nutzte diese Notation in den 1960ern, 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 Perl, C, Java, JavaScript, Python, PHP, 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.2 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[Bearbeiten]

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. Die Meta-Eigenschaft eines Zeichens kann durch ein vorangestelltes Backslash-Zeichen aufgehoben werden. Alle übrigen Zeichen des Alphabets stehen für sich selbst.

Zeichenliterale[Bearbeiten]

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[Bearbeiten]

Mit eckigen Klammern lässt sich eine Zeichenauswahl definieren ([ und ]). 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/invertiert wird (im Sinne der Komplementbildung). Steht ein Zirkumflex jedoch irgendwo sonst in der Definition, ist es literal zu verstehen. Ebenfalls kontextabhängig ist die Bedeutung des Bindestrich-Zeichens (-). Zudem unterscheiden sich hier die Regexp-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 literal interpretiert.

Beispiele für Zeichenauswahl
[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)
[-A-Z], [A-Z-] (bzw. [A-Z\-a-z], allerdings nicht gemäß POSIX)[3] Auswahl enthält auch den Bindestrich „-“, wenn er das erste oder das letzte Zeichen in der Aufzählung einer Zeichenklasse ist bzw. bei PCRE, wenn seine Metafunktion innerhalb einer Auswahl durch ein vorangestelltes „\“-Zeichen aufgehoben wird

Vordefinierte Zeichenklassen[Bearbeiten]

Es gibt vordefinierte Zeichenklassen, die allerdings nicht von allen Implementierungen in gleicher Weise unterstützt werden, da sie lediglich Kurzformen sind und auch durch eine Zeichenauswahl beschrieben werden können. Wichtige Zeichenklassen sind:

\d digit eine Ziffer, also [0-9] (und evtl. auch weitere Zahlzeichen in Unicode, z. B. bengalische Ziffern)
\D no digit ein Zeichen, das keine Ziffer ist, also [^\d]
\w word character ein Buchstabe, eine Ziffer oder der Unterstrich, also [a-zA-Z_0-9] (und evtl. auch nicht-lateinische Buchstaben, z. B. Umlaute)
\W no word character ein Zeichen, das weder Buchstabe noch Zahl noch Unterstrich ist, also [^\w]
\s whitespace meist zumindest das Leerzeichen und die Klasse der Steuerzeichen \f, \n, \r, \t und \v
\S no whitespace ein Zeichen, das kein Whitespace ist, also [^\s]

Ein Punkt (.) bedeutet, dass an seinem Platz ein (fast) beliebiges Zeichen stehen kann. Die meisten RegExp-Implementierungen sehen standardmäßig Newline (Zeilenumbruch) nicht als beliebiges Zeichen an, jedoch kann in einigen Programmen mithilfe des sogenannten Single-Line-Modifiers s (zum Beispiel in /foo.bar/s) ebendies erreicht werden.

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:

Beispiele für Zeichenklassen, hierarchisch sortiert
  • [:cntrl:] — Steuerzeichen. Im ASCII sind das die Zeichen 00 bis 1F und 7F (DEL).
  • [:print:] — Druckbare Zeichen: [:alnum:], [:punct:] und Leerzeichen
    • [:space:]Whitespace: Horizontaler und vertikaler Tabulator, Zeilen- und Seitenvorschub, Wagenrücklauf und LeerzeichenZK1
    • [:graph:] — Graphische Zeichen: [:alnum:] oder [:punct:]
      • [:punct:] — Satzzeichen wie: ! " # $ % & ' ( ) * + , - . / : ; < = > ? @ [ \ ] ^ _ ` { | } ~
      • [:alnum:]Alphanumerische Zeichen: [:alpha:] oder [:digit:]
        • [:xdigit:]Hexadezimale Ziffern: 0 bis 9, A bis F, a bis f.
          • [:digit:] — Die Ziffern 0 bis 9
        • [:alpha:] — Buchstaben: [:lower:] oder [:upper:]
          • [:lower:] — KleinbuchstabenZK2: nicht notwendigerweise nur von a bis z
          • [:upper:] — GroßbuchstabenZK2: nicht notwendigerweise nur von A bis Z
Anmerkungen:
ZK1 Das auch als „geschütztes Leerzeichen“ bekannte Zeichen mit der Unicode-Nummer 160 (hex: A0) (entspricht dem HTML-Entity &nbsp;)[4] wird von der Klasse [:space:] möglicherweise nicht gefunden und muss separat anhand des Kodierpunktes identifiziert werden.
ZK2 Was Buchstaben sind, ist im Allgemeinen locale-abhängig, also abhängig von der eingestellten Region und Sprache.[5]

Quantoren[Bearbeiten]

Quantoren (englisch quantifier, 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, das heißt 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.
{min,max} Der voranstehende Ausdruck muss mindestens min-mal und darf maximal max-mal vorkommen.
{0,max} Der voranstehende Ausdruck darf maximal max-mal vorkommen.

Die Quantoren beziehen sich dabei auf den vorhergehenden regulären Ausdruck, jedoch nicht zwangsläufig auf die durch ihn gefundene Übereinstimmung. So wird zwar zum Beispiel durch a+ ein „a“ oder auch „aaaa“ vertreten, jedoch entspricht [0-9]+ nicht nur sich wiederholenden gleichen Ziffern, sondern auch Folgen gemischter Ziffern, beispielsweise „072345“.

Weitere Beispiele sind:

  • [ab]+“ entspricht „a“, „b“, „aa“, „bbaab“ etc.
  • [0-9]{2,5}“ entspricht zwei, drei, vier oder fünf Ziffern in Folge, z. B. „42“ oder „54072“, jedoch nicht den 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 Implementierungen explizit definiert werden, dass das Muster vom Anfang (\A oder ^)QF1 bis zum Ende der Zeichenkette (\Z, \z oder $)QF1 reichen soll. Andernfalls erkennt zum Beispiel [0-9]{2,5} auch bei der Zeichenkette „1234507“ die Teilzeichenkette „12345“. Aus dem gleichen Grund würde beispielsweise a* immer einen Treffer ergeben, da jede Zeichenfolge – selbst das leere Wort „“ – mindestens 0-mal das Zeichen „a“ enthält.

Quantoren sind standardmäßig „gierig“ (englisch greedy) implementiert. Das heißt, ein regulärer Ausdruck wird zur größtmöglichen Übereinstimmung aufgelöst. Da dieses Verhalten jedoch nicht immer so gewollt ist, lassen sich bei vielen neueren Implementierungen Quantoren als „genügsam“ oder „zurückhaltend“ (englisch non-greedy, reluctant) deklarieren. Zum Beispiel wird in Perl hierfür dem Quantor ein Fragezeichen ? nachgestellt. Die Implementierung von genügsamen Quantoren ist vergleichsweise aufwändig (erfordert Backtracking), weshalb nicht alle Implementierungen diese unterstützen.

Beispiel (Perl-Syntax)
Angenommen, es wird der reguläre Ausdruck A.*B auf die Zeichenfolge „ABCDEB“ angewendet, so würde er sie komplett als „ABCDEB“ finden. Mit Hilfe des „non-greedy“-Quantors „*?“ matcht der nun modifizierte Ausdruck – also A.*?B – nur die Zeichenkette „AB“, bricht also die Suche nach dem ersten gefundenen „B“ ab. Ein gleichwertiger regulärer Ausdruck für Interpreter, die diesen Quantor nicht unterstützen, wäre A[^B]*B.
QF1 Die Zeichen ^ und $ matchen im multiline-Modus, also wenn der m-Modifier gesetzt wird, auch Zeilenanfänge und -enden.

Possessives Verhalten[Bearbeiten]

Eine Variante des oben beschriebenen gierigen Verhaltens ist das possessive Matching. Da hierbei jedoch das Backtracking verhindert wird, werden einmal übereinstimmende Zeichen nicht wieder freigegeben. Aufgrund dessen finden sich in der Literatur auch die synonymen Bezeichnungen atomic grouping, independent subexpression oder non-backtracking subpattern. Die Syntax für diese Konstrukte variiert bei den verschiedenen Programmiersprachen. Ursprünglich wurden solche Teilausdrücke (Subpattern) in Perl durch (?>Ausdruck) formuliert. Daneben existieren seit Perl 5.10 die äquivalenten, in Java bereits üblichen possessiven Quantoren ++, *+, ?+ und {min,max}+.

Beispiel
Angenommen es wird auf die Zeichenfolge „ABCDEB“ der reguläre Ausdruck A.*+B angewendet, so würde er keine Übereinstimmung finden. Bei der Abarbeitung des regulären Ausdrucks würde der Teil .*+ bis zum Ende der Zeichenkette übereinstimmen. Um jedoch den gesamten Ausdruck zu matchen, müsste ein Zeichen – hier also das „B“ – wieder freigegeben werden. Der possessive Quantor verbietet dies aufgrund des unterdrückten Backtrackings, weshalb keine erfolgreiche Übereinstimmung gefunden werden kann.

Gruppierungen und Rückwärtsreferenzen[Bearbeiten]

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

Einige Implementierungen speichern die gefundenen Übereinstimmungen von Gruppierungen ab und ermöglichen deren Wiederverwendung im regulären Ausdruck oder bei der Textersetzung. Diese werden Rückwärtsreferenzen (englisch back references) genannt. Häufig wird dazu die Schreibweise \n oder $n verwendet, wobei n die Übereinstimmung der n-ten Gruppierung entspricht. Eine Sonderstellung stellt dabei n=0 dar, das meist für die Übereinstimmung des gesamten regulären Ausdrucks steht.

Beispiel
Ein Suchen und Ersetzen mit AA(.*?)BB als regulärem Suchausdruck und \1 als Ersetzung ersetzt alle Zeichenketten, die von AA und BB eingeschlossen sind, durch den zwischen AA und BB enthaltenen Text. Das heißt AA und BB und der Text dazwischen werden ersetzt durch den Text, der ursprünglich zwischen AA und BB stand, also fehlen AA und BB im Ergebnis.

Interpreter 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 zeigen, dass ein regulärer Ausdruck, der feststellt, ob in einer Zeichenkette vor und nach der 1 die gleiche Anzahl von 0 steht, keine reguläre Sprache ist.

Daneben gibt es auch noch Gruppierungen, die keine Rückwärtsreferenz erzeugen (englisch non-capturing). Die Syntax dafür lautet in den meisten Implementierungen (?:). Regexp-Dokumentationen weisen darauf hin, dass die Erzeugung von Rückwärtsreferenzen stets vermieden werden soll, wenn kein späterer Zugriff auf sie erfolge. Denn die Erzeugung der Referenzen kostet Ausführungszeit und belegt Platz zur Speicherung der gefundenen Übereinstimmung. Zudem lassen die Implementationen nur eine begrenzte Anzahl an Rückwärtsreferenzen zu (häufig nur maximal 9).

Beispiel

Mit dem regulären Ausdruck „\d+(?:-\d+)*“ können Folgen von durch Bindestriche getrennten Zahlenfolgen gefunden werden, ohne dabei die letzte durch einen Bindestrich getrennte Zahlenfolge als Rückreferenz zu erhalten.

Alternativen[Bearbeiten]

Man kann alternative Ausdrücke mit dem „|“-Symbol zulassen.

Beispiel
ABC|abc“ bedeutet „ABC“ oder „abc“, aber z. B. nicht „Abc“.

Weitere Zeichen[Bearbeiten]

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, wobei bei manchen Implementierungen noch ein „\n“ folgen darf. Das tatsächliche Ende wird von \z gematcht.
\ hebt gegebenenfalls die Metabedeutung des nächsten Zeichens auf (siehe Maskierungszeichen). Beispielsweise lässt der Ausdruck „(A\*)+“ die Zeichenketten „A*“, „A*A*“, usw. zu. Auf diese Weise lässt sich auch ein Punkt „.“ mit „\.“ suchen, während nach „\“ mit „\\“ gesucht wird.
\b leere Zeichenkette am Wortanfang oder am Wortende
\B leere Zeichenkette, die nicht den Anfang oder das Ende eines Wortes bildet
\< leere Zeichenkette am Wortanfang
\> leere Zeichenkette am Wortende
\n ein Zeilenumbruch im Unix-Format
\r ein Zeilenumbruch im Mac-Format
\r\n ein Zeilenumbruch im Windows-Format
Beispiel 
[^ ]$“ bedeutet: die Zeichenkette muss aus mindestens einem Zeichen bestehen und das letzte Zeichen darf kein Leerzeichen sein.

Look-around assertions[Bearbeiten]

Perl Version 5 führte zusätzlich zu den üblichen regulären Ausdrücken auch look-ahead und look-behind assertions (etwa „vorausschauende“ bzw. „nach hinten schauende“ Annahmen/Behauptungen) ein, was unter dem Begriff look-around assertions zusammengefasst wird.[6] Diese Konstrukte erweitern die regulären Ausdrücke um die Möglichkeit, kontextsensitive Bedingungen zu formulieren, ohne den Kontext selbst zu matchen. Das heißt, möchte man alle Zeichenfolgen „Sport“ matchen, denen die Zeichenfolge „verein“ folgt, ohne dass jedoch die gematchte Zeichenfolge die Zeichenfolge „verein“ selbst enthält, wäre dies mit einer look-ahead assertion möglich: Sport(?=verein). Im Beispielsatz „Ein Sportler betreibt Sport im Sportverein.“ würde jener reguläre Ausdruck also nur das letzte Vorkommnis von „Sport“ matchen, da nur diesem die Zeichenfolge „verein“ folgt; er würde jedoch nicht die komplette Teilzeichenkette „Sportverein“ matchen.

Aufgrund der Eigenschaft, dass der angegebene Kontext (im Beispiel „verein“) zwar angegeben wird, jedoch kein expliziter Bestandteil der gematchten Zeichenkette (hier „Sport“) ist, wird im Zusammenhang mit assertions meist das Attribut zero-width mitgenannt. Die vollständigen Bezeichnungen lauten somit – je nachdem ob ein bestimmter Kontext gefordert (positiv) oder verboten (negativ) ist – zero-width positive/negative look-ahead/behind assertions. Die Bezeichnungen der Richtungen rühren daher, dass Regexp-Parser eine Zeichenkette immer von links nach rechts abarbeiten.

Definition Bezeichnung Erklärung Schreibweise
(?=Ausdruck) positive look-ahead assertion Ausdruck muss auf vorgenannten Ausdruck folgen Ausdruck(?=Ausdruck)
(?!Ausdruck) negative look-ahead assertion Ausdruck darf nicht auf vorgenannten Ausdruck folgen Ausdruck(?!Ausdruck)
(?<=Ausdruck) positive look-behind assertion Ausdruck muss nachfolgendem Ausdruck vorausgehen (?<=Ausdruck)Ausdruck
(?<!Ausdruck) negative look-behind assertion Ausdruck darf nachfolgendem Ausdruck nicht vorausgehen (?<!Ausdruck)Ausdruck

Look-arounds werden nicht nur von Perl und PCRE, sondern unter anderem auch von Java, .NET und Python unterstützt. Auch einige Texteditoren wie zum Beispiel Vim bieten die Möglichkeit, wenn auch mit teilweise anderer Syntax.

Beispiel 
\s(?=EUR)“ steht für ein Whitespace-Zeichen, dem die Zeichenkette „EUR“ folgt. Im Gegensatz zu „\sEUR“ gehört hier „EUR“ nicht zu einer gematchten Zeichenkette.

Bedingte Ausdrücke[Bearbeiten]

Relativ wenig verbreitet sind bedingte Ausdrücke. Diese sind unter anderem in Perl, PCRE und dem .NET-Framework einsetzbar. Python bietet für solche Ausdrücke im Zusammenhang mit look-around assertions nur eingeschränkte Funktionalität.[7]

(?(Bedingung)wahr-Ausdruck|falsch-Ausdruck) Wenn der gegebene Ausdruck „Bedingung“ gefunden wird, kommt der „wahr-Ausdruck“ zur Anwendung. Wenn der Suchausdruck nicht gefunden werden kann, kommt der „falsch-Ausdruck“ zur Anwendung.
Beispiel
Mit dem Ausdruck (\()?\d+(?(1)\)) werden Zeichenfolgen wie „1“, „(2)“, „34“ oder „(567)“, aber nicht „3)“ gefunden.

Literatur[Bearbeiten]

Reguläre Ausdrücke

Reguläre Ausdrücke und natürliche Sprachen

  • Kenneth R. Beesley, Lauri Karttunen: Finite-State Morphology. Distributed for the Center for the Study of Language and Information. 2003, 696 p. (est.). 2003 Series: (CSLI-SCL) Studies in Computational Linguistics.

Reguläre Ausdrücke und Automatentheorie

  • Jan Lunze: Ereignisdiskrete Systeme. Oldenbourg, 2006, ISBN 3-486-58071-X, S. 160–192.

Forschungsliteratur

  • Stephen C. Kleene: Representation of Events in Nerve Nets and Finite Automata. In: Claude E. Shannon, John McCarthy (Hrsg.): Automata Studies. Princeton University Press, 1956, S. 3–42.

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1.  Stephen C. Kleene: Representation of Events in Nerve Nets and Finite Automata. In: Claude E. Shannon, John McCarthy (Hrsg.): Automata Studies. Princeton University Press, 1956.
  2.  John E. Hopcroft, Jeffry D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Addison Wesley, Bonn 1994, ISBN 3-89319-744-3.
  3. POSIX-Spezifikationen
  4. HTML Codes – Characters and symbols, [1]
  5. The Open Group Base Specifications, RE Bracket Expression, IEEE Std 1003.1, 2004
  6. Regular-Expressions.info: Lookahead and Lookbehind Zero-Width Assertions
  7. Regular-Expressions.info: If-Then-Else Conditionals in Regular Expressions