Montag, Oktober 20, 2008

Reguläre Ausdrücke

Eine typische Aufgabenstellung, mit der sich ein Software-Entwickler bzw. eine Software-Entwicklerin immer wieder konfrontiert sieht, ist die Verarbeitung von Textdateien. In der Regel interessiert die Verarbeitung von Textdateien oder Zeichenströmen, die von Maschinen für Maschinen gedacht sind. Solche Textdateien folgen klaren, eindeutigen Regeln des Aufbaus. Sonst ist die maschinelle Verarbeitung eher schwierig bis unmöglich.

Bei der Verarbeitung von Textdateien bzw. Zeichenströmen kommt man an regulären Ausdrücken (regular expressions) nicht vorbei. Mit ihnen kann man Zeichenfolgen in einem Text suchen und weiter verarbeiten. Reguläre Ausdrücke stehen in praktisch jeder Programmiersprache als nachladbare Bibliothek zur Verfügung (so z.B. in Java) oder sie sind bereits fester Bestandteil der Sprache (wie z.B. in Perl oder JavaScript). Jeder moderne Texteditor erlaubt die Suche nach Zeichenketten mit Hilfe von regulären Ausdrücken.

Reguläre Ausdrücke selbst sind Zeichenketten (strings). Die in dem String verwendeten Zeichen folgen bestimmten Vereinbarungen (Konventionen). Zum Beispiel steht die Zeichenfolge "\d" in einem regulären Ausdruck nicht für die Folge der Zeichen "\" und "d". Der Backslash "\" ist ein sogenanntes escape symbol. Die normale Bedeutung des Zeichens "\" als Backslash wird ausgehebelt. Zusammen mit dem "d" bekommt es eine Sonderfunktion. Die Zeichen "\d" stehen für eine beliebige Ziffer (digit) von 0 bis 9. Gleichwertig dazu ist der reguläre Ausdruck "[0-9]". In der Tat ist "\d" nicht mehr als eine Kurzform für "[0-9]". Die eckigen Klammer haben ebenso wie der Backslash eine Sonderbedeutung. Die zwischen den eckigen Klammern gelisteten Zeichen stellen Alternativen dar. Ein "[012]" steht entweder für eine "0" oder eine "1" oder eine "2". Ein Digit ist also ein "[0123456789]". Die von/bis-Notation "[0-9]" verkürzt den Schreibaufwand.

Und was ist, wenn man die Sonderbedeutung von "\", "[" bzw. "]" aufheben möchte? Dann kommt wieder das Escape-Zeichen, der Backslash, zum Einsatz. Ein "\\" meint genau das Zeichen "\". Und ein "\[" bzw. "\]" schaltet die Sonderbedeutung der eckigen Klammern aus und meint nun ausdrücklich die Zeichen "[" und "]".

Nachfolgende ist eine kurze Einführung in die Arbeit mit regulären Ausdrücken in der Programmiersprache Python gegeben. Diese Einführung ist weder vollständig noch umfassend. Ziel ist, Ihnen die Einstiegshürde zu nehmen.

In Python werden reguläre Ausdrücke über eine Bibliothek (ein Modul) zur Verfügung gestellt.

>>> import re

Ist die Suche nach einem Muster erfolgreich, liefert das re-Modul ein "Muster erkannt"-Objekt zurück. Schlägt die Suche fehl, wird None als Wert ausgeliefert.

>>> re.search("ll","hello")
<_sre.SRE_Match object at 0x00B8DBB8>
>>> re.search("ll","hexxo")
>>> re.search("ll","hexxo") == None
True

Neben der search-Methode steht auch eine match-Methode zur Verfügung. Ein Match erwartet im Gegensatz zum Search eine Passung des regulären Ausdrucks mit dem Anfang des übergebenen Strings. Bei Search wird im gesamten String nach dem Muster gefahndet.

>>> re.search("ll","hello")
<_sre.SRE_Match object at 0x00B8DB80>
>>> re.match("ll","hello")

Zur effizienten Verarbeitung können reguläre Ausdrücke intern compiliert werden. Das macht vor allem dann Sinn, wenn ein Muster mehrfach zum Einsatz kommt.

>>> hhmmRE = re.compile("\d\d:\d\d")
>>> hhmmRE
<_sre.SRE_Pattern object at 0x00B24870>
>>> hhmm = hhmmRE.search("It's 14:00!")
>>> hhmm
<_sre.SRE_Match object at 0x00B8DC28>

Match-Objekte bieten eine Reihe von Methoden an. Man kann z.B. den zum Muster passenden String erfragen oder sich die Position des Muster-Treffers im String angeben lassen.

>>> hhmm.group()
'14:00'
>>> hhmm.start()
5
>>> hhmm.end()
10
>>> hhmm.string
"It's 14:00!"
>>> hhmm.string[hhmm.start():hhmm.end()]
'14:00'

Teile eines regulären Ausdrucks können in Gruppen strukturiert werden. Auf die einzelnen Teile kann dann über das Match-Objekt zugegriffen werden. Angenommen, wir wollen die Stunden und die Minuten einer Uhrzeitangabe separat erfassen. Runde Klammern in einem regulären Ausdruck markieren Gruppen, die von 1 an aufsteigend durchgezählt werden.

Zusätzlich verbessern wir unser Suchmuster dahingehend, dass auch Uhrzeiten mit einstelliger Stundenangabe (z.B. 7:00 Uhr) erkannt werden. Ein Fragezeichen markiert als Sondersymbol die Optionalität des voranstehenden Zeichens. Ein "\d?" steht für einen Digit, der optional ist.

>>> hhmmRE = re.compile("(\d?\d):(\d\d)")
>>> hhmm = hhmmRE.search("Let's meet at 2:00 pm.")
>>> hhmm
<_sre.SRE_Match object at 0x00B97578>
>>> hhmm.group(1)
'2'
>>> hhmm.group(2)
'00'

Gruppen können auch mit sprechenden Namen assoziiert werden, was aus software-technischer Sicht zu empfehlen ist. Beim Durchzählen von Gruppen kann sich ein Programmierer oder eine Programmiererin leicht verzählen. Referenzbezüge mit sprechenden Namen sind weniger fehleranfällig.

Eine benamte Gruppe wird mit "(?P<name>...)" markiert.

>>> hhmmRE = re.compile("(?P<hh>\d?\d):(?P<mm>\d\d)")
>>> hhmm = hhmmRE.search("Let's meet at 13:45.")
>>> hhmm.group("hh")
'13'
>>> hhmm.group("mm")
'45'

Soweit der Einstieg mit Python. Es gibt noch eine Menge zu regulären Ausdrücken zu entdecken. Sie sind ein leistungsfähiges Werkzeug bei der Verarbeitung von Strings.

Es lohnt nicht unbedingt, sich ein Buch zu regulären Ausdrücken zuzulegen, auch wenn es zu diesem Thema exzellente Werke gibt. Einen raschen Überblick zur Historie und zum theoretischen Hintergrund liefern Ihnen beispielsweise der deutsche und der englische Wikipedia-Eintrag. Dort finden Sie auch etliche hilfreiche Weblinks. Im "Tagesgeschäft" sollte die Dokumentation zu den regulären Ausdrücken in der von Ihnen verwendeten Programmiersprache vollends ausreichen.

Kommentare:

Anonym hat gesagt…

Moin,

ein Hinweis: im letzten Beispiel hat das Blog (wohl wegen der spitzen Klammern) die Namen der Gruppen gefressen.

dh hat gesagt…

Argh, ja, HTML und spitze Klammern ... vielen Dank für den Hinweis! Ist gefixt.

Aaron Müller hat gesagt…

Ich hab auf meinem Blog vor Kurzem einen kleinen Programmierwettbewerb veranstaltet, bei dem man gut sehen konnte, dass reguläre Ausdrücke einiges an Code einspart und Fehler reduziert.

http://aaron-mueller.de/blog/programmierwettbewerb-analyse-teil1

Zum Testen von kompilzierteren Ausdrücken kann ich Rubular oder RegexPal empfehlen:
http://www.rubular.com/ (Ruby)
http://regexpal.com/ (JavaScript)

bernoulli hat gesagt…

Mal wieder eine Spitzfindigkeit, sorry:

Es werden auch "Uhrzeiten" (akzeptiert), die - zumindest in unserer Welt - nicht gültig sind.

(([01]?\d)|(2[0-3])):([0-5]\d) trifft's besser.

dh hat gesagt…

Lieber Bernoulli, ich werde dazu noch einen Blogeintrag liefern. Dieser Beitrag sollte nur in die regulären Ausdrücke einführen. Denn oft ist die Frage, wie weit man es mit den Pattern treiben möchte. Stay tuned! ;-)

Gruß,

DH

Till hat gesagt…

Ich habe mich im vergangenen Semester auch schon mit Regex (unter Java) beschäftigen dürfen.

Man muss speziell bei der Verarbeitung von Unicode sehr aufpassen, da es gewisse Zeichen gibt, die sowohl aus zwei Glyphen kombiniert als auch nur durch eine Dargestellt werden können. Mehr dazu hier

Zum Thema "Denn oft ist die Frage, wie weit man es mit den Pattern treiben möchte." Das kann ich nur bestätigen. Bei der Inputvalidierung steht dabei mal wieder Usability bzw. Fehlertoleranz gegen Sicherheit.