M. Sperber, H. Klaeren Wintersemester 1998/99

Compilerbau I

Blatt 4

Abgabe: 17.11.1998

1. [15 Punkte] Implementieren Sie in der Struktur Grammar Funktionen für und mit der folgenden Signatur:

   first : ('n, 't, 'attrib) grammar -> int
             -> ('n, 't) symbol list
               -> 't list list
   follow : ('n, 't, 'attrib) grammar -> int -> 'n
             -> 't list list

   Legen Sie die Implementation so an, daß first g k eine Funktion liefert, die effizient arbeitet.

   Hinweis: Benutzen Sie Fixpunktiteration und Lemma 2.4.

2. [5 Punkte] Zeigen Sie, daß sowohl der Parser mit rekursivem Abstieg als auch jener mit rekursivem Aufstieg die Eigenschaft des fortsetzungsfähigen Präfixes hat: Jeder von einem solchen Parser konsumierter Präfix (nicht eingeschlossen der Lookahead) kann zu einem Wort der Sprache fortgesetzt werden.
3. [3 Punkte] Was für Mehrdeutigkeiten können beim Parsen mit rekursivem Aufstieg auftreten?
4. [7 Punkte] Implementieren Sie Yacc-artige Fehlerbehandlung für den Parser aus der Vorlesung.

• Über dieses Dokument ...