Attribute Grammar

Eine normale Grammatik (BNF) definiert nur die Syntax. E -> E + T. (Ein Ausdruck ist Summe plus Term). Aber was bedeutet das? Was ist der Wert? Donald Knuth erfand Attribute Grammars. Man klebt an jeden Knoten im Baum Attribute (Werte). E.val = E1.val + T.val. T.type = int. Man definiert Regeln, wie diese Werte fließen. Von unten nach oben (synthesized: Ergebnis berechnen). Von oben nach unten (inherited: Kontext weitergeben, z. B. "Variable x ist definiert").

Merksatz: Eine formale Methode zur Definition der Semantik einer kontextfreien Grammatik, indem Grammatiksymbolen Eigenschaften (Attribute) und Auswertungsregeln zugeordnet werden.

Tools wie ANTLR oder Yacc nutzen Aktionen { $$ = $1 + $3; }. Das sind attribute Grammars "light". Echte AG-Systeme analysieren Abhängigkeiten und berechnen die Attribute automatisch in der richtigen Reihenfolge. Modern: React oder Svelte Compiler nutzen ähnliche Konzepte, um den Komponenten-Baum zu analysieren.

1. Synthesized vs. Inherited

Synthesized: Information fließt von den Blättern zur Wurzel. (Typischer Interpreter: 3+4 -> 7).
Inherited: Information fließt von der Wurzel zu den Blättern. (Typ-Checker: "Ich erwarte hier einen String, überprüfe das!" -> print("hallo")). Attribute Grammars erlauben komplexe Flüsse (Zig-Zag).

2. Circularity

Man muss aufpassen, keine Zyklen zu bauen. A braucht B, B braucht A. Knuth zeigte Algorithmen, um Zirkularität zu erkennen.

1. Die OAG (Ordered Attribute Grammar)

Damit eine AG effizient ist, darf sie nicht wild "raten", in welcher Reihenfolge sie Attribute berechnet. Kastens entwickelte das Konzept der Ordered Attribute Grammars. Hierbei wird zur Compiler-Bau-Zeit (offline) bewiesen, dass es eine feste Sequenz von Besuchen (Visits) der Baumknoten gibt, die alle Abhängigkeiten auflöst. Der resultierende Compiler ist extrem schnell, da er nur starr den Baum abwandert und keine dynamischen Abhängigkeits-Graphen zur Laufzeit verwalten muss. Das ist der Goldstandard für die Implementierung von statischen Analysetools in der Industrie.

2. Incremental Evaluation

Stell dir eine IDE vor, während du tippst. Der AST ändert sich bei jedem Tastendruck. Man möchte nicht bei jedem Buchstaben den kompletten Baum neu berechnen. Incremental Attribute Grammars tracken die Abhängigkeiten so fein-granular, dass nur die Attribute neu berechnet werden, die von der Textänderung wirklich betroffen sind. Besonders stark ist hier das Konzept der Reference Attribute Grammars (RAGs) (wie in der Sprache JastAdd). Sie erlauben es Attributen, Pointers auf weit entfernte Knoten im Baum zu halten (z. B. eine Variablen-Nutzung zeigt direkt auf die Deklaration). Das macht die Typ-Analyse von Java-Klassen in Millisekunden möglich.

3. Higher-Order Attribute Grammars (HOAG)

Normalerweise ist die Struktur des Baums fest. In einer HOAG kann ein Attribut selbst ein ganzer Teil-Baum sein, der wiederum Attribute besitzt. Das ist extrem mächtig für Code-Generierung. Du transformierst Source-Code in einen Zwischen-Baum (IR). Dieser Zwischen-Baum wird dann wie ein normales Attribut behandelt und weiter analysiert. Es ist die mathematische Krönung der Compilerbau-Theorie, da sie Lexing, Parsing und Transformation in einem einheitlichen logischen Rahmen zusammenführt.