Compiler

Ein Übersetzer ist ein Programm, das als Eingabe ein in einer Quellsprache formuliertes Programm akzeptiert und es in ein semantisch äquivalentes Programm in einer Zielsprache übersetzt.[1] Es wird also insbesondere gefordert, dass das erzeugte Programm die gleichen Ergebnisse wie das gegebene Programm liefert. Als Ausnahme wird oft die Quell-Sprache Assembler angesehen – ihr Übersetzer (in Maschinencode) heißt „Assembler“ und wird i. A. nicht als „Compiler“ bezeichnet. Die Aufgabe des Übersetzers umfasst ein großes Spektrum an Teilaufgaben, von der Syntaxanalyse bis zur Zielcodeerzeugung. Eine wichtige Aufgabe besteht auch darin, Fehler im Quellprogramm zu erkennen und zu melden.

Das Wort „Compiler“ stammt vom Englischen „to compile“ (dt. zusammentragen, zusammenstellen) ab und heißt im eigentlichen Wortsinn also „Zusammentrager“. In den 1950er-Jahren war der Begriff noch nicht fest in der Computerwelt verankert.[2] Ursprünglich bezeichnete Compiler ein Hilfsprogramm, das ein Gesamtprogramm aus einzelnen Unterprogrammen oder Formelauswertungen zusammentrug, um spezielle Aufgaben auszuführen. (Diese Aufgabe erfüllt heute der Linker, der jedoch auch im Compiler integriert sein kann.) Die einzelnen Unterprogramme wurden noch „von Hand“ in Maschinensprache geschrieben. Ab 1954 kam der Begriff „algebraic compiler“ für ein Programm auf, das die Umsetzung von Formeln in Maschinencode selbständig übernahm. Das „algebraic“ fiel im Laufe der Zeit weg.[3]

Ende der 1950er-Jahre wurde der Begriff des Compilers im englischsprachigen Raum noch kontrovers diskutiert. So hielt das Fortran-Entwicklerteam noch jahrelang am Begriff „translator“ (deutsch „Übersetzer“) fest, um den Compiler zu bezeichnen. Diese Bezeichnung ist sogar im Namen der Programmiersprache Fortran selbst enthalten: Fortran ist zusammengesetzt aus Formula und Translation, heißt also in etwa Formel-Übersetzung. Erst 1964 setzte sich der Begriff Compiler auch im Zusammenhang mit Fortran gegenüber dem Begriff Translator durch. Nach Carsten Busch liegt eine „besondere Ironie der Geschichte darin“, dass der Begriff Compiler im Deutschen mit „Übersetzer“ übersetzt wird.[2][4] Einige deutsche Publikationen verwenden jedoch auch den englischen Fachbegriff Compiler anstelle von Übersetzer.[5]

In einem engeren Sinne verwenden einige deutschsprachige Publikationen den Fachbegriff Compiler jedoch nur, wenn die Quellsprache eine höhere Programmiersprache ist als die Zielsprache.[6] Typische Anwendungsfälle sind die Übersetzung einer höheren Programmiersprache in die Maschinensprache eines Computers, sowie die Übersetzung in Bytecode einer virtuellen Maschine. Zielsprache von Compilern (in diesem Sinne) kann auch eine Assemblersprache sein. Ein Übersetzer zur Übertragung von Assembler-Quellprogrammen in Maschinensprache wird als Assembler oder Assemblierer bezeichnet.[7]

Bereits für die erste entworfene höhere Programmiersprache, den Plankalkül von Konrad Zuse, plante dieser – nach heutiger Terminologie – einen Compiler. Zuse bezeichnete ein einzelnes Programm als Rechenplan und hatte schon 1944 die Idee für ein sogenanntes Planfertigungsgerät, welches automatisch aus einem mathematisch formulierten Rechenplan einen gestanzten Lochstreifen mit entsprechendem Maschinenplan für den Zuse-Z4-Computer erzeugen sollte.[8]

Konkreter als die Idee von Zuse eines Planfertigungsgeräts war ein Konzept von Heinz Rutishauser[9] zur automatischen Rechenplanfertigung. In einem Vortrag vor der Gesellschaft für Angewandte Mathematik und Mechanik (GAMM) wie auch 1951 in seiner Habilitationsschrift an der ETH Zürich beschrieb er, welche zusätzlichen Programmierbefehle (Instruktionen) und Hardware-Ergänzungen an der damals an der ETHZ genutzten Z4 nötig seien, um den Rechner ebenfalls als Hilfsmittel zur automatischen Programmerstellung einzusetzen.[10][11][12]

Grace Hopper (1984)

Ein früher Compiler wurde 1949 von der Mathematikerin Grace Hopper konzipiert. Bis zu diesem Zeitpunkt mussten Programmierer direkt Maschinencode erstellen. (Der erste Assembler wurde zwischen 1948 und 1950 von Nathaniel Rochester für eine IBM 701 geschrieben.) Um diesen Prozess zu vereinfachen, entwickelte Grace Hopper eine Methode, die es ermöglichte, Programme und ihre Unterprogramme in einer mehr an der menschlichen als der maschinellen Sprache orientierten Weise auszudrücken.[13] Am 3. Mai 1952 stellte Hopper den ersten Compiler A-0 vor, der Algorithmen aus einem Katalog abrief, Code umschrieb, in passender Reihenfolge zusammenstellte, Speicherplatz reservierte und die Zuteilung von Speicheradressen organisierte.[14] Anfang 1955 präsentierte Hopper bereits einen Prototyp des Compilers B-0, der nach englischen, französischen oder deutschen Anweisungen Programme erzeugte.[15] Hopper nannte ihren Vortrag zum ersten Compiler „The Education of a Computer“ („Die Erziehung eines Computers“).

Die Geschichte des Compilerbaus wurde von den jeweils aktuellen Programmiersprachen (vgl. Zeittafel der Programmiersprachen) und Hardwarearchitekturen geprägt. Weitere frühe Meilensteine sind 1957 der erste Fortran-Compiler und 1960 der erste COBOL-Compiler. Viele Architekturmerkmale heutiger Compiler wurden aber erst in den 1960er Jahren entwickelt.

Früher wurden teilweise auch Programme als Compiler bezeichnet, die Unterprogramme zusammenfügen.[16] Dies geht an der heutigen Kernaufgabe eines Compilers vorbei, weil Unterprogramme heutzutage mit anderen Mitteln eingefügt werden können: Entweder im Quelltext selbst, beispielsweise von einem Präprozessor (siehe auch Precompiler) oder bei übersetzten Komponenten von einem eigenständigen Linker.

Die prinzipiellen Schritte bei der Übersetzung eines Quellcodes in einen Zielcode lauten:

Syntaxprüfung

Es wird geprüft, ob der Quellcode ein gültiges Programm darstellt, also der Syntax der Quellsprache entspricht. Festgestellte Fehler werden protokolliert. Ergebnis ist eine Zwischendarstellung des Quellcodes.

Analyse und Optimierung

Die Zwischendarstellung wird analysiert und optimiert. Dieser Schritt variiert im Umfang je nach Compiler und Benutzereinstellung stark. Er reicht von einfacheren Effizienzoptimierungen bis hin zu Programmanalyse.

Codeerzeugung

Die optimierte Zwischendarstellung wird in entsprechende Befehle der Zielsprache übersetzt. Hierbei können weitere, zielsprachenspezifische Optimierungen vorgenommen werden.

Beachte: Moderne Compiler führen mittlerweile (meist) keine Codegenerierung mehr selbst durch.

• C++ bei eingeschalteter globaler Optimierung: Die Codegenerierung erfolgt beim Linken.
• C#: Die Codegenerierung erfolgt aus, während der Kompilierung erzeugtem, Common-Intermediate-Language-Code während der Laufzeit durch den JIT- oder NGEN-Compiler der .NET-Umgebung.
• gleiches gilt für andere Sprachen, die die Common Language Infrastructure nutzen wie F# und VB.NET, siehe Liste von .NET-Sprachen.
• Java: Die Codegenerierung erfolgt aus, während der Kompilierung erzeugtem, Java-Byte-Code während der Laufzeit durch den Java-JIT-Compiler.

Codegenerierung während der Runtime ermöglicht:

• modulübergreifende Optimierungen,
• exakte Anpassungen an die Zielplattform (Befehlssatz, Anpassung an die Fähigkeiten der CPU),
• Nutzung von Profiling-Informationen.

Der Compilerbau, also die Programmierung eines Compilers, ist eine eigenständige Disziplin innerhalb der Informatik.

Moderne Compiler werden in verschiedene Phasen gegliedert, die jeweils verschiedene Teilaufgaben des Compilers übernehmen. Einige dieser Phasen können als eigenständige Programme bzw. Softwarekomponenten realisiert werden, z. B. Precompiler oder Präprozessor. Sie werden sequentiell ausgeführt. Im Wesentlichen lassen sich zwei Phasen unterscheiden: das Frontend (auch Analysephase), das den Quelltext analysiert und daraus einen attributierten Syntaxbaum erzeugt, sowie das Backend (auch Synthesephase), das daraus den Programmcode der Zielsprache erzeugt.

Native Compiler

Compiler, der den Zielcode für die Plattform erzeugt, auf der er selbst läuft. Der Code ist plattformspezifisch.

Cross-Compiler

Compiler, der auf einer Plattform ausgeführt wird und Zielcode für eine andere Plattform, zum Beispiel 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 eine neue Plattform.

Single-pass-Compiler

Compiler, der in einem einzigen Durchlauf aus dem Quellcode den Zielcode erzeugt (im Gegensatz zum Multi-pass-Compiler); der Compiler liest also den Quelltext von vorne nach hinten nur ein Mal und erzeugt zugleich das Ergebnisprogramm. Üblicherweise ist ein derartiger Compiler sehr schnell, aber kann nur einfache Optimierungen durchführen. Nur für bestimmte Programmiersprachen, zum Beispiel Pascal, C und C++, kann ein Single-Pass-Compiler erstellt werden, denn dazu darf die Programmiersprache keine Vorwärtsbezüge enthalten (es darf nichts verwendet werden, was nicht bereits „weiter oben“ im Quelltext deklariert wurde).

Multi-pass-Compiler

Bei diesem Compilertyp wird der Quellcode in mehreren Schritten in den Zielcode übersetzt (ursprünglich: der Quellcode wird mehrmals eingelesen bzw. mehrfach „von vorne nach hinten“ komplett durchgearbeitet). In den Anfangszeiten des Compilerbaus wurde der Übersetzungsprozess hauptsächlich deshalb in mehrere Durchläufe zerlegt, weil die Kapazität der Computer oft nicht ausreichte, um den vollständigen Compiler und das zu übersetzende Programm gleichzeitig im Hauptspeicher zu halten. Heutzutage dient ein Multi-pass-Compiler vor allem dazu, Vorwärtsreferenzen (Deklaration eines Bezeichners „weiter unten im Quelltext“ als dessen erste Verwendung) aufzulösen und aufwändige Optimierungen durchzuführen.

• Bei einem Transcompiler (auch als Transpiler oder Quer-Übersetzer bezeichnet) handelt es sich um einen speziellen Compiler, der Quellcode einer Programmiersprache in den Quellcode einer anderen Programmiersprache übersetzt, zum Beispiel von Pascal in C.[17] Man nennt diesen Vorgang „Code-Transformation“ oder „übersetzen“. Da jedoch viele Programmiersprachen besondere Eigenschaften und Leistungsmerkmale besitzen, kann es, wenn diese nicht vom Transcompiler berücksichtigt werden, zu Effizienzverlusten kommen.[18] Da Programmiersprachen meist unterschiedlichen Programmierparadigmen folgen, ist der neu generierte Quelltext oft nur schwer für Entwickler lesbar. Manchmal ist auch eine manuelle Nachbearbeitung des Codes nötig, da die automatische Übersetzung nicht in allen Fällen reibungsfrei funktioniert. Außerdem gibt es in vielen modernen Programmiersprachen umfangreiche Unterprogrammbibliotheken. Das Umsetzen von Bibliotheksaufrufen erschwert den Übersetzungsvorgang zusätzlich.
• Compiler-Compiler und Compilergeneratoren sind Hilfsprogramme zur automatischen Generierung von Compilerteilen oder vollständigen Compilern. Siehe auch: ANTLR, Coco/R, JavaCC, Lex, Yacc
• Just-in-time-Compiler (oder JIT-Compiler) übersetzen Quellcode oder Zwischencode erst bei der Ausführung des Programms in Maschinencode. Dabei werden Programmteile erst übersetzt, wenn diese erstmals oder mehrmals ausgeführt werden. Meist ist der Grad der Optimierung abhängig von der Benutzungshäufigkeit der entsprechenden Funktion.
• 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 das Programm ausgeführt wird. Auch ein Bytecode-Interpreter ist ein Compreter, z. B. die virtuellen Maschinen von Java bis Version 1.2.

Viele Optimierungen, die früher Aufgabe des Compilers waren, werden mittlerweile innerhalb der CPU während der Codeabarbeitung vorgenommen. Maschinencode ist gut, wenn er kurze kritische Pfade und wenig Überraschungen durch falsch vorhergesagte Sprünge aufweist, Daten rechtzeitig aus dem Speicher anfordert und alle Ausführungseinheiten der CPU gleichmäßig auslastet.

Parallelisierte Berechnung der Mandelbrotmenge auf einer Haswell i7-CPU (2014). Die Grafik zeigt die gleichzeitig auf einem Kern stattfindenden Berechnungen (Datentyp: Gleitkomma, einfache Genauigkeit), das sind zwischen 64 und 128 Berechnungen in 8 bis 16 Befehlen pro Kern, aufgeteilt auf 2 Threads. Auf einem Haswell Core i7-5960X (8 Kerne) findet damit bis zu 1024 parallele Berechnungen (96 Mrd. Iterationen/sec) statt, auf einem Haswell Xeon E7-8890 V3 bis zu 2304 (180 Mrd. Iterationen/sec pro Sockel). Die Aufgabe moderner Compiler ist es, Code so zu optimieren, um diese Verschachtelung von Befehlen zu ermöglichen. Dies ist eine grundsätzlich andere Aufgabe als Compiler in den späten 1980er Jahren hatten.

Zur Steuerung des Übersetzens kann der Quelltext neben den Anweisungen der Programmiersprache zusätzliche spezielle Compiler-Anweisungen enthalten.

Üblicherweise bietet ein Compiler Optionen für verschiedene Optimierungen mit dem Ziel, die Laufzeit des Zielprogramms zu verbessern oder dessen Speicherplatzbedarf zu minimieren. Die Optimierungen erfolgen teilweise in Abhängigkeit von den Eigenschaften der Hardware, zum Beispiel wie viele und welche Register der Prozessor des Computers zur Verfügung stellt. Es ist möglich, dass ein Programm nach einer Optimierung langsamer ausgeführt wird, als das ohne die Optimierung der Fall gewesen wäre. Dies kann zum Beispiel eintreten, wenn eine Optimierung für ein Programmkonstrukt längeren Code erzeugt, der zwar an sich schneller ausgeführt werden würde, aber mehr Zeit benötigt, um erst einmal in den Cache geladen zu werden. Er ist damit erst bei häufigerer Benutzung vorteilhaft.

Einige Optimierungen führen dazu, dass der Compiler Zielsprachenkonstrukte erzeugt, für die es gar keine direkten Entsprechungen in der Quellsprache gibt. Ein Nachteil solcher Optimierungen ist, dass es dann kaum noch möglich ist, den Programmablauf mit einem interaktiven Debugger in der Quellsprache zu verfolgen.

Optimierungen können sehr aufwendig sein. Vielfach muss vor allem in modernen JIT-Compilern daher abgewogen werden, ob es sich lohnt, einen Programmteil zu optimieren. Bei Ahead-of-time-Compilern werden bei der abschließenden Übersetzung alle sinnvollen Optimierungen verwendet, häufig jedoch nicht während der Software-Entwicklung (reduziert den Kompilier-Zeitbedarf). Für nichtautomatische Optimierungen seitens des Programmierers können Tests und Anwendungsszenarien durchgespielt werden (s. Profiler), um herauszufinden, wo sich komplexe Optimierungen lohnen.

Im Folgenden werden einige Optimierungsmöglichkeiten eines Compilers betrachtet. Das größte Optimierungspotenzial besteht allerdings oft in der Veränderung des Quellprogramms selbst, zum Beispiel darin, einen Algorithmus durch einen effizienteren zu ersetzen. Dieser Vorgang kann meistens nicht automatisiert werden, sondern muss durch den Programmierer erfolgen. Einfachere Optimierungen können dagegen an den Compiler delegiert werden, um den Quelltext lesbar zu halten.

pi = 3.14159
u  = 2 * pi * r

100   goto 900
200   k=3
900   i=7
...   ...

subroutine test (a,b)
    b = 2 * a
    c = 3.14 * b
    return b

int a = array[25]->element.x;
int b = 3 * array[25]->element.x;

Folgendes in ANTLR erstelltes Beispiel soll die Zusammenarbeit zwischen Parser und Lexer erklären. Der Übersetzer soll Ausdrücke der Grundrechenarten beherrschen und vergleichen können. Die Parsergrammatik wandelt einen Dateiinhalt in einen abstrakten Syntaxbaum (AST) um.

tree grammar Eval;
options {
	tokenVocab=Expression;
	ASTLabelType=CommonTree;
}
@header {
import java.lang.Math;
}
start	: line+; //Eine Datei besteht aus mehreren Zeilen
line	: compare {System.out.println($compare.value);}
	;

compare returns [double value]
	: ^('+' a=compare b=compare) {$value = a+b;}
	| ^('-' a=compare b=compare) {$value = a-b;}
	| ^('*' a=compare b=compare) {$value = a*b;}
	| ^('/' a=compare b=compare) {$value = a/b;}
	| ^('%' a=compare b=compare) {$value = a\%b;}
	| ^(UMINUS a=compare)        {$value = -1*a;} //Token UMINUS ist notwendig, um den binären
                                                      //Operator nicht mit einem Vorzeichen zu verwechseln
	| ^('^' a=compare b=compare) {$value = Math.pow(a,b);}
	| ^('=' a=compare b=compare) {$value = (a==b)? 1:0;} //wahr=1, falsch=0
	| INT {$value = Integer.parseInt($INT.text);}
	;

grammar Expression;
options {
	output=AST;
	ASTLabelType=CommonTree;
}
tokens {
	UMINUS;
}
start	:	(line {System.out.println($line.tree==null?"null":$line.tree.toStringTree());})+;
line	:	compare NEWLINE -> ^(compare); //Eine Zeile besteht aus einem Ausdruck und einem
                                              //terminalen Zeichen
compare	:	sum ('='^ sum)?; //Summen sind mit Summen vergleichbar
sum	: 	product	('+'^ product|'-'^ product)*; //Summen bestehen aus Produkten (Operatorrangfolge)
product	:	pow ('*'^ pow|'/'^ pow|'%'^ pow)*; //Produkte (Modulo-Operation gehört hier dazu) können
                                                  //aus Potenzen zusammengesetzt sein
pow	: 	term ('^'^ pow)?; //Potenzen werden auf Terme angewendet
term	:	number //Terme bestehen aus Nummern, Subtermen oder Summen
		|'+' term -> term
		|'-' term -> ^(UMINUS term) //Subterm mit Vorzeichen
		|'('! sum ')'! //Subterm mit Klammerausdruck
		;
number	:	INT; //Nummern bestehen nur aus Zahlen
INT	:	'0'..'9'+;
NEWLINE	:	'\r'? '\n';
WS	:	(' '|'\t'|'\n'|'\r')+ {skip();}; //Whitespace wird ignoriert

5 = 2 + 3
32 * 2 + 8
(2 * 2^3 + 2) / 3

(= 5 (+ 2 3))
(+ (* 32 2) 8)
(/ (+ (* 2 (^ 2 3)) 2) 3)
1.0
72.0
6.0

• Uwe Meyer: Grundkurs Compilerbau. 1. Auflage. Rheinwerk Computing, Bonn 2021, ISBN 978-3-8362-7733-4.
• Niklaus Wirth: Grundlagen und Techniken des Compilerbaus. 3., bearbeitete Auflage. Oldenbourg Wissenschaftsverlag, München 2011, ISBN 978-3-486-70951-3.
• Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman: Compiler. Pearson, 2008, ISBN 978-3-8273-7097-6 (Deutsche Übersetzung).
• Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman: Compilers: principles, techniques, & tools. Pearson Addison-Wesley, Boston 2007, ISBN 978-0-321-48681-3.
• Reinhard Wilhelm, Dieter Maurer: Übersetzerbau – Theorie, Konstruktion, Generierung. Springer, 1997, ISBN 3-540-61692-6.