Description
Diese Monographie gibt einen systematischen berblick ber Attributierte Grammatiken als ein Mittel zur Darstellung und Analyse von Kontextabhngigkeiten in Compilern unter Betonung der fr Compiler-erzeugende Systeme erforderlichen Algorithmen. Attributierte Grammatiken sind ein inzwischen weltweit anerkanntes Mittel zur Beschreibung der statischen Semantik von Programmiersprachen. Mit der verstrkten Verbreitung von Compiler-Generatoren wird es auch fr den Praktiker interessant, fr spezielle Zwecke geeignete Sprachen zu entwickeln und zu implementieren. Diese ausfhrliche vergleichende Darstellung der verfgbaren Ergebnisse und Methoden weist auch dem Nichtspezialisten den Weg, einen fr seine Sprache geeigneten Algorithmus zu finden. Betont werden vor der Systematik der theoretischen Erkenntnisse vor allem die in Compiler-Erzeugenden Systemen wie GAG oder HLP78 bewhrten Algorithmen. Fr den im Compilerbau Ttigen sind sicherlich die einheitliche Zusammenfassung der groen Vielzahl bekannter Ergebnisse ber Attributierte Grammatiken und die sehr umfangreiche Bibliographie von Interesse. 1. Einfhrung.- 1.1. Aufgaben und Struktur von Compilern.- 1.2. Attributierungen im Compilerbau.- 1.3. Attributierte Grammatik.- 1.4. Attributabhngigkeiten.- 1.5. Einsatz bei der Entwicklung von Compiler-Compilern.- 1.6. Historische und bibliographische Anmerkungen.- 2. Attributierte Grammatiken – ein systematischer berblick.- 2.1. Wohldefinierte Attributierte Grammatiken.- 2.1.1. Wohldefiniertheit.- 2.1.2. Zerlegbarkeit.- 2.1.3. Problematik von Attributierungsalgorithmen.- 2.1.4. Induzierte Attributabhngigkeiten.- 2.2. Zyklenfreiheit.- 2.2.1. Verfahren zum Test auf Zyklenfreiheit nach Knuth.- 2.2.2. Verfahren zum Test auf Zyklenfreiheit nach Jazayeri.- 2.2.3. Zeitkomplexitt des Circularity-Problems.- 2.2.4. Zyklenfreiheitstest nach Chebotar.- 2.3. 1-Pass-Attributierte Grammatiken.- 2.3.1. L-Attributierte Grammatiken.- 2.3.2. 1-Visit-Attributierte Grammatiken.- 2.3.3. S-Attributierte Grammatiken.- 2.3.4. LL/LR-Attributierte Grammatiken.- 2.4. Multi-Pass-L/R-Attributierte Grammatiken.- 2.4.1. Die LAG-Eigenschaft.- 2.4.2. Algorithmus zum Test der LAG-Eigenschaft.- 2.4.3. Links-Rechts-Attributierungsalgorithmus.- 2.4.4. Die RAG-Eigenschaft.- 2.4.5. Vergleich von LAG und RAG.- 2.5. Alternierende Attributierte Grammatiken.- 2.5.1. Die AAG-Eigenschaft.- 2.5.2. Algorithmen fr Alternierende Attributierte Grammatiken.- 2.5.3. Vergleich von Multi-Pass-Attributierten Grammatiken.- 2.5.4. Bestimmung der optimalen Richtungsfolge.- 2.5.5. Markierter Attributabhngigkeitsgraph.- 2.6. Multi-Sweep-Attributierte Grammatiken.- 2.7. Multi-Visit und Geordnete Attributierte Grammatiken.- 2.7.1. Multi-Visit-Attributierte Grammatiken.- 2.7.2. Attributzerlegungen fr Geordnete AG.- 2.7.3. Geordnete Attributierte Grammatiken.- 2.7.4. Besuchsfolgen fr Geordnete Attributierte Grammatiken.- 2.7.5. Beispiel von Kontextbeziehungen in Programmiersprachen.- 2.7.6. Attributierung von Multi-Visit-AG und Geordneten AG.- 2.7.7. Inkrementelle Attributierung von Geordneten AG.- 2.8. Reine Attributierte Grammatiken.- 2.8.1. Reine Multi-Pass-Attributierte Grammatiken.- 2.8.2. Reine Multi-Sweep-Attributierte Grammatiken.- 2.8.3. Reine Multi-Visit-Attributierte Grammatiken.- 2.9. Absolut zyklenfreie Attributierte Grammatiken.- 2.9.1. Charakterisierung von Absolut zyklenfreien AG.- 2.9.2. Der Attributierungsalgorithmus von Kennedy-Warren.- 2.9.3. Konstruktion eines Kennedy-Warren-Algorithmus.- 2.9.4. Automatische Konstruktion eines KW-Algorithmus.- 2.9.5. Rekursive Attributierung von Absolut zyklenfreien AG.- 2.10. Dynamische Attributierung.- 2.10.1. Einfache Dynamische Attributierung.- 2.10.2. Inkrementelle Dynamische Attributierung.- 2.10.3. Optimale Dynamische Attributierung.- 2.11. Algebraische Definition einer Attributierten Grammatik.- 2.11.1. Attributierte Grammatik als heterogene Algebra.- 2.11.2. Stetige Attributierte Grammatik und Fixpunktattributieru.- 2.11.3. quivalenz von Attributierten Grammatiken.- 2.11.4. Elimination von ererbten Attributen.- 2.12. Affix-Grammatiken.- 2.13. Hierarchie der Attributierten Grammatiken.- 3. Einsatz von AG in Compiler-Erzeugenden Systemen.- 3.1. ALADIN – eine applikative Sprache zur Beschreibung einer AG.- 3.2. GAG – ein Compilergenerator fr Geordnete AG.- 3.3. HLP78 – ein Compilergenerator fr Alternierende AG.- 3.4. FNC/ERN.- 3.5. COCO – ein Compiler-Compiler fr Mikrocomputer.- 3.6. LINGUIST-86 – ein kommerziell genutzter Compiler-Compiler.- 3.7. Weitere Compilergeneratoren.- 3.8. bersicht ber Attributierungen von Programmiersprachen.- 4. Ausblick.- 5. Anhang.- 5.1. bersetzung englischer Fachausdrcke.- 5.2. Bibliographie ber Attributierte Grammatiken.- 5.3. Sonstige Literatur.
