Compiler

Related Topics:
Compiler_Construction_Kits :: Compilers_and_Interpreters :: Compilers :: Compilers_and_Environments

Ein Compiler (auch Kompilierer oder Übersetzer) ist ein Computerprogramm, das ein in einer Quellsprache geschriebenes Programm in ein semantisch äquivalentes Programm einer Zielsprache umwandelt. Üblicherweise handelt es sich dabei um die Übersetzung eines von einem Programmierer in einer Programmiersprache geschriebenen Quelltextes in Assemblersprache, Bytecode oder Maschinensprache. Die Anwendung eines Compilers wird als Kompilierung bezeichnet.

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

compilerphasen.gif Es lassen sich im Wesentlichen zwei Phasen unterscheiden: eine Analysephase, die den Quelltext analysiert und daraus einen attributierten 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. Dies kann mit Hilfe von Attributgrammatiken realisiert werden. Dabei werden die Knoten des vom Parser generierten Ableitungsbaums mit Attributen "versehen", die so Informationen enthalten. So kann zum Beispiel eine Liste aller deklarierten Variablen erstellt werden. Die Ausgabe der semantischen Analyse nennt man dann dekorierter oder attributierter Syntaxbaum.

Synthesephase (auch „Backend“)

Die Synthesephase erzeugt aus dem in der Analysephase erstellten Baum den Programmcode der Zielsprache.

Zwischencodeerzeugung

Einige Compiler erzeugen einen 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.

Einordnung verschiedener Arten

Native Compiler

Compiler, der Programmcode für die Plattform erzeugt, auf der er selbst läuft.

Cross-Compiler

Compiler, der auf einer Plattform ausgeführt wird und Programmcode für eine andere Plattform, z. B. ein anderes Betriebssystem oder eine andere Prozessorarchitektur, erzeugt.

Eine typische Anwendung ist die Erstellung von Programmen für ein eingebettetes System, das selbst keine oder keine guten Werkzeuge zur Softwareerstellung enthält, sowie die Erstellung oder Portierung eines Betriebssystems auf einer neuen Plattform.

Single-pass-Compiler

Compiler, der in einem einzigen Durchlauf aus dem Quellcode den Zielcode erzeugt (im Gegensatz zum Multi-pass-Compiler). Üblicherweise ist ein derartiger Compiler sehr schnell, aber kann nur einfache Optimierungen durchführen. Nur für bestimmte Programmiersprachen, z. B. Pascal, kann ein Single-Pass-Compiler erstellt werden.

Multi-pass-Compiler

Bei diesem Compilertyp wird der Quellcode in mehreren Schritten in den Zielcode übersetzt. Während in den Anfangszeiten des Compilerbaus der Übersetzungsprozess noch hauptsächlich deshalb meist in mehrere, oft viele Durchläufe zerlegt wurde, weil die Kapazität früherer Computer oft nicht ausreichte, um den vollständigen Compiler und das zu übersetzende Programm gleichzeitig im Hauptspeicher zu halten, dient ein Multi-pass-Compiler heutzutage vor allem dazu, Vorwärtsreferenzen aufzulösen (einige Programmiersprachen lassen die Deklaration eines Bezeichners nach dessen erster Verwendung zu) und aufwendige Optimierungschritte auf dem vollständigen Syntaxbaum des Programms ausführen zu können.

Sonderformen

Bei einem Transcompiler (auch als Transpiler bezeichnet) handelt es sich um einen speziellen Compiler, der Quellcode von einer Programmiersprache in den Quellcode einer anderen Programmiersprache übersetzt, z. B. von Pascal in C.
Da jedoch viele Programmiersprachen besondere Eigenschaften und Leistungsmerkmale besitzen, die nur in den seltensten Fällen von Transcompilern berücksichtigt werden, kommt es häufig zu Effizienzverlusten. Oft ist auch eine manuelle Nachbearbeitung des Codes nötig, da die automatische Übersetzung nicht in allen Fällen zu hundert Prozent funktioniert.

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. Effektiv sind viele heutige Interpreter zur Verringerung der Ausführungszeit intern als Compreter implementiert, die den Quellcode zur Laufzeit übersetzen, bevor er ausgeführt wird.

Geschichte

Grace Hopper.jpg 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. Ein Nachteil ist allerdings, 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, lediglich 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 (s. Profiler) 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

In vielen höheren Programmiersprachen benötigt man beispielsweise eine Hilfsvariable, um den Inhalt zweier Variablen zu vertauschen:

Programmiersprache ohne Optimierung mit Optimierung Register 1 → t Register 1 → a Register 1 → b Register 2 → a

**Einsparung von Maschinenbefehlen**
Höhere	Maschinenbefehle	Maschinenbefehle
t = a	a → Register 1	a → Register 1
a = b	b → Register 1	b → Register 2
b = t	t → Register 1	Register 1 → b

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.2830 * r auswerten. Dies spart die Multiplikation 2 * pi zur Laufzeit des erzeugten Programms. Diese Vorgehensweise wird als Konstantenfaltung (engl. „constant folding“) bezeichnet. (Compiler für die Sprache Ada müssen diese Compile-Zeit-Berechnungen sogar in beliebiger Genauigkeit durchführen.)

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).
statt eines Index, mit dem auf Elemente eines Feldes (englisch array) zugegriffen wird, Zeiger auf die Elemente verwendet. Dadurch wird der Aufwand beim Zugriff auf Feldelemente geringer.
Berechnungen innerhalb der Schleife, die in jedem Durchlauf dasselbe Ergebnis liefern, nur einmal vor der Schleife ausführt.
zwei Schleifen, die über denselben Wertebereich gehen, zu einer Schleife zusammenfasst. Damit fällt der Verwaltungsaufwand für die Schleife nur einmal an.
die Schleife teilweise oder (bei Schleifen mit konstanter, niedriger Durchlaufzahl) komplett auflöst (englisch loop unrolling), sodass die Anweisungen innerhalb der Schleife mehrfach direkt hintereinander ausgeführt werden, ohne dass jedesmal nach den Anweisungen eine Prüfung der Schleifenbedingung und ein Sprung zum Schleifenbeginn erfolgen.
die Schleife (vor allem bei Zählschleifen mit for) umgedreht wird, da beim Herunterzählen auf 0 effiziente Sprungbefehle (Jump-Not-Zero) benutzt werden können.
die Schleife umformt, damit die Überprüfung der Abbruchbedingung am Ende der Schleife durchgeführt wird (Schleifen mit Anfangsüberprüfung haben stets eine bedingte und eine unbedingte Sprunganweisung, während Schleifen mit Endüberprüfung nur eine bedingte Sprunganweisung haben).
wenn eine Schleife (nach einigen Optimierungen) einen leeren Rumpf besitzt, sie ganz entfernen kann. Dies kann allerdings dazu führen, dass Warteschleifen, die ein Programm absichtlich verlangsamen sollen, entfernt werden. Allerdings sollten für diesen Zweck, soweit möglich, sowieso möglichst Funktionen des Betriebssystems benutzt werden.

Einfügen von Unterprogrammen

Bei kleinen Unterprogrammen fällt der Aufwand zum Aufruf des Unterprogrammes verglichen mit der vom Unterprogramm geleisteten Arbeit stärker ins Gewicht. Daher versuchen Compiler, den Maschinencode kleinerer Unterprogramme direkt einzufügen. Diese Technik wird auch als Inlining bezeichnet. In manchen Programmiersprachen ist es möglich, durch inline-Schlüsselwörter den Compiler darauf hinzuweisen, dass das Einfügen von bestimmten Unterprogrammen gewünscht ist. Das Einfügen von Unterprogrammen eröffnet oft, abhängig von den Parametern, weitere Möglichkeiten für Optimierungen.

Halten von Werten in Registern

Anstatt mehrfach auf dieselbe Variable im Speicher, beispielsweise in einer Datenstruktur, zuzugreifen, kann der Wert nur einmal gelesen und für weitere Verarbeitungen in Registern oder im Stack zwischengespeichert werden.
In C, C++ und Java muss dieses Verhalten ggf. mit dem Schlüsselwort volatile abgeschaltet werden: Eine als volatile bezeichnete Variable wird bei jeder Benutzung wiederholt vom originalem Speicherplatz gelesen, da ihr Wert sich unterdessen geändern haben könnte. Das kann beispielsweise der Fall sein, wenn es sich um einen Hardware-Port handelt oder ein parallel laufender Thread den Wert geändert haben könnte.

Beispiel: int a = array^*->element.x; int b = 3 * array^*->element.x;

Im Maschinenprogramm wird nur einmal auf array^*->element.x zugegriffen, der Wert wird zwischengespeichert und zweimal verwendet. Ist x volatile, dann wird zweimal zugegriffen.

Es gibt außer volatile noch einen anderen Grund, der eine Zwischenspeicherung in Registern unmöglich macht: Wenn der Wert der Variablen v durch Verwendung des Zeigers z im Speicher verändert werden könnte, kann eine Zwischenspeicherung von v in einem Register zu fehlerhaftem Programmverhalten führen. Da die in der Programmiersprache C oft verwendeten Zeiger nicht auf ein Array beschränkt sind (sie könnten irgendwohin im Hauptspeicher zeigen), hat der Optimizer oft nicht genügend Informationen, um eine Veränderung einer Variable durch einen Zeiger auszuschließen.

Verwendung von schnelleren äquivalenten Anweisungen

Statt einer Multiplikation oder Division von Ganzzahlen mit einer Zweierpotenz kann eine Shift-Anweisung verwendet werden. Es gibt Fälle, in denen nicht nur Zweierpotenzen, sondern auch andere Zahlen (einfache Summen von Zweierpotenzen) für diese Optimierung herangezogen werden. So kann z. B. n << 1 + n << 2 schneller sein als n * 6. Statt einer Division durch eine Konstante kann eine Multiplikation mit dem Reziprokwert der Konstante erfolgen. Selbstverständlich sollte man solch spezielle Optimierungen auf jeden Fall dem Compiler überlassen.

Weglassen von Laufzeitüberprüfungen

Programmiersprachen wie Pascal und Java fordern Laufzeitüberprüfungen beim Zugriff auf Felder oder Variablen. Wenn der Compiler ermittelt, dass ein bestimmter Zugriff immer im erlaubten Bereich sein wird, kann der Code für diese Laufzeitüberprüfungen weggelassen werden.

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.

Ein Beispielcompiler

Folgendes in der Programmiersprache C definierte Programm stellt einen einfachen Einpass-Compiler dar. Dieser Compiler übersetzt einfache Ausdrücke in Infix-Notation in Ausdrücke der Postfix-Notation sowie in eine maschinennahe Assemblersprache.

#include 
include 
include 
define MODE_POSTFIX 	0
define MODE_ASSEMBLY 	1
char    lookahead;
int     pos;
int	compile_mode;
char    expression^*;
void error() {
  printf("Syntaxfehler!\n");
}
void match( char t ) {
  if( lookahead == t ) {
    pos++;
    lookahead = expression^*;            
  }
  else
    error();
}
void digit() {
  switch( lookahead ) {
    case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
        printf( compile_mode == MODE_POSTFIX ? "%c" : "\tPUSH %c\n", lookahead );
        match( lookahead );
        break;
    default:
        error();
        break;
  }
}
void term() {
  digit();
  while( 1 ) {
    switch( lookahead ) {
      case '*':
        match('*');
        digit();
        printf( "%s", compile_mode == MODE_POSTFIX ? "*" : "\tPOP B\n\tPOP A\n\tMUL A, B\n\tPUSH A\n" );
        break;
      case '/':
        match('/');
        digit();
        printf( "%s", compile_mode == MODE_POSTFIX ? "/" : "\tPOP B\n\tPOP A\n\tDIV A, B\n\tPUSH A\n" );
        break;
      default:
        return;
    }
  }
}
void expr() {
  term();
  while( 1 ) {
    switch( lookahead ) {
      case '+':
        match('+');
        term();
        printf( "%s", compile_mode == MODE_POSTFIX ? "+" : "\tPOP B\n\tPOP A\n\tADD A, B\n\tPUSH A\n" );
        break;
      case '-':
        match('-');
        term();
        printf( "%s", compile_mode == MODE_POSTFIX ? "-" : "\tPOP B\n\tPOP A\n\tSUB A, B\n\tPUSH A\n");
        break;
      default:
        return;
    }
  }
}
int main ( int argc, char** argv ) {
  printf("Bitte geben Sie einen Ausdruck in Infix-Notation ein:\n\n\t");
  gets( expression );
        
  printf("\nCompilierter Ausdruck in Postfix-Notation:\n\n\t");	
  compile_mode = MODE_POSTFIX;
  pos = 0;
  lookahead = *expression;
  expr();
                
  printf("\n\nCompilierter Ausdruck in Assemblersprache:\n\n");        
  compile_mode = MODE_ASSEMBLY;
  pos = 0;
  lookahead = *expression;
  expr();
  return 0;
}

Ein Lauf dieses Compilers führt beispielsweise zu folgender Ausgabe:

Bitte geben Sie einen Ausdruck in Infix-Notation ein:

5+3*2-9

Compilierter Ausdruck in Postfix-Notation:

532*+9-

Compilierter Ausdruck in Assemblersprache:

PUSH 5 PUSH 3 PUSH 2 POP B POP A MUL A, B PUSH A POP B POP A ADD A, B PUSH A PUSH 9 POP B POP A SUB A, B PUSH A

Bekannte Compiler

GNU Compiler Collection (GCC)
Intel C++ Compiler (ICC)
Microsoft Visual C++
Borland C++Builder
Turbo Pascal (historisch)
Jikes, ein Java-Compiler, der ursprünglich von IBM entwickelt wurde und nun als quelloffenes Projekt weitergeführt wird.
Viele andere, die zusammen mit IDEs (Integrierte Entwicklungsumgebung) ausgeliefert werden (Microsoft Visual Basic, Borland Delphi etc.)

Siehe auch

Compilerbau

Literatur

Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Compilers - Principles, Techniques, and Tools, Addison Wesley, 2003, ISBN 0-201-10194-7
deutsche Fassung: Compilerbau, 2. durchges. Aufl.; Oldenbourg, 1999, Tl. 1 ISBN 3-486-25294-1, Tl. 2 ISBN 3-486-25266-6

Weblinks

compilers.net
Ken Thompson, Reflections on Trusting Trust. Exzellenter englischer Artikel über Softwaresicherheit und deren Untergrabung, etwa durch Trojaner in Compilern.

Compilerbau | Programmierwerkzeug

Gourt Home::Gourt :: Compiler