Aufgabe 1

Sei G=(N,T,P,S) eine kontextfreie Grammatik, und V = (N U T). Zur Berechnung der LR(k)-Information werden terminale k-Anfänge der Ableitungen von g aus V (Lk(g))benötigt. Hilfreich dazu sind folgende Betrachtungen:

1. Seien L1, L2 Teilmengen von T^*. Dann definiert man

   L1 +k L2 := k( L1 · L2 )

2. Dann definieren wir induktiv die Firstmengen für ein A aus V und k aus N0:

   F0(A) :=	{k(A)}	falls A aus T
   	{x aus T* | A::=a aus P, a aus T*, x=k(a)}	falls A aus N
   und für i>0
   Fi(A) :=	Fi-1(A) U { x | A::=y1...yn aus P, x aus Fi-1(y1)+k...+k Fi-1(yn) }

Zeigen Sie:

1. Lk(A) = Ui>0Fi(A)
2. Falls ein i existiert mit Fi = Fi+1, dann gilt auch Fi = Fi+j für alle j>0.
3. Sei y=y1...yn aus V*. Dann gilt Lk(y) = Lk(y1)+k...+kLk(yn)

Aufgabe 2

Gegeben sei G=({S,X,Y},{s,t,u,v},P,S) mit folgenden Regeln und Attributierungen:

Regel	Attributierung
S::=X	X.a <-- 1;
X::=sY	X.b <-- Y.f; Y.c <-- X.a; Y.d <-- Y.e
X::=tY	X.b <-- Y.e; Y.c <-- Y.f; Y.d <-- X.a;
Y::=u	Y.e <-- 2; Y.f <-- Y.d;
Y::=v	Y.e <-- Y.c; Y.f <-- 3;

Attributieren Sie alle möglichen Strukturbäume dieser Grammatik, und werten Sie die Attribute aus. Welche Attribute sind ererbt, welche synthetisiert?