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)

Lösung:

- keine Musterlösung vorgesehen -

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?

Lösung

Es gibt vier Strukturbäume. Wir geben auch die Auswertung der Attributierung an, auch wenn genaugenommen die Annotierung der Attribute gereicht hätte.

S                   S
|                   |
X {a=1, b=2}        X {a=1, b=2}
|\                  |\
| \                 | \
s  Y {c=1, d=2,     t  Y {c=1, d=1,
   |  e=2, f=2}        |  e=2, f=1}
   |                   |
   u                   u

S                   S
|                   |
X {a=1, b=3}        X {a=1, b=3}
|\                  |\
| \                 | \
s  Y {c=1, d=1,     t  Y {c=3, d=1,
   |  e=1, f=3}        |  e=3, f=3}
   |                   |
   v                   v

      

Gemäß den Hinweisen gilt: X.a, Y.c und Y.d sind ererbt, alle anderen Attribute sind synthetisiert.