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

 

Aufgabe 1 (2 + 2 + 1 Punkte)

Sei G die Grammatik mit Terminalen (, a und ), Nichtterminalen S', S und R, Startsymbol S' und Produktionen

S' -> S
S  -> (R  |  a
R  -> S R  |  )
 

1. Stellen Sie das zu G gehörende rekursive Gleichungssystem für die Fi₁-Mengen auf.
2. Lösen Sie das System mit einem Einzelschrittverfahren in einer geeigneten Reihenfolge.
3. Genügen die Fi₁-Mengen, um zwischen den beiden Produktionen aus S und aus R auszuwählen? Wenn ja, geben Sie an, bei welchen Terminalen jeweils die erste und die zweite Produktion gewählt wird.

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

Sei G die Grammatik mit Terminalen (, -, a und ), Nichtterminalen S', S, R, F und A, Startsymbol S' und Produktionen

S' -> S
S  -> -S  |  (S)  |  FR
R  -> -S  |  epsilon
F  -> aA
A  -> (S) |  epsilon
 

1. Stellen Sie mit Hilfe des Algorithmus aus der Vorlesung fest, welche der Nichtterminale epsilon produzieren können.
2. Berechnen Sie die Fi₁-Mengen der Nichtterminale nach dem nicht-iterativen schnellen Verfahren aus der Vorlesung als Lösung eines reinen Vereinigungsproblems unter Benutzung der Information aus (a). Die benötigten starken Zusammenhangskomponenten dürfen durch genaues Hinsehen ermittelt werden.
3. Berechnen Sie die Fo₁-Mengen der Nichtterminale unter denselben Bedingungen wie bei (b).
4. Berechnen Sie aus den Fi₁- und Fo₁-Mengen die Lookahead-Mengen der einzelnen Produktionen.
5. Konstruieren Sie eine LL(1)-Parsertafel und prüfen Sie dabei, ob die Grammatik LL(1) ist.