M. Sperber, H. Klaeren Wintersemester 1997/98

Compilerbau I

Blatt 2

Abgabe: 4.11.1997

1. [5 Punkte] Schreiben Sie eine Caml-Funktion lcs : string -> string -> string, so daß die längste gemeinsame Teilfolge zweier Zeichenketten x und y liefert. (So ist tie die längste gemeinsame Teilfolge von striped und tiger.)

   Schreiben Sie außerdem eine Funktion diff : string -> string -> int, so daß die Distanz zweier Zeichenketten berechnet, also die minimale Anzahl von Einfügungen und Löschungen, die erforderlich sind, um x in y zu überführen.

2. [5 Punkte] Ändern Sie den in der Vorlesung angegebenen Code für lexikalische Analyse derart, daß er
   • Streams (siehe die Caml-Bibliothek Stream) statt Listen als Eingabe akzeptiert und
   • Zeilen und Spalten mitzählt und diese sowohl in Fehlermeldungen erwähnt als auch in der Ausgabe des Scanners durchreicht.
   Was für Konsequenzen ergeben sich für die Signatur der Struktur Lex? Falls es negative sind, wie lassen sich diese korrigieren?
3. [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?
4. [5 Punkte] Beschreiben Sie, wie die unterschiedlichen Kommentarkonventionen für C und Caml mit dem in der Vorlesung angegebenen Scanner behandelt werden können.
5. [10 Punkte] Geben Sie mit Hilfe des in der Vorlesung angegebenen Codes die Definition eines Scanners für Caml gemäß der Abschnitte ,,Lexical Conventions`` und ,,Names`` (dort nur bis einschl. label-name) in der Caml-Dokumentation an. Die Beschreibung soll Literale richtig interpretieren, also z.B. den Wert von Integer-Literalen berechnen und Escape-Sequenzen in Zeichenketten und Zeichen auflösen. Ignorieren Sie Fließkomma''=Konstanten.

• Über dieses Dokument ...