Fortsetzung Hauptstudium

Praktikum Compilerbau, 6tes Semester

Ein Beispiel-Compiler in Java

Ein Beispielprogramm

program test
declare {
    b : boolean;
    a : integer
}
run {
    if b == true then { 
        b = false
    }
    else {
        a = 10 + 20 * 2 / 2
    };
    
    b = !! b;
    
    while a >= 0 do
    {
        a = a - 1;
        b = ! b
    };
    
    for i = 0 to 100 do
    {
        b = i > 50
    }
}

Starten des Compilers

    java -jar testCompiler.jar test
	

Erweiterungen

Logische Programmierung

% Fakten:
weiblich(anna).           % Anna ist weiblich
weiblich(trientje).       % Trientje ist weiblich
mutter(trientje, anna)    % Die Mutter von Trientje ist Anna

% Regel:
tochter(Elternteil, Tochter) :-
    weiblich(Tochter),                  % muss weiblich sein UND
        ( mutter(Tochter, Elternteil);  % und Elternteil ist Mutter
          vater(Tochter, Elternteil) ). % ODER Vater

Kombinatorische Optimierung

Simplex ... ein Verfahren zur Optimierung von linearen Problemen. Das Verfahren beruht auf dem Gauss-Jordan Algorithmus mit einer speziellen Pivotsuche. Es werden die Kanten eines konvexen Polyeders durchlaufen, eine der Ecken stellt eine optimale Lösung dar, sofern eine solche existiert. In der Dokumentation steht dann noch mehr dazu (auch in den Vorlesungsmitschrieben)

Blocksatz ... Hier ging es darum einen Text so zu rücken, dass das die Summe der Quadrate der Leerstellen zu einem gegebenen Rand über den gesamten Text minimiert wird. Die Aufgabe war zur Lösung des Problems Dynamische Programmierung zu verwenden. Es lässt sich wohl ähnlich wie die Kettenmultiplikation von Matrizen lösen. Unser Ansatz ist zwar dynamisch, unterscheidet sich aber von der Umsetzung von dem der Kettenmultiplikation.

TSP Traveling Salesman Problem. Hier war die Aufgabe dieses allgemein bekannte Problem mit verschiedenen Algorithmen zu lösen. Wir haben uns für Branch And Bound, Great Deluge, Ant Colony Optimisation entschieden. Das besondere an dem Programm dürfte die schöne Oberfläche sein, mit der man Graphen zeichnen / oder über eine Entfernungsmatrix definieren kann.
Die Algorithmen können schrittweise ausgeführt werden, wobei die (Zwischen) Ergebnisse auf verschiedene Arten graphisch dargestellt werden. Das Programm enthält eine Online Hilfe und benötigt JRE1.4 (Erhältlich bei java.sun.com).

RSA Demo

RSA Demo ist ein kleines Programm, dass graphisch den Verschlüsselungsalgorithmus von RSA verdeutlicht. Man kann einen Satz verschlüsseln (Bob), versuchen ihn zu knacken (Eve) und natürlich auch wieder entschlüsseln (Alice). Das ganze ist ein Java-Programm, dass begleitend einen HTML Text enthält, der sich mit der rechtlichen Seite und der Theorie von RSA beschäftigt. Diese Hilfe wurde mit Latex2HTML erstellt. JRE1.4 ist aufgrund der besseren HTML Anzeige wünschenswert.