M. Sperber, H. Klaeren Wintersemester 1998/99

Compilerbau I

Blatt 2

Abgabe: 3.11.1998

1. [5 Punkte] Implementieren Sie gewöhnliche Mengen als Datentyp, der mit dem Typ seiner Elemente parametrisiert ist. Eine Menge soll dabei durch ihre charakteristische Funktion repräsentiert werden. Realisieren Sie die Operationen Konstruktion einer einelementigen Menge, Element-Test, Vereinigung, Durchschnitt, Differenz und Komplement.
2. [10 Punkte] Geben Sie eine Definition von map unter Verwendung von List.fold_right an, welche selbst nicht rekursiv ist.
3. [10 Punkte] Geben Sie eine Funktion regexp_accepts_empty : 'a regexp -> bool an, so daß regexp_accepts_empty r genau dann true liefert, wenn zur Sprache des regulären Ausdrucks r gehört.
4. [5 Punkte] Beweisen Sie die Korrektheit der in der Vorlesung angegebenen Funktion after_symbol. Funktioniert matches immer noch korrekt, wenn in after_symbol die Funktion concat durch den Konstruktor Concat sowie alternate durch Alternate ersetzt wird?

• Über dieses Dokument ...