| W. Wiedl Skripte CGI & Perl Reguläre Ausdrücke | Inhaltsverzeichnis < Suche |
Reguläre Ausdrücke stehen in vielen Sprachen bzw. Programmen zur Verfügung, werden aber nicht immer gleich gehandhabt. Hier beschränken wir uns auf Perl, wo es im wesentlichen drei Funktionen bzw. Operatoren zum Umgang mit regulären Ausdrücken gibt, die allerdings je nach Kontext, in dem sie aufgerufen werden, und je nach verwendeten Modifiern, auf die wir noch eingehen werden, sehr unterschiedlich wirken können.
Wegen der Eigenschaft, möglichst immer die maximal mögliche Anzahl der Treffer im Suchtext zu beanspruchen, nennt man die Quantifier und die Elemente mit solchen Quantifiern gierig.
Perl kennt zu jedem gierigen Quantifier auch eine genügsame Variante, die jeweils durch ein angehängtes Fragezeichen gekennzeichnet wird:
Der oben angegebene regulären Ausdruck besteht aus einer Kette von 7 Elementen. Der Reihe nach sind dies \d, \d, \.,
\d, \d, \., \d{2,4}. Jedes Element gibt ein Zeichen oder eine Zeichenfolge im
Muster vor. Die Kette der Elemente gibt eine Zeichenfolge vor, die sich aus der
Verkettung dieser Zeichen oder Zeichenfolgen ergibt.
Bei der Mustersuche sucht das Element \d nach einer Dezimalziffer im
Suchtext. Die Elementen-Kette \d\d\. sucht nach drei aufeinander folgenden
Zeichen, wovon die beiden ersten Dezimalziffern, das dritte ein Punkt ist. Wenn
eine solche Zeichenfolge gefunden wird, nennen wir sie Treffer und sprechen davon, dass der reguläre Ausdruck auf den
Suchtext passt.
Der angegebene reguläre Ausdruck stellt keinerlei Bedingungen bezüglich der
Position oder der vorangehenden bzw. nachfolgenden Zeichen im Suchtext. Er passt
daher auf beide folgenden Suchtexte:
geboren am 10.02.1898 in
Augsburg
die Code-Nummer ist 219.83.712365
Im ersten wird
der Treffer 10.02.1898, im zweiten der Treffer
19.83.7123 gefunden. Beachten Sie insbesondere, dass der
Quantifier {2,4} zwar die Zahl der Dezimalziffern im Treffer von \d{2,4} auf 4
begrenzt, aber nicht ausschließt, dass dieser Treffer in einer längeren
Ziffernfolge auftritt, etwa in 712365.
Die Komplementärmenge zu den literalen Zeichen wird von den Metazeichen gebildet. Metazeichen sind:
\
. ( ) [ ] { } ^ $
? * + |
Ein einzelnes Metazeichen kann ein Element eines regulären Ausdruckes bilden, dieses Element sucht dann aber nicht nach genau diesem Zeichen im Suchtext, es hat eine andere Bedeutung. Ein Beispiel dafür ist der Punkt. Ein Punkt ist ein atomares Element, dessen Bedeutung von einer Reihe von Gegebenheiten abhängt, in der Regel aber nach irgendeinem Zeichen sucht, das vom Zeichen für 'Zeilenumbruch', also "\n" verschieden ist.
Andere Metazeichen bilden alleine nie ein Element. Ein Beispiel dafür ist der Backslash \. Ein einzelner Backslash bildet immer mit dem nachfolgenden Zeichen zusammen ein Element.
Ein literales Zeichen verliert hinter einem Backslash seine literale Eigenschaft und bildet meist zusammen mit dem Backslash ein Element. So sucht ein Element 'd', das nicht hinter einem Backslash steht, nach einem Zeichen 'd' im Suchtext, aber das Element '\d' sucht nach einer Dezimalziffer.
Allgemein bezeichnen wir eine durch ein Backslash eingeleitete Zeichenfolge, die im jeweiligen Kontext eine Einheit bildet, als Escape-Sequenz . Die Escape-Sequenz '\n' bezeichnet in einem regulären Ausdruck eine Element, in einem "-begrenzten String ein Zeichen. Das Element '\n' im regulären Ausdruck sucht nach einem Zeichen "\n" im Suchtext. In einem '-begrenzten String kann man das Zeichen "\n" nicht bezeichnen, da dort nur die Escape-Sequenzen "\\" und "\'" ausgewertet werden.
Ein Zeichen, das alleine stehend ein nicht-literales Zeichen ist, erhält dagegen durch einen vorangestellten Backslash seine literale Bedeutung zurück. So sucht "\." nach einem "." während das Element "." in der Regel auf jedes Zeichen ausser "\n" passtt. "\\" sucht nach einem einzelnen Backslash-Zeichen im Suchtext und analoges gilt für jedes Metazeichen hinter einem "\".
Da es nicht nur Escape-Sequenzen der Länge 2 gibt, ist das Lesen von regulären Ausdrücken nicht immer einfach. Man muss erkennen, dass die Sequenz '\\\n' zwei Elemente '\\' und '\n' beschreibt, die nach je einem Zeichen '\' bzw. "\n" suchen.
In einem Perl-Programm muss man irgendwie Anfang und Ende eines regulären
Ausdruckes markieren. Man verwendet dazu Zeichen, die man als Begrenzer bezeichnet, zumeist /. Die
Begrenzer gehören selbst nicht mehr zum regulären Ausdruck.
Aus
naheliegenden Gründen kann man die Begrenzer-Zeichen im regulären Ausdruck nicht
als literale Zeichen verwenden, man muss sie dort wie die Metazeichen durch
einen vorangestellten Backslash maskieren.
Wenn wir einen regulären Ausdruck schreiben wollen, der nach der Zeichenfolge
'/usr/bin/vi' im Suchtext sucht und als Begrenzer die äblichen Slashes /
verwenden, so müssen wir den regulären Ausdruck (mit Begrenzern) wie folgt
formulieren:
/\/usr\/bin\/vi/
Die Begrenzer-Zeichen
sind jedoch keine Metazeichen.
Zeichenklassen mit frei vorgegebenen Treffermengen definiert man in der Form
[_] , wobei innerhalb der Klammern, die
Zeichen der Treffermenge aufgelistet werden. Das erste Zeichen der Liste darf
kein Caret-Zeichen sein, da mit [^_]
eine Zeichenklasse beschrieben wird, die alle Zeichen umfasst, die in der
Komplementärmenge der aufgelisteten Zeichen liegen. Die Zeichen der Treffermenge
bzw. der Komplementärmenge werden dabei innerhalb der Klammerung ohne Trenner
hintereinander aufgelistet, die Reihenfolge ist im Prinzip ohne Bedeutung.
Wenn man die codeabhängige Reihenfolge der Zeichen kennt, kann man mit Hilfe
des Bindestriches auch Zeichenbereiche
angeben, die Zeichenklasse [A-E] ist ä,quivalent zur Zeichenklasse [ABCDE].
Zeichenklassen der Form [^...] nennt man negierte Zeichenklassen, Zeichenklassen der
Form [_] werden gelegentlich positive
Zeichenklassen genannt.
Suchtext =~ m/regulärer Ausdruck/
mit dem Bindungs-Operator =~, dem Mustersuche-Operator m/.../ und den Begrenzern /, die Anfang und Ende des regulären Ausdruckes markieren, selbst aber nicht mehr zu ihm gehören.
Der Suchtext kann als Ausdruck angegeben
werden, dessen Auswertung eine Zeichenkette liefert.
sprintf("%5.2d",(25/30)*100) =~ m/^[89]\d\./;
Gesucht wird hier im
Suchtextes nach einem Muster, das mit einer 8 oder 9 beginnt und mit einer
weiteren Ziffer und einem Punkt fortgesetzt wird. Wird bei der Mustersuche kein
Suchtext angegeben, so wird per Default der Wert der Variablen $_ verwendet.
Der reguläre Ausdruck kann mit Hilfe von Variablen angegeben werden, diese werden ausgewertet und als String in die Definition des regulären Ausdrucks äbernommen.
Die Operation liefert einen Wert, der vom Kontext abhängig ist, in jedem Falle aber eine Interpretation als "wahr" oder "falsch" zulässt. "wahr", wenn das Muster im Suchtext gefunden wird, "falsch" anderenfalls.
Skalarer Kontext liegt z.B. in den
beiden folgenden Fällen vor:
$wieoft = $Suchtext =~ m/regulärer
Ausdruck/;
if ( $Suchtext =~ m/regulärer Ausdruck/ )
Das
Ergebnis ist jeweils 0 oder 1, was im Boolschen Kontext auch als "falsch" oder "wahr"
interpretiert werden kann. Es wird nur nach dem ersten Treffer im Suchtext
gesucht.
Listen-Kontext liegt in folgenden Fällen
vor:
@Treffer = $Suchtext =~ m/regulärer Ausdruck/g;
sort $Suchtext =~ m/regulärer Ausdruck/g;
print $Suchtext =~
m/regulärer Ausdruck/g;
Der Listen-Kontext ergibt sich aus aus der links stehenden Operation, also der Listen-Zuweisung im ersten Falle und der sort- bzw. print-Operation in den beiden anderen Fällen.
Zusätzlich wird in diesen Beispielen die Mustersuche mit dem /g-Modifier durchgeführt, was im Listen-Kontext bewirkt, dass nach allen Treffern im Suchtext gesucht wird. Was als Ergebnis geliefert wird, hängt noch davon ab, ob im regulären Ausdruck Klammern der Form ( ... ) auftreten oder nicht, ist das nicht der Fall, so werden genau alle gefundenen Treffer als Ergebnis geliefert.
Beispiel 1.1:Eine typische Anwendung der Mustersuche ist die Ausgabe aller Zeilen einer Datei, die ein bestimmtes Muster aufweisen. Für diese spezielle Aufgabe gibt es auch eine spezielle Operation: grep, auf die wir später noch eingehen werden, im Moment wollen wir unser Problem mit einfacher Mustersuche lösen.Das Muster werde gegeben durch: $Muster = ' \d{1,2}\.\d{1,2}\.\d{2} ' Beachten Sie, dass das Muster mit einem Element ' ' beginnt und endet. Leerstellen sind literale Zeichen. Wir suchen also nach einer Zeichenkette, die mit einer Leerstelle beginnt und mit einer, besser 2 Dezimalziffern und einem Punkt fortgesetzt wird. Dahinter sollen abermals eine, besser zwei Dezimalziffern und ein Punkt folgen, dahinter sollen dann genau zwei Dezimalziffern und eine Leerstelle folgen. Da Zeilenende durch ein Zeichen 'neue Zeile' angezeigt wird, muss dieses Muster vollständig in einer Zeile enthalten sein. Beachten Sie auch, dass der reguläre Ausdruck in der Mustersuche durch einen Variablenwert angegeben werden kann. #!/usr/bin/perl -w open(DAT,'Pfadname') || die 'Datei laesst sich nicht lesen'; $Muster = ' \d{1,2}\.\d{1,2}\.\d{2} '; print $_ while ( <DAT> =~ m/$Muster/ ); |
Die Mustersuche in Perl wird im dritten Kapitel dieses Textes ausführlich besprochen.
Die Klammerung dient allerdings in Perl nicht nur der Zusammenfassung einer Elementenfolge zu einem komplexen Element, sondern auch zur Abspeicherung des Treffers. Die obigen Ausdrücke beschreiben daher zwar dasselbe Muster, sind aber trotzdem nicht gleichwertig.
Angewandt auf den Suchtext:
$Tx = 'Bert Brecht wurde am
10.02.1898 in Augsburg geboren.';
liefert:
$Erg =
$Tx =~ m/\d{2}\.\d{2}\.\d{4}/;
nur das Ergebnis:
$Erg == 1;
zeigt also an, dass das Muster im Suchtext gefunden
wurde. Dagegen liefert:
$Erg = $Tx =~
m/(\d{2}\.){2}\d{4}/;
die Ergebnisse:
$Erg ==
1;
$1 == 02.
Die Klammern sind einfangende Klammern die die Zeichenfolge, die das geklammerte Element gefunden hat, innerhalb desselben regulären Ausdruckes in Rückwärtsreferenzen der Form \1, \2 usw. zur Verfügung stellt. Ausserhalb der regulären Ausdruckes stehen diese Treffer dann nach einer insgesamt erfolgreichen Mustersuche in den local-Variablen $1, $2 usw. zur Verfügung. Man nennt solche Veränderungen von Variablen, die nicht durch das Ergebnis der Operation hervorgerufen werden, Seiteneffekte. Dabei gelten folgende Regeln:
Beispiel 1.2:Aus einer Log-Datei sollen alle Zeilen mit dem Muster:/^(.)+( GET default\/ida\?)(\w)\3+(\.)$/ herausgefiltert und ausgegeben werden. Die Zeichenkette, die durch die beiden Elemente (\w)\3+ gefunden wird, ist sehr lang, deshalb soll dieses Zeichen nur einmal ausgegeben werden. Bemerkung: Es handelt sich um die Eintraege die der 'code red' Wurm hinterlaesst. while ( <DAT> =~ m/^(.)+( GET default\/ida\?)(\w)\3+(\.)$/ ) { print $1,$2,$3,$4 if $1 ne '' )} |
Eine ausführliche Beschreibung der verschiedenen Klammerungen finden Sie in einem späteren Abschnitt. Ebenso verschieben wir eine genaue Beschreibung der Variablen $1, .. auf später.
Neben den Wortgrenzen gibt es auch Nicht-Wortgrenzen, die mit \B bezeichnet
werden. Beachten Sie, dass die deutschen Umlaute keine \w-Zeichen sind. Im
Suchtext:
$Hlin = "Mit gelben Birnen hänget\n Und voll mit wilden
Rosen";
findet man daher Wortgrenzen vor und nach jeder Leerstelle, vor
und nach dem ä, vor und nach "\n" sowie am Anfang und Ende des Suchtextes. Die
beiden letzten Wortgrenzen ergeben sich daraus, dass ein Suchtext für die Suche
nach Wort- und Nicht-Wortgrenzen vorne und hinten virtuell in \W-Zeichen
eingebettet werden.
Anker sind Elemente die in der Regel nach keinem Zeichen suchen, die Ausnahme
davon sind Lookahead-Konstrukte die wir
im Moment noch nicht betrachten. Diese Anker suchen nach Positionen vor oder
nach Zeichen im Suchtext. Wir wollen zwischen Anker-Positionen zwischen den Zeichen und Zeichen-Positionen unterscheiden, auf denen jeweils
ein Zeichen steht. Die Zählung der Positionen beginnt immer mit 0. Der
Anker-Position 0 folgt die Zeichen-Position 0, dieser die Ankerposition 1. Der
Suchtext endet mit einer Anker-Position, die wir als Textende bezeichnen. Anker-Position 0 wird dementsprechend Textanfang genannt. Anker-Position n und
Zeichen-Position n bilden zusammen die Position n.
In der Perl-Literatur bezeichnet dieser Begriff allerdings häufig auch nur die
Ankerposition.
|M|i|t| |g|e|l|b|e|n| |B|i|r|n|e|n|
00112233445566778899AABBCCDDEEFFGGH
Die Anker-Positionen 0 und H sind
Textanfang und Textende, die Anker-Positionen 0, 3, 4, A, B und H sind
Wortgrenzen, alle anderen Anker-Positionen sind Nicht-Wortgrenzen.
Ein regulärer Ausdruck wie:
/^\w/
ist als Verkettung von 2 Elementen zu lesen, die im Suchtext nacheinander nach Treffern suchen, wobei Element ^ nur auf Anker-Positionen, Element \w nur auf Zeichenpositionen sucht. Die Treffer der beiden Elemente müssen im Suchtext unmittelbar aufeinanderfolgen. Da ^ auf Anker-Position 0 und \w auf Zeichenposition 0 fündig wird, wird insgesamt ein Treffer erzielt.
Quantifier sind bei Ankern nicht sinnvoll, werden aber nicht
beanstandet:
/^{1,2}/
Die Anker ^ und $ machen unter normalen Bedingungen auch nur am Anfang und
Ende des regulären Ausdruckes Sinn. Sie werden aber deshalb innerhalb einer
Elementen-Kette nicht als literale Zeichen interpretiert. Um in einem Suchtext
nach den Zeichen ^ bzw. $ zu suchen, müssen Sie diese maskieren:
$T = 'abc^def$g';
$erg = $T =~ /c\^def\$g/;
Beachten Sie, dass
man mit Hilfe von Ankern, die Anzahl der Zeichen im Suchtext festlegen kann. Die
Mustersuche mit:
/^\w{8}$/
liefert nur dann als
Ergebnis "wahr", wenn der Suchtext genau 8 \w-Zeichen umfasst. (Später werden
wir diese Aussage noch präzisieren, die Frage dabei ist, ist ein
Satzende-Zeichen zusätzlich erlaubt oder nicht?).
Wenn nicht durch spezielle Anker etwas anderes vorgegeben wird, kann der Treffer irgendwo im Suchtext beginnen und enden, muss aber vollständig durch den regulären Ausdruck beschrieben werden. Es ist also nicht möglich, mit nur einer Mustersuche nach zwei Teilmustern zu suchen ohne das Muster der dazwischenliegenden Zeichenkette irgendwie zu beschreiben, was manchmal gar nicht so einfach ist.
Wenn wir in einem Text wie:
Am 10.02.1898 wurde Bert Brecht in
Augsburg geboren.
nach Geburtsdatum, Namen und Geburtsort suchen wollen,
dann müssen wir auch ein oder mehrere Elemente angeben, die den Text zwischen
den drei relevanten Angaben schlucken, also z.B:
$Datum =
'((\d{2}\.){2}\d{4})';
$Fuell = '[a-z ]+';
$Name =
'([A-Z][a-z]+ [A-Z][a-z]+)';
$Ort = '([A-Z][a-z]+)';
m/$Datum$Fuell$Name$Fuell$Ort/;
Wir haben in diesem Falle ein Element
der Form:
$Fuell = [a-z ]+
dafür verwendet und setzen
voraus, dass die folgenden Grossbuchstaben jeweils die gesuchten Angaben
markieren.
Am 10.02.1898 wurde Bert Brecht in Augsburg geboren.
---1111111111.......33333333333....44444444---------
Der reguläre
Ausdruck trifft die Teilkette ab den mit 1 markierten Zeichen, diese werden in
$1 abgespeichert, bis zu den mit 4 markierten Zeichen, diese werden in $4
abgespeichert. Die zweite einfangende Klammer tritt innerhalb der ersten auf,
ihr Treffer wird hier nicht angegeben. Die Zwischenstücke sind durch Punkte
markiert.
Häufig sucht man nach Mustern oder auch Teilmustern, die sich nicht durch
eine Kette von Elementen beschreiben lassen. Nehmen wir an, dass das Geburtsjahr
in unserem Text durch 2 oder 4 Ziffern angegeben sein kann. Mit dem regulären
Ausdruck:
$Datum = '((\d{2}\.){2}\d{2,4})';
$Fuell =
'[a-z ]+';
$Name = '[A-Z][a-z]+ [A-Z][a-z]+';
$Ort =
'[A-Z][a-z]+';
m/$Datum$Fuell$Name$Fuell$Ort/;
kommen wir dem
Problem zwar nahe, lassen aber auch zu, dass das Jahr durch drei Ziffern
beschrieben wird, was wir hier ja , aus welchen Gründen auch immer,
ausschliessen wollen. Brauchbar ist allerdings der reguläre
Ausdruck:
/\d{2}\.\d{2}\.(\d{2}){1,2}$Fuell$Name$Fuell$Ort/
Im Element (\d{2}){1,2} steckt, wie in vielen Quantifiern implizit eine
oder-Verknüpfung.
Eine solche können wir natürlich auch mit Hilfe des externen or-Operators
beschreiben:
$Datum2 = '((\d{2}\.){2}\d{2})';
$Datum4 =
'((\d{2}\.){2}\d{4})';
m/$Datum2$Fuell$Name$Fuell$Ort/
or
/$Datum4$Fuell$Name$Fuell$Ort/;
Man kann sie aber auch direkt im regulären Ausdruck mit Hilfe der oder-Verknüpfung | angeben. Der Ausdruck lautet
dann:
$Datum = '(\d{2}\.){2}(\d{2}|\d{4})';
m/$Datum$Fuell$Name$Ort/
Deutlicher werden die Möglichkeiten der oder-Verknüpfung, wenn wir nicht nur
Sätze mit dem Muster: "Geburtsdatum vor Name vor Geburtsort" sondern auch solche
mit dem Muster "Name vor Geburtsdatum vor Geburtsort" durchsuchen müssen. Der
reguläre Ausdruck lautet dann:
m/($Datum$Fuell$Name|$Name$Fuell$Datum)$Fuell$Ort/;
Es gibt keine der oder-Verknüpfung entsprechende Konstruktion für die und-Verknüpfung in regulären Ausdrücken.
Man kann leicht reguläre Ausdrücke konstruieren, die nur auf einen Nullstring
passen, etwa:
m/a{0}/
oder solche, die auch auf
Nullstrings passen wie:
m/^\a*/
m/a?/
m/$/
m/a??/
m/a*?/
Die erste Frage ist nun, welche
Treffer erzielen solche Ausdrücke und wo liegen sie im Suchtext?
Die Antwort
ist einfach:
Ein Nullstring passt auf jede Position im Suchtext, auch auf den
Textanfang und das Textende.
Wir bezeichnen Treffer in Form von
Nullstrings kurz als Null-Treffer. Beachten
Sie, dass auch Anker wie ^ und $ Null-Treffer erzielen.
Eine explizite
Mustersuche nach einem Nullstring ist äberflüssig, da Null-Treffer immer und
äberall erzielt werden können. Wenn nur ein Treffer gesucht wird und durch Anker
nichts anderes erzwungen wird, wird immer der Treffer gefunden, der im Suchtext
am weitesten vorne beginnt, bei einem Null-Treffer ist dies der Nullstring am
Textanfang.
Problematischer sind die Fragen:
Problematisch ist diese Regelung, wenn ein Null-Treffer erzielt wird, denn dann würde die nachfolgende Mustersuche an derselben Stelle wie die vorhergehende beginnen und wir hätten eine Endlos-Schleife bei der Suche nach allen Treffern.
Perl löst dieses Problem mit einer Zusatz-Regeln, die aber nicht in allen Versionen einheitlich implementiert sind. Wir gehen auf das Problem der Null-Treffer bei eine Folge von Mustersuchen noch öfter ein. Die unterschiedliche Implementierung sollte aber zur Vorsicht mit derartigen Konstruktionen mahnen.
Von besonderem Interesse ist diese Fragestellung im Zusammenhang mit der
Text-Ersetzung. Ersetzt man eine nicht leere Zeichenfolge durch einen
Nullstring, so heißt dies, dass diese Zeichenfolge aus dem Suchtext eliminiert
wird. Ersetzt man umgekehrt einen Nullstring durch eine nicht leere
Zeichenfolge, so bedeutet dies, dass diese Zeichenfolge an der betreffenden
Position in den Suchtext eingefügt wird. Der Text:
$Hdlin = 'Mit
gelben Birnen haenget';
wird durch die Substitution:
$Hdlin =~
s/\b/_/;
z.B. äbergeführt in:
_Mit gelben Birnen
hänget';
Die Substitution s/\b/_/ besagt, dass im Suchtext der erste
Treffer des Ausdruckes /\b/ durch ein Zeichen '_' zu ersetzen ist. Als Treffer
von /\b/ erhält man einen Nullstring am Textanfang. Dieser Nullstring wird
ersetzt, nicht die Wortgrenze, die sich durch die Substitution allerdings
verschiebt und nicht mehr am Textanfang steht.
Die Textersetzung:
$Hdlin =~ s/(en)*/e/;
ersetzt
nicht, wie man auf den ersten Blick vielleicht erwartet, 'gelben' durch
'gelbe', sondern 'Mit' durch 'eMit', denn /(en)*/ passt auf den Nullstring am
Textanfang und ersetzt diesen durch 'e'.
Ein verwandtes Problem ist das, wie ein leerer regulärer Ausdruck zu interpretieren
ist. Perl lässt Anweisungen wie m// zu, kritischer sind aber solche,
bei denen sich erst nach der Entwicklung des regulären Ausdruckes ergibt, dass
dieser Ausdruck leer oder undefiniert (ASCII: 000) ist, etwa:
undef $M; $T =~ m/$M/
Auch hier gibt es keine allgemein gültige Antwort,
da es z.B. bei der Mustersuche anders zu beantworten ist, als bei der
Textersetzung. Wir gehen bei den einzelnen Operatoren auf dieses Problem ein.
Schließlich kann auch der Suchtext
leer sein. Auch ein Nullstring hat einen Anfang und ein Ende, dazwischen steht
allerdings kein Zeichen. Eine Anweisung:
print '' =~
m/^z*$/:
wird also '1' liefern.
| Startseite | Algorithmus der Mustersuche |