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 wird - ein 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 der Typüberprüfung im Kapitel 3 benützt. Die Arbeit wird mit einer Zusammenfassung abgeschlossen.
Inhaltsverzeichnis
1 Von der Quellsprache zur Zielmaschine
2 Syntaxgerichtete Übersetzung
2.1 Syntaxgerichtete Definition
2.2 Auswertungsreihenfolge für syntaxgerichtete Definitionen
2.3 Verfahren zur syntaxgerichteten Übersetzung
2.4 Implementierung von L-attributierten syntaxgerichteten Definitionen
3 Typüberprüfung
3.1 Typsysteme
3.2 Regeln für die Typüberprüfung
3.3 Spezifikation eines einfachen Typüberprüfers
4 Zusammenfassung
Zielsetzung & Themen
Diese Arbeit bietet eine kompakte Einführung in die zentralen Grundlagen und Techniken des Compilerbaus, mit besonderem Fokus auf die syntaktische und semantische Analyse sowie deren praktische Implementierung.
- Syntaxgerichtete Übersetzung und deren formale Grundlagen
- Methoden der Attributauswertung in Grammatiken
- Klassifizierung und Implementierung von L- und S-attributierten Übersetzungen
- Grundlagen der statischen und dynamischen Typüberprüfung
- Spezifikation von Typsystemen und deren Implementierung als Übersetzer
Auszug aus dem Buch
3.1 Typsysteme
Eine Variable/Einheit kann während der Ausführung eines Programms verschiedene Werte einnehmen; ein Typ der Variable spezifiziert den möglichen Wertebereich und die darauf definierten Operationen der Variable. [WG85, S. 227] Der Typ eines Sprachkonstrukts wird durch den Typausdruck definiert. Typen werden für die Speicherverwaltung und für die Vermeidung von Laufzeitfehlern gebraucht. Ein Typausdruck kann entweder ein einfacher Typ sein oder durch Anwendung eines Operators auf Basis andere Typausdrücke gebildet sein. [ALSU86, S. 423] Typen werden durch Typausdrücke beschrieben. Die Menge der Typausdrücke enthält Basistypen, Typkonstruktoren und Typnamen. Es gibt zwei Formen der Typisierung - die statische und die dynamische Typisierung. Bei der statischen Typisierung kann der Typ aller Ausdrücke schon zur Übersetzungszeit bestimmt werden, so dass während der Laufzeit des Programms keine Typüberprüfung mehr notwendig ist. Bei der dynamischen Typisierung kann der Typ einzelner Ausdrücke erst zur Laufzeit bestimmt werden. Ein Beispiel hierfür ist die Programmiersprache Scheme. [BH98, S. 128]
Der fundamentale Zweck eines Typsystems ist die Vermeidung von Laufzeitfehlern, indem es zum Beispiel Typverletzungen erkennt. Bestandteile eines Typsystems sind zum ersten die Typen, die mittels einer Typdefinition erzeugt sind oder ein fester Bestandteil einer bestimmten Sprache sind. Zum zweiten ist es die Möglichkeit, Programmelemente mit einem bestimmten Typ zu deklarieren. Und zum dritten sind es die Regeln sowohl zur Prüfung der Typkorrektheit als auch um Werte von Ausdrücken einem Typ zuzuordnen. Grob gesagt, besteht ein Typsystem aus einer Sammlung von Regeln zur Zuweisung von Typausdrücken den verschieden Teilen eines Programms. [LC97, S.1] Eine konkrete Definition eines Typsystems ist die von Benjamin Pierce: „A type system is a tractable syntactic method for proving the absence of certain program behaviors by classifying phrases according to the kinds of values they compute.” [BP02, S.1]
Zusammenfassung der Kapitel
1 Von der Quellsprache zur Zielmaschine: Gibt einen Überblick über die verschiedenen Phasen der Übersetzung eines Programms und definiert die Rolle des Compilers innerhalb der Informatik.
2 Syntaxgerichtete Übersetzung: Erläutert die formale Basis der attributierten Grammatiken und untersucht verschiedene Ansätze zur Übersetzung mittels syntaktischer Strukturen.
3 Typüberprüfung: Behandelt die Konzepte der Typsysteme, die Unterscheidung zwischen statischer und dynamischer Prüfung sowie die Implementierung von Typüberprüfern.
4 Zusammenfassung: Fasst die wesentlichen Erkenntnisse der Arbeit zusammen und vergleicht die Merkmale der vorgestellten Attributarten und Übersetzungsklassen.
Schlüsselwörter
Compilerbau, Syntaxgerichtete Übersetzung, Parser, Attributierte Grammatik, L-attributiert, S-attributiert, Typüberprüfung, Typsystem, Statische Prüfung, Dynamische Prüfung, Semantische Analyse, Syntaktische Analyse, Syntaxbaum, Codeerzeugung, Sprachdefinition.
Häufig gestellte Fragen
Worum geht es in der Arbeit grundsätzlich?
Die Arbeit befasst sich mit den Grundlagen des Compilerbaus, insbesondere den Phasen der syntaktischen und semantischen Analyse.
Was sind die zentralen Themenfelder?
Die zentralen Themenfelder sind die syntaxgerichtete Übersetzung, die Implementierung von Attributierungen sowie die theoretischen und praktischen Aspekte der Typüberprüfung.
Was ist das primäre Ziel der Arbeit?
Das primäre Ziel ist eine kompakte Einführung in die Techniken zur Übersetzung von Quellsprachen in Zielprogramme unter Verwendung von Grammatiken und Typsystemen.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit nutzt die Literaturanalyse und formale Methoden wie kontextfreie Grammatiken, Abhängigkeitsgraphen und Übersetzungsschemata zur Beschreibung von Compilermechanismen.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die detaillierte Beschreibung syntaxgerichteter Übersetzungsverfahren (inklusive L- und S-Attributierung) und die Spezifikation eines Typüberprüfers.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit wird durch Begriffe wie Compilerbau, Syntaxgerichtete Übersetzung, Typüberprüfung, Typsystem und Attributierte Grammatik charakterisiert.
Wie unterscheidet sich die statische von der dynamischen Typüberprüfung?
Statische Typüberprüfung erfolgt während der Übersetzungszeit durch den Compiler, während die dynamische Prüfung erst zur Laufzeit des Programms stattfindet.
Was ist der Vorteil von L-attributierten Definitionen?
Ein großer Vorteil ist, dass die Übersetzung bereits während der Syntaxanalyse durchgeführt werden kann, ohne dass explizit ein vollständiger Syntaxbaum im Speicher aufgebaut werden muss.
- Arbeit zitieren
- Marco Castillo (Autor:in), 2009, Syntaxgerichtete Übersetzung und Typüberprüfung bei Computern, München, GRIN Verlag, https://www.hausarbeiten.de/document/154886
