Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


20. Pattern Matching



Darstellung des Automaten

Alle unsere nichtdeterministischen Automaten werden ausschließlich unter Verwendung der drei oben dargelegten Regeln für die Zusammensetzung konstruiert, und wir können ihre einfache Struktur ausnutzen, um sie in einer sehr einfachen Weise zu handhaben. Zum Beispiel führen aus keinem Zustand mehr als zwei Linien heraus. Tatsächlich gibt es nur zwei Typen von Zuständen: Zustände, die mit einem Zeichen aus dem Eingabealphabet markiert sind (mit einer herausführenden Linie) und nichtmarkierte Zustände (Nullzustände, mit zwei oder weniger herausführenden Linien). Das bedeutet, daß der Automat mit nur wenigen Informationen pro Zustand dargestellt werden kann. Da wir oft nur über die Nummer auf die Zustände zugreifen wollen, ist die zweckmäßigste Organisation für den Automaten eine Darstellung als Feld. Wir werden die drei mit dem Index state (Zustand) versehenen parallelen Felder ch, next1 und next2 verwenden, um den Automaten darzustellen und auf ihn zuzugreifen. Es wäre möglich, mit zwei Drittel dieses Platzbedarfs auszukommen, da für jeden Zustand tatsächlich nur zwei Informationen von Bedeutung verwendet werden, doch wir wollen im Interesse der Klarheit (und auch weil Musterbeschreibungen gewöhnlich nicht besonders lang sind) auf diese Verbesserung verzichten.

Der obige Automat kann wie in Abbildung 20.7 dargestellt werden. Die mit dem Index state versehenen Einträge können als Anweisungen für den nichtdeterministischen Automaten von der Art »Wenn du dich in state befindest und ch[state] siehst, dann durchlaufe das Zeichen und gehe in den Zustand next1[state] (oder next2[state]) über« interpretiert werden. Zustand 9 ist der Endzustand in diesem Beispiel, und Zustand 0 ist ein Pseudo-Anfangszustand, dessen Einträge next die Nummer des eigentlichen Anfangszustands sind. (Man beachte die spezielle Darstellung, die für Nullzustände mit 0 oder 1 Ausgängen verwendet wird.)

Abbildung 20.7
Abbildung 20.7 Darstellung des Automaten aus Abblidung 20.1 als Feld.

Wir haben gesehen, wie Automaten aus Beschreibungen von Mustern mittels regulärer Ausdrücke aufgebaut werden können und wie solche Automaten als Felder dargestellt werden können. Die Erstellung eines Programms zur Realisierung des Übergangs von einem regulären Ausdruck zu der entsprechenden Darstellung als nichtdeterministischen Automaten ist jedoch eine ganz andere Sache. Selbst ein Programm zur Bestimmung, ob ein gegebener regulärer Ausdruck zulässig ist, läßt sich nur mit einer gewissen Erfahrung erstellen. Im folgenden Kapitel untersuchen wir diese Operation, die Syntaxanalyse (parsing) genannt wird, wesentlich ausführlicher. Einstweilen wollen wir annehmen, daß dieser Übergang vollzogen worden ist, so daß wir die Felder ch, next1 und next2 zur Verfügung haben, die einen speziellen nichtdeterministischen Automaten darstellen, der der uns interessierenden Musterbeschreibung durch einen regulären Ausdruck entspricht.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]