Compiler
Der Compilerbau, also die Programmierung eines Compilers, ist eine eigenständige Disziplin innerhalb der Informatik.
Die Bezeichnungen Compiler oder Kompilierer sind eigentlich irreführend, weil sie von der Zusammenstellung von Tabellen herrühren, die der Compiler für seine interne Datenverwaltung benötigt, was aber an der Kernaufgabe eines Compilers vorbeigeht.
Verwandt mit einem Compiler ist ein Interpreter, der ein Programm nicht in die Zielsprache übersetzt, sondern Schritt für Schritt direkt ausführt.
Aufbau eines Compilers
Es lassen sich im Wesentlichen zwei Phasen unterscheiden: eine Analysephase, die den Quelltext analysiert und daraus einen Syntaxbaum erzeugt, sowie die Synthesephase, die daraus das Zielprogramm erzeugt.
Analysephase (auch "Frontend")
Lexikalische Analyse
Die lexikalische Analyse zerteilt den eingelesenen Quelltext in zusammengehörende Token verschiedener Klassen, z.B. Schlüsselwörter, Bezeichner, Zahlen und Operatoren. Dieser Teil des Compilers heißt Scanner oder Lexer.Ein Scanner benutzt gelegentlich einen separaten Screener, um Whitespace (Leerraum, also Leerzeichen, Zeilenenden, usw.) und Kommentare zu überspringen.
Syntaktische Analyse
Die syntaktische Analyse überprüft, ob der eingelesene Quellcode formal richtig ist, d.h. der Syntax (Grammatik) der Quellsprache entspricht. Dabei wird die Eingabe in einen Syntaxbaum umgewandelt. Dieser Teil wird auch als Parser bezeichnet.Semantische Analyse
Die semantische Analyse überprüft die statische Semantik, also "logische Rahmenbedingungen". Zum Beispiel muss eine Variable deklariert worden sein, bevor sie verwendet wird, und Zuweisungen müssen mit kompatiblen (verträglichen) Datentypen erfolgen.Synthesephase (auch "Backend")
Die Synthesephase erzeugt aus dem in der Analysephase erstellten Baum den Programmcode der Zielsprache.Zwischencodeerzeugung
Einige Compiler erzeugen Zwischencode, der schon relativ maschinennah ist, und führen auf diesem Zwischencode z. B. die Programmoptimierung durch. Das bietet sich besonders bei Compilern an, die mehrere verschiedene Zielplattformen unterstützen.Programmoptimierung
Die Optimierungen finden hier meist auf dem zuvor erstellten Objektcode statt. Siehe Programmoptimierung.Codegenerierung
Bei der Codegenerierung wird endgültig aus dem Syntaxbaum der Programmcode in der Zielsprache erzeugt. Falls die Zielsprache die Maschinensprache ist, kann das Ergebnis direkt ein ausführbares Programm sein oder eine so genannte Objektdatei, die durch das Linken mit der Laufzeitbibliothek und evtl. weiteren Objektdateien zu einer Bibliothek oder einem ausführbaren Programm führt.Sonderformen
- Transpiler (auch Transcompiler) übersetzen Quellcode einer Programmiersprache in den Quellcode einer anderen Programmiersprache. Zum Beispiel ist bei den .NET-Programmiersprachen von Microsoft eine Übersetzung von C# nach VB.NET relativ einfach, da beide Sprachen auf demselben Grundgerüst aufbauen (.NET-Framework).
- Compilercompiler|Compiler-Compiler und Compilergeneratoren sind Hilfsprogramme zur automatischen Generierung von Compilerteilen oder vollständigen Compilern. siehe auch: JavaCC, Lex, Yacc
- Just-In-Time-Compiler (oder JIT-Compiler) übersetzen Quellcode oder Bytecode erst bei der Ausführung des Programmes in Maschinencode. Dabei werden meist nur die benötigten Programmteile übersetzt und von einer virtuellen Maschine interpretiert.
- Beim Compreter wird der Programm - Quellcode zunächst in einen Zwischencode übersetzt, der dann zur Laufzeit interpretiert wird. Compreter sollten die Vorteile des Compilers mit den Vorteilen des Interpreters verbinden.
Geschichte
Der erste Compiler (A-0) wurde 1952 von der Mathematikerin Grace Hopper entwickelt.
Programmoptimierung (ausführlich)
Üblicherweise bietet ein Compiler Optionen für verschiedene Optimierungen mit dem Ziel, die Laufzeit der einzelnen Programmschritte oder den Speicherplatzbedarf des Zielprogramms zu minimieren.Die Optimierung erfolgt teilweise in Abhängigkeit von den Eigenschaften der Hardware, z. B. wie viele und welche Register der Prozessor des Computers zur Verfügung stellt.
Einige Optimierungen führen dazu, dass der Compiler Programmkonstrukte in semantisch äquivalente, aber günstigere Konstrukte umwandelt, die keine Entsprechung im Quellcode haben. Eine Folge ist, dass es bei Aktivierung entsprechender Optimierungen kaum noch möglich ist, den Programmablauf mit einem interaktiven Debugger zu verfolgen.
"Optimierung" bedeutet nicht, dass das Programm danach in irgendeiner Weise optimal wäre, nur besser. Es ist auch möglich, dass das Programm nachher "totoptimiert" ist, also die Optimierung über das Ziel so weit hinausgeschossen ist, dass das Programm effektiv langsamer ausgeführt wird. Das ist z. B. dadurch möglich, dass längerer Code erzeugt wird, der zwar an sich schneller ausgeführt wird, aber mehr Zeit benötigt, um erst einmal in den Cache geladen zu werden, und damit erst bei häufigerer Benutzung vorteilhaft ist.
Viele Optimierungen moderner Compiler sind solche Abwägungen zwischen dem, was möglich ist, und dem, was sinnvoll ist. Die Grenze zwischen beiden ist meist nicht klar ersichtlich und muss durch Tests (Profiling) herausgefunden werden.
Im Folgenden betrachten wir einige Optimierungsmöglichkeiten eines Compilers. Es sollte aber nicht vergessen werden, dass das größte Optimierungspotenzial oft darin besteht, den Algorithmus selbst zu verändern bzw. durch einen besseren zu ersetzen. Dieser Vorgang kann meistens nicht automatisiert werden, sondern muss durch den Programmierer erfolgen. Einfachere Optimierungen kann er dagegen an den Compiler delegieren und so den Quelltext lesbarer halten.
Einsparung von Maschinenbefehlen
Wenn man zum Beispiel in einer höheren Programmiersprache den Inhalt von 2 Variablen vertauscht, dann benötigt man eine Hilfsvariable:
| Maschinenbefehle ohne Optimierung | Maschinenbefehle mit Optimierung | ||||
|---|---|---|---|---|---|---|
| t = a |
| a --> Register 1 | ||||
| a = b |
| b --> Register 2 | ||||
| b = t |
|
| ||||
Mit der Optimierung werden statt 6 nur noch 4 Assemblerbefehle benötigt, außerdem wird der Speicherplatz für die Hilfsvariable t nicht gebraucht. D.h. diese Vertauschung wird schneller ausgeführt und benötigt weniger Hauptspeicher. Dies gilt jedoch nur, wenn ausreichend Register im Prozessor zur Verfügung stehen. Die Speicherung von Daten in Registern statt im Hauptspeicher, ist eine häufig angewendete Möglichkeit der Optimierung.
Statische Formelauswertung zur Übersetzungszeit
Die Berechnung des Kreisumfangs mittels
pi = 3.1415
u = 2 * pi * r
kann ein Compiler bereits zum Übersetzungszeitpunkt zu "u = 6.283 * r" auswerten. Dies spart die Multiplikation "2*pi" zur Laufzeit des erzeugten Programms. Diese Vorgehensweise wird als Konstantenfaltung (engl. "constant folding") bezeichnet.Elimination toten Programmcodes
Wenn der Compiler erkennen kann, dass ein Teil des Programmes niemals durchlaufen wird, dann kann er diesen Teil bei der Übersetzung weglassen.
Beispiel: ... ...
100 goto 900
200 k=3
900 i=7
... ...
Wenn in diesem Programm niemals ein GOTO auf das Label 200 erfolgt, dann kann auf die Anweisung "200 k=3" verzichtet werden.Erkennung von unbenutzten Variablen
Wird eine Variable nicht benötigt, so muss dafür kein Speicherplatz zugewiesen und kein Programmcode erzeugt werden.
Beispiel: subroutine test (a,b)
b = 2 * a
c = 3.14 * b
return b
Hier wird die Variable c nicht benötigt: Sie steht nicht in der Parameterliste, wird in späteren Berechnungen nicht verwendet und wird auch nicht ausgegeben. Deshalb kann die Anweisung "c = 3.14 * b" entfallen.Optimierung von Schleifen
Insbesondere Schleifen versucht man zu optimieren, indem man z.B.:
- möglichst viele Variablen in Registern hält (normalerweise mindestens die Schleifenvariable)
- Berechnungen innerhalb der Schleife, die in jedem Durchlauf dasselbe Ergebnis liefern, nur einmal vor der Schleife berechnet
- die Schleife teilweise oder (bei Schleifen mit konstanter, niedriger Durchlaufzahl) komplett auflöst (englisch loop unrolling), sodass die Anweisungen innerhalb der Schleife mehrfach hintereinander ausgeführt werden, ohne dass jedesmal nach den Anweisungen ein Sprung zum Schleifenbeginn erfolgt.
- die Schleife (vor allem bei Zählschleifen mit for) umgedreht wird, da dekrementieren schneller vonstatten geht.
Reduktion von Paging zur Laufzeit
Zusammenhängender Code - z. B. eine Schleife - sollte zur Laufzeit möglichst auf der gleichen "Seite" (zusammenhängend vom Betriebssystem verwalteter Speicherblock) im Hauptspeicher liegen. Dies kann man z. B. dadurch erreichen, dass man dem Programmcode geeignete Leeranweisungen ("NOPs" - No OPeration) hinzufügt. Dadurch wird der Programmcode zwar größer, aber wegen des reduzierten Pagings wird das Programm schneller ausgeführt.
Vorziehen/Verzögern von Speicherzugriffen
Durch das Vorziehen von Speicherlesezugriffen und das Verzögern von Schreibzugriffen lässt sich die Fähigkeit moderner Prozessoren zur Parallelarbeit verschiedener Funktionseinheiten ausnutzen. So kann beispielsweise bei den Befehlen: a = b * c; d = e * f; der Operand e bereits geladen werden während ein anderer Teil des Prozessors noch mit der ersten Multiplikation beschäftigt ist.
Bekannte Compiler
- GNU Compiler Collection (GCC)
- Intel C Compiler (ICC)
- Microsoft Visual C++
- Turbo Pascal (historisch)
Siehe auch: Compilerbau
