| Compilerbau - Hinweise |
Attributierte Gammatiken
Wir geben hier eine relativ einfach handhabbare formale
Definition für die
Eigenschaften "abgeleitetet"
und "ererbte" bei Attributen von attributierten Grammatiken,
die sich auf die Definition von Mahn (s.u.) stützt, der
wiederum D. Knuth zitiert.
Definition
Sei eine attributierte Grammatik G
gegeben,
X
aus den Symbolen von G
, und
X.a
ein Attribut zu X
. Dann gilt
-
X.a
heißt genau dann abgeleitetes
(bzw. synthetisiertes) Attribut, wenn eine Regel
p
in den Produktionen von G
existiert, so daß
-
p = X ::= X1
... Xn_p
, d.h. X
tritt auf der
linken Seite der Produktion p
auf, und
-
X.a <-- fp(a,0)(...)
ist in R(p)
,
es gibt also in den
semantischen Reglen zur Produktion p
eine
sematische Funktion für das Attribut X.a
-
X.a
heißt genau dann ererbtes
Attribut, wenn eine Regel
q
in den Produktionen von G
existiert, so daß
-
q = Y ::= Y1 ...Yj-1 X Yj+1
... Yn_q
, d.h. X
tritt auf der
rechten Seite der Produktion q
auf, und
-
X.a <-- fq(a,j)(...)
ist in R(q)
,
es gibt also in den
semantischen Reglen zur Produktion q
eine
sematische Funktion für das Attribut X.a
-
Bei Beginn der Attributierung bekannte Attribute (etwa vom
Lexer erkannte Konstanten) nennt man auch
eigentliche Attribute.
Da semantische Regeln nur die in einer Produktion vorkommenden
Symbole benutzen dürfen, kann man in einem Strukturbaum mit an
die Knoten dekorierten Attributen folgendes beobachten:
- Synthetisierte Attribute hängen immer nur vom Knoten
selbst oder den Nachfolgern des Knotens ab.
-
Ererbte Attribute hängen vom direkten Vorgänger oder
dessen anderen Kinder (also den Nachbarn) ab.
Diese Beobachtung folgt direkt aus dem Zusammenhang von
Produktion und Strukturbaub (bzw. Parsebaum).
Literatur
Verfasser: Mahn, Ulrich
Hauptsachtitel: Attributierte Grammatiken und
Attributierungsalgorithmen
Verlag: Springer-Verlag
Erscheinungsjahr: 1988
Gesamttitel fortlaufendes Werk; Zaehlung (1): Informatik Fachberichte ; 157
ISBN: 3-540-18650-6
Dietmar Lammers
Last modified: Tue Jan 18 10:46:10 MET 2000