Die regulären Ausdrücke (ITG/slu)

1. Einführung

Das Konzept der regulären Ausdrück (abgekürzt „RA“ oder „RE“ für engl. Regular Expressions) ist ein System zur variablen bzw. vereinfachten Beschreibung von Zeichenketten („strings“). Sie werden praktisch ausschließlich zum Auffinden von Zeichenketten in Textdokumenten verwendet. Als ihr „Erfinder“ gilt der amerikanische Mathematiker Stephen Cole Kleene (1909-1994). Ursprünglich aus dem Bereich der Informatik bzw. der Programmierung stammend, sind die regulären Ausdrücke auch im Umfeld der Korpuslinguistik von großem Nutzen.

Ein kleines Beispiel kann Funktionsweise und Vorteile ihres Einsatzes illustrieren. Angenommen, man möchte in einem Text die beiden Wörter „Band“ und „Bund“ finden. Ohne die Verwendung von regulären Ausdrücken müsste man, nach einander, zunächst nach dem Wort „Band“ und anschließend nach dem Wort „Bund“ suchen:

Finde "Band" in Text
Finde "Bund" in Text

Beim Einsatz regulärer Ausdrücke wäre diese Aufgabe mit einer einzigen Suchaktion zu erledigen, nämlich folgendermaßen:

Finde "B[au]nd" in Text

Die eckigen Klammern bezeichnen eine sogenannte Zeichenklasse, die in der Weise zu interpretieren ist, dass innerhalb der Klammern aufgeführten Zeichen als Alternativen zu verstehen sind. Im gegebenen Beispiel wäre also paraphrasiert zu lesen: Find ein großes B, gefolgt von entweder einem a oder einem u, gefolgt von einem n, gefolgt von einem d.

Das Konzept der Regulären Ausdrücke ist in einer Vielzahl von Softwareprodukten  implementiert. Nicht selten gibt es dabei anwendungsspezifische Besonderheiten und Erweiterungen des Basiskonzepts der Regulären Ausdrücke. 

2. Literale und Metazeichen

Das Konzept der REs unterscheidet zwischen Literalen und Metazeichen. Literale stehen jeweils für sich selbst, Metazeichen haben Sonderbedeutung. Die wichtigsten Metazeichen lauten wie folgt:

Platzhalter:
. (Punkt) für "ein beliebiges Zeichen"

Zeichenklassen (jeweils genau ein Zeichen aus dem angegebenen Bereich):
[A-Z], [A-Za-z], [A-Za-zäöüßÄÖÜ][0-9] usw. - Grundlage ist die ASCII-Tabelle

Negation:
[^0-9] -> keine Ziffer [^\t-~] -> keine ASCII-Zeichen

Kontextoperatoren: 
^ (Anfang von String) - außerhalb eckiger Klammern! Sonst: Negation!
$ (Ende von String)

Wiederholungsoperatoren (beziehen sich jeweils auf das unmittelbar vorangehende Literal 
(oder Zeichenklasse):
* -> 0-n Wiederholungen (greedy; s. unten)
\{-} -> 0-n Wiederholungen (non greedy: as few as possible; vim-spezifisch)
+ -> 1-n Wiederolungen (vim: \+)
? -> 0 oder 1 Vorkommen (vim: \=)
{m,n} -> mindestens m Vorkommen, maximal n Vorkommen 
    Beispiele: o{1,2} = mindestens ein "o", maximal zwei "o"; o{,3} = maximal drei "o"

Um Metazeichen in Literale zu verwandeln, müssen ihnen Backslashes vorangestellt werden (sog. Maskierung): Der RE \[Haus\] „matcht“ den String „Haus“ zwischen eckigen Klammern, also [Haus]. Ohne die Maskierung würde es sich um eine Zeichenklasse, bestehend aus den Zeichen „H“, „a“, „u“ und „s“ handeln.

3. Greediness

Bei Wiederholungsoperatoren, die 0-n oder 1-n Wiederholungen beschreiben, spielt die „Greediness“ („Gierigkeit“) eine Rolle.

Beispiel: Man möchte in einem XML-Dokument die sog. Tags, also die mit < beginnenden und mit > endenden Strings „matchen“ (= finden). In natürlicher Sprache würde man formulieren: „Finde einen String, der mit einem < beginnt, daran anschließend eine beliebige Anzahl von beliebigen Zeichen enthält und mit einem > abgeschlossen wird„. In der formalen Sprache der regulären Ausdrücke würde man zunächst scheiben: <.*>. Durch die Greediness von * wird im folgenden Beispiel nicht die schließend spitze Klammer des ersten Tags (<h1>), sondern die des zweiten Tags (</h1>) gematcht:

Greediness von *. Die Farben von Regulärem Ausdruck und String korrespondieren.

Regulärer Ausdruck: <.*>
String:             <h1>Einführung in die Regulären Ausdrücke</h1>

Bei Verwendung eines nicht-„gierigen“ Wiederholungsoperators wird hingegen die schließende spitze Klammer des ersten Tags gematcht. Leider enthält das Basiskonzept der Regulären Ausdrücke keinen nicht-gierigen Wiederholungsoperator. In manchen Implementierungen existieren solche Operatoren jedoch als spezifische Erweiterung. Vim z.B. kennt den nicht-gierigen Wiederholungsoperator \{-}:

Non-Greediness von \{-}. Die Farben von Regulärem Ausdruck und String korrespondieren.

Regulärer Ausdruck: <.\{-}>
String:             <h1>Einführung in die Regulären Ausdrücke</h1>

4. Gruppierung und Backreferencing

    • Die Definition einer Gruppierung erfolgt durch runde Klammern. Im Programm vim müssen diese unter Umständen (im non-magic-mode) durch Baslashes maskiert werden: \(abc\)
    • „Backreferencing“: \([^aeiou]\)\1 (findet alle doppelten Zeichen, außer doppelten Vokalen) – \1 referiert auf die erste durch runde Klammern definierte Gruppe. Bei mehreren Gruppen: \2, \3 …
  • Beispiel: 
    gegeben sei folgender String: b12y

vim-Ersetzungsbefehl (s.u.):

:%s/\([ab]\)12\([xy]\)/\2XX\1/g

Ergebnis: yXXb

    Die Numerierung der Gruppen orientiert sich an der Reihenfolge der Gruppen von links nach rechts.
  • Alternativen angeben durch „|“ (sog. „pipe“):
[aeiou]\|[3-8]

Findet entweder einen Vokal oder eine Ziffer zwischen 3 und 8; die Maskierung der Pipe durch \ ist in vim erforderlich

  • Suche über Zeilengrenzen hinweg: Einbeziehung der Zeilenendkodierung in das Muster: \n; evtl. vorübergehende Tilgung *aller* Zeilenenden, um nach Muster zu suchen, anschließend über u („undo“; vim!) zurück zum „status quo ante“.

ACHTUNG: Teile der hier vorgeführten RE-Syntax sind vim-spezifisch!

4.0.1. Vim

  • Vim kann bei Suchen Groß- und Kleinschreibung berücksichtigen (:se noignorecase) oder auch nicht (:se ignorecase). Die entsprechende Einstellung beeinflusst auch die Suche nach regulären Ausdrücken. Bei Einstellung :se ignorecase „matcht“ der RE „Haus“ auch den String „HAUS“.
  • Besonderheiten der Regex-„Engine“ von vim (Dokumentation in vim -> :he 27 und :he 27.4 [Matching multiple times]; außerdem: http://www.softpanorama.org/Editors/Vimorama/vim_regular_expressions.shtml)
  • Kommando :nohl („no highlighting“ -> entfernt farbige Hervorhebung der gefundenen Muster)
  • Sammlung verschiedener REs in vim-Syntax: http://vim.wikia.com/wiki/Search_patterns

5. Nützliche REs

5.1. Berücksichtigung von Zeilenanfang und -ende

Suche nach „ein“ am Anfang, Ende oder in der Zeile: 

[ \n]\+ein[\n ]\+

5.2. Leere Zeilen

^$

5.3. Leere Zeilen mit Whitespace-Characters (Leerzeichen und Tabulatoren)

^[ \t]*$ oder ^\s*$ (\s ist Kürzel für Whitespace-Character)

5.4. Löschen leerer Zeilen mit Whitespace-Characters in Vim

:%s/^\s*$\n//gc

5.5. Beschreibung von Wiederholungen (VIM-Syntax)

  • Buchstabendoppelungen (mm, nn etc.)

\([a-zA-Z]\)\1
  • Wortwiederholungen (die die) [Achtung: Leerzeichen am Beginn!]

 \([^ ]\+\)\_s\+\1
  • Wiederholung von Wortgruppen

\(.\+\)[\_s\n]\+\1

5.6. XML-Tags (VIM-Syntax; zeilenübergreifend)

<\_.\{-}> 

Der Operator \_.  steht für „any character including a newline“, \{-} ist der, ebenfalls vim-spezifische, nicht-„gierige“ (non greedy) Operator für 0-n Wiederholungen.

5.7. Bestimmte Artikel im Deutschen

der – die – das | des – der – des | dem – der – dem | den – die – das (nur Singular)

d[eia][resmn]
nn@pcxyz:~$ echo d{e,i,a}{r,e,s,m,n}
der dee des dem den dir die dis dim din dar dae das dam dan

Unter folgender Adresse ist ein Test für reguläre Ausdrücke verfügbar:

https://regex101.com/

Zu Besonderheiten im Umgang mit REs in MySQL s. den Beitrag „Reguläre Ausdrücke (RAs) in MySQL (ITG/slu)

6. Nützliche Links

Einführung in die RAs von Stefanie Schneider (MAX)

https://regex101.com/

Schreibe einen Kommentar