 |
|||
| HSG |
|
Übersetzungsschablone für die Bedingung
Bei vielen Programmen stößt man auf Schleifen der Form
while a >= b do begin ... end; .
Eine systematische Behandlung sei hier am Beispiel der Ganzzahlwurzel vorgeführt (Delphiprojekt: ganzzahlwurzel.zip) :
Folgender Pascal-Auszug ermittelt den Ganzzahlanteil w der Wurzel aus n :
w := 0; u := 1;
while n >= u do
begin
n := n-u; u := u+2; w := w+1;
end;
Bei der Behandlung der Bedingung ist zunächst zu bedenken, dass die in der Bedingung vorkommenden Variablen durch die Auswertung nicht verändert werden dürfen. Außerdem muss der "Wert" der Bedingung in einer Variablen, im Folgenden der logische Schalter logS, aufbewahrt werden. Es wird folgendermaßen vorgegangen:
- Zunächst werden die zu vergleichenden Variablen beide auf Null getestet. Sollte mindestens eine der Variablen Null sein, so kann eine Entscheidung gefällt werden (Fälle Fja und Fnein), dh. die Variable logS wird gegebenfalls gesetzt. In dem Fall, dass die zu vergleichenden Variablen beide ungleich Null (Fall Fweiter) sind, werden sie heruntergezählt. Dabei wird zur späteren Restauration eine Hilfsvariable h hochgezählt.
- Konnte eine Entscheidung gefällt werden, so müssen vor der Auswertung der logischen Variablen die zu vergleichenden Variablen restauriert werden.
- Jetzt wird in Abhängigkeit von der logischen Variablen der Schleifenkörper durchgeführt oder gleich an das Ende gesprungen.
- Es darf im ja-Fall nicht vergessen werden, den logischen Schalter zurückzusetzen und anschließend wieder zur Bedingung zu springen.
Der folgende Pascal-Auszug zeigt die Realisierung der genannten Schritte. Bitte die Kommentare beachten. Der eigentliche Schleifenkörper blieb zur Verdeutlichung zunächst unangetastet.
w := 0; u := 1;
logS := 0; h := 0; { logischer Schalter, Hilfsvariable }
{while n >= u do}
{ Fälle ja, nein, noch nicht entscheidbar ermitteln }
B: if n = 0 then goto H1 else goto H2;
H1: if u = 0
then goto Fja else goto Fnein;
H2: if u = 0
then goto Fja else goto Fweiter;
Fweiter: { Herunterzählen }
dec(n); dec(u); inc(h);
goto B;
Fja:
inc(logS);
Fnein:
RB: { Restaurierung im Fall ja und im Fall nein }
if h > 0 then goto RS else goto RE;
RS:
dec(h); inc(n); inc(u);
goto RB;
RE:
{ je nach Bedingung Schleifenkörper ausführen }
if logS > 0 then goto S else goto E;
S:
begin {--------------------------------------------}
n := n-u; u := u+2; w := w+1;
end; {--------------------------------------------}
dec(logS); { logischen Schalter zurücksetzen }
goto B; { Sprung zur Bedingung }
E:
Der Vollständigkeit halber sei die Assembler-gerechte Vereinfachung der Schleife auch gezeigt.
{--------------------------------------------}
{n := n-u;}
MB: { minus-Bedingung }
if u = 0 then goto ME else goto MS;
MS:
dec(n); dec(u); inc(h);
goto MB;
ME:
R2B: { Restaurierung 2 - Bedingung }
if h = 0 then goto R2E else goto R2S;
R2S:
dec(h); inc(u);
goto R2B;
R2E:
{u := u+2;} inc(u); inc(u);
{w := w+1;} inc(w);
{--------------------------------------------}
Das so systematisch ermittelt Bonsai-Assembler-Programm hat gerade die Wurzel aus 30000 ermittelt:
