imported>Karlito: G=(N,T,P,Z) wird nicht in der referenzierten Seite zu CFG verwendet. Um Verwirrung vorzubeugen, hier korrigiert zu G=(N,T,P,S) wie im Artikel zu CFG zumindest als Alternative dargestellt

2021-02-18T16:20:25Z

G=(N,T,P,Z) wird nicht in der referenzierten Seite zu CFG verwendet. Um Verwirrung vorzubeugen, hier korrigiert zu G=(N,T,P,S) wie im Artikel zu CFG zumindest als Alternative dargestellt

Neue Seite

Eine '''Attributgrammatik''' ist eine [[kontextfreie Grammatik]], die um Attribute sowie Regeln und Bedingungen erweitert ist. Angewandt wird das Konzept im [[Compilerbau]], um beispielsweise die Einhaltung von Regeln zu überprüfen, die mit [[Kontextfreie Grammatik|kontextfreien Grammatiken]] nicht formuliert werden können. Solche Regeln sind z. B. die, dass jede Variable [[Deklaration (Programmierung)|deklariert]] sein muss und ihrem [[Datentyp]] entsprechend verwendet wird. Das Konzept der Attributgrammatiken wurde ursprünglich von [[Donald E. Knuth]] eingeführt.<ref>{{Literatur|Autor=Donald E. Knuth|Titel=Semantics of context-free languages|Sammelwerk=Mathematical systems theory|Band=2|Nummer=2|Seiten=127–145|ISSN=0025-5661|DOI=10.1007/BF01692511|Online=https://link.springer.com/article/10.1007/BF01692511|Abruf=2017-01-08}}</ref><ref>{{Literatur|Autor=Donald E. Knuth|Titel=Semantics of context-free languages: Correction|Sammelwerk=Mathematical systems theory|Band=5|Nummer=2|Seiten=95–96|ISSN=0025-5661|DOI=10.1007/BF01702865|Online=https://link.springer.com/article/10.1007/BF01702865|Abruf=2017-01-08}}</ref>

Ein Compiler überprüft die Einhaltung dieser Regeln während der [[Compiler#Semantische Analyse|semantischen Analyse]]. Dabei hat er nur die Informationen zur Verfügung, die im [[Syntaxbaum]] des Programms enthalten sind. Zusätzliche Informationen, die die semantische Analyse erleichtern, kann man als Attribute in den Syntaxbaum integrieren.

Zum Beispiel kann der Typ eines Ausdrucks als Attribut an den entsprechenden Knoten im Syntaxbaum annotiert werden. Durch Attributregeln und -bedingungen können zusätzlich Abhängigkeiten von anderen Attributen (auch anderer Knoten im Syntaxbaum) angegeben werden.

Die Programmierung der betreffenden Teile des Compilers vereinfacht sich, wenn die Produktionen der Grammatik selbst mit entsprechenden Attributen versehen werden.

== Notation ==
* <math>X_i.a := f(\ldots,X_j.b,\ldots) \in R(p)</math> ist ein Attribut <math>a</math>, das zu einem Nichtterminal <math>X_i</math> der Produktion <math>p:X_0 \rightarrow X_1\ldots X_n</math> gehört, mit <math>0 \le i,j \le n</math>.

== Definitionen ==
<math>AG = (G,A,R,B)</math> ist eine Attributgrammatik, die durch folgende Komponenten definiert ist:
* <math>G=(N,T,P,S)</math> ist eine [[kontextfreie Grammatik]].
* <math>A=\bigcup_{X\in(T\cup N)}A(X)</math> ist eine endliche Menge von Attributen, die jeweils eindeutig einem Symbol <math>X</math> zugeordnet sind. Die einzelnen Attributmengen <math>A(X)</math> sind disjunkt, es gilt also <math>A(X) \cap A(Y) \ne \varnothing \Rightarrow X = Y</math>.
* <math>R=\bigcup_{p\in P}R(p)</math> ist eine endliche Menge von Attributionsregeln.
* <math>B=\bigcup_{p\in P}B(p)</math> ist eine endliche Menge von Bedingungen. Die Bedingung <math>B(p)</math> einer Produktion <math>p:X_0 \rightarrow X_1\ldots X_n</math> kann in der Form <math>X_0.b</math> auch als Attribut der linken Seite aufgefasst werden, daher sind mit den Attributen auch alle Bedingungen erfasst.
* <math>AF(p):=\{X_i.a \; \vert \; p:X_0 \rightarrow X_1\ldots X_n,0 \le i \le n, X_i.a:=f(\ldots) \in R(p)\}</math> ist die Menge der Attribute, die in den Regeln <math>R(p)</math> einer Produktion <math>p \in P</math> definiert sind.

Die Attribute <math>A(X)</math> eines Symbols lassen sich in zwei [[Disjunkt|disjunkte]] Klassen unterteilen, da es für alle Attribute <math>a \in A(X)</math> nur eine Berechnungsregel der Form <math>X.a \leftarrow f(\ldots)</math> in <math>R</math> gibt:
* <math>AS(X) := \{X.a \; \vert \; \exists \; p:X \rightarrow X_1\ldots X_n \in P \land X.a \in AF(p)\}</math> ist die Menge der synthetisierten (abgeleiteten) Attribute. Dies sind die Attribute, die in den Regeln <math>r \in R(p)</math> einer Produktion <math>p \in P</math> definiert sind, bei der <math>X</math> auf der linken Seite steht.
* <math>AI(X) := \{X.a \; \vert \; \exists \; q:Y \rightarrow uXv \in P \land X.a \in AF(q)\}</math> ist die Menge der ererbten (inherited) Attribute. Dies sind die Attribute, die in den Regeln <math>r \in R(p)</math> einer Produktion <math>p \in P</math> definiert sind, bei der <math>X</math> auf der rechten Seite steht.

== Zirkularität ==
Attributgrammatiken sind zirkulär, wenn der Abhängigkeitsgraph der Attributvariablen, der durch die funktionale Abhängigkeit induziert wird, eine Schleife enthält.

Diese Zirkularität lässt sich in exponentieller Zeit testen.

Ein vereinfachter Test, der weniger Grammatiken zulässt, berechnet das Problem in polynomieller Zeit.

== Grammatiktypen ==

=== S-Attributgrammatiken ===
S-Attributgrammatiken, kurz SAG sind Attributgrammatiken, die nur auf synthetischen Attributen arbeiten. So können sie direkt bei den Reduce-Schritten des Parse-Vorgang eines [[LR-Parser|LR(k)-Parsers]] berechnet werden. Implementiert in [[yacc]].

=== L-Attributgrammatiken ===
L-Attributgrammatiken (LAG) können in einem Top-down-Durchgang von links nach rechts durch den abstrakten Syntaxbaum ausgewertet werden. Sie können für jede [[LL-Parser|LL-Grammatik]] ausgewertet werden und somit für Pascal-ähnliche Programmiersprachen verwendet werden. Bei diesen dürfen nur abgeleitete und nachstehende Baumteile auf aktuelle Attribute zugreifen.

Beispiel:
# <math> A \rightarrow B C, a.1=a.0, b.0=b.1, c.2=c.1, c.2=c.0</math> (erlaubt)
# <math> A \rightarrow B C, a.1=a.2</math> (verboten)

Das erleichtert die vorwärtsgerichtete Deklaration von Variablen und Funktionen.

=== LR-Attributgrammatiken ===
Eine Teilklasse der L-Attributgrammatiken, und zwar gerade diejenigen, die sich in einem Durchgang von links nach rechts während des LR-Parsens auswerten lassen. Implementierung: zyacc; in yacc von Hand über globale Variablen realisierbar. Der Vorteil der größeren Mächtigkeit des LR-Parsens gegenüber dem LL-Parsen manifestiert sich somit spiegelbildlich im Nachteil der geringeren Mächtigkeit der LR-Attributgrammatiken gegenüber den L-Attributgrammatiken.

=== ECLR-Attributgrammatiken ===
Eine Variante der LR-Attributgrammatiken; sie benutzt eine [[Äquivalenzrelation]], um die Attributauswertung zu optimieren. Implementierung: rie.

== Einzelnachweise ==
<references />

[[Kategorie:Compilerbau]]
[[Kategorie:Theorie formaler Sprachen]]

Attributgrammatik - Versionsgeschichte

imported>Karlito: G=(N,T,P,Z) wird nicht in der referenzierten Seite zu CFG verwendet. Um Verwirrung vorzubeugen, hier korrigiert zu G=(N,T,P,S) wie im Artikel zu CFG zumindest als Alternative dargestellt