Übersetzerbau: Theorie, Konstruktion, Generierung

ISBN-13: 9783540616924 / Niemiecki / Twarda / 1997 / 640 str.

Reinhard Wilhelm; Dieter Maurer

Spis treści

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.

Blurb

Diese zweite, überarbeitete und erweiterte Auflage vermittelt Studenten der Informatik Fundament und Rüstzeug des Übersetzerbaus für imperative, funktionale, logische und - neu hinzugekommen - objektorientierte Programmiersprachen und moderne Zielarchitekturen: von den theoretischen Grundlagen bis zu konstruktiven und generativen Verfahren.
Die statische Analyse von Programmen, die für die Unterstützung des Softwareentwicklungsprozesses 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 passend bereitgestellt.
Das Buch enthält zahlreiche Übungsaufgaben und eignet sich zur Vorlesungsbegleitung ebenso wie zum Selbststudium.