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

 

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

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

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

1. Bestimmen Sie den LR(0)-Automaten zu G. Ist G LR(0)?
2. Zeigen Sie, daß G SLR(1) ist.
3. Geben Sie die Aktions- und goto-Tabellen für den SLR(1)-Parser an.
4. Bestimmen Sie die Aktions- und goto-Tabellen für den LALR(1)-Parser.

Aufgabe 2 (3 + 2 Punkte)

Gegeben sei die folgende Grammatik G mit dem Startsymbol S', den weiteren Nichtterminalen A und B, den Terminalen a, b, c und d und den Produktionen

S' ->  A
A  ->  a B  |  a B c
B  ->  b  |  d A
 

1. Weisen Sie mit Hilfe des kanonischen LR(1)-Verfahrens nach, daß G nicht LR(1) ist. Der LR(1)-Automat braucht nur so lange konstruiert werden, bis ein Konflikt offenbar wird.
2. Zeigen Sie, wie G die LR(1)-Eigenschaft (laut Definition in der Vorlesung) verletzt. D.h. geben Sie eine Situation bestehend aus zwei Rechtsableitungen an, bei der ein lookahead von 1 den "Griff" (handle) nicht eindeutig festlegt.