In einem Supermarkt gibt es eine Maschine zur Flaschenrückgabe. Erweitern Sie die nachfolgende Grammatik um Attribute, um den Flaschen- bzw. Kisteneinsatz zu berechnen.
S -> RL RL -> R RL | R R -> K FL | F K -> milch | bier FL -> F FL | F | e F -> milch | bier
Der Flascheneinsatz beträgt: Milch 4 S, Bier 5 S. Der Kisteneinsatz beträgt: Milch 30 S, Bier 50 S.
Ein Element R der Rückgabeliste RL
besteht aus einer Flasche F oder einer Kiste
K mit Flaschen FL. In einer Kiste
müssen alle Flaschen vom gleichen Typ sein (z.B. passen
in Milchkisten nur Milschflaschen) sonst wird für die
ganze Kiste kein Einsatz berechnet.
Die Anzahl der Flaschen, Kisten und fehlerhaften Flaschen (z.B. eine Bierflasche in einer Milchkiste) sowie der errechnete Einsatz der angenommenen Flaschen und Kisten sollen in den synthetisierten Attributen S.f, S.k, S.ff und S.e geliefert werden.
S -> RL S.f = RL.f
S.k = RL.k
S.ff = RL.ff
S.e = RL.e
RL -> R RL RL.f = R.f + RL1.f
RL.k = R.k + RL1.k
RL.ff = R.ff + RL1.ff
RL.e = R.e + RL1.e
RL -> R RL.f = R.f
RL.k = R.k
RL.ff = R.ff
RL.e = R.e
R -> K FL FL.kt = K.kt
if( FL.fehler )
R.f = 0
R.k = 0
R.ff = FL.n
R.e = 0
else
R.f = FL.n
R.k = 1
R.ff = 0
R.e = K.e + FL.e
R -> F R.f = 1
R.k = 0
R.ff = 0
R.e = F.e
K -> milch K.kt = milch
K.e = 30
K -> bier K.kt = bier
K.e = 50
FL -> F FL FL1.kt = FL.kt
FL.n = 1 + FL1.n
if( FL.kt == F.ft )
FL.e = F.e + FL1.e
FL.fehler = FL1.fehler
else
Fl.e = 0
FL.fehler = true
FL -> F FL.n = 1
if( FL.kt == F.ft )
FL.e = F.e
FL.fehler = false
else
FL.e = 0
FL.fehler = true
FL -> e FL.n = 0
FL.e = 0
FL.fehler = false
F -> milch F.ft = milch
F.e = 4
F -> bier F.ft = bier
F.e = 5
Erklärungen von attributierten Grammatiken sind immer schwierig, weil es beliebig viele Möglichkeiten gibt, eine Grammatik zu attributieren. In diesem Zusammenhang verweise ich zuallererst auf den Appendix des letzten Skriptums.
Was ist eigentlich zu tun? Wo liegt das (eigentliche) Problem?
Es macht einen großen Unterschied aus, ob man eine bestehende Grammatik attributieren oder eine ganz neue Grammatik erstellen soll. Im ersten Fall muß man unbedingt das Gesamtkonzept erfassen und die Intention der Grammatik begreifen.
Folgende Anforderungen stellen sich:
Sehen wir uns die Grammatik einmal ganz genau an. Die erste Produktion
S -> RL bezeichnet eine Rückgabeliste
RL. RL wiederum wird in
RL -> R RL | R R -> K FL | F
genauer spezifiziert, nämlich als Liste von R
Elementen die ihrerseits entweder aus einer Kiste mit Flaschen K
FL oder aus einer Einzelflasche F bestehen
können.
Eine Flaschenliste FL besteht laut
FL -> F FL | F | e
aus einzelnen Flaschen, kann aber auch leer sein. Sowohl Flaschen als
auch Kisten haben einen eindeutigen Typ: milch
bzw. bier. Wir müssen also hier irgendwo
überprüfen, ob nicht eine falsche Flasche in einer Kiste
steht (in diesem Fall wird ja für die ganze Kiste kein
Einsatz berechnet) und einen Fehler melden.
Wie immer bei der Attributierung fangen wir dort an, wo es uns am leichtesten fällt. Den Typ und den Einsatz von Flaschen und Kisten können wir ganz einfach bestimmen:
K -> milch K.kt = milch
K.e = 30
K -> bier K.kt = bier
K.e = 50
F -> milch F.ft = milch
F.e = 4
F -> bier F.ft = bier
F.e = 5
kt steht für Kistentyp, ft für
Flaschentyp und e natürlich für den Einsatz.
Den Kistentyp
Nach dem Zusammensetzen der einzelnen Bausteine und dem Hinzufügen der Durchreicheregeln erhalten wir die endgültige Lösung.