Übersetzerbau	WS 98/99 Heckmann Pape
8. Übungsblatt

 

Aufgabe 1 (2 + 3 + 3 + 1 + 3 + 3 + 2 Punkte)

Gegeben sei die folgende Grammatik mit den Nichtterminalen S', E, T, F, den Terminalen v, (, ), +, * und den Produktionen

S'  ->   E
E   ->   TE'
E'  ->   +T | -T | epsilon
T   ->   FT'
T'  ->   *F | epsilon
F   ->   (E) | v
 

1. Stellen Sie fest, welche der Nichtterminale und Produktionen epsilon produzieren können. Schreiben Sie dazu das Gleichungssystem für E(k) hin und löse es mit einer beliebigen Methode.
2. Berechnen Sie die Fi-Mengen für die einzelnen Nichtterminale und Produktionen. Schreiben Sie dazu das Fi-Gleichungssystem als reines Vereinigungsproblem auf, zeichnen Sie den Graphen dazu und erstellen Sie mit Hilfe des Graphen eine Tabelle der Fi-Mengen.
3. Berechnen Sie die Fo-Mengen für die einzelnen Nichtterminale und Produktionen. Gehen Sie dabei wie in (b) vor.
4. Weisen Sie nach, daß die Grammatik die LL(1)-Eigenschaft besitzt.
5. Generieren Sie eine LL(1)-Parser-Tabelle für die Grammatik.
6. Generieren Sie schematisch (ohne Optimierungen) einen LL(1)-Parser in Programmversion für die Grammatik.
7. Optimieren Sie den in (f) generierten Parser.