Attributierte Grammatiken


Am Beispiel der Türme von Hanoi läßt sich gut ein Konzept demonstrieren, das beim Compilerbau sehr hilfreich ist, um über den formal korrekten Aufbau  eines Textes hinaus Teile der Bedeutung  zu erfassen: es gibt dafür eine Attributierte Grammatik.

Damit ist folgendes gemeint: Wir gehen aus von einer kontextfreien Grammatik und ordnen jedem Nichtterminalsymbol eine Klasse zu; in den Regeln stehen dann jeweils Instanzen dieser Klassen, die wir, falls nötig, durch Indizes unterscheiden. Jedes Objekt hat einen Satz von Attributen, welche mit seiner Bedeutung  zu tun haben können, und die Attributwerte stehen innerhalb einer Regel in Beziehungen  untereinander, die als Zusatzforderungen zu den kontextfreien Regeln hinzutreten und etwa die Menge der syntaktisch korrekt  aufgebauten Texte in Richtung der sinnvollen  Texte einschränken.

In unserem Beispiel hat eine Scheibe  ein Attribut Durchmesser,  und ein Turm  hat einen Durchmesser  und eine Höhe.  Wir schreiben die Attribute wie Komponenten eines Verbundes, und bekommen damit folgende Regeln:

Turm <leer>
Turm.Höhe = 0
Turm.Durchmesser = 0
Turm Scheibe Turm_1
Turm.Höhe = Turm_1.Höhe + 1
Turm.Durchmesser = Scheibe.Durchmesser
Scheibe.Durchmesser > Turm_1.Durchmesser
Damit haben wir auch die Nebenbedingungen unseres Problems in einer Form erfaßt, die nahe an den Grammatikregeln liegt, und die von einem intelligenten Generator womöglich automatisch verarbeitet werden kann.


zurück | Inhalt | Index | vor | Vorlesung

Klaus Lagally, 22. Februar 2000, 19:36