Übersetzerbau

Dieses Buch vermittelt Studenten der Informatik Fundament und Rüstzeug des Übersetzerbaus für imperative, funktionale und logische Programmiersprachen. Die ersten vier Kapitel führen in die Thematik und die theoretischen Grundlagen ein. In den weiteren sieben Kapiteln werden konstruktive Verfahren zur automatischen Erzeugung von lexikalischen, syntaktischen und semantischen Analysatoren und von Codeerzeugern vorgestellt. Neben der Übersetzung konventioneller, imperativer Programmiersprachen, wie Fortran, Pascal und C, werden auch die Klassen der funktionalen und der logischen Programmiersprachen mit Lisp und Miranda bzw. Prolog als prominenten Vertretern erfaßt. Bei der automatischen Codeerzeugung finden moderne parallele Zielarchitekturen gebührende Berücksichtigung. Die statische Analyse von Programmen, die für die Unterstützung des Softwareentwicklungsprozesses im allgemeinen ebenso wichtig ist wie hier für die Erzeugung effizienter Zielprogramme, wird semantisch fundiert. Die erforderlichen Grundkenntnisse aus der Theorie der formalen Sprachen und Automaten werden hergeleitet. Zahlreiche Aufgaben ermöglichen eine gründliche Einübung der Lehrinhalte. Das Buch eignet sich zum Gebrauch für ein- oder zweisemestrige Vorlesungen ebenso wie zum Selbststudium.

Inhalt
1 Einleitung.- 1.1 Höhere Programmiersprachen.- 1.2 Implementierung von Programmiersprachen.- 2 Übersetzung imperativer Programmiersprachen.- 2.1 Sprachkonzepte und ihre Übersetzung.- 2.2 Die Architektur der P-Maschine.- 2.3 Wertzuweisungen und Ausdrücke.- 2.4 Bedingte und iterative Anweisungen, Anweisungsfolgen.- 2.5 Speicherbelegung für Variablen einfachen Typs.- 2.6 Speicherbelegung für Felder.- 2.7 Speicherbelegung für Verbunde.- 2.8 Zeiger und dynamische Speicherbelegung.- 2.9 Prozeduren.- 2.10 Hauptprogramm.- 2.11 Übungen.- 2.12 Literaturhinweise.- 3 Übersetzung funktionaler Programmiersprachen.- 3.1 Sprachtyp und einleitendes Beispiel.- 3.2 LaMa, eine einfache funktionale Programmiersprache.- 3.3 Einführung in die Übersetzung von LaMa.- 3.4 Umgebungen und Bindungen.- 3.5 Die Architektur der MaMa.- 3.6 Kellerverwaltung und Adressierung.- 3.7 Befehlsvorrat und Übersetzung.- 3.8 Implementierung von Listen.- 3.9 Übungen.- 3.10 Literaturhinweise.- 4 Übersetzung logischer Programmiersprachen.- 4.1 Logische Programmiersprachen.- 4.2 Prädikatenlogische Grundlagen.- 4.3 Unifikation.- 4.4 Ausführung von logischen Programmen.- 4.5 Prolog.- 4.6 Prolog: Abstrakte Maschine und Übersetzung.- 4.7 Übersetzung von Prolog.- 4.8 Effizienzverbesserungen.- 4.9 Übungen.- 4.10 Literaturhinweise.- 5 Struktur von Übersetzern.- 5.1 Übersetzerteilaufgaben.- 5.2 Die lexikalische Analyse.- 5.3 Der Sieber.- 5.4 Die syntaktische Analyse.- 5.5 Die semantische Analyse.- 5.6 Die maschinenunabhängige Optimierung.- 5.7 Die Adreßzuordnung.- 5.8 Die Erzeugung des Zielprogramms.- 5.9 Die maschinenabhängige Codeverbesserung.- 5.10 Reale Übersetzerstrukturen.- 5.11 Formale Spezifikation und Generierung von Übersetzermoduln.- 5.12 Literaturhinweise.- 6 Lexikalische Analyse.- 6.1Die Aufgabe der lexikalischen Analyse.- 6.2 Theoretische Grundlagen.- 6.3 Sprache zur Spezifikation der lexikalischen Analyse.- 6.4 Die Generierung eines Scanners.- 6.5 Der Sieber.- 6.6 Übungen.- 6.7 Literaturhinweise.- 7 Syntaktische Analyse.- 7.1 Die Aufgabe der syntaktischen Analyse.- 7.2 Theoretische Grundlagen.- 7.3 Top down-Syntaxanalyse.- 7.4 Bottom up-Syntaxanalyse.- 7.5 Übungen.- 7.6 Literaturhinweise.- 8 Semantische Analyse.- 8.1 Aufgabe der semantischen Analyse.- 8.2 Attributgrammatiken.- 8.3 Einige Attributgrammatiken.- 8.4 Die Generierung von Attributauswertern.- 8.5 Übungen.- 8.6 Literaturhinweise.- 9 Abstrakte Interpretation.- 9.1 Einführung.- 9.2 Grundlagen.- 9.3 Abstrakte Interpretation (denotationelle Semantik).- 9.4 Abstrakte Interpretation (operationelle Semantik).- 9.5 Übungen.- 9.6 Literaturhinweise.- 10 Bäume: Mustererkennung und Analyse.- 10.1 Programmtransformationen.- 10.2 Codeselektion.- 10.3 Das Mustererkennungsproblem.- 10.4 Das Baumanalyseproblem.- 10.5 Endliche Baumautomaten.- 10.6 Die Generierung von Baumanalysatoren.- 10.7 Baumautomaten mit Kosten.- 10.8 Implementierung.- 10.9 Übungen.- 10.10 Literaturhinweise.- 11 Codeerzeugung.- 11.1 Abstrakte und reale Maschinen.- 11.2 Klassifikation von Architekturen.- 11.3 Programmdarstellungen.- 11.4 Codeerzeugung, integrierte Verfahren.- 11.5 Registerzuteilung durch Graphfärbung.- 11.6 Instruktionsanordnung.- 11.7 Übungen.- 11.8 Literaturhinweise.- Literatur.