38. Reguläre Ausdrücke I

Unsere Grammatiken müssen jetzt auch anders aussehen – wir haben keine automatische Unterscheidung von Terminal- und Nichtterminalsymbolen. Vereinbarung: Terminalsymbole sollen jetzt in doppelten Anführungszeichen stehen, Nichtterminale sind „nackt”:

NP -> n
n -> "dog"

Spätestens jetzt wird es mit Bordmitteln schwierig. Abhilfe: Reguläre Ausdrücke bzw. regular expressions (RE).

In Python stehen Routinen für REs im Modul re.

Reguläre Ausdrücke sind eine Sprache zur Beschreibung von Zeichenfolgen.

Die einfachsten regulären Ausdrücke sind „normale” Zeichen, der Punkt (ein beliebiges Zeichen) und Mengen (in eckigen Klammern). Dabei ist ein Zeichen normal, wenn es nicht speziell ist. Spezialzeichen (Metacharacters, Metazeichen) in Pythons regulären Ausdrücken sind . ^ $ * + ? [ ] [ | ( ).

In gewisser Weise lernt ihr mit den regulären Ausdrücken eine Sprache innerhalb der Sprache Python. Zwar ist diese Sprache bei weitem weniger mächtig als Python selbst (was heißen soll, dass man mit dieser Sprache weniger „Probleme lösen” kann als in Python – klarer wird das in der Vorlesung über formale Grundlagen der Linguistik), aber fürs Zerstückeln von Texten gerade deswegen unwahrscheinlich praktisch.

(Weiterführend:) Wer schon formale Grundlagen gehört hat, wird ahnen, dass reguläre Ausdrücke im Groben reguläre Sprachen beschreiben (tatsächlich sind Pythons reguläre Ausdrücke allerdings erheblich mächtiger), während Python-Programme natürlich im Prinzip alle allgemeinen Regelsprachen beschreiben können (es ist nicht schwierig, eine Turingmaschine in Python zu schreiben).

Ein erstes Beispiel für diese einfachen REs:

>>> from re import search as s
>>> s("m", "abc"),s("a", "abc").group(0)
(None, ’a’)
>>> s(".", "abc").group(0)
’a’
>>> s("[A-Z]", "abc"),s("[cde]", "abc").group(0)
(None, ’c’)

Man sucht also mit der Funktion re.search im zweiten Argument nach Entsprechungen („matches”) für den regulären Ausdruck im ersten Argument. Die Funktion gibt None oder ein Match-Objekt zurück; im zweiten Fall gibt die group-Methode des Ergebnisses mit dem Argument 0 zurück, auf welchen Substring des zweiten Arguments der reguläre Ausdruck gepasst („gematcht”) hat.

Die Schreibweise from x import y as z übrigens setze ich hier zur Platzersparnis ein – ich habe auf dieser Folie nicht genug Platz, um search immer auszuschreiben. Für euch gilt: Verwendet sowas nicht, bevor ihr etwas mehr Erfahrung habt, wozu sowas gut sein könnte – Einsparung von Tipparbeit ist jedenfalls im Allgemeinen kein guter Grund, Objekte einfach so umzubenennen.

Daraus lassen sich durch | (verodern), * (null oder mehr Vorkommen), + (ein oder mehr Vorkommen), ? (null oder ein Vorkommen) neue Ausdrücke bauen:

>>> s("ab|re", "abc").group(0),s("ab|re",
...   "reg").group(0)
(’ab’, ’re’)
>>> s("a*b", "aaab").group(0),s("a*bb+", "aaab")
(’aaab’, None)

Mit Klammern lassen sich Gruppen bauen:

>>> s("(ab)+", "abba").group(0),s("(ab)+",
...   "abab").group(0)
(’ab’, ’abab’)

^ und $ markieren Anfang und Ende:

>>> s("^b", "abb"), s("b$", "abb").group(0)
(None, ’b’)

Unsere Terminalsymbole folgen dem regulären Ausdruck ^"[^"]*"$. In [] werden Mengen von Zeichen angegeben, ^ am Anfang einer Menge hat die spezielle Bedeutung „alle außer die angegebenen Zeichen”.

>>> (s(’^"[^"]*"$’, ’"Trm"’).group(),
  s(’"[^"]"’, ’NT’).group())
("Trm", None)

Noch ein bisschen mehr zu Mengen von Zeichen: [abc] heißt also eines der Zeichen a, b oder c. Man kann auch „Ranges” bilden: [A-Z] sind alle Zeichen zwischen A und Z, [A-Za-z] alle „normalen” Klein- oder Großbuchstaben (Umlaute oder das scharfe s sind da nicht dabei, sie wären etwa durch [A-Za-zÄÜÖüöäß] erfasst – aber für sowas werden wir später bessere Methoden kennenlernen). Wenn der Bindestrich in der Menge sein soll, kann er an den Anfang oder ans Ende der Menge gestellt werden (sonst würde er einen Range kennzeichnen).

Ein Caret an erster Stelle wählt das Komplement der angegebenen Menge, matcht also alle Zeichen außer den angegebenen. [^0-9] sind alle Zeichen außer Ziffern, [^:.;,()-!] wäre etwas wie „alles außer Satzzeichen” – man sieht hier auch, dass Metazeichen (z.B. der Punkt) in Mengen normalerweise keine spezielle Bedeutung haben. Das Caret an einer anderen als der ersten Position entspricht einem literalen Caret. [-^] matcht also entweder einen Bindestrich oder ein Caret.

Will man Metazeichen literal matchen, muss man in der Regel Backslashes vor das Metazeichen oder es einzeln in eine Menge schreiben. r"[*" oder "[*]" matchen beispielsweise einen Stern, [( oder [(] eine öffnende Klammer.

Zum Selbststudium geeignet ist Andrew Kuchlings Python RE Howto.

Übungen zu diesem Abschnitt

Ihr solltet euch wenigstens an den rötlich unterlegten Aufgaben versuchen

(1)

Denkt euch reguläre Ausdrücke aus, die folgende Dinge matchen (in Python-Syntax, für whitespace könnt ihr vorerst Leerzeichen nehmen):

  1. Python-Namen
  2. Zuweisungen zu Namen, die mit einem Großbuchstaben anfangen
  3. Den Kopf einer Klassendefinition (also class Foo(Bar):)
  4. Den Kopf einer Funktionsdefinition
  5. Zuweisungen konstanter Zahlen

Hinweis: Viele Editoren (allen voran vi und emacs) können auch reguläre Ausdrücke, die sich subtil von Pythons REs unterscheiden. Wenn ihr diese Unterschiede kennt, könnt ihr diese Aufgabe auch einfach interaktiv im Editor probieren.

(2)

Schreibt ein Programm firstmatch.py, das im ersten Kommandozeilenargument einen regulären Ausdruck und im zweiten einen Dateinamen nimmt. Die Ausgabe soll entweder nichts sein, wenn der reguläre Ausdruck in der bezeichneten Datei nicht matcht, oder der erste Match innerhalb der Datei.

Hinweis: Einige der Metazeichen regulärer Ausdrücke werden von den üblichen Shells selbst interpretiert. Ihr solltet die regulären Ausdrücke also zumindest unter den üblichen Unix-Shells immer in einfache Anführungszeichen schreiben (Generalausnahme: Man weiß, was man tut):

examples> python firstmatch.py "def[^:]*:" firstmatch.py
def firstMatch(regExp, text):

(3)

Erweitert das Programm aus der letzten Aufgabe so, dass nach dem regulären Ausdruck beliebig viele Dateinamen kommen können. Verändert es so, dass es alle Matches ausgibt (ein Programm, das das tut, gibt es übrigens auf Unix-Systemen schon – es heißt grep).


Markus Demleitner

Copyright Notice