Kellerautomat einfach erklärt: Aufbau und Beispiel

Ein Keller (auch Stapelspeicher, Stapel oder Stack genannt) ist eine Datenstruktur. Stell dir einen Stapel Umzugskisten vor. Du kannst nur oben eine Kiste daraufstellen oder von oben eine herunternehmen. Der Zugriff ist im Regelfall nur auf das oberste Element möglich. Weiter unten im Stapel kannst du nichts hinzufügen oder entfernen.

Deshalb kommen die Elemente in umgekehrter Reihenfolge wieder heraus. Das zuerst abgelegte (unterste) Element wird als letztes abgerufen. Das zuletzt abgelegte (oberste) Element wird zuerst abgerufen. Dieses Prinzip heißt Last In – First Out, kurz LIFO.

Das Ablegen eines neuen Objekts nennt man „Push“. Bei „Pop“ wird das oberste Objekt gelesen und gleichzeitig gelöscht. Soll das oberste Objekt nur gelesen werden, benutzt man „Top“ oder „Peek“.

Ein Kellerautomat ist ein endlicher Automat, der um einen Kellerspeicher erweitert wurde. Er soll klären, ob eine Eingabe zu einer bestimmten formalen Sprache gehört. Die Eingabe ist ein Wort aus null, einem oder mehreren Zeichen. Die Sprache ist eine Menge von Wörtern. Der Automat arbeitet das Eingabewort Schritt für Schritt von links nach rechts ab. Zu Anfang ist er im Startzustand.

Typischerweise wird in jedem Verarbeitungsschritt ein Zeichen aus der Eingabe gelesen. Außerdem wird das oberste Kellerzeichen gelesen, das dabei entfernt wird. Abhängig vom aktuellen Zustand, dem gelesenen Eingabezeichen und dem gelesenen Kellerzeichen geht der Automat in einen neuen Zustand über. Anstelle des entfernten Kellerzeichens legt er ein neues Wort auf dem Keller ab.

Es gibt Abweichungen. Nicht in jedem Schritt muss ein Eingabezeichen gelesen werden. Dann wird das gelesene Wort ε genannt, das leere Wort. Außerdem kann man die erkannte Sprache auch über einen Endzustand definieren, den der Automat erreicht. Bei der einfachen Erklärung gilt: Ist die gesamte Eingabe gelesen und der Keller leer, gehört die Eingabe zur erkannten Sprache. Beim Klammerbeispiel im nächsten Abschnitt zählt stattdessen: Im Keller liegt nur das Endzeichen #.

Eine typische Aufgabe: In einem Ausdruck muss zu jeder öffnenden Klammer eine schließende Klammer existieren, zum Beispiel { … { … } … }. Genau das prüft der Kellerautomat mit seinem Keller.

Der Automat beginnt im Startzustand z0. Im Keller liegt ein Zeichen, das das Ende kennzeichnet: #. Der Lesekopf zeigt auf das Zeichen der Eingabe, das gerade gelesen wird, und bewegt sich Zeichen für Zeichen weiter. Trifft er auf eine öffnende Klammer, wird sie in den Keller geschrieben. Trifft er auf eine schließende Klammer, wird das oberste Klammer-auf-Zeichen im Keller gelöscht.

Der Ausdruck ist erfolgreich abgearbeitet, wenn der Lesekopf das Ende der Eingabe erreicht hat und im Keller nur # liegt. Liegt am Ende noch eine geöffnete Klammer im Keller, fehlt eine schließende Klammer. Das ist ein syntaktischer Fehler. Ein Fehler liegt auch vor, wenn das Ende des Kellers erreicht wird, bevor die Eingabe zu Ende ist. Dann stehen zu viele schließende Klammern in der Eingabe.

Bei manchen Kombinationen aus Zustand, Eingabezeichen (oder ε) und Kellerzeichen kann ein Kellerautomat die Wahl zwischen mehreren Übergängen haben. Ein Übergang ist die Kombination aus Folgezustand und Kellerwort. Solche Automaten heißen nichtdeterministisch. Eine Eingabe gilt dort als erkannt, wenn der Keller geleert werden kann oder ein Endzustand erreicht werden kann.

Bei einem deterministischen Kellerautomaten ist die Wahl eingeschränkt. Für jede Kombination aus Zustand, Eingabezeichen (oder ε) und Kellerzeichen gibt es zusammen höchstens einen möglichen Übergang. Zu einer festen Eingabe gibt es dann höchstens eine Abfolge von Zustandsübergängen. Mehrdeutigkeiten können nicht auftreten.

Die Sprachklassen: Die von nichtdeterministischen Kellerautomaten akzeptierten Sprachen sind genau die kontextfreien Sprachen. Das sind Sprachen, die eine kontextfreie Grammatik beschreiben kann (Typ 2 der Chomsky-Hierarchie). Die von deterministischen Kellerautomaten akzeptierten Sprachen heißen deterministisch kontextfreie Sprachen. Sie sind eine echte Teilklasse der kontextfreien Sprachen. Jede reguläre Sprache ist auch kontextfrei. Die Sprache aus den Wörtern a^n b^n c^n ist kontextsensitiv, aber nicht kontextfrei.

Für deterministisch kontextfreie Sprachen gibt es LR-Parser. Das sind Verfahren, die beim Lesen von links nach rechts in linearer Zeit entscheiden, ob die Eingabe ein Wort der Sprache ist. Viele in der Praxis verwendete formale Sprachen, insbesondere Programmiersprachen, gehören zu dieser Klasse.