Wie verhält sich der Stack bei einem rekursiven Algorithmus?

[Penelopee]

Hallo!

Ich habe hier einen mathematischen Parser, der einen String rekursiv zerlegt.

Quelltext:
if pos0('+',s)>0 then result:=TTR(anfang(s,'+'))+TTR(ende(s,'+')) Quelle: http://delphi.zsg-rottenburg.de/parser.html

Dabei findet die Funktion "pos0" das erste Rechenzeichen, in unserem obigen Fall das '+' in einem String S. Die Funktion "Anfang"
schneidet den Teil des Strings vor dem Rechenzeichen heraus, die Funktion "Ende" dementsprechend den String nach dem Rechenzeichen.

Der mathematische Term wird allgemein in ein Editfeld eingegeben!



Gehen wir nun einmal von dem Beispiel: 2x^2+1 aus.

Der Term wird zunächst in 2x^2 zerlegt, wobei die "1" im Stack gespeichert wird. Anschließend wird x^2 nach meinem Verständnis im Stack gespeichert und die Funktion nur noch mit dem String S='2' aufgerufen. Diesen String kann er nun nicht mehr weiter zerlegen. Er wendet sich nun dem nächsten Teilproblem x^2 zu. Doch wie merkt er sich nun diese 2? Kommt diese auch in den Stack? Oder habe ich das Stackprinzip falsch verstanden? Kann mir mal einer bitte die Funktionsweise des Stacks genau erklären?

Danke im Vorraus,

Penelopee

[sirius]

Auf dem Stack liegen erstmal grundsätzlich:
-(alle) Übergabeparameter
-(alle) lokale Variablen, und zwar von jeder Instanz
-irgendwelche geretteten Register (meist mindestens ebp und esi)
-bei jedem Aufruf einer Funktion, die Rücksprungadresse

ausgleichend kann man noch sagen, dass im Zuge der Optimierung (bzw. aus anderen Gründen) manche Variablen/Übergabeparameter nie auf dem Stack landen, sondern in Registern gehalten werden. Dass erhöht die Zugriffsgeschwindigkeit, allerdings hat man in umfangreichen Funktionen selten Register übrig. Und Delphi übergibt die ersten 3 Parameter einer Funktion immer in Registern (siehe Aufrufkonvention register; C macht das z.B. nicht; hat vor- und nachteile)

Weiterhin gibt es Variablen, die größer sind als 1 Platz im Stack, alos alles was größer als 4 Bytes ist (Strings, Arrays und Records z.B.). Die liegen irgendwo im Speicher (können auch im "Stackbereich" der Funktion liegen, die z.B. den Record angelegt hat) und es wird nur mit Zeigern darauf gearbeitet. Bei einem String ist das generell so, der leigt irgendwo auf dem Heap und in deiner lokalen Variable liegt nur der Zeiger (4 Bytes). So, dann gibts noch die Möglichkeit, Werte im Stack der FPU zu speichern, was im gelegentlich für Fließkommazahlen gemacht wird.

Wenn du es mal genau für deine Funktion wissen willst dann debugge sie doch mal und drücke Strg+Alt+C.


Am Auszug deiner Funktion würde ich jetzt mal vermuten (muss aber nicht sein), dass jede Instanz von TTR min 8*4Bytes benötigt:
-Rücksprungadresse
-Rettung von ebp,esi und edi (ebp:Zeiger für lokale Variablen, esi und edi wird für Stringoperationen benötigt
-Adresse auf s
-Adresse auf anfang
-Adresse auf ende
-result (was auch immer das jetzt ist)
Allerdings könnte es sein, dass ein Strinzeiger in esi gehalten wird. Das kommt letztenendes auf den Compiler an. Wie gesagt schau es dir doch einfach mal an!

[MatWur]

Hallo,

der Stack ist ein Speicherbereich der eigentlich vom System komplett verwaltet wird und auf den der Delphi Programmierer selten zugreifen muss.
Ich versuche es einmal so herum:
Jede Rekursion wird durch eine Abbruchbedingung beendet. In diesem Fall also, wenn ein 'Atomstring' der nicht weiter zerlegbar ist erreicht wurde. Dieser nun vorhandene 'Atomstring' wird nun in ein vorher bereitgestelltes Array aus Strings gespeichert und der Index auf dieses Array um 1 inkrementiert. Dann geht es in der Rekursion einen Schritt zurück, das Programm holt sich den 'Reststring' vom Stack zurück (damit muss sich der Programmierer gar nicht befassen, das macht das System automatisch) und isoliert den nächsten 'Atomstring'. Der wird dann wieder ins Array abgelegt etc. pp.
Wenn die Rekursion dann beendet ist und der komplette String zerlegt wurde liegt dem Programmierer eben dieses sortierte Array an Strings vor das er dann sequentiell abarbeiten kann.

Nochmal zum Stack: wenn Delphi eine Funktion oder Prozedur aufruft (z.Bsp. cos (1.5) ) werden automatisch einige Werte auf den Stack gespeichert, z. Bsp. die Aufrufadresse oder das Argument (in diesem fall also 1.5 ). Innerhalb der Funktion kann dann auf das Argument wie auf eine normale Variable zugegriffen werden. Nach Beendigung der Funktion/Prozedur holt sich das System dann die Aufrufadresse zurück und kann damit zur richtigen Stelle im Hauptprogramm zurückspringen, aber damit hat der Programmierer wie gesagt gar nichts zu tun.

Hoffe es hilft etwas

mfg

Matthias

[Penelopee]

Danke ersteinmal für eure Hilfe!

Ich habe noch ein paar Fragen zum Beitrag von matwur.

Wenn ich dich richtig verstanden habe, so wird der gesamte Strings erstmal in die sogenannten Atomstrings zerlegt, die jeweils in einem Array of String abgespeichert werden.

Jetzt mal meine Frage:
Woher weiß das Programm, was er mit den einzelnen "Atomstrings" machen soll, also welche er miteinander multiplizieren oder potenzieren, etc. muss. Wo wird das festgehalten?
Kannst du vielleicht auch erklären, was es mit dieser Rücksprungadresse auf sich hat?

Sorry, dass ich so primitive Fragen stellen muss, aber mein Wissen über den Stack ist doch sehr beschränkt und muss eine Präsentation für den Informatikunterricht vorbereiten, deswegen danke ich für eure Hilfe!

Mit freundlichen Grüßen,

Penelopee

[SirThornberry]

multiplizieren etc. hat nichts mit den Stack direkt zu tun, das ist aufgabe des Programmierss zu wissen was er rechnen will.
Letzendlich ist der Stack ähnlich wie ein Wäschestabel. Man kann nur oben was drauf legen und auch nur von oben was runternehmen.
Wenn eine Procedure aufgerufen wird, so wird auf dem Stack eben die Adresse abgelegt wo es nach dem Aufruf der Procedure weiter geht.
Bsp.:

Delphi-Quellcode:

//Beim Aufruf von ShowMessage wird auf dem Stack "mein Text" abgelegt und die Adresse wo der Befehl "Beep" steht
//Nach dem ShowMessage also fertig ist wird "mein Text" vom Stack runter genommen und dann die Adresse von "Beep" und dort wird dann hinn gesprungen (ist jetzt alles sehr vereinfacht ausgedrückt
ShowMessage('mein Text');
beep;

Bei Rekursion sieht es nicht anders aus

Delphi-Quellcode:

procedure DoSomeThing();
begin
  DoSomething();
end;

Das ist eine Endlosrekursion und irgendwann läuft der Stack über weil immer wieder eine Rücksprungadresse etc. auf den Stack gelegt wird aber nie wieder was runter genommen wird.

[Penelopee]

Also wenn ich das jetzt richtig verstanden habe, würde das für folgendes Beispiel folgendermaßen ablaufen:

String: '2*x^3+1'

Der Term wird zunächst in 2*x und 1 zerlegt, wobei die 1 in den Stack kommt. Anschließend wird der String 2*x^3 in die 2 und x^3 zerlegt, wobei x^3 in den Stack kommt.
Nun hat man nur noch die 2 und springt mit Hilfe der Rücksprungadresse an die Stelle zurück, an der man sich befand bevor die Funktion ausgelöst wurde, also an die Stelle, wo das Malzeichen steht.


if pos0('*',s)>0 then result:=TTR(anfang(s,'*'))*TTR(ende(s,'*')) Nun wird der String x^3 in gleicher Weise zerlegt. Gleichzeitig merkt sich das Programm mit Hilfe der Rücksprungadresse, dass es nach der Zerlegung von x^3 den Term mit der 2 multiplizieren muss. Dabei wird der Befehl "multipliziere mit der 2" im Arbeitsspeicher(???) festgehalten. Anschließend holt sich das Programm noch die 1 vom Stack und verfährt in gleicher Weise.

Habe ich das so richtig verstanden?

[MatWur]

wegen
if pos0('*',s)>0 ...
weiss das Programm, das es hier multiplizieren muss. Wenn das Quadrat zerlegt wird schreibt der Parser entsprechend
if pos0('^',s)>0 then result:=power(TTR(anfang(s,'^')),TTR(ende(s,'^')))

das Ergebnis wird also direkt nach rekursiver Termbestimmung berechnet, er braucht sich nicht merken welche arithmetische Operation hier ausgeführt wird, das wird gleich gemacht. Beachte das durch die Rekursion die beiden Terme die man für die jeweilige Operation braucht, bereits explizit berechnet sind.

Zitat von Penelopee:

Also wenn ich das jetzt richtig verstanden habe, würde das für folgendes Beispiel folgendermaßen ablaufen:

String: '2*x^3+1'

and diesem Bleistift gehen wir mal die Rekursion durch

-

1. Schritt
if pos0('+',s)>0 then TTR(anfang(s,'+'))+TTR(ende(s,'+'))

der Term 1.1 ist noch kein Atomstring, also wird der weiter zerlegt

2. Schritt
if pos0('*',s)>0 then TTR(anfang(s,'*'))*TTR(ende(s,'*'))

der Term 2.1 ist ein Atomstring, der Term 2.2 wird weiter zerlegt

3. Schritt
if pos0('^',s)>0 then result:=power(TTR(anfang(s,'^')),TTR(ende(s,'^')))

die Potenz wird berechnet und zurück zum 2. Schritt gesprungen. Das Ergebnis der Operation hier ist das Funktionsergebnis von TTR(ende(s,'*')).

2. Schritt zum zweiten
Term 2.1 ist bekannt, Term 2.2 wurde gerade zurückgeliefert also kann gerechnet werden und das jetzige Ergebnis geht als Rückgabewert des Aufrufs TTR(anfang(s,'+')) zurück nach Schritt 1

1 Schritt zum zweiten
Term 1.1 ist nun berechnet, Term 1.2 ist ein Atomstring und kann nun direkt addiert werden.
Jetzt liegt das Endergebnis vor und wird an das aufrufende Hauptprogramm zurückgeliefert.

-

im 1. Schritt muss gar nichts zwischengespeichert werden, im 2. Schritt wird der Term 2.1, also der Atomstring kurz auf den Stack gelegt, dann zur Auswertung der Potenz gesprungen. Wenn dieser Funktionsaufruf zurückkehrt wird der Term 2.1 vom Stack geholt und mit dem Ergebnis der Potenz multipliziert.
Der Stack ist hier nur ein ganz normaler Speicher für kurzzeitig zu sichernde Zwischenwerte. Genauso verhält es sich mit den Adressen der Funktionsaufrufe. Springst du zum Beispiel aus Schritt 2 heraus zum 3. Schritt (zum potenzieren) merkt sich das Programm die Adresse (den Ort von wo losgesprungen wird). Das diese Adresse dabei auf den Stack kommt ist eigentlich auch nebensächlich Wurde die Potenz dann berechnet wird die letzte Adresse vom Stack gelesen und eben dorthin zurückgesprungen. Auf dem Stack liegen natürlich noch andere Adressen von Funktionsaufrufen. Aber es wird immer die letzte Adresse verwendet (und dann der 'Stackpointer', das ist ein Zeiger auf den Stack, korrigiert).

Operationen wie 'multipliziere' werden nie auf den Stack gelegt oder gespeichert, die werden direkt berechnet. Eben durch den rekursiven Aufbau des Parsers wird ja sichergestellt das beide benötigten Terme als Atomstrings zurückgeliefert werden und direkt berechnet werden können. Diese Berechnung liefert nun einen nächsten Atomstring der zur vorherigen Operation zurückgegeben wird oder eben das Endergebnis des Gesamtaufrufes darstellt.
noch'n Bleistift:
if pos0('+',s)>0 then TTR(anfang(s,'+'))+TTR(ende(s,'+'))
TTR(anfang(s,'+')) stellt den Aufruf einer Funktion dar. Durch die Rekursion ergibt der Rückgabewert dieser Funktion einen Atomstring (oder einfach eine Zahl, je nach Auffassung). Dieser Atomstring kommt auf den Stack. Nun wird der 2. Funktionswert durch den Aufruf von TTR(ende(s,'+')) bestimmt, ebenso rekursiv, und ebenso ist der Rückgabewert wieder ein Atomstring. Nun wird die Addition explizit ausgeführt und der neue Atomstring ist fertig und wird wieder zurückgegeben.

ich hoffe jetzt wird's klarer

mfg

Matthias

[sirius]

Also ich habe es mal in Inline-ASM probiert. Unter der vorraussetzung, dass alle Zahlen integer sind, benötigt jede Rekursive Instanz 20 Bytes auf dem Stack. Unter dem habe ich es nicht geschafft und auch der Delphi-compiler wird nicht besser sein. Zudem ist es Quatsch bei solchen Aufgaben um jedes Byte Stack zu knausern.
die Stackplatze sind in 4-Byte-Schrittenm belegt von:
-Rücksprungadresse
-rettung des EBP (als Referenz vür lokale Variablen)
-Result der Funktion
-String der an die Funktion übergeben wird
-der aktuelle Teilstring (aus der Funktion Anfang bzw. Ende --- bei mir getstring)

Wenn man statt integer double nehmen würde, wären es nochmal 4 Bytes mehr (bei result)

Das Programm liegt im Anhang.

-----------------------

Zitat:

im 1. Schritt muss gar nichts zwischengespeichert werden,

Doch, auch in dem Beispiel. Du musst dir doch den Zeiger auf s merken, dann das Ergebnis von Anfang und das Zwischenergebnis aus TTR(anfang...). Genau dasselbe, wie ich oben beschrieben habe.

Zitat:

Der Stack ist hier nur ein ganz normaler Speicher für kurzzeitig zu sichernde Zwischenwerte.

Aber genau diese Zwischenwerte müssen wir uns merken, wenn wir die nächste Instanz von TTR aufrufen.

Wenn wir aber mal von den "Interna" absehen, hat MatWur schon Recht.

[MatWur]

hmmm ... wenn Penelopee hauptsächlich den Parser beschreiben soll denke ich das das Problem an der Rekursion liegt, wenn sie aber den Stack beschreiben soll würde ich den Parser ganz raushauen (der Rekursion wegen) und eher den Ablauf eines normalen (nicht rekursiven) Funktionsaufrufes beschreiben. Das ein rekursiver Funktionsaufruf dann entsprechend mehr Speicherplatz auf dem Stack braucht sollte klar sein. Ich habe den Quellcode nur überflogen aber kein Assembler gesehen, alles Hochsprache. Auch einen direkten Bezug zum Stack innerhalb des Parsers (ausser das er implizit genutzt wird) habe ich nicht gefunden. Die Hochsprache soll ja den Programmierer gerade von solchen (maschinenabhängigen) Details befreien.
Vielleicht kann Penelopee noch einmal genauer spezifizieren, was erklärt werden soll...

mfg

Matthias

[Penelopee]

Hallo!

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!

Ich wollte eigentlich noch eine Sache fragen, was jetzt aber sirius schon beantwortet hat, nämlich ob bei dem ersten Schritt nicht zumindest die Rücksprungadresse in den Stack kommen muss!

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,'+')).

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.

Hoffe, ich habe das dann jetzt einigermaßen verstanden!

Danke für eure ganze Mühe,

Penelopee