Zitat von
Penelopee:
...
Also ein Assembler ist definitiv nicht in meinem Programmtext, alles "Hochsprache" (kenne mich Assembler-Code überhaupt nicht aus).
Ich muss wie gesagt hauptsächlich die Funktionsweise des Parsers vorstellen. Aber mir wurde gesagt, dass ich dabei auch auf die Aufgabe des Stacks eingehen soll!
...
ok, das ist deutlich
Zitat von
Penelopee:
...
Ansonsten habe ich es so verstanden, dass wenn er ein Teilproblem gelöst hat (also z.B. den Wert 2*x^3) gelöst hat, so wird dieses Ergebnis an die vorhergehende Funktion geschickt und ersetzt praktisch die Anweisung: TTR(anfang(s,'+')).
...
Exakt. Man kann sogar noch weiter gehen und den Funktionsaufruf TTR selber als Zahl ansehen. Wenn diese Zahl halt noch nicht berechnet ist wird zu dem Programmteil gesprungen (mit Stacknutzung, dazu gleich mehr) der die Berechnung vornimmt und der Rückgabewert *ist* dann die Funktion.
Zitat von
Penelopee:
...
Springt er nun also zurück zu der Zeile, liest das Programm praktisch (nehmen wir jetzt mal x=1 an und berechnen den Term, wobei man als Ergebnis 2 erhält):
2 + TTR(ende(s,'+'))
Da TTR(ende(s,'+')) ein Atomstring ist, wird das sofort berechnet, man erhält als Ergebnis: 3.
...
hier würde ich etwa so formulieren: In TTR(ende(s,'+')) wird sofort ein Atomstring festgestellt und die Zahl die dieser Atomstring repräsentiert wird direkt zurückgegeben.
D.h. der Funktionsaufruf findet statt, das Programm verzweigt 'kurz' wieder in die Funktion TTR, ermittelt quasi sofort den Zahlwert des Atomstrings und gibt diesen zurück (bzw. ersetzt den Funktionsaufruf durch diese Zahl)
Zitat von
Penelopee:
...
Hoffe, ich habe das dann jetzt einigermaßen verstanden!
Danke für eure ganze Mühe,
Penelopee
jo, klingt ganz verständlich so.
Und keine Ursache
Zum Stack würde ich in etwas folgendes sagen:
Der Stack (zu deutsch: Stapel) ist ein Speicherbereich, dessen Verwaltung komplett vom Betriebssystem übernommen wird. Im wesentlichen wird zur Verwaltung und zur Beschreibung lediglich der SP (StackPointer) benötigt, der einfach einen Zeiger auf das erste frei Byte im Stack enthält. Ein Stack funktioniert nach dem 'lifo'-Prinzip (Last In - First Out) das man sich sehr gut mit einem Stapel Karten vorstellen kann. Auf jeder Karte kann genau ein Byte geschrieben werden. Schreibt man nun ein Byte in den Stack passiert folgendes: das Betriebssytem liest den SP, weiss dadurch wo das Byte hinkommt, schreibt es dorthin und erhöht den SP-Zeiger um eins, so das er wieder auf das erste freie Byte zeigt. (Eine Karte wird beschrieben und auf den Tisch bzw. auf den schon existierenden Kartenstapel oben drauf gelegt). Beim lesen eines Bytes verringert das Betriebssytem den SP um 1, erhält so den Zeiger auf das zuletzt geschrieben Byte und liest es aus. (Oberste Karte vom Stapel nehmen, darauf notierten Byte-wert verwenden und Karte wegschmeissen)
Der Stack wird vor allem bei Prozedur- und Funktionsaufrufen verwendet, am Beispiel eines einfachen Funktionsaufrufes sei dies hier beschrieben:
y := cos (0.5);
hmmm, meine family brüllt irgendwas von 'Kaffee', noch 3 Sätze dann muss ich weg. Heute abend evtl. noch mal was wenn noch was unklar ist.
also, das Programm muss der Variablen y eine Zahl zuordnen, es erkennt das dazu der Aufruf eines Unterprogramms namens 'cos' nötig ist. Dazu wiederum braucht es erst das Argument der Funktion (die 0.5). Das Argument liegt explizit vor, dafür ist also kein Funktionsaufruf nötig. Nun nimmt das programm die Adresse hinter dem cos-Aufruf (also nach der schliessenden Klammer) und legt diese Adresse auf den Stack. Zu dieser Adresse soll das Unterprogramm nach getaner Arbeit zurückspringen. Der Zeiger wird der Anzahl der Bytes solch einer Adresse entsprechend erhöht (wie Sirius sagte bei den
Win32 Systemen im Normalfall um 4). Dann wird noch das Argument auf den Stack gelegt und der SP-Zeiger wieder entsprechend des Speicherbedarfs des Arguments erhöht. Nun wird in die Unterroutine 'cos' gesprungen.
Die Unterroutine weiss erst mal gar nichts ausser, das sie aufgerufen wurde. Daher weiss sie, das auf dem Stack ein Argument liegt. Also wird der SP-Zeiger entsprechend verringert und dann das Argument ausgelesen. Nun wird der cos aus dem Argument berechnet. Nun weiss die Unterroutine noch das auch die rücksprungadresse auf dem Stack liegen muss, also SP um 4 verringern und diese Adresse vom Stack lesen. Jetzt wird das Ergebnis der Berechnung (also der cos) auf den Stack geschrieben und der Sp wieder entsprechend erhöht. Auf dem Stack wird die Rücksprungadresse also überschrieben, aber das Unterprogramm hat sie sich natürlich gemerkt. Genau zu dieser Adresse springt nun das Unterprogramm (zurück).
Zurück in der Hauptroutine.... die weiss gar nichts ausser das gerade der vorhergehende Aufruf des cos-Unterprogramms zurückgekehrt ist und deswegen auf dem Stack das Ergebnis liegen muss. Also den SP-Zeiger wieder verringern und das Ergebnis vom Stack lesen. Dem y zuordnen, fertig.
So, der letzte meiner 3 Sätze:
Noch ein paar Anmerkungen
- die Implementierung des Stacks ist Maschinenabhängig. Z. Bsp. kann die SP-Korrektur nach dem Schreiben/vor dem Lesen erfolgen, sie könnte aber auch vor dem Schreiben/nach dem Lesen erfolgen.
- neben dem SP legt das Programm bei jedem Funktionsaufruf noch andere Werte auf den Stack
- erfolgt ein Funktionsaufruf rekursiv, wie in dem besprochenen Parser, kann es bei entsprechender Rekursionstiefe und Argumentgrösse vorkommen, das der Speicherplatz des Stacks nicht ausreicht.
- und @ sirius: ich schaue mir nachher dein Post noch mal an, aber die Interna sind mir tatsächlich auch weniger geläufig, einfach weil für mich nie ein Bedarf bestand den Stack irgendwie direkt zu manipulieren... auf die Schnelle fällt mir folgende Frage auf: Wird der Speicherplatz für das Funktionsergebnis tatsächlich vor dem Funktionsaufruf auf dem Stack reserviert?
die können laut brüllen...
bis denne
mfg
Matthias