Attributgrammatik

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 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. Das Konzept der Attributgrammatiken wurde ursprünglich von Donald E. Knuth eingeführt.^[1][2]

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.

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

• ${\displaystyle X_{i}.a:=f(\ldots ,X_{j}.b,\ldots )\in R(p)}$ ist ein Attribut ${\displaystyle a}$, das zu einem Nichtterminal ${\displaystyle X_{i}}$ der Produktion ${\displaystyle p:X_{0}\rightarrow X_{1}\ldots X_{n}}$ gehört, mit ${\displaystyle 0\leq i,j\leq n}$.

Definitionen

${\displaystyle AG=(G,A,R,B)}$ ist eine Attributgrammatik, die durch folgende Komponenten definiert ist:

• ${\displaystyle G=(N,T,P,S)}$ ist eine kontextfreie Grammatik.
• ${\displaystyle A=\bigcup _{X\in (T\cup N)}A(X)}$ ist eine endliche Menge von Attributen, die jeweils eindeutig einem Symbol ${\displaystyle X}$ zugeordnet sind. Die einzelnen Attributmengen ${\displaystyle A(X)}$ sind disjunkt, es gilt also ${\displaystyle A(X)\cap A(Y)\neq \varnothing \Rightarrow X=Y}$.
• ${\displaystyle R=\bigcup _{p\in P}R(p)}$ ist eine endliche Menge von Attributionsregeln.
• ${\displaystyle B=\bigcup _{p\in P}B(p)}$ ist eine endliche Menge von Bedingungen. Die Bedingung ${\displaystyle B(p)}$ einer Produktion ${\displaystyle p:X_{0}\rightarrow X_{1}\ldots X_{n}}$ kann in der Form ${\displaystyle X_{0}.b}$ auch als Attribut der linken Seite aufgefasst werden, daher sind mit den Attributen auch alle Bedingungen erfasst.
• ${\displaystyle AF(p):=\{X_{i}.a\;\vert \;p:X_{0}\rightarrow X_{1}\ldots X_{n},0\leq i\leq n,X_{i}.a:=f(\ldots )\in R(p)\}}$ ist die Menge der Attribute, die in den Regeln ${\displaystyle R(p)}$ einer Produktion ${\displaystyle p\in P}$ definiert sind.

Die Attribute ${\displaystyle A(X)}$ eines Symbols lassen sich in zwei disjunkte Klassen unterteilen, da es für alle Attribute ${\displaystyle a\in A(X)}$ nur eine Berechnungsregel der Form ${\displaystyle X.a\leftarrow f(\ldots )}$ in ${\displaystyle R}$ gibt:

• ${\displaystyle AS(X):=\{X.a\;\vert \;\exists \;p:X\rightarrow X_{1}\ldots X_{n}\in P\land X.a\in AF(p)\}}$ ist die Menge der synthetisierten (abgeleiteten) Attribute. Dies sind die Attribute, die in den Regeln ${\displaystyle r\in R(p)}$ einer Produktion ${\displaystyle p\in P}$ definiert sind, bei der ${\displaystyle X}$ auf der linken Seite steht.
• ${\displaystyle AI(X):=\{X.a\;\vert \;\exists \;q:Y\rightarrow uXv\in P\land X.a\in AF(q)\}}$ ist die Menge der ererbten (inherited) Attribute. Dies sind die Attribute, die in den Regeln ${\displaystyle r\in R(p)}$ einer Produktion ${\displaystyle p\in P}$ definiert sind, bei der ${\displaystyle X}$ 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(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-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:

1. ${\displaystyle A\rightarrow BC,a.1=a.0,b.0=b.1,c.2=c.1,c.2=c.0}$ (erlaubt)
2. ${\displaystyle A\rightarrow BC,a.1=a.2}$ (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

1. Donald E. Knuth: Semantics of context-free languages. In: Mathematical systems theory. Band 2, Nr. 2, ISSN 0025-5661, S. 127–145, doi:10.1007/BF01692511 (springer.com [abgerufen am 8. Januar 2017]).
2. Donald E. Knuth: Semantics of context-free languages: Correction. In: Mathematical systems theory. Band 5, Nr. 2, ISSN 0025-5661, S. 95–96, doi:10.1007/BF01702865 (springer.com [abgerufen am 8. Januar 2017]).