Ist die Alternation gierig?

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

Die Funktionsweise der Alternation ist ein wichtiger Punkt, weil sie bei den zwei Regex-Typen ganz unterschiedlich ist. Wenn eine Alternation erreicht wird, kann jede der Alternativen auf den String passen, aber welche wird gewählt? Anders gefragt: Wenn mehrere Alternativen passen können – welche gewinnt? Gewinnt immer die längste Variante? Dann ist die Alternation gierig. Oder gewinnt die kürzeste? Dann ist die Alternation genügsam. Oder gewinnt keine von beiden?

Betrachten wir zunächst die traditionelle NFA-Maschine wie die von Perl, Java, PHP, den .NET-Sprachen und vielen anderen (siehe Typen von Regex-Maschinen). Bei einer Alternation werden die einzelnen Alternativen der Reihe nach ausprobiert, von links nach rechts, wie sie in der Regex stehen. Wenn beim Beispiel ˹^(Subject|Date):●˼ die Alternation erreicht wird, wird die erste Alternative ausprobiert, ˹Subject˼. Wenn sie passt, wird der Rest der Regex angewendet. Wenn sie nicht passt und wenn andere Alternativen bestehen (in diesem Fall ˹Date˼), dann geht die Regex-Maschine mittels Backtracking zurück und testet die nächste Alternative. Das ist nur ein weiterer Fall, bei dem die Maschine durch Backtracking zu einem Zustand zurückkehrt, an dem es noch nicht getestete Möglichkeiten gibt. Das wiederholt sich, bis entweder ein globales Matching erreicht wird oder bis alle Möglichkeiten (in diesem Fall: Alternativen) ausgeschöpft sind.

Welchen Text findet nun ein traditioneller NFA mit dem Ausdruck ˹zucker|zu|zuckerhut˼, wenn der String ›den●zuckerhut●besteigen‹ vorgelegt wird? Die Alternativen werden ausprobiert und schlagen fehl, und zwar zunächst an jeder Zeichenposition im String. Erst wenn das Getriebe weiterschaltet und bei ›den●▵zuckerhut●besteigen‹ einen Versuch startet, passt die erste Alternative, ˹zucker˼. Weil die Alternation das letzte Element der Regex ist, ist hier die Mustersuche auch gleich beendet. Die anderen Alternativen werden gar nicht erst getestet.

Die Alternation ist also weder gierig noch genügsam, sondern geordnet, sie folgt der Reihenfolge der Alternativen in der Regex – zumindest bei einem traditionellen NFA. Das ist flexibler als gieriges Verhalten, weil wir so mehr Kontrolle über den Vorgang des Matchings bekommen – der Programmierer kann fordern: »Probier dies, dann das und schließlich dieses, bis ein Treffer gefunden wird.«

Nicht alle Dialekte haben diese geordnete Alternation. Bei DFAs und POSIX-NFAs ist die Alternation gierig; von mehreren passenden Alternativen wird die verfolgt, die auf den längsten Teilstring passt (in diesem Fall ˹zuckerhut˼). In Perl, in PHP, in allen .NET-Sprachen, in java.util.regex und in jedem anderen System mit einem traditionellen NFA (vgl. die Tabelle Einige Programme und ihre Regex-Maschinentypen) ist die Alternation geordnet.

  

<< zurück

vor >>