Gier, Genügsamkeit, Backtracking: Die Essenz

(Auszug aus "Reguläre Ausdrücke" von Jeffrey E. F. Friedl)

In Gierig oder genügsam -– der Treffer geht vor haben Sie gelernt, dass es nicht nur darauf ankommt, ob in einer Regex gierige oder nicht-gierige Elemente vorhanden sind: Zuerst muss ein Treffer erzielt werden, das geht vor. Auch wenn einem gierigen Konstrukt wieder Zeichen abgezwackt werden müssen oder einem nicht-gierigen Element Zeichen aufgedrängt werden müssen, gilt Folgendes: Wenn ein »lokaler Fehlschlag« erreicht wird, probiert die Maschine alle gespeicherten Zustände aus (sie geht den Brotkrumen nach zurück) und versucht von diesen aus die noch nicht eingeschlagenen Wege. Ob gierig oder nicht, die Maschine probiert alle möglichen Wege aus, bevor sie sich geschlagen gibt und einen Fehlschlag meldet.

Im gierigen Fall werden die Wege in einer anderen Reihenfolge ausprobiert als beim nicht-gierigen (genau darum gibt es ja beide!), wenn aber kein Treffer gefunden wird, sind genau die gleichen Wege ausprobiert worden.

Wenn es für eine bestimmte Mustersuche genau einen Treffer gibt, wird dieser von einer Regex mit gierigen Elementen genauso gefunden wie von einer mit genügsamen – wiederum werden aber die erfolglosen Wege in anderer Reihenfolge durchprobiert. In einem solchen Fall hat »gierig oder nicht« keinen Einfluss auf den Treffer, aber auf die Art, wie die Maschine zu diesem findet (das ist ein Effizienzthema und gehört daher zu Die Kunst, reguläre Ausdrücke zu schreiben).

Wenn es mehr als einen möglichen Treffer gibt, wählen die gierigen Konstrukte einen anderen »richtigen« Treffer als die nicht-gierigen. Beim Beispiel mit ˹".*"˼ gibt es drei mögliche Treffer:

Der Name "McDonald's" wird japanisch "makudonarudo" ausgesprochen
Der Name "McDonald's" wird japanisch "makudonarudo" ausgesprochen
Der Name "McDonald's" wird japanisch "makudonarudo" ausgesprochen

Der Ausdruck ˹".*"˼ mit dem gierigen Stern ergibt den längsten Treffer; mit ˹".*?"˼, dem nicht-gierigen Quantor, erhalten wir die kürzeste Möglichkeit.

  

<< zurück

vor >>