3. Beispiel: Quadrupel-Code

Angabe

VAR
	a: ARRAY[5,10,20] OF LONG;
	r: LONG;
	i,j,k: INTEGER;
...
WHILE (j<10) AND (NOT ((j>i) OR (j>k)) ) DO
	r := a[i,j,20-j];
	j := j + 1;
END

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

Wbegin:
	if j<10 goto ANDtrue
	goto Wfalse
ANDtrue:
	if j>i goto Wfalse
	goto ORfalse
ORfalse:
	if j>k goto Wfalse
	goto Wtrue
Wtrue:
	t1 := i * 10
	t2 := t1 + j
	t3 := t2 * 20
	t4 := 20 - j
	t5 := t3 + t4
	t6 := t5 * 8
	t7 := t6 + adr(a)
	t8 := @t7
	r := t8
	t9 := j + 1
	j := t9
	goto Wbegin
Wfalse:

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[i₁,i₂,...,i_k] durch die folgende Formel berechnet:

((...((i₁*n₂+i₂)*n₃+i₃)...)*n_k+i_k)*w+adr(a)
mit n_j: 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,20-j] ergibt daher die Formel

((i*10+j)*20+(20-j))*8+adr(a)

weil die Definition des Arrays a[5,10,20] OF LONG lautete, der dritte Index durch 20-j berechnet wird und außerdem ein LONG 8 Byte groß ist.

Der Quadrupelcode für diesen Ausdruck ist

t1 := i * 10
t2 := t1 + j
t3 := t2 * 20
t4 := 20 - j
t5 := t3 + t4
t6 := t5 * 8
t7 := t6 + adr(a)

dann erfolgt der Zugriff auf den Wert der Array-Eintrags

t8 := @t7

Boolsche Ausdrücke

Für die Übersetzung boolscher Ausdrücke werden die Kapitel 7.6 "Boolesche Ausdrücke" und 7.7 "Kontrollanweisungen" 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.

WHILE-Anweisung

Wir wollen die Anweisung

WHILE (j<10) AND (NOT ((j>i) OR (j>k)) ) DO

übersetzen. Wie wir in Abbildung 7.10 "Übersetzung von Kontrollanweisungen bei der Kontrollfluß-Methode" des Skriptums sehen, werden bei der WHILE-Produktion drei neue Label erzeugt. Sie erhalten die Werte

begin := Wbegin B.true := Wtrue B.false := Wfalse

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 das Label begin generieren, dann den Code der Bedingung B.c, das Label B.true, den Code für die Schleife, ein "goto Wbegin" und zuletzt das Label B.false.

In unserem Fall kommt dieses Codefragment heraus:

Wbegin:
	<B.c>
Wtrue:
	<S1.c>
	goto Wbegin
Wfalse:

AND-Ausdruck

Die Bedingung B aus der obigen Produktion ist - wie wie aus der Klammerung sehen - eine AND-Verknüpfung aus den beiden Bedingungen

B₁: (j<10)

und

B₂: (NOT ((j>i) OR (j>k)) )

Aus Abbildung 7.7 "Übersetzung Boolescher Ausdrücke nach der Kontrollfluß-Methode" sehen wir, welche Labels dafür erzeugt bzw. vererbt werden

B₁.true := newlabel = ANDtrue B₁.false := B.false = Wfalse B₂.true := B.true = Wtrue B₂.false := B.false = Wfalse

und welcher Code dafür erzeugt wird:

	<B1.c>
ANDtrue:
	<B2.c>

Den Code für B1.c können wir gleich hinschreiben (siehe Bedingungen). Dieser ist ganz einfach

	if j<10 goto ANDtrue
	goto Wfalse

Der Code für B2.c ist etwas schwieriger, weil er einen weiteren, verschachtelten Booleschen Ausdruck verbirgt: NOT und OR

NOT-Ausdruck

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 := Wfalse B.false := Wtrue

Der generierte Code wird einfach durchgereicht.

OR-Ausdruck

Der OR-Ausdruck besteht aus den beiden Bedingungen

B₁: (j>i)

und

B₂: (j>k)

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

B₁.true := B.true = Wfalse B₁.false := newlabel = ORfalse B₂.true := B.true = Wfalse B₂.false := B.false = Wtrue

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

	<B1.c>
ORfalse:
	<B2.c>

1. Bedingung

Nach der Belegung der Labels gilt für B1.c

	if j>i goto Wfalse
	goto ORfalse

2. Bedingung

Nach der Belegung der Labels gilt für B2.c

	if j>k goto Wfalse
	goto Wtrue

Bedingungen

Bei den relationalen Operatoren wird jetzt endlich wirklich Code erzeugt und zwar nach dem Muster

	if <E1.c> <rop.x> <E2.c> goto <B.true>
	goto <B.false>

Für <E1.c> bzw. <E2.c> wird dann der Code für den jeweilige Ausdruck eingefügt, der ja auch eine Berechnung oder eine Konstante sein kann. <rop.x> ist das Zeichen für den relationalen Operator.

Achtung! Wie wir hier sehen, werden ganz stur irgendwelche Sprungbefehle auf irgendwelche Labels erzeugt. Die Werte der entsprechenden vererbten Attribute werden jedoch nicht berücksichtigt. Dadurch kommt es immer wieder zu Sprüngen auf die nachfolgende Adresse. Diese Sprungbefehle dürfen jedoch zu diesem Zeitpunkt nicht entfernt werden. Der Code wird ja erzeugt!

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

Alex's University Page / Alex's Home Page / alex@complang.tuwien.ac.at
TEL +43 1 58801-4463, FAX +43 1 5057838