Aufgaben zur Vorlesung

Aufgabe 1:

Schreiben Sie ein dem obigen funktionalen Programm äquivalentes Programm in C++ (oder Java) und lassen dieses laufen. Was stellen Sie fest? Was schließen daraus über die Auswertungsreihenfolge von C?

Aufgabe 2:

Schreiben Sie das obige Programm mit einen Texteditor ihrer Wahl. Speichern Sie es als FirstProgram.java ab. Übersetzen Sie es mit dem Java-Übersetzer javac. Es entsteht eine Datei FirstProgram.class. Führen Sie das Programm mit dem Javainterpreter java aus. Führen Sie dieses sowohl einmal auf Linux als auch einmal unter Windows durch.

Aufgabe 3:

Sollten Sie mit Java noch nicht vertraut sein, so kompilieren Sie die beiden obigen Klassen. Schreiben Sie eine minimale Testklasse, die ein Paar und eine Liste erzeugt und auf dem Bildschirm ausgibt. (Hinweis: in der nachfolgenden Aufgabe finden Sie ein Beispiel für eine main-Methode und den Ausgabebefehl println.)In dieser Aufgabe soll hauptsächlich der Umgang mit Javacompiler und Interpreter geübt werden. Eine kleine Testklasse könnte dann wie folgt aussehen: 
package name.panitz.util;
public class TestLi {
  public static void main(String [] args){
    System.out.println(new Pair<String,Integer>("hallo",42));
    System.out.println(new Li<String>());
    System.out.println(
          new Li<String>("hallo"
         ,new Li<String>("welt"
         ,new Li<String>())));
  }
}

Aufgabe 4:

Mit den zwei oben vorgestellten Klassen, lassen sich Abbildungen realisieren. Eine endliche Abbildung läßt sich als Liste von Schlüssel/Wert-Paaren darstellen. Schreiben Sie eine in einer Klasse eine statische Methode mit folgender Signatur:
public static <keyType,valueType> 
valueType lookUp(keyType key,Li<Pair<keyType,valueType>> map)
lookUp soll für ein Schlüsselobjekt einen entsprechend damit gepaarten Wert in einer Liste von Paaren nachschlagen.

Testen Sie Ihre Methode mit folgender Testklasse:

package name.panitz.util;
public class TestStaticMap {
 public static void main(String [] args){

  Li<Pair<String,Integer>> notenliste =
    new Li<Pair<String,Integer>>(
       new Pair<String,Integer>("john",4),
    new Li<Pair<String,Integer>>(
       new Pair<String,Integer>("paul",3),
    new Li<Pair<String,Integer>>(
       new Pair<String,Integer>("george",1),
    new Li<Pair<String,Integer>>(
       new Pair<String,Integer>("ringo",4),
    new Li<Pair<String,Integer>>(
       new Pair<String,Integer>("stu",2),
    new Li<Pair<String,Integer>>())))));

  System.out.println(notenliste);
  System.out.println(StaticMap.lookUp("george",notenliste));
  System.out.println(StaticMap.lookUp("stu",notenliste));
  System.out.println(StaticMap.lookUp("pete",notenliste));
 }
}
Der Rumpf der Methode hat tatsächlich nur drei Zeilen. Wer bisher keine Erfahrung in Java hatte, wird wahrscheinlich statt des Aufrufs der Methode equals den Operator == verwendet haben. 
package name.panitz.util;
public class StaticMap {
  public static <keyType,valueType> 
  valueType lookUp(keyType key,Li<Pair<keyType,valueType>> map){
    if (map.isEmpty()) return null;
    if (map.head().e1.equals(key)) return map.head().e2;
    return lookUp(key,map.tail());
  }
}

Aufgabe 5:

Schreiben Sie jetzt eine generische Klasse MyMap<keyType,valueType>, die den Typ Li<Pair<keyType,valueType>> erweitert. Implementieren Sie in der Klasse MyMap die Methode
public valueType lookUp(keyType key),
die für ein Schlüsselobjekt das mit diesem Schlüssel gepaarte Wertobjekt zurückgibt.

Testen Sie Ihre Implementierung mit folgender Klasse:

package name.panitz.util;
public class TestYourMap {
  public static void main(String [] args){
    MyMap<String,Integer> notenliste
     =  new MyMap<String,Integer>("john",4,
        new MyMap<String,Integer>("paul",1,
        new MyMap<String,Integer>("george",1,
        new MyMap<String,Integer>("ringo",5,
        new MyMap<String,Integer>("stu",2,
        new MyMap<String,Integer>())))));

    System.out.println(notenliste.lookUp("john"));
    System.out.println(notenliste.lookUp("george"));
    System.out.println(notenliste.lookUp("pete"));
  }
}

Aufgabe 6:

Implementieren Sie eine zu NNum analoge Klasse NChar, die primitive Zeichen (char) im Heap darstellen kann.

Aufgabe 7:

Implementieren Sie die Klasse NInd, die Indirektionsknoten im Heap darstellt.

Aufgabe 8:

Schreiben Sie ähnlich der Klasse EinsZwei eine kleine Testmethode, die den Graph aus Abbildung erzeugt.

Aufgabe 9:

Implementieren Sie in der Klasse GmHeap eine aussagekräftige Methode toString.

Aufgabe 10:

Implementieren Sie eine Klasse Pop, die den G-Maschinenbefehl Pop umsetzt.

Aufgabe 11:

Implementieren Sie eine Klasse Slide, die den G-Maschinenbefehl Slide umsetzt.

Aufgabe 12:

Implementieren Sie eine Klasse PushChar, die den G-Maschinenbefehl PushChar umsetzt.

Aufgabe 13:

Implementieren Sie den Rumpf Methode process nach entsprechender Spezifikation. Beachten Sie auch hier wieder, zunächst mit dem garbage collector zu checken, ob es freie Heapzellen gibt.

Aufgabe 14:

Implementieren Sie die Klassen Sub, Mult und Div.

Aufgabe 15:

Schreiben Sie die Klassen für die übrigen Vergleichsoperatoren: Eq, Gt, Ge und Le.

Aufgabe 16:

Implementieren Sie die Klasse MkAp, die den entsprechenden G-Maschinenbefehl realisiert. Denken Sie wieder daran, zunächst einen Check vom garbage collection Objekt durchführen zu lassen.

Aufgabe 17:

Implementieren Sie die Klasse Update.

Aufgabe 18:

Führen Sie die manuelle Ausführung des Programm square in der G-Maschine fort. Zeichnen Sie für jeden Ausführungsschritt Heap und Stack der Maschine.

Aufgabe 19:

Schreiben Sie ein kleines Testprogramm, das den Code für das Programm square in der G-Maschine ausführt.

Aufgabe 20:

Es war ein mühsames Geschäft, die G-Maschine von Hand auszuführen. Schön wäre eine spezielle G-Maschine die Schrittweise alle Zustände, die sie bei der Ausführung durchläuft, loggt.

In objektorientierten Sprachen läßt sich dieses leicht implementieren, indem eine Unterklasse von GmState geschrieben wird, die nur die Methode evalStep überschreibt, so daß in dieser Methode vor dem Aufruf der gleichen Methode aus der Oberklasse, der Maschinenzustand auf die Konsole ausgegeben wird.

{System.out.println(this);super.evalStep();}
Schreiben Sie eine solche Unterklasse GmStateLog und führen Sie mit dieser den Code aus der letzten Aufgabe aus.

Aufgabe 21:

Implementieren Sie die Klasse Jump.

Aufgabe 22:

Jetzt sind Sie dran. Ergänzen Sie die Switschanweisung für alle weiteren Befehle der G-Maschine. In der Klasse DataInputStream stehen Ihnen Methoden ReadInt und readChar zur verfügung.

Aufgabe 23:

Mit der obigen Klasse ForwardNode läßt sich eine Garbage Collecion für die G-Maschine umsetzen. Schreiben Sie eine Klasse TwoSpaceCopyGC, die die Klasse GC erweitert. Sie hat einen Konstruktor, in dem die Maschinenzustandsobjekt übergeben wird:
  public TwoSpaceCopyGC(GmState st)
Beim Aufruf von check(i) sollen, falls keine i Speicherplätze mehr im Heap sind, alle noch gebrauchten Heapknoten in einen neuen Heap copiert werden. Der neue Heap wird schließlich der neue Heap im Maschinenzustand. Denken Sie daran auf Stack und den im Dump gespeicherten Stacks abgelegten Adressen auf die Adressen im neuen Heap abgelegt werden müssen. Vergessen Sie nicht auch die globalen Funktionsknoten des Heaps zu kopieren.

Aufgabe 24:

Erweitern Sie die obige Grammatik so, daß sie mit ihr auch geklammerte arithmetische Ausdrücke ableiten können. Hierfür gibt es zwei neue Terminalsymbole: ( und ).

Schreiben Sie eine Ableitung für den Ausdruck: 1+(2*20)+1

Aufgabe 25:

Betrachten Sie die einfache Grammatik für arithmetische Ausdrücke aus dem letzten Abschnitt. Zeichnen Sie einen Syntaxbaum für den Audruck 1+1+2*20.

Aufgabe 26:

Implementieren Sie einen Parser für die Sprache Fab4. Hierzu ist für die folgende Header-Datei eine Implementierung zu erstellen:
#ifndef __FAB4PARSER_H
#define __FAB4PARSER_H 

#include "../name/panitz/parser/ParsLib.h"
#include "Fab4.h"
#include "Fab4Lexer.h"
#include <string>
#include <iostream>

using namespace name::panitz::parser;
using namespace std;

namespace fab4 {
ParsResult<Fab4*,Token>* parsFab4(string fileName);
}
#endif
Ihr Programm wird etwas übersichtlicher und leichter zu lesen, wenn sie sich der Möglichkeit von Typsynonymen bedienen. Folgende Typsynonyme sind dabei sinnvoll:
typedef CAF<Parser<Token*,Token>*>         PToken;
typedef CAF<Parser<Operator*,Token>*>      POperator;
typedef CAF<Parser<Number*,Token>*>        PNumber;
typedef CAF<Parser<StringLiteral*,Token>*> PStringLit;
typedef CAF<Parser<CharLiteral*,Token>*>   PCharLit;

Aufgabe 27:

Testen Sie Ihren Parser mit folgendem kleinen Hauptprogramm anhand einer Reihe unterschiedlicher Fab4-Programme. 
#include "Fab4Parser.h"
using namespace fab4;
using namespace name::panitz::parser;

int main(int argc,char* args[]){
  vector<Token*> xs;  

  cout<<"PairCount: "<<PairCount<<endl;
  cout<<"ParsResultCount: "<<ParsResultCount<<endl;

  ParsResult<Fab4*,Token>* res = parsFab4(args[1]);
  cout<<show(res)<<endl;

  cout<<"PairCount: "<<PairCount<<endl;
  cout<<"ParsResultCount: "<<ParsResultCount<<endl;
}

Aufgabe 28:

Ergänzen Sie den Rumpf der Methode eval für NumExpr, so daß der korrekte G-Maschinencode dem Ergebnisvektor result zugefügt wird.
    virtual void eval(NumExpr* arg){
    }

Aufgabe 29:

Ergänzen Sie den Rumpf der Methode eval für Variablennamen, so daß der korrekte G-Maschinencode dem Ergebnisvektor result zugefügt wird.

Um zu testen, ob der Variablenname ein Funktionsname ist benutzen Sie die Funktion contains aus Modul Instruction mit folgender Gleichheitsfunktion: 

    static bool stringEq(string s1,string s2){return s1==s2;}
    virtual void eval(Var* arg){
    }

Aufgabe 30:

Ergänzen Sie den Rumpf der Methode eval für Funktionsapplikationen App, so daß der korrekte G-Maschinencode dem Ergebnisvektor result zugefügt wird.
    virtual void eval(App* arg){
    }

Aufgabe 31:

Ergänzen Sie den Rumpf der Methode eval für Operatorausdrücke OpExpr, so daß der korrekte G-Maschinencode dem Ergebnisvektor result zugefügt wird.
    virtual void eval(OpExpr* arg){
    }

Aufgabe 32:

Ergänzen Sie den Rumpf der Methode eval für Zeichenkonstanten CharExpr, so daß der korrekte G-Maschinencode dem Ergebnisvektor result zugefügt wird.
    virtual void eval(CharExpr* arg){
    }

Aufgabe 33:

Ergänzen Sie den Rumpf der Methode eval für Konstruktoraufrufe Constr, so daß der korrekte G-Maschinencode dem Ergebnisvektor result zugefügt wird.
    virtual void eval(Constr* arg){
    }

Aufgabe 34:

Ergänzen Sie den Rumpf der Methode eval für case-Ausdrücke caseExpr, so daß der korrekte G-Maschinencode dem Ergebnisvektor result zugefügt wird.
    virtual void eval(CaseExpr* arg){
Diese Lösung ist weit von einer Musterlösung entfernt. Insbesondere der neue Besucher, der mit new erzeugt wird, sollte auch wieder aus dem Speicher gelöscht werden. Auch sonst idt die Lösung unübersichtlich und kaum mehr zu verstehen.
      arg->e1->visit(this);
      result->insert(result->end(),new Eval());
      vector<CaseAlt*>* alts = arg->alts;
      vector<int>* jumpPointToEnd= new vector<int>();
      vector<Instruction*>* code=new vector<Instruction*>();

      CaseJump* jump=new CaseJump();
      result->insert(result->end(),jump);
      int startAddress = 0;
      for (int i=0;i<alts->size();i++){
        CaseAlt* alt=(*alts)[i];
        (*jump)[constructors[alt->constr]]=startAddress;

        vector<Instruction*>* altCode=new vector<Instruction*>();
        int n= alt->vars.size();
        altCode->insert(altCode->end(),new Split(n));
        vector<Pair<string,int> > newEnv=env;
        for (int j=0;j<env.size();j++)
          newEnv[j].snd=newEnv[j].snd+n;
        for (int j=0;j<n;j++){
          newEnv.insert(newEnv.begin(),Pair<string,int>(alt->vars[j],j));
        }
        alt->alt->visit(new GenExprCode
         (altCode,newEnv,functions,constructors,constructorArity));
        altCode->insert(altCode->end(),new Slide(n));
        altCode->insert(altCode->end(),new Jump(0));
        code->insert(code->end(),altCode->begin(),altCode->end());;
        startAddress=code->size(); 
        jumpPointToEnd->insert(jumpPointToEnd->end(),startAddress-1);
     }
     for (int i=0;i<jumpPointToEnd->size();i++){
      int jumpPoint=(*jumpPointToEnd)[i];
      (*code)[jumpPoint]=new Jump(startAddress-jumpPoint-1);
     }
     result->insert(result->end(),code->begin(),code->end());;

    }