3. Beispiel: Quadrupel-Code

• Angabe

• Lösung

• Erklärung

Angabe

VAR
	a: ARRAY[4,20,40] OF LONG;
	b: ARRAY[60] OF INTEGER;
	i,j,k,f: INTEGER;
...
IF NOT((a[i,j,k] > 5) OR (i > j)) THEN
	f := b[j + k];
ELSE
	f := k + i + j;
END
k := k + 1;

Erzeugen Sie für das obige Programmstück Quadrupel-Code nach der Kontrollfluß-methode. Ein LONG ist 8 Byte und ein INTEGER 4 Byte groß. Die Untergrenze aller Indexbereiche ist 0.

Lösung

          t1 := i * 20 
          t2 := t1 + j 
          t3 := t2 * 40 
          t4 := t3 + k 
          t5 := t4 * 8 
          t6 := t5 + adr(a) 
          t7 := @t6 
          if t7 > 5 goto IFfalse 
          goto ORfalse 
ORfalse:  if i>j goto IFfalse 
          goto IFtrue 
IFtrue:   t8 := j + k 
          t9 := t8 * 4 
          t10 := t9 + adr(b) 
          t11 := @t10 
          f := t11 
          goto end 
IFfalse:  t12 := k + i 
          t13 := t12 + j 
          f := t13 
end:      t14 := k + 1
          k := t14

Erklärung

Dieses Beispiel hat zwei Teilaufgaben: Array-Zugriffe und die Auflösung des boolschen Ausdrucks.

Array-Zugriffe

Laut Skriptum wird die Adresse einer indizierten Variablen a[i1,i2,...,ik] durch die folgende Formel berechnet:

((...((i1*n2+i2)*n3+i3)...)*nk+ik)*w+adr(a)

mit nj: Anzahl der Elemente der j-ten Dimension
w: Anzahl der Speichereinheiten für ein Element
adr(a): Anfangsadresse des Arrays a im Speicher

Der Zugriff auf a[i,j,k] ergibt daher die Formel

((i*20+j)*40+k)*8+adr(a)

weil die Definition des Arrays a[4,20,40] OF LONG lautete und außerdem ein LONG 8 Byte groß ist.

Für den Zugriff auf b[j+k] erhalten wir

(j+k)*4+adr(b)

weil die Definition des Arrays b[60] OF INTEGER lautete und ein INTEGER 4 Byte groß ist. Zu beachten ist, daß der (einzige) Index durch den Ausdruck j+k berechnet wird. Das Array ist nur eindimensional, d.h. es muß nur noch mit der Größe eines Elements (hier 4) multipliziert werden.

Für diese beiden Ausdrücke muß Quadrupelcode erzeugt werden, also für den Zugriff auf a zunächst

          t1 := i * 20 
          t2 := t1 + j 
          t3 := t2 * 40 
          t4 := t3 + k 
          t5 := t4 * 8 
          t6 := t5 + adr(a) 

dann erfolgt der Zugriff auf den Wert der Array-Eintrags

          t7 := @t6 

Der Zugriff auf b sieht so aus:

          t1 := j + k 
          t2 := t1 * 4 
          t3 := t2 + adr(b) 
          t4 := @t3

Boolsche Ausdrücke

Für die Übersetzung boolscher Ausdrücke werden die Kapitel 7.6 und 7.7 des Skriptums verwendet.

Bei der Übersetzung boolscher Ausdrücke werdem im Großen und Ganzen nur Labels und Sprünge erzeugt. Dazwischen kommt der Code der für die restlichen Programmstücke benötigt wird.

IF-Anweisung

Wir wollen die Anweisung

IF NOT((a[i,j,k] > 5) OR (i > j))

übersetzen. Wie wir in Abbildung 7.10 des Skriptums sehen, werden bei der IF-Produktion drei neue Label erzeugt. Sie erhalten die Werte

B.true := IFtrue
B.false := IFfalse
end := end

Zwei von ihnen werden damit an die Bedingung B vererbt. An dieser Stelle in der Produktion sehen wir auch, wie der resultierende Code aussehen soll. Wir müssen zuerst den Code der Bedingung B.c generieren, dann das Label B.true (in unserem Fall "IFtrue:"), den Code für den TRUE-Zweig, ein goto end, das Label B.false (in unserem Fall "IFfalse:"), den Code für den FALSE-Zweig und das Ende-Label (in unserem Fall "end:").

NOT-Ausdruck

Doch zunächst steigen wir tiefer hinab in den Baum der Produktionen. Wir müssen den NOT-Ausdruck übersetzen. (Wir merken uns dabei natürlich den Wert der Attribute B.true bzw. B.false.)

Ein NOT-Ausdruck wird ganz einfach übersetzt (beachten Sie die Produktion in Abbildung 7.7 des Skriptums): Das TRUE-Label der eingeschlossenen Bedingung bekommt den Wert des FALSE-Labels und umgekehrt. Die vererbten Attribute an dieser Stelle haben also jetzt die Werte

B.true := IFfalse
B.false := IFtrue


Der generierte Code wird einfach durchgereicht.

OR-Ausdruck

In der Produktion für den OR-Ausdruck sehen wir, daß neue Labels erzeugt werden. Wir erhalten folgende Werte:

B1.true := B.true = IFfalse
B1.false := newlabel = ORfalse
B2.true := B.true = IFfalse
B2.false := B.false = IFtrue


Der zurückgelieferte Code besteht aus dem Code der ersten Bedingung, dem Label B₁.false (also "ORfalse:") und dem Code der zweiten Bedingung.

Bedingung

In der ersten Bedingung wird jetzt endlich wirklich Code erzeugt. Zuerst der Code für die zwei Expressions (in unserem Fall der Zugriff auf das Array a) und danach der Ausdruck

if t7 > 5 goto IFfalse
goto ORfalse

(Die vererbten Attribute B.true bzw. B.false haben an dieser Stelle ja die Werte IFfalse bzw. ORfalse.)

Wichtig: Wir wir bei der Codeerzeugung für den OR-Ausdruck sahen, wird gleich danach das Label "ORfalse:" erzeugt. Obwohl direkt davor der entsprechende Sprungbefehl steht, dürfen beide nicht sofort wegoptimiert werden! Der Code wird ja erzeugt!

Der Code für die zweite Bedingung sieht einfach so aus:

if i>j goto IFfalse
goto IFtrue

Auch in diesem Fall dürfen der Sprungbefehl und das bei der IF-Anweisung erzeugte Label "IFtrue:" nicht wegoptimiert werden, obwohl sie direkt hintereinander stehen.

Jetzt setzen wir die restlichen Codestücke zusammen und erhalten die vollständige Lösung.