Kapitel 2. Grundlagen

Reguläre Ausdrücke

Reguläre Ausdrücke (Regular Expressions, REs) wurden von 1956 Stephen Cole Kleene eingeführt und sie erwiesen sich als sehr effektiv, um Zeichenketten zu beschreiben.

REs werden dann verwendet, wenn man die Form einer Zeichenkette (String) angeben will; sie beschreiben also Klassen von Strings. Es ist zum Beispiel einfacher die natürlichen Zahlen als "eine Zeichenkette, bestehend aus einer oder mehreren Ziffern aus der Menge {0,1,2,3,4,5,6,7,8,9}" zu definieren, als alle Zahlen von 0 bis unendlich aufzuzählen. Mit Hilfe von Regulären Ausdrücken kann man solche Klassen von Strings eindeutig beschreiben.

Man sagt eine RE passt auf eine Zeichenkette, wenn diese in der von der RE umrissenen Klasse enthalten ist. Häufig werden REs verwendet, um aus einem String einen Teilstring heraus zu picken, welcher von der RE beschrieben ist. Dabei gilt das Prinzip der längsten Übereinstimmung (longest match), was heißen soll dass dies der längste Teilstring ist, auf den die RE passt. In diesem Zusammenhang spricht man auch davon, REs sind gefräßig (greedy).

Tabelle 2.1. Erweiterte Reguläre Ausdrücke (Extended Regular Expressions)

Regulärer AusdruckErklärung
xdas Zeichen 'x'
\xEscape: wenn das Zeichen nach dem \ eines eines der folgenden ist: {a, b, f, n, r, t, v} dann wird es als Spezielles Zeichen gemäß ANSI C interpretiert. Zum Beispiel '\n' für einen Zeilenumbruch. Jedes andere x verliert seine Sonderbedeutung (falls es eine hat) und wird als einfaches Zeichen interpretiert, z.B. \* wird als Stern interpretiert und nicht als Quantifikator.
\123das Zeichen mit oktalem ASCII-Code 123
\xe5das Zeichen mit hexadezimalem ASCII-Code e5
.jedes beliebige Zeichen außer \n (newline)
[xyz]eine "character class": x ODER y ODER z
[ako-sP]eine "character class" mit einer Bereichsangabe, also a ODER k ODER ein Character aus dem Bereich o BIS s ODER P
[^x-z]eine "negated character class": Jedes Zeichen außer x bis z
(r)die RE r selber
rsdie RE r gefolgt von der RE s
r|sdie RE r ODER die RE s
r*die RE r null oder mehrere male
r+die RE r ein oder mehrere male
r?die RE r null oder ein mal
r{2,6}die RE r zwei bis sechs mal
r{2,}die RE r zwei oder mehrere male
r{,6}die RE r null bis sechs mal
r{4}die RE r genau vier mal
^rdie RE r am Anfang der Zeile
r$die RE r am Ende der Zeile
[:str:]mit str eine der folgenden Bezeichner: alnum, alpha, blank, cntrl, digit, graph, lower, print, punct, space, upper, xdigit dann die betreffende Charakterklasse. Siehe ctype(3) für Details.


Für detailliertere Informationen siehe die man-page regex(7) oder, falls nicht vorhanden die man-page zu awk(1), welche lange Zeit auch als die Referenz für REs galt, oder flex(1) oder die Online-Dokumentation der Open Group.

Basic Regular Expressions

sed verwendet Basic Regular Expressions, eine Art Untermenge der oben vorgestellten Erweiterten Regulären Ausdrücke. Die Unterschiede zu den Erweiterten Regulären Ausdrücken sind:

  • Die Quantifikatoren '|', '+' und '?' sind normale Zeichen, und es gibt keine äquivalenten Operatoren dafür. GNU sed kennt diese Operatoren, wenn sie durch einen vorangestellten Backslash "escaped" werden.

  • Die geschwungenen Klammern sind normale Zeichen, und müssen mit Backslashs "escaped" werden, werden also als '\{' und '\}' geschrieben. Das selbe gilt für runde Klammern; die Zeichen, die durch '\(' und '\)' eingeschlossen werden, können später mit '\1' usw. dereferenziert werden.

  • '^' ist ein normales Zeichen, wenn es nicht am Beginn einer Zeile oder eines Klammerausdrucks steht.

  • '$' ist ein normales Zeichen, wenn es nicht am Ende einer Zeile oder eines Klammerausdrucks steht.

  • '*' ist ein normales Zeichen am Beginn einer Zeile oder eines Klammerausdrucks.

Reguläre Beispiele

Die Menge der Natürlichen Zahlen kann man mit einer Basic Regular Expression wie folgt umschreiben: '[0-9][0-9]*'. Die einfachere RE '[0-9]*' passt zwar auch auf die natürlichen Zahlen, aber auch auf einen leeren String der keine Ziffer enthält: der Quantifikator '*' steht für null oder mehrere male. Die Bereichsklasse '[0-9]' hätte auch als '[[:digit:]]' geschrieben werden können und mit Extended REs kann man ein paar Zeichen sparen indem man den '+'-Quantifikator verwendet: '[0-9]+'.

Hier ein berühmtes Shakespearezitat in Nerd-Schreibweise:

(bb|[^b]{2})

Diese RE passt auf Strings, die entweder aus zwei 'b' bestehen oder aus zwei Zeichen verschieden von 'b'. Auf Englisch liest sich das in etwa als "two b or not two b" (sprich: to be or not to be).

Streng genommen liest sich die RE '(bb|[^b]{2})' als "two b or two not b". Gönnen wir uns die dichterische Freiheit und lassen die RE trotzdem als Shakespearezitat durchgehen.

Tipp

Eine Reihe von Programmen helfen die ersten Experimente mit Regulären Ausdrücken zu erleichtern. pcretest (enthalten in der PCRE library) ist eines davon, oder kregexpeditor, mit grafischer Benutzeroberfläche für KDE. Aber es geht auch einfach mit sed. Das folgende Script-Gerüst schreibt alle Zeilen, auf die ein Regulärer Ausdruck passen, auf den Bildschirm (der String 'RE' muss durch den gewünschten Regulären Ausdruck ersetzt werden):

sed -ne '/RE/p'

Wenn man 'interaktiv' mit sed arbeitet, also wenn Ein- und Ausgabe mit Tastatur und Bildschirm erfolgen (so wie im obigen Beispiel) dann sieht man sowohl Eingabe als auch Ausgabe auf dem Bildschirm. Das bedeutet, dass Zeilen, die nicht auf die RE passen, einmal am Bildschirm auftauchen (als Eingabe). Zeilen die hingegen auf die RE passen, erscheinen zweimal (einmal als Eingabe, einmal als Ausgabe).

Das folgende Beispiel schreibt alle Zeilen mit mindestens einer Ziffer auf den Bildschirm:

sed -ne '/[0-9]/p'

Dieses Beispiel schreibt alle Zeilen die den String "Rumpelstilzchen" enthalten auf den Bildschirm:

sed -ne '/Rumpelstilzchen/p'

Tipp

sed kennt nur Basic Regular Expressions, aber das weit verbreitete GNU sed ist in der Lage, Extended REs auszuführen, wenn man die Option '-r' angibt.

Reguläre Ausdrücke sind sehr flexibel und sehr oft kann man ein gewünschtes Ergebnis auf mehreren verschiedenen Wegen erreichen. So ist zum Beispiel die Extended RE '(x|y|z)' äquivalent zu '[xyz]' und '(a|b)' ist äquivalent zu '(b|a)'.

Die RE '[FB]all' passt sowohl auf "Fall" als auch auf "Ball". Das selbe Ergebnis könnte mit einer Extended RE zum Beispiel auch so erreicht werden: '(F|B)al{2}'.

Die RE '^#.*' passt auf alle Zeilen, die mit einem '#' anfangen. Ist die deutlich kürzere RE '^#' äquivalent zur vorhergehenden? Zur reinen Mustersuche passen beide REs auf die selben Zeilen, der Unterschied kommt dann zu Tage, wenn man die gefundenen Muster weiterverarbeiten will. Erstere RE benennt die ganze Zeile, vom Beginn bis zum newline, zweitere benennt nur das Zeichen '#' am Anfang der Zeile.

Grenzen von REs

Mit REs lassen sich nicht alle Zeichenketten beschreiben. Es ist zum Beispiel unmöglich ein System von balancierten Klammern zu beschreiben, auch ist die Menge {wcw | w ist ein String bestehend aus 'a's und 'b's} als RE nicht auszudrücken. Mehr zu REs kann man im 'Drachenbuch', Compilers - Principles, Techniques and Tools von Aho, Sethi und Ullman nachlesen.

REs können sehr schnell unleserlich werden. Eine Gleitkommazahl wie 3.675E-15 kann man mit '[[:digit:]]+\.[[:digit:]]*([eE][+-]?[[:digit:]]+)?' beschreiben. Zu beachten ist der Backslash '\' vor dem Punkt, da jener eine Sonderbedeutung hat, die mit dem vorangestellten '\' unterbunden wird. Leider hat diese Beschreibung einen Nachteil: sie passt zwar auf die Zahl '1.', aber nicht auf die Zahl '.1', also noch einmal: '(([[:digit:]]+\.[[:digit:]]*)|(\.[[:digit:]]+))([eE][+-]?[[:digit:]]+)?' Wie man sieht, werden REs schnell unübersichtlich. Das Chaos wird in Verbindung mit sed und bash perfekt, da sich noch viele lustige '\' und '/' hinzugesellen werden. Dazu aber später.