---
 

Institut für Informatik und Praktische Mathematik
Christian-Albrechts-Universität zu Kiel

Übungen zu Implementierung objektorientierter Sprachen
Priv.-Doz. Dr. Wolfgang Goerigk

Serie 4    [PostScript]

---

Abgabetermin für diese Aufgaben ist Mittwoch, der 10. Januar 2001. Bis dahin sollten diese allesamt praktischen Programmieraufgaben fertiggestellt sein.

Am Mittwoch, 10. Januar 2001 findet die Übung im Rechnerraum 709 im 7. Obergeschoss des Hochhauses statt, wo wir uns die Lösungen gemeinsam anschauen wollen.

---


In der Übung haben wir eine (abstrakte) Maschine mit Maschinenprogrammen der Form

    p ::= d1 ... dn { ins1; ...; insk}
    d ::= f <- { ins1; ...; insk}
    ins ::= pushc(c) | pushv(i) | store(i) | jsr(f) | ret() | iret() |
            opr(+) | ... | jmp(k) | branch(k)

kennengelernt, deren Konfiguration  folgende Komponenten enthält: Der Bereich code bindet Unterprogrammnamen f an Felder codef[1 .. k] von Instruktionen, der Laufzeitkeller stack ist eine linear verketteten Liste von Aktivierungsrahmen (stack frames), und der (abstrakte) Instruktionszeiger (p,i) enthält das aktuelle Unterprogramm p und den Index der aktuellen Instruktion (Bytecode) in codep[].  Aktivierungsrahmen sind strukturiert und enthalten einen Operandenkeller opstack, ein Rückkeradressenfeld retaddr, einen Verweis dld auf den Aktivierungsrahmen des dynamisch vorangehenden (aurufenden) Unterprogramms und ein Feld locals[1 .. kf] der lokalen Variablen und Parameter.
 

   
Aufgabe 9 ( Maschinenkonfigurationen, Praktische Hausaufgabe 6 Pkt.)

Schreiben Sie Klassendefinitionen für (Rückkehr)-Adressen, Aktivierungsrahmen (stack frames) und schließlich für Maschinenkonfigurationen. Überlegen Sie sich knappe Repräsentationen (Bytecodes) für die Maschinenbefehle in codef[1 .. k]. Was muss beachtet werden, damit diese Bytecodes allgemein zur Repräsentation beliebiger der obigen Instruktionen verwendet werden können?
 

Hinweis:  Beachten Sie die Java-Klasse Vector aus dem Package java.util. Vektoren können zur Implementierung des Operandenkellers verwendet werden. Beachten Sie ferner, dass zur Implementierung (Interpretation) des Unterprogrammsprungs jsr(f) für f neben dem Code codef[1 .. k] auch die Länge kf des locals[]-Feldes und die Anzahl der formalen Parameter bekannt sein müssen.
 

Abgabetermin: Mittwoch, 10.1.2001
 
 

---


Aufgabe 10 ( Bytecode-Interpretation 1, Hausaufgabe 6 Pkt. )

Maschineninstruktionen bedeuten eine 1-Schritt-Konfigurationstransformation, d.h. die Interpretation einer Instruktion ins (eines Bytecodes) in einer aktuellen Konfiguration k ist eine neue Maschinenkonfiguration , die sich von k durch den Effekt (die Auswirkung)  effect(ins, k) unterscheidet. So ist beispielsweise der Effekt  effect(pushc(c), k) diejenige Konfiguration k´, die sich von k dadurch unterscheidet, dass der Operandenkeller des aktuellen Kellerrahmens um die Konstante c verlängert ist.

Schreiben Sie für die in Aufgabe 9 gewählte Repräsentation von Maschinenkonfigurationen den Effekt der einzelnen Maschineninstruktionen in Programmnotation auf, also beispielsweise für effect(pushc(c), k) etwa in der folgenden Form

   k.stack[.top()].opstack.push(c); k.iptr.index++

Beachten Sie dabei die in der Übung angegebene informelle Definition der Befehle.
 
 

Abgabetermin: Mittwoch, 10.1.2001
 
 

---


Aufgabe 11 (Bytecode-Interpretation 2, Praktische Hausaufgabe 6 Pkt. )

Die Bedeutung einer Maschinenbefehlssequenz ist dann der iterierte Effekt der einzelnen Maschineninstruktionen, die Bedeutung eines Programms folglich der iterierte Effekt der Instruktionen im Hauptprogramm. Wir stellen uns vor, dass die Maschine hält, wenn der Effekt des ret()-Befehls auf eine Konfiguration angewendet werden soll, deren aktueller Kellerrahmen ein leeres retaddr-Feld hat. Die Maschine startet in einer initialen Konfiguration, die durch das Programm bestimmt ist.

Schreiben Sie eine (statische) Methode download, die zu einem Programm p der obigen Form die initiale Maschinenkonfiguration kinit ausrechnet. Dabei besteht der initiale Laufzeitkeller stack aus nur einem Kellerrahmen, der ein leeres retaddr-Feld enthält, der Programmbereich code ist gefüllt mit der Bindung der fi an die zugehörigen Bytecodes und der Bindung des speziellen Namens main an die Bytecodes der Hauptprogramminstruktionen. Der initiale Instruktionszeiger ist (main,1).
 

Abgabetermin: Mittwoch, 10.1.2001
 

---


Aufgabe 12 (Bytecode-Interpretation 3, Praktische Hausaufgabe 6 Pkt. )

Schreiben Sie einen Bytecode-Interpreter, der für Maschinenprogramme der obigen Form und die zugehörige initiale Konfiguration kinit die finale Konfiguration, d.h. die Bedeutung des Maschinenprogramms, berechnet (falls dieses terminiert).
 

Abgabetermin: Mittwoch, 10.1.2001
 
 
 

---