Inhaltsverzeichnis

1  Von der Quellsprache zur Zielmaschine.  3

2  Syntaxgerichtete Übersetzung  5

2.1  Syntaxgerichtete Definition.  6

2.2  Auswertungsreihenfolge für syntaxgerichtete Definitionen  7

2.3  Verfahren zur syntaxgerichteten Übersetzung  9

2.4  Implementierung von L-attributierten syntaxgerichteten Definitionen.  12

3  Typüberprüfung  16

3.1  Typsysteme.  17

3.2  Regeln für die Typüberprüfung.  18

3.3  Spezifikation eines einfachen Typüberprüfers  20

4  Zusammenfassung.  23

Literaturverzeichnis   25

II

Kapitel 1: Von der Quellsprache zur Zielmaschine

1 Von der Quellsprache zur Zielmaschine

Jegliche Software bzw. Computerprogramme auf unseren Computer werden in einer Programmiersprache geschrieben. Die Programmiersprachen spezifizieren den Ablauf von Rechenprozessen. Bevor ein Programm laufen kann, muss die Quellsprache sinngemäß in eine Befehlsfolge übersetzt werden, damit es vom Computer ausgeführt werden kann. Die Computerprogramme, die diese Übersetzung durchführen, werden Compiler genannt. Ein Compiler übersetzt - weshalb es auch Übersetzer genannt wirdein in einer Quellsprache geschriebenes Programm in gleichbedeutende Sätze einer Zielsprache, das Zielprogramm. [ALSU07, S. 2] Der Bereich des Compilerbaus, also die Programmierung eines Compilers, hat eine lange Tradition in der Informatik. Es ist eine eigenständige Disziplin innerhalb der Informatik und gilt als das älteste Gebiet der praktischen Informatik. Ihre Grundlagen gehen auf die Automatentheorie und die formalen Sprachen zurück. [BH98, S. 3]

Die Übersetzung erfolgt in einer Folge von Phasen, die jeweils verschiedene Teilaufgaben des Compilers übernehmen. Jede Phase verwandelt das zu übersetzsende Programm von einer Darstellungsform in eine andere. Abb. 1.1 stellt die Übersetzungsphasen im Überblick dar. [GE99, S. 3] Im Wesentlichen lassen sich zwei Hauptphasen unterscheiden, die Analysephase und die Synthesephase. Die Analysephase zerlegt den Quelltext in seine Bestandteile und gibt ihm eine grammatische Struktur. Anhand des analysierten Quelltexts wird einen attribuierten Syntaxbaum erzeugt. Diese Zwischendarstellung wird zusammen mit einer Symboltabelle, in welcher Informationen über den Quelltext gesammelt werden, der Synthesephase übergeben. Bei der Synthese wird aus der Zwischendarstellung und den Informationen in der Symboltabelle das gewünschte Zielprogramm erzeugt. Der Teil des Compilers, der sich mit der Analyse, Strukturierung und Fehlerüberprüfung befasst, wird oft als Front-End bezeichnet, und der für die Synthese zuständige Teil ist als Back-End bekannt. [ALSU07, S. 2]

In dieser Arbeit wird der Fokus auf den Front-End Bereich gesetzt, vor allem auf die syntaktische und die semantische Analyse. Schwerpunkt der Arbeit ist die syntaxgerichtete Übersetzung, die im Kapitel 2 ausführlich erläutert wird. Die Übersetzungstechniken, die im 2. Kapitel besprochen werden, werden zur Durführung

3

Kapitel 1: Von der Quellsprache zur Zielmaschine

der Typüberprüfung im Kapitel 3 benützt. Die Arbeit wird mit einer Zusammenfassung abgeschlossen.

Kapitel 2: Syntaxgerichtete Übersetzung

2 Syntaxgerichtete Übersetzung

Durch die Techniken und Methoden der lexikalischen Analyse und der Syntaxanalyse ist der Compiler in der Lage, für eine gegebene Eingabezeichenfolge der Quellsprache einen Ableitungsbaum (Parse-Baum) zu erzeugen. Der nächste Schritt wäre aus dem vorliegenden Ableitungsbaum Programme der Zielsprache der Übersetzung zu konstruieren. Ein anderer möglicher Schritt ist die syntaxgerichtete Übersetzung, die den Gedanke der Übersetzung von Sprachen anhand kontextfreier Grammatiken fortführt. [ALSU07, S. 364]

Die syntaxgerichtete Übersetzung (auch als syntaxgesteuerte Übersetzung bekannt) verfolgt den Ansatz, einen Parse-Baum zu generieren und anschließend die Werte der Attribute an den Knoten des Baumes zu berechnen, indem diese Knoten aufgesucht werden. Der Ablauf einer syntaxgerichteten Übersetzung wird in Abb. 2.1 dargestellt. Die syntaxgerichtete Übersetzung ist eine Technik, deren formale Grundlage die attributierten Grammatiken bildet, die ihrerseits ermöglichen, semantische Regeln mit Produktionen zu verbinden. [GE99, S. 121] Bei der attributierten Grammatik werden Informationen mit einem Programmiersprachenkonstrukt verbunden, indem an die Grammatiksymbole, die diese Konstrukte repräsentieren, Attribute angeheftet werden. Die Menge an Attributen dient als Informationsbehälter. Die Werte für die Attribute werden durch semantische Regeln berechnet, die mit Grammatikproduktionen in Verbindung gesetzt werden. [WM97, S. 424]

Abb. 2.1: Konzeptuelle Sicht der syntaxgerichteten Übersetzung [ALSU86, S. 341] In diesem Kapitel werden zwei verschiedene Notationen erläutert, die es ermöglichen, semantische Regeln mit Produktionen zu verbinden - die syntaxgerichtete Definition und die Übersetzungsschemata. Es werden auch die Fälle behandelt, in denen der Ableitungsbaum nicht erst komplett aufgebaut und dann mit der Übersetzung begonnen wird; sondern die Übersetzungsschritte werden durchgeführt, sobald Teilstrukturen des Ableitungsbaums erkannt werden. Übersetzungsschritte werden mit der Analyse verzahnt. Es handelt sich um die Klasse der L-attributierten Übersetzungen, d. h. alle

5

Kapitel 2: Syntaxgerichtete Übersetzung

Übersetzungen, die ohne explizierte Erstellung eines Syntaxanalysebaumes ausgeführt werden können.

2.1 Syntaxgerichtete Definition

Eine syntaxgerichtete Definition ist im Wesentlichen ein Formalismus zur Beschreibung von Übersetzungen programmiersprachlicher Konstrukte. Sie entspricht einer kontextfreien Grammatik mit Attributmengen für jedes Grammatiksymbol und Semantikregel für jede Grammatikregel. Eine kontextfreie Grammatik stellt ein formales System von Ersetzungsregeln dar. Diese Regeln erklären, wie bestimmte Folgen von Symbolen als Sätze der so definierten Sprache erzeugt werden können. [UK90, S. 70] Attribute können Beliebiges repräsentieren, zum Beispiel Zahlen, Typen, einen Speicherplatz oder Strings und werden durch Semantikregeln berechnet, die mit den Grammatikregeln assoziiert werden. In der Abb. 2.2 wird eine syntaxgerichtete Definition eines einfachen Taschenrechners dargestellt. [ALSU86, S. 341]

Abb. 2.2: Syntaxgerichtete Definition eines einfachen Taschenrechners [ALSU86, S. 342]

Die Attribute für Nichtterminale sind in zwei Untermengen aufgeteilt - synthetisierte und ererbte Attribute. Der Unterschied zwischen den beiden Mengen ist die Abhängigkeit der Attribute bzw. die Auswertungsreihenfolge derselben. Im Falle der synthetisierten Attribute hängt der berechnete Wert nur vom Nachfolgeknoten im Parse-Baum ab. Abhängig davon muss die Reihenfolge, in der die Attributwerte berechnet werden, mit der Reihenfolge beim Aufbau bzw. Durchlauf des Parse-Baumes zusammenpassen. Das heißt, synthetisierte Attribute werden innerhalb eines Parse-Baumes bewertet, indem die Semantikregeln für die Attribute an jedem Knoten von unten nach oben, also von den Blättern zu Wurzel, ausgewertet werden. Die Werte von ererbten Attributen hängen von den Vorgänger und den Geschwister ab. Ererbte

6

Kapitel 2: Syntaxgerichtete Übersetzung

Attribute sind nützlich, um an ein Symbol geheftete Informationen aus dem Kontext, in dem es auftritt, übertragen zu können. [WM97, S. 425]

2.2 Auswertungsreihenfolge für syntaxgerichtete Definitionen

Abhängigkeitsgraph

Ein Abhängigkeitsgraph ist eine Erweiterung eines kommentierten Parse-Baumes. Ein kommentierter Parse-Baum zeigt nur die Werte der Attribute. Darüber hinaus zeigt der Abhängigkeitsgraph wie diese Werte zu berechnen sind, indem er die Auswertungsreihenfolge für die Attributinstanzen eines gegebenen Parse-Baumes darstellt.

In der Abb. 2.3 wird einen Abhängigkeitsgraph für den Eingabestring 3*5 dargestellt. Es zeigt, wie der Informationsfluss zwischen den Attributinstanzen eines gegebenen Parse-Baumes abläuft. Eine Kante von einer Attributinstanz zu einer anderen sagt aus, dass um den zweiten Wert zu berechnen, der Wert der ersten Attributinstanz benötigt wird. Kanten drücken die durch die Semantikregeln definierten Einschränkungen aus. [ALSU07, S. 373]

Abb. 2.3: Abhängigkeitsgraph für einen kommentierten Parse-Baum [ALSU07, S. 373]

Um aus einem Abhängigkeitsgraphen eine geeignete Reihenfolge für die Auswertung der Semantikregeln zu erhalten, ist eine topologische Sortierung nötig. Man muss die einzelnen Knoten (n 1 ,…,n k ) in einer Reihenfolge ermitteln, so dass für jede Kante (n i ,n j ) im Graphen i<=j gilt. Um eine topologische Sortierung durchzuführen, sind verschiedene Methoden denkbar, beispielsweise die Syntaxbaummethode, die

7