Startseite
Informatik
Algorithmen
Datenstrukturen
Software-Engineering
Programmiersprachen
DRUCK
2004
2005
2006
2007
2008
2009
Compiler
Interpreter
Java
C/C++
POV-Ray
LaTeX
Künstliche Intelligenz
Schach
Privates
Inhalt
Compiler
Der Compiler übersetzt eine Quellsprache in eine Zielsprache.
Der Compiler übersetzt eine Quellsprache in eine Zielsprache.
Einführung
Definition: Compiler
Was ist ein Compiler?
Ein
Compiler
(zu deutsch: Übersetzer oder Kompilator)
ist ein Programm, das Programme aus einer Programmiersprache
A
in eine Programmiersprache
B
übersetzt.
Die Programmiersprache
A,
aus der die zu übersetzenden Programme stammen, wird dabei als
Quellsprache,
die Programmiersprache
B
als
Zielsprache
des Übersetzers bezeichnet.
Entsprechend nennt man das zu übersetzende Programm
Quellprogramm
und das übersetzte Programm
Zielprogramm.
[INFODUDEN S. 745]
Primäres Ziel bei der Erstellung eines Compilers ist es, eine neue Programmiersprache auf dem Computer ausführbar machen zu können. Für Hochsprachen werden üblicherweise Compiler entwickelt, welche in eine Low-Level-Sprache (Assemblersprache) übersetzen, die wiederum in eine Maschinensprache übersetzt werden kann. Maschinenprogramme können nämlich direkt auf einem Rechner, welcher natürlich mit einem passenden Betriebssystem ausgerüstet sein muss, ausgeführt werden.
Sekundäres Ziel bei der Erstellung eines Compilers ist die Erzeugung eines effizienten Zielprogramms, welches bzgl. seiner Ausführungsgeschwindigkeit und bzgl. seiner Speichergröße optimiert ist.
Primäres Ziel bei der Erstellung eines Compilers ist es, eine neue Programmiersprache auf dem Computer ausführbar machen zu können. Für Hochsprachen werden üblicherweise Compiler entwickelt, welche in eine Low-Level-Sprache (Assemblersprache) übersetzen, die wiederum in eine Maschinensprache übersetzt werden kann. Maschinenprogramme können nämlich direkt auf einem Rechner, welcher natürlich mit einem passenden Betriebssystem ausgerüstet sein muss, ausgeführt werden.
Sekundäres Ziel bei der Erstellung eines Compilers ist die Erzeugung eines effizienten Zielprogramms, welches bzgl. seiner Ausführungsgeschwindigkeit und bzgl. seiner Speichergröße optimiert ist.
Aufbau
Aufbau eines Compilers
Die Phasen eines Compilers
Um ein Quellprogramm in ein entsprechendes Zielprogramm abzubilden,
sollten folgende Compilerphasen verwendet werden:
- Präprozessor
Der Präprozessor vereinfacht das Quellprogramm für die nachfolgenden Compilerphasen. Diese Vorbereitung auf den eigentlichen Kompiliervorgang bringt ein neues Programm hervor, welches zum Quellprogramm äquivalent ist und zudem immer noch in der Quellsprache liegt. Es werden praktisch alle Elemente, die das Quellprogramm für den Menschen lesbarer machen, durch den Präprozessor eliminiert.
Beispielsweise werden Kommentare, welche eigentlich nur für den Menschen vorgesehen sind, entfernt. Auch werden alle im Code verwendeten Makros ersetzt (Makroexpansion). Zudem werden ganze Dateien mittels Dateiinklusion"#include <dateiname>"in den zu kompilierenden Code kopiert.
Da nun derartige Nebensächlichkeiten wegfallen, nimmt der Schwierigkeitsgrad für die Entwicklung der nachfolgenden Compilerphasen ab.
Einfaches Beispiel eines Präprozessors: Im Folgenden wird das durch den Präprozessor veränderte Quellprogramm ebenfalls als Quellprogramm bezeichnet. - Front-End
Das FrontEnd ist der Analyseabschnitt eines Compilers. Dieser Abschnitt ist dafür zuständig, das Quellprogramm zu lesen, zu strukturieren und zu prüfen, ob das Quellprogramm überhaupt „richtig” sein könnte (lexikalische und syntaktische Korrektheit des Quellprogramms). Jede einzelne Phase des FrontEnd kann auf Fehler im Quellprogramm stoßen und eventuell diese auch eigenständig beheben bzw. übergehen.- Lexikalische Analyse
(Scanner)
Bei der lexikalischen Analyse wird mit Hilfe des Scanners 1 der Zeichenstrom des Quellprogramms in eine Folge von bedeutungstragenden Symbolen (Tokens) transformiert. Diese Symbole sind üblicherweise Terminalsymbole der Grammatik der Quellsprache. Ein Symbol des Scanners wird als Token bezeichnet.
Der Scanner transformiert beispielsweise Folgen von Ziffern in Zahlen (Tokens) und Folgen von Buchstaben in Worte (Tokens). Überflüssige Zeichenfolgen wie beispielsweise Leerzeichen oder Tabulatoren sind in den meisten Sprachen keine Tokens.
Dank der Vorarbeit des Scanners muss der Parser nichts über die textuelle Zusammensetzung einer Zahl bzw. eines Wortes bzw. eines Tokens wissen. Da sich der Scanner um diesen „Kleinkram” kümmert, kann sich der Parser bei der syntaktischen Analyse ungestört größeren Aufgaben widmen. :-)
Scanner-Beispiele: - Syntaktische Analyse
(Parser)
Bei der syntaktischen Analyse prüft der Parser, 2 ob die Folge der Tokens, die er vom Scanner erhält, in der (kontextfreien) Grammatik der Quellsprache liegt. Während dieser Prüfung werden die Tokens nach und nach in eine Datenstruktur (spezieller Mehrwegebaum) eingepaßt. Der dabei entstehende Mehrwegebaum repräsentiert das Quellprogramm in Form einer für die nachfolgenden Compilerphasen handhabbaren Datenstruktur, der sogenannte Syntaxbaum (zu englisch: parse tree).
Mit der iterativen und vollständigen Abarbeitung des Quellprogramms über die Schnittstelle des Scanners endet der Parsevorgang. Das Endprodukt der syntaktischen Analyse ist der Syntaxbaum. Dieser Syntaxbaum stellt viele nützliche Operationen zur Verfügung, welche die weitere Analyse und Verarbeitung des Quellprogramms (diesmal als Datenmenge des Syntaxbaumes) erheblich erleichtern.
Parser-Beispiele: - Semantische Analyse
Bei der semantischen Analyse wird der Syntaxbaum auf Fehler geprüft und die Codeerzeugung vorbereitet. Die semantische Analyse wird notwendig, wenn die Quellsprache kontextsensitiv ist. Eine Quellsprache ist kontextsensitiv, wenn sie beispielsweise Variablen und Funktionen verwendet. Bei der Verwendung von typisierten Variablen ist eine Namens- und Typanalyse (type-check) sinnvoll, um sicherzustellen, dass die Variablen auch typgerecht eingesetzt werden.
- Lexikalische Analyse
(Scanner)
- Back-End
Das BackEnd ist der Syntheseabschnitt eines Compilers, der für die Erzeugung des Zielprogramms zuständig ist.- Zwischencodeerzeugung
Bei der Zwischencodeerzeugung wird das Zielprogramm generiert, wobei hier die Aspekte der Optimierung noch fehlen. Sinn macht aber auch, die Generierung in eine Pseudosprache, welche sich besonders gut als Grundlage für den Optimierer eignet. - Optimierung
Bei der Optimierung wird der Zwischencode optimiert, d. h. der Zwischencode wird in ein gleichwertiges Programm umgewandelt, welches weniger Speicher und weniger Rechenzeit bei der Ausführung benötigt. Beispielsweise verspricht man sich von der Eliminierung überflüssiger Variablen sowie überflüssiger Funktionen ein effizienteres Zielprogramm. Oft erreicht man durch Aufhebung der Modularität weitaus effizientere Zielprogramme. Zur Optimierung des Zwischencodes finden häufig bewährte Heuristiken, aber auch relationale Datenbankmanagementsysteme Anwendung. - Codeerzeugung
Nun denn, die Ausgabe des optimierten Zielprogramms!
- Zwischencodeerzeugung
Komponenten eines Compilers
- Präprozessor
Der Präprozessor bereitet den Compiliervorgang vor, indem er den Source-Code vereinfacht. - Scanner
Der Scanner transformiert einen Zeichenstrom in einen Tokenstrom. - Parser
Der Parser gruppiert die Token des Scanners zu grammatikalischen Phrasen. - Syntaxbaum
Der Syntaxbaum wird vom Parser erzeugt. - Das war noch nicht alles! :-(
Fußnoten
- Ein Scanner wird manchmal als lexikalischer Analysator oder als Abtaster oder als Symbolentschlüsseler bezeichnet.
- Ein Parser wird manchmal als syntaktischer Analysator oder als Zerteiler bezeichnet.
Quellenangabe
-
[INFODUDEN]