Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Attributgrammatik aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Attributgrammatik

Eine Attributgrammatik ist eine kontextfreie Grammatik, die um Attribute, sowie Regeln und Bedingungen für diese Attribute, erweitert ist. Angewandt wird das Konzept im Compilerbau, um die Einhaltung von Regeln zu überprüfen, die mit kontextfreien_Grammatiken nicht formuliert werden können. Solche Regeln sind z.B. die, dass jede Variable deklariert sein muss und ihrem Datentyp entsprechend verwendet wird.

Ein Compiler überprüft die Einhaltung dieser Regeln während der 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.

Z.B. 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

* $X\_i.a\; :=\; f(...,X\_j.b,...)\; \backslash in\; R(p)$ ist ein Attribut $a$, das zu einem Nichtterminal $X\_i$ der Produktion $p:X\_0\; \backslash rightarrow\; X\_1...X\_n$ gehört, mit $0\; \backslash le\; i,j\; \backslash le\; n$.

Definitionen

$AG\; =\; (G,A,R,B)$ ist eine Attributgrammatik, die durch folgende Komponenten definiert ist:
* $G=(T,N,P,Z)$ ist eine kontextfreie Grammatik.
* $A=\backslash bigcup\_\{X\backslash in(T\backslash cup\; N)\}A(X)$ ist eine endliche Menge von Attributen, die jeweils eindeutig einem Symbol $X$ zugeordnet sind. Die einzelnen Attributmengen $A(X)$ sind disjunkt, es gilt also $A(X)\; \backslash cap\; A(Y)\; \backslash ne\; \backslash varnothing\; \backslash Rightarrow\; X\; =\; Y$.
* $R=\backslash bigcup\_\{p\backslash in\; P\}R(p)$ ist eine endliche Menge von Attributionsregeln.
* $B=\backslash bigcup\_\{p\backslash in\; P\}B(p)$ ist eine endliche Menge von Bedingungen. Die Bedingung $B(p)$ einer Produktion $p:X\_0\; \backslash rightarrow\; X\_1...X\_n$ kann in der Form $X\_0.b$ auch als Attribut der linken Seite aufgefasst werden, daher sind mit den Attributen auch alle Bedingungen erfasst.
* $AF(p):=\backslash \{X\_i.a\; \backslash ;\; \backslash vert\; \backslash ;\; p:X\_0\; \backslash rightarrow\; X\_1...X\_n,0\; \backslash le\; i\; \backslash le\; n,\; X\_i.a:=f(...)\; \backslash in\; R(p)\backslash \}$ist die Menge der Attribute, die in den Regeln $R(p)$ einer Produktion $p\; \backslash in\; P$ definiert sind.

Die Attribute $A(X)$ eines Symbols lassen sich in zwei disjunkte Klassen unterteilen, da es für alle Attribute $a\; \backslash in\; A(X)$ nur eine Berechnungsregel der Form $X.a\; \backslash leftarrow\; f(...)$ in $R$ gibt:
* $AS(X)\; :=\; \backslash \{X\_0.a\; \backslash ;\; \backslash vert\; \backslash ;\; \backslash exists\; \backslash ;\; p:X\_0\; \backslash rightarrow\; X\_1...X\_n\; \backslash in\; P\; \backslash land\; X\_0.a\; \backslash in\; AF(p)\backslash \}$ ist die Menge der synthetisierten (abgeleiteten) Attribute. Dies sind die Attribute, die in den Regeln $r\; \backslash in\; R(p)$ einer Produktion $p\; \backslash in\; P$ definiert sind, bei der $X$ auf der rechten Seite steht.
* $AI(X)\; :=\; \backslash \{X.a\; \backslash ;\; \backslash vert\; \backslash ;\; \backslash exists\; \backslash ;\; q:Y\; \backslash rightarrow\; uXv\; \backslash in\; P\; \backslash land\; X.a\; \backslash in\; AF(q)\backslash \}$ ist die Menge der ererbten (inherited) Attribute. Dies sind die Attribute, die in den Regeln $r\; \backslash in\; R(p)$ einer Produktion $p\; \backslash in\; P$ definiert sind, bei der $X$ auf der linken 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(k)-Parser berechnet werden.

L-Attributgrammatiken

L-Attributgrammatiken (LAG) können für Pascal-ähnliche Programmiersprachen verwendet werden. Bei diesen dürfen nur abgeleitete und nachstehende Baumteile auf aktuelle Attribute zugreifen.

Beispiel:
# $A\; \backslash rightarrow\; B\; C,\; a.1=a.0,\; b.0=b.1,\; c.2=c.1,\; c.2=c.0$ (erlaubt)
# $A\; \backslash rightarrow\; B\; C,\; a.1=a.2$ (verboten)

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

       VIDEO-NEWS UND ANGEBOTE