26.1 Kellerautomaten

Beispiel

Betrachten Sie folgende Abbildung:

Ein Kellerautomat für arithmetische Ausdrücke

Dies ist ein erweiterter deterministischer endlicher Automat (DEA). Der Automat ist endlich, denn er besitzt nur zwei Zustände. Auch ist er determiniert, denn es ist völlig eindeutig, mit welchen Zeichen man von welchem Zustand in den nächsten Zustand gelangt. Das Alphabet dieses Automaten ist

{add, mul, num, (, )} 

Dabei steht num für jede mögliche (korrekt geschriebene) Zahl. Die Zeichen add und mul stehen für die Additions- und Multiplikations-Operatoren * und +. Die rot geschriebenen Symbole push und pop gehören nicht zum Alphabet dieses Automaten, sondern sind Anweisungen an einen integrierten Stack.

Wenn sich der Automat im Zustand 1 befindet und dann eine geöffnete Klammer erkennt, bleibt er im Zustand 1 und führt gleichzeitig einen push-Befehl aus. Die geöffnete Klammer wird sozusagen auf den Stack gelegt. Befindet sich der Automat im Zustand 2 und erkennt jetzt eine geschlossene Klammer, wird ein pop-Befehl ausgeführt. Die auf den Stack gelegte Klammer wird also wieder entfernt.

Nähere Beschreibung anhand eines Beispiels

Betrachten wir den arihtmetischen Ausdruck

( ( 2 + 3 ) * 4 + 1) * 5

Der Automat startet mit Zustand 1.  Als erstes kommt eine geöffnete Klammer. Der Zustand ändert sich also nicht, aber die Klammer wird auf den Stack gepusht. Wie der Automat sich bei der Abarbeitung des arithmetischen Ausdrucks verhält, ist in der folgenden Tabelle dargestellt:

Kellerautomaten

Was wir eben so detailliert beschrieben haben, wird in der Fachsprache als Kellerautomat bezeichnet. Ein Kellerautomat ist ein determinierter endlicher Automat, der zählen kann. Zum Zählen verwendet man einen Stack oder Kellerspeicher. Im Grunde hätte aber hierfür auch ein einfacher Zähler gereicht, der inkrementiert und dekrementiert werden kann.

Bei der lexikalischen Analyse eines Compilers spielen Kellerautomaten noch keine Rolle, dafür gibt es ja die deterministischen endlichen Automaten, die reguläre Ausdrücke erkennen. Kellerautomaten sind für die syntaktische Analyse erforderlich. Klammerausdrücke sind nur ein einfaches Beispiel hierfür. In einer Programmiersprache gibt es viele Konstrukte, die im Prinzip Klammerausdrücken entsprechen. Denken Sie nur an mehrfach verschachtelte while-Schleifen oder if-else-Bedingungen.

Im Abschnitt über determinierte endliche Automaten hatten wir gesehen, was die Sprache eines DEAs ist, nämlich die Menge aller Wörter aus dem Alphabet des Automaten, die den Automaten vom Startzustand in einen der Endzustände überführen. Diese Definition ist zwar korrekt, aber nicht sehr anschaulich und hilfreich für die Praxis. In der Praxis gibt es tatsächlich Sprachen, deren Worte von DEAs akzeptiert werden. Am bekanntesten sind die sogenannten regulären Ausdrücke (siehe dazu den Lexikon-Artikel).