M. Sperber, H. Klaeren Wintersemester 1997/98

Compilerbau I

Blatt 7

Abgabe: 11.12.1997

1. [5 Punkte] Schreiben Sie eine Funktion

   rename_uniquely : Ident.t program -> Ident.t program

   welche alle gebundenen Namen eines Programms unter Semantikerhaltung derart umbenennt, daß jeder Name nur einmal gebunden wird. Die Umbenennung soll so erfolgen, daß kein programmgebundener Bezeichner den gleichen Namen trägt wie ein Builtin. (Für die Lösung der Aufgabe ist es sinnvoll, die Struktur Ident zu erweitern und eine Referenz zu benutzen.)
2. [10 Punkte] Implementieren Sie ein Lösungsverfahren für reine Vereinigungsprobleme. Gegeben sei also eine Relation auf einer Menge A und eine mengenwertige Funktion . Gesucht ist eine Funktion , welche folgende Gleichung löst:

   

3. [5 Punkte] Welche Zeitkomplexität hat Lambda-Lifting? Wählen Sie zur Berechnung einen beliebigen Algorithmus für die Lösung des Vereinigungsproblems.
4. [10 Punkte] Implementieren Sie Lambda-Lifting als Abbildung

   caml_to_lambda : 'ident Camlsyn.program -> 'ident Lambda.scheme

   Wählen Sie dabei den Aufruf einer Funktion main : unit -> unit als Eintrittspunkt. Sie können dabei annehmen, daß in der abstrakten Syntax alle Bezeichner wie in Aufgabe 1 umbenannt worden sind. Ignorieren Sie dabei (für den Moment) raise und try.

• Über dieses Dokument ...