Gier

Beim Umgang mit regulären Ausdrücken gibt es für Neulinge auf diesem Gebiet eine überaschende und recht häufig verwirrende Eigenschaft der Quantoren: deren Gier. Um zu verstehen, was hier gemeint ist, muß man sich zuerst einmal einen Eindruck von der Arbeitsweise der Algorithmen machen, die die regulären Ausdrücke auswerten.

Betrachten wir als Beispiel einen eher harmlos aussehenden Ausdruck wie:

.*(#+,##) €

Offensichtlich soll hier ein Geldbetrag gesucht werden, von dem nicht von vornherein klar ist, wieviele Stellen vor dem Komma stehen. Wendet man diesen Ausdruck auf den Text 'Endbetrag: 123,45 €' an, würde man im ersten Ansatz erwarten, daß im Textpuffer '123,45' steht. Das ist aber nicht der Fall.

Der Algorithmus zur Auswertung schaut sich als erstes das 'E' aus dem zu prüfenden Text an. Ein 'E' ist eine gültige Ausprägung des Musters '.'. Durch den (gierigen) Quantor '*' kann das Muster '.' aber noch beliebig oft wiederholt werden. Also wird auch das 'n', 'd', 'b', usw bis zum '€' vom Muster '.*' absorbiert. Dann ist zwar das Ende des Textes erreicht, aber es ist noch (nicht optionales) Muster übrig. Damit wäre der Ausdruck zunächst einmal nicht erkannt.

Jetzt prüft der Algorithmus aber noch weitere Möglichkeiten, die er sich beim Aufsammeln der Zeichen für das '.*' gemerkt hat. Er gibt jetzt das '€' heraus und prüft es gegen das Teilmuster '#+,## €' (die Klammern spielen im Moment keine Rolle). Auch diese Prüfung geht negativ aus, also wird auch noch das Leerzeichen herausgegeben. Er prüft also ' €' gegen '#+,## €' mit dem gleichen negativen Ergebnis. Als nächstes wird die '5' herausgegeben, usw. Dies geht solange weiter, bis die '3' herausgegeben wird. Jetzt wird '3,45 €' gegen '#+,## €' geprüft, mit positivem Ergebnis!

Der zu prüfende Text ist jetzt zu Ende, aber auch das Muster. Also wurde der reguläre Ausdruck insgesamt erkannt! Im Textpuffer steht '3,45', was wahrscheinlich nicht das erwartete Ergebnis ist.

Die Tücke dieses regulären Ausdrucks ist, daß auf den gierigen '*' ein weiterer Quantor folgt, der sich aber bereits mit einer einzigen Wiederholung zufrieden gibt.


Zum Glück lassen sich solche Situationen mit etwas Wissen über den zu prüfenden Text aber leicht vermeiden. In unserem Fall hier wird das Einfügen einer Leerstelle im Muster unmittelbar vor dem ersten '#' das Problem beseitigen:

.* (#+,##) €

Der Algorithmus gibt jetzt alle Zeichen bis zur vorletzten Leerstelle heraus, bevor das Teilmuster ' (#+,##) €' erkannt wird. Im Textpuffer steht jetzt die erwartete Zahl '123,45'.


Beim Entwurf regulärer Ausdrücke sollte man daher immer darauf achten, daß nach einem Quantor nicht sofort wieder ein Teilmuster mit Quantor folgt, weil dies oft zu dem hier gezeigten Ergebnis führt. Es ist damit natürlich auch klar, daß Muster wie '.*(b*)' unsinnig sind.

Andererseits kann man aber auch die Gier sehr bewußt einsetzen, um quasi einen Text von hinten her zu durchsuchen. Als Beispiel mag ein 30 Zeichen langes Textfeld dienen, dessen Inhalt ohne nachfolgende Leerstellen ausgelesen werden soll. Dies erledigt elegant der reguläre Ausdruck:

(.{0,29}[^ ]).*

Hier werden zunächst bis zu 29 Zeichen vom '.{0,29}' aufgesammelt. Ist das 30. Zeichen keine Leerstelle, ist der Ausdruck erkannt, und im Textpuffer stehen alle 30 Zeichen. Ist das 30. Zeichen eine Leerstelle, gibt '.{0,29}' das 29. Zeichen heraus. Das wird dann wieder gegen '[^ ]' getestet, usw. Am Schluß ist der Textpuffer entweder leer, oder das letzte Zeichen des Puffers ist keine Leerstelle. Übrigens: das abschliessende '.*' ist unbedingt notwendig, weil es ja die unerwünschten Leerstellen absorbieren muß.

Hinweise