Übersetzerbau

1 Einleitung.- 1.1 Höhere Programmiersprachen.- 1.2 Implementierung von Programmiersprachen.- 1.2.1 Interpreter.- 1.2.2 Übersetzer.- 1.2.3 Reale und abstrakte Maschinen.- 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.6.1 Statische Felder.- 2.6.2 Dynamische Felder.- 2.7 Speicherbelegung für Verbunde.- 2.8 Zeiger und dynamische Speicherbelegung.- 2.9 Prozeduren.- 2.9.1 Speicherorganisation für Prozeduren.- 2.9.2 Adressierung von Variablen.- 2.9.3 Berechnung der Adreßumgebungen.- 2.9.4 Prozedureintritt und Prozedurverlassen.- 2.9.5 Parameterübergabe.- 2.9.6 Zugriff auf Variablen und formale Parameter.- 2.9.7 Formale Prozeduren als Parameter.- 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.3.1 Die Übersetzungsfunktionen.- 3.4 Umgebungen und Bindungen.- 3.5 Die Architektur der MaMa.- 3.5.1 Der Keller der MaMa.- 3.5.2 Die Halde der MaMa.- 3.6 Kellerverwaltung und Adressierung.- 3.6.1 Adressierung von Namen in der MaMa.- 3.6.2 Aufbau von Bindungen.- 3.7 Befehlsvorrat und Übersetzung.- 3.7.1 Programmausdrücke.- 3.7.2 Einfache Ausdrücke.- 3.7.3 Angewandte Vorkommen von Variablen.- 3.7.4 Funktionsdefinitionen.- 3.7.5 Funktionsanwendungen.- 3.7.6 Aufbau und Auswertung von Abschlüssen.- 3.7.7 Letrec-Ausdrücke und lokale Variablen.- 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.5.1 Beweisbäume.- 4.5.2 Umgebungen.- 4.6 Prolog: Abstrakte Maschine und Übersetzung.- 4.6.1 Entwicklung der Prolog Implementierung.- 4.6.2 Die Architektur der WiM.- 4.7 Übersetzung von Prolog.- 4.7.1 Ziele.- 4.7.2 Kopfterme.- 4.7.3 Übersetzung von Klauseln.- 4.7.4 Zurücksetzen (Backtracking).- 4.7.5 Prozeduren, Programme und Anfragen.- 4.7.6 Ein Beispiel.- 4.8 Effizienzverbesserungen.- 4.8.1 Argumentregister.- 4.8.2 Rücksetzrahmen.- 4.8.3 Verkleinerung der lokalen Umgebung.- 4.8.4 Letztes Ziel und Endrekursion.- 4.8.5 Indizieren von Klauseln.- 4.9 Übungen.- 4.10 Literaturhinweise.- 5 Übersetzung objektorientierter Sprachen.- 5.1 Konzepte objektorientierter Sprachen.- 5.1.1 Objekte.- 5.1.2 Objektklassen.- 5.1.3 Vererbung.- 5.1.4 Generizität.- 5.1.5 Informationskapselung.- 5.1.6 Zusammenfassung.- 5.2 Die Übersetzung von Methoden.- 5.3 Schemata zur Übersetzung von Vererbung.- 5.3.1 Ein Übersetzungsschema für einfache Vererbung.- 5.3.2 Übersetzungsschemata für mehrfache Vererbung.- 5.4 Generizität.- 5.5 Übungen.- 5.6 Literaturhinweise.- 6 Struktur von Übersetzern.- 6.1 Übersetzerteilaufgaben.- 6.2 Die lexikalische Analyse.- 6.3 Der Sieber.- 6.4 Die syntaktische Analyse.- 6.5 Die semantische Analyse.- 6.6 Die maschinenunabhängige Optimierung.- 6.7 Die Adreßzuordnung.- 6.8 Die Erzeugung des Zielprogramms.- 6.9 Die maschinenabhängige Codeverbesserung.- 6.10 Reale Übersetzerstrukturen.- 6.11 Formale Spezifikation und Generierung von Übersetzermoduln.- 6.12 Literaturhinweise.- 7 Lexikalische Analyse.- 7.1 Die Aufgabe der lexikalischen Analyse.- 7.2 Theoretische Grundlagen.- 7.2.1 Worte und Sprachen.- 7.2.2 Reguläre Sprachen, reguläre Ausdrücke und endliche Automaten.- 7.3 Sprache zur Spezifikation der lex. Analyse.- 7.3.1 Zeichenklassen.- 7.3.2 Folgen von regulären Definitionen.- 7.3.3 Nichtrekursive Klammerung.- 7.4 Die Generierung eines Scanners.- 7.4.1 Zeichenklassen.- 7.4.2 Folgen von regulären Definitionen.- 7.4.3 Implementierung des until-Konstrukts.- 7.4.4 Die Darstellung eines Scanners.- 7.5 Der Sieber.- 7.5.1 Die Erkennung von Schlüsselwörtern.- 7.5.2 Scanner mit Aufrufschnittstelle zum Sieber.- 7.5.3 Symbolklassen.- 7.6 Flex, ein Scanner-Generator unter UNIX.- 7.6.1 Die Arbeitsweise von Flex-generierten Scannern.- 7.6.2 Flex-Spezifikationen.- 7.7 Übungen.- 7.8 Literaturhinweise.- 8 Syntaktische Analyse.- 8.1 Die Aufgabe der syntaktischen Analyse.- 8.2 Theoretische Grundlagen.- 8.2.1 Kontextfreie Grammatiken.- 8.2.2 Kellerautomaten.- 8.2.3 Der Item-Kellerautomat einer kontextfreien Grammatik.- 8.2.4 Grammatikflußanalyse.- 8.2.5 Ein lineares Verfahren.- 8.2.6 FIRST und FOLLOW.- 8.2.7 Der Spezialfall FIRST1 und FOLLOW1.- 8.2.8 Reine Vereinigungsprobleme.- 8.3 Top-down-Syntaxanalyse.- 8.3.1 Einführung.- 8.3.2 Top-down-Syntaxanalyse mit Zurücksetzen in Prolog.- 8.3.3 LL(k): Definition, Beispiele, Eigenschaften.- 8.3.4 (Starke) LL(k)-Parser.- 8.3.5 LL-Parser für rechtsreguläre kontextfreie Grammatiken.- 8.3.6 Fehlerbehandlung in LL(k)-Parsern.- 8.4 Bottom-up-Syntaxanalyse.- 8.4.1 Einführung.- 8.4.2 Bottom-up-Analyse mit Zurücksetzen in Prolog.- 8.4.3 LR(k)-Analysatoren.- 8.4.4 LR(k): Definition, Eigenschaften, Beispiele.- 8.4.5 LR(k)-Parser.- 8.4.6 Fehlerbehandlung in LR-Parsern.- 8.4.7 Scannergenerierung mit LR-Techniken.- 8.5 Bison, ein LALR(1)-Parsergenerator.- 8.5.1 Bison-Eingabe.- 8.5.2 Fehlerbehandlung.- 8.6 Übungen.- 8.7 Literaturhinweise.- 9 Semantische Analyse.- 9.1 Aufgabe der semantischen Analyse.- 9.1.1 Gültigkeits-und Sichtbarkeitsregeln.- 9.1.2 Überprüfung der Kontextbedingungen.- 9.1.3 Überladung von Bezeichnern.- 9.1.4 Polymorphismus.- 9.2 Attributgrammatiken.- 9.2.1 Die Semantik einer Attributgrammatik.- 9.2.2 Eine Notation für Attributgrammatiken.- 9.3 Einige Attributgrammatiken.- 9.4 Die Generierung von Attributauswertern.- 9.4.1 Attributabhängigkeiten.- 9.4.2 Attributauswertung.- 9.4.3 Besuchsorientierte Auswerter.- 9.4.4 l-geordnete Attributgrammatiken.- 9.4.5 Absolut zyklenfreie Attributgrammatiken.- 9.4.6 Parsergesteuerte Attributauswertung.- 9.5 Übungen.- 9.6 Literaturhinweise.- 10 Abstrakte Interpretation.- 10.1 Einführung.- 10.1.1 Beispiel 1: Rechnen mit Resten.- 10.1.2 Beispiel 2: Neunerprobe.- 10.1.3 Beispiel 3: Vorzeichenregeln.- 10.1.4 Bestandteile einer abstrakten Interpretation.- 10.2 Abstrakte Interpretation (denotationelle Semantik).- 10.2.1 Die denotationelle Methode.- 10.2.2 Grundprinzip der abstrakten Interpretation.- 10.2.3 Verwendung von Hilfssemantiken.- 10.2.4 Fallbeispiel: Striktheitsanalyse.- 10.3 Abstrakte Interpretation (operationelle Semantik).- 10.3.1 Die operationelle Methode.- 10.3.2 Grundprinzip der abstrakten Interpretation.- 10.3.3 Konstruktion abstrakter Interpretationen.- 10.3.4 Verwendung von Hilfssemantiken.- 10.4 Literaturhinweise.- 11 Bäume: Mustererkennung und Analyse.- 11.1 Programmtransformationen.- 11.1.1 Effizienzsteigernde Programmtransformationen.- 11.1.2 Standardisierende Transformationen.- 11.1.3 Das zugrundeliegende Problem.- 11.2 Codeselektion.- 11.3 Das Mustererkennungsproblem.- 11.4 Das Baumanalyseproblem.- 11.5 Endliche Baumautomaten.- 11.6 Generierung von Mustererkennern.- 11.7 Die Generierung von Baumanalysatoren.- 11.8 Baumautomaten mit Kosten.- 11.9 Implementierung.- 11.10 Übungen.- 11.11 Literaturhinweise.- 12 Codeerzeugung.- 12.1 Abstrakte und reale Maschinen.- 12.1.1 Sprachspezifische abstrakte Maschinen.- 12.1.2 Universelle reale Maschinen.- 12.1.3 Codeerzeugung für abstrakte und reale Maschinen.- 12.2 Klassifikation von Architekturen.- 12.2.1 CISC (Complex Instruction Set Computer).- 12.2.2 RISC (Reduced Instruction Set Computer).- 12.2.3 Intraprozessorparallelität.- 12.3 Programmdarstellungen.- 12.4 Codeerzeugung, integrierte Verfahren.- 12.4.1 Optimale Auswertungsordnung.- 12.4.2 Dynamisches Programmieren.- 12.5 Registerzuteilung durch Graphfärbung.- 12.6 Instruktionsanordnung.- 12.6.1 Abhängigkeitsgraphen für Basisblöcke.- 12.6.2 Befehlsfließband.- 12.6.3 Lange Befehlswörter.- 12.6.4 Realistische VLIW-Rechner.- 12.7 Übungen.- 12.8 Literaturhinweise.- Literatur.