Stapelspeicher

In der Informatik bezeichnet ein Stapelspeicher oder Kellerspeicher (kurz Stapel oder Keller, häufig auch mit dem englischen Wort Stack bezeichnet) eine häufig eingesetzte Datenstruktur. Sie wird von den meisten Mikroprozessoren in der Hardware direkt unterstützt.

Funktionsprinzip

Ein Stapel kann eine beliebige Menge von gleich langen Informationsstrukturen (Objekten) aufnehmen und gibt diese entgegengesetzt zur Reihenfolge der Aufnahme wieder zurück. Dazu stellen Stapel die Operationen

push (einkellern) zum Hinzufügen eines Objektes und
pop (auskellern) zum Zurückholen und Entfernen eines Objektes

bereit. Außerdem steht oft der Operator

peek (nachsehen) zum Holen eines Objektes ohne es zu entfernen

zur Verfügung.

Dabei wird nach dem Last In – First Out-Prinzip (deutsch zuletzt hinein – zuerst heraus, kurz LIFO) gearbeitet, das heißt es wird von pop immer das Objekt aus dem Stapel zurückgegeben, welches als letztes mit push hineingelegt wurde.

In der theoretischen Informatik werden Stapel benutzt, um bestimmte Problemklassen theoretisch betrachten zu können (vgl. Kellerautomat). Sie unterscheidet deshalb genauer zwischen einem echten Kellerspeicher (kurz Keller), bei dem kein Element außer dem obersten gelesen werden kann, und einem Stapelspeicher, bei dem ohne Veränderung der Daten jedes Element betrachtet werden kann (vergleichbar einem Lesezugriff auf einen Array). Diese Unterscheidung spielt jedoch in der Praxis keine Rolle, beinahe jede Implementation ist ein Stapel, daher werden die Begriffe im Allgemeinen synonym verwendet.

Illustration

WikipediaKellerspeicher.png

Ein Stapelspeicher ist mit einen Stapel von Umzugskisten vergleichbar. Es kann immer eine neue Kiste oben auf den Stapel gepackt werden (entspricht push) oder eine Kiste von oben heruntergenommen werden (entspricht pop). Der Zugriff ist immer nur auf das oberste Element des Stapels möglich. Ein Hinzufügen oder Entfernen einer Kiste weiter unten im Stapel ist nicht möglich.

Geschichte

Die Verwendung eines Stapelspeichers zur Übersetzung von Programmiersprachen wurde 1957 von Friedrich Ludwig Bauer und Klaus Samelson unter dem Namen "Kellerprinzip" patentiert. Die lange ausgebliebene internationale Anerkennung und Ehrung ihrer Leistung erfolgte erst im Jahre 1988. Friedrich Ludwig Bauer erhielt (als einziger noch Lebender) den legendären Computer Pioneer Award (IEEE) für Computer Stacks.

Anwendungen

Mikroprozessoren

In Mikroprozessoren gibt es dazu oft ein spezielles Register, den Stackpointer (Stapelzeiger). Dieses Register enthält eine Speicheradresse, die auf den gerade obersten Stapeleintrag zeigt. Wenn mit der Operation push ein weiteres Objekt auf dem Stapel abgelegt wird, dann erhöht sich der Wert des Stapelzeigers und zeigt so auf die nächste Adresse, in die der neue Stapeleintrag geschrieben wird. Bei pop wird der Eintrag der Adresse gelesen und anschließend der Stapelzeiger vermindert, so dass er auf den letzten Stapeleintrag zeigt. Dieses Register kann im Allgemeinen auch direkt gesetzt werden. In manchen Prozessoren wird der Stapelzeiger bei push vermindert und bei pop erhöht. Am Prinzip ändert dies aber nichts.

Der Stapel des Mikroprozessors wird oft von diesem selbst bei Aufruf und Rücksprung von Unterprogrammen zur Speicherung der Rücksprungadresse genutzt, ohne dass ein zusätzliches push oder pop zum Ablegen oder Holen dieser Rücksprungadresse nötig ist, da die entsprechenden Anweisungen das Register selbst richtig setzen.

In Multitasking-Systemen gibt es für jedes Programm einen eigenen Stapelspeicher. Beim Umschalten zwischen Prozessen wird dieser durch direktes Setzen des Stapelzeigers initialisiert.

Moderne Programmiersprachen

Compiler für moderne Programmiersprachen nutzen gewöhnlich push- und pop-Operationen vor dem Aufruf eines Unterprogramms, um an dieses Parameter zu übergeben. Ähnlich können so auch Ergebnisse des Unterprogramms zurückgegeben werden. Lokale Variablen, zum Beispiel von Unterprogrammen, werden ebenfalls auf dem Stapel gespeichert. Für rekursive Programmierung wird dieser Mechanismus nochmal erweitert, indem auch für die lokalen Variablen des Unterprogramms auf dem Stapelspeicher Platz reserviert wird. Bei der Umwandlung einer rekursiven Funktion in eine iterative Funktion muss dieser Mechanismus häufig explizit implementiert werden.

Compiler

Zur Übersetzung des Quellcodes einer Formalen Sprache nutzen Compiler und Interpreter einen Parser, der bei der Textanalyse Syntax-Regeln auf einem Stapel ablegt und so vergleichend dem nachfolgenden Textelement eine angenommene Bedeutung (das oberste Stapelelement) zuordnen kann. Programmiersprachen, die auf eine virtuelle Maschine aufsetzen (zum Beispiel Java, C#, P-Code-Pascal), optimieren den kompilierten Zwischencode für die Verwendung eines Stapels, um zur Laufzeit die Interpretation dieses Zwischencodes zu beschleunigen.

Verarbeitung von Klammerstrukturen

Stapelspeicher eignen sich auch zur Auswertung von Klammerausdrücken, wie sie etwa in der Mathematik geläufig sind. Dabei wird zunächst für Operatoren und Operanden je ein Stapelspeicher initialisiert. Der zu verarbeitende Klammerausdruck wird nun symbolweise eingelesen. Wird eine öffnende Klammer eingelesen, so ist diese zu ignorieren. Wird ein Operand oder Operator eingelesen, so ist dieser auf den jeweiligen Stapelspeicher zu legen. Wird eine schließende Klammer eingelesen, so wird der oberste Operator vom Stapelspeicher für die Operatoren genommen und entsprechend diesem Operator eine geeignete Anzahl von Operanden, die zur Durchführung der Operation benötigt werden. Das Ergebnis wird dann wieder auf dem Stapelspeicher für Operanden abgelegt. Sobald der Stapelspeicher für die Operatoren leer ist, befindet sich im Stapelspeicher für die Operanden das Ergebnis.

Postfixnotation

Zur Berechnung von Termen wird gelegentlich die Postfixnotation verwendet, die mit Hilfe der Operationen eine Klammersetzung und Prioritätsregeln für die Operationen überflüssig macht. Zahlwerte werden automatisch auf dem Stapel abgelegt. Binäre Operatoren (zum Beispiel +, −, *, /) holen die oberen beiden Werte, unäre Operatoren (zum Beispiel Vorzeichenwechel) einen Wert vom Stapel und legen anschließend das (Zwischen-)Ergebnis dort wieder ab.

Infixnotation

Bei der maschinengestützten Auflösung von arithmetischen Ausdrücken in der so genannten Infixnotation (der Operator steht zwischen den beteiligten Zahlwerten) werden zunächst vorrangige Teilterme in einem Stapel zwischengelagert und so faktisch der Infix-Term schrittweise in einen Postfix-Term umgewandelt, bevor das Ergebnis durch Abarbeiten des Stapels errechnet wird.

Stapelorientierte Sprachen

Stapelorientierte Sprachen (z. B. Forth oder Postscript) wickeln fast alle Variablen-Operationen über einen Stapel ab und stellen neben den oben genannten Operatoren noch weitere zur Verfügung. Beispielsweise tauscht der Forth-Operator swap die obersten beiden Elemente des Stapels. Arithmetische Operationen werden in der Postfix-Notation aufgeschrieben und beeinflussen damit ebenfalls den Stapel.

Forth benutzte einen zweiten Stapel (Return-Stapel) zur Zwischenspeicherung der Rücksprungadressen von Unterprogrammen während der Ausführungsphase. Dieser Stapel wird auch während der Übersetzungsphase für die Adressen der Sprungziele für die Kontrollstrukturen verwendet. Die Übergabe und Rückgabe von Werten an Unterprogrammen geschieht über den ersten Stapel, der zweite nimmt die Rücksprungadresse auf.

Literatur

Deutsches Patentamt, Auslegeschrift 1094019, B441221X/42m. Verfahren zur automatischen Verarbeitung von kodierten Daten und Rechenmaschine zur Ausübung des Verfahrens. (Anmeldetag: 30. März 1957. Bekanntmachung der Anmeldung und Ausgabe der Auslegeschrift: 1. Dezember 1960. Dr. Friedrich Ludwig Bauer und Dr. Klaus Samelson, München, sind als Erfinder genannt worden. Erteilt 12. August 1971, DE-PS 1094019.)

Weblinks

Ehrung von Friedrich Ludwig Bauer

Datenstruktur

Gourt Home::Gourt :: Stapelspeicher