Zusammenfassung in Deutscher Sprache

Je stärker sich Programmiersprachen von den Konzepten realer Maschinen lösen (``Von-Neumann Style''), desto mehr gewinnen abstrakte Maschinen an Bedeutung. Verwendet man abstrakte Maschinen, so kann man das Übersetzen in zwei Schritten vornehmen. Im ersten Schritt wird Code für die abstrakte Maschine erzeugt. Im zweiten Schritt wird dieser Code in Code für eine reale Maschine übersetzt oder der abstrakte Maschinencode einfach direkt interpretiert. Diese Trennung erlaubt bessere Portabilität und erleichtert dem Programmierer das Verständnis des Übersetzungsvorganges.
Das Entwerfen von abstrakten Maschinen ist bisher noch nicht automatisiert worden. Für eingefleischte Compilerbauer ist es immer noch eine Kunst, die viel Einsicht und Erfahrung verlangt.
Im klassischen Compilerbau werden die Aufgaben eines Compilers in mehrere Phasen unterteilt: lexikalische, syntaktische und semantische Analyse, Optimierungen und Codeerzeugung. Für einige dieser Phasen existieren Generatoren. Die bekanntesten Generatoren sind sicherlich LEX und YACC, die lexikalische und syntaktische Analysatoren erzeugen. Eine wesentliche Gemeinsamkeit aller Generatoren besteht darin, daß die Compilerphase mittels einer Metasprache (z.B. reguläre Ausdrücke oder kontextfreie Grammatiken) beschrieben wird und der Generator das entsprechende Modul des Compilers produziert. Leider beantworten selbst die neusten Compilerbaubücher nicht die Frage, wie ein Compilerbauer Übersetzungsschemata, d.h. Abbildungen von Quellsprachen auf Zielsprachenkonstrukte, entwickelt. Die Autoren präsentieren solche Schemata einfach anstatt sie herzuleiten. Das gleiche gilt für abstrakte Maschinen. Typischerweise werden abstrakte Maschinen zusammen mit Übersetzungsschemata von der Quellsprache zur abstrakten Maschinensprache eingeführt. Es gibt nur wenige Arbeiten, die sich mit dem Entwickeln oder Ableiten von abstrakten Maschinen beschäftigen. Um abstrakte Maschinen für eine Quellsprache zu generieren, brauchen wir zuerst eine Metasprache. Nach der Übersetzung muß das erzeugte abstrakte Maschinenprogramm das gleiche Verhalten aufzeigen wie das ursprüngliche Quellsprachenprogramm, d.h. es muß dessen Semantik erhalten. Dieser Aspekt von Programmiersprachen wird häufig nur in natürlicher Sprache beschrieben. Solche Beschreibungen sind in der Regel mehrdeutig und ungenau. Für den Generator brauchen wir aber eine eindeutige, präzise und wohldefinierte Sprache. Solche Sprachen werden Semantikformalismen genannt. In dieser Arbeit wird hauptsächlich ein Formalismus, der unter dem Namen ``Natürliche Semantik'' bekannt ist, verwendet, außerdem spielen auch noch denotationale Semantik und Aktionensemantik eine wichtige Rolle.
Die Frage ist nun, wie man aus der Beschreibung der Semantik einer Quellsprache eine abstrakte Maschine erzeugt.
In dieser Arbeit stellen wir einen Ansatz vor, der eine Transformation zur Phasentrennung verwendet, um aus einer Beschreibung in Natürlicher Semantik vollkommen automatisch eine abstrakte Maschine und einen Compiler zu erzeugen.
Im einzelnen enthält die Arbeit

Überblick über Semantikformalismen:
Wir illustrieren mehrere Semantikformalismen anhand von Beispielen und diskutieren, ob sie zur Semantik-basierten Compilererzeugung geeignet sind.
Überblick über existierende Arbeiten:
Die Arbeiten im Bereich Semantik-basierter Compilererzeugung und des Ableitens abstrakter Maschinen verwenden unterschiedlichste Formalismen und Methoden. Wir betrachten einige grundlegende Techniken und klassifizieren eine Vielzahl existierender Systeme und Ansätze aufgrund relevanter Kriterien.
Generator für abstrakte Maschinen aus Natürlichen Semantiken:
Aus einer Spezifikation in Natürlicher Semantik erzeugt der Generator vollkommen automatisch einen Compiler und eine abstrakte Maschine. Im Gegensatz zu allen existierenden Semantik-basierten Compilergeneratoren, die partielle Auswertung oder eine direkte Übersetzung in eine feste Zielsprache verwenden, bildet eine Phasentrenntransformation das Herzstück unseres Generators.
Bewertung der Performanz der erzeugten abstrakten Maschinen:
Wir testeten den Generator anhand von Semantikspezifikationen von zwei rudimentären Sprachen (SIMP und Mini-ML) und einer Spezifikation von Action Notation, der Sprache in der Aktionensemantiken geschrieben werden. Für Mini-ML wurde eine abstrakte Maschine erzeugt, die der CAM (categorial abstract machine) ähnelt, einer abstrakten Maschine, die in effizienten Implementierungen von ML verwendet wird. Die Performanztests belegen, daß unser System mit anderen Semantik-basierten Compilergeneratoren konkurrieren kann.
Korrektheitsbeweis des Generators ohne Optimierungen:
Zuerst definieren wir eine Semantik für unsere Metasprache, dann verwenden wir diese, um die Korrektheit der wesentlichen Transformationen des Systems zu beweisen.
Interessante Anwendung des Generators:
Indem wir einen aus einer Natürlichen Semantikspezifikation erzeugten Compiler für Action Notation mit den semantischen Gleichungen von Aktionensemantiken komponieren, erhalten wir einen Aktionensemantik-basierten Compilergenerator.

Die wesentliche Neuerung unseres Natürliche Semantik-basierten Compilergenerators besteht darin, daß er Compiler und abstrakte Maschinen erzeugt. Die Laufzeiten der abstrakten Maschinenprogramme, die der generierte Compiler erzeugt, sind vergleichbar mit denen von Programmen die Compiler erzeugen, die auf traditionelle Weise aus Semantikspezifikationen generiert wurden. Die erzeugten Spezifikationen von Compilern und abstrakten Maschinen sind geeignet als Grundlage für handgeschriebene Compiler und abstrakte Maschinen. Unser Generator arbeitet vollkommen automatisch und die Korrektheit seiner Kerntransformationen wurde bewiesen.
Zieht man außer diesen vielversprechenden Ergebnissen noch in Betracht, daß der Generator in einem Ein-Mann Projekt entwickelt wurde, kann man erahnen, welches Potential in der vorgestellten Methode steckt.