Compiler

Begriff und Aufgabe

Ein Compiler, auch Kompilierer, ist ein Computerprogramm, das Quellcode einer Programmiersprache in eine Form übersetzt, die ein Computer direkt oder nahezu direkt ausführen kann. Das Ergebnis ist ein mehr oder weniger direkt ausführbares Programm. Der Übersetzungsvorgang heißt Kompilierung oder Umwandlung.

Ein Übersetzer nimmt ein Programm in einer Quellsprache auf und erzeugt ein semantisch äquivalentes Programm in einer Zielsprache. Semantisch äquivalent bedeutet, dass das erzeugte Programm dieselben Ergebnisse liefert wie das Ausgangsprogramm. Compiler sind spezielle Übersetzer: Sie übersetzen meist höhere Programmiersprachen in Maschinensprache, Assemblersprache oder den Zwischencode einer virtuellen Maschine. Die Begriffe Übersetzer und Compiler werden jedoch nicht immer streng unterschieden.

Ein Übersetzer für Assembler-Quellprogramme heißt Assembler oder Assemblierer und wird im Allgemeinen nicht Compiler genannt. Die Rückübersetzung von Maschinensprache in Quelltext heißt Dekompilierung; entsprechende Programme heißen Decompiler. Im Unterschied zum Compiler erzeugt ein Interpreter, etwa für frühe BASIC-Versionen, keinen Maschinencode, sondern führt Quellcode unmittelbar beziehungsweise schrittweise aus. Eine wichtige Aufgabe jedes Übersetzers ist außerdem, Fehler im Quellprogramm zu erkennen und zu melden.

Entwicklung und grundlegender Aufbau

Schon Konrad Zuse plante für den Plankalkül, die erste entworfene höhere Programmiersprache, ein automatisches Planfertigungsgerät. Es sollte aus einem mathematisch formulierten Rechenplan einen Maschinenplan für den Zuse-Z4-Computer erzeugen. Heinz Rutishauser beschrieb 1951, welche Befehle und Hardware-Ergänzungen für eine automatische Rechenplanfertigung nötig wären.

Grace Hopper konzipierte 1949 einen frühen Compiler. Am 3. Mai 1952 stellte sie A-0 vor. Dieses Programm rief Algorithmen aus einem Katalog ab, schrieb Code um, stellte ihn in passender Reihenfolge zusammen, reservierte Speicherplatz und ordnete Speicheradressen zu. Anfang 1955 präsentierte Hopper den Prototyp B-0, der aus englischen, französischen oder deutschen Anweisungen Programme erzeugte. Weitere Meilensteine waren der erste Fortran-Compiler 1957 und der erste COBOL-Compiler 1960. Viele Merkmale heutiger Compiler entstanden in den 1960er-Jahren.

Moderne Compiler sind in Phasen gegliedert. Das Frontend, auch Analysephase, analysiert den Quelltext und erzeugt einen annotierten beziehungsweise attributierten Syntaxbaum. Das Backend, auch Synthesephase, erzeugt daraus den Zielcode. Dazwischen kann ein Zwischencode stehen, der besonders nützlich ist, wenn ein Compiler mehrere Quellsprachen oder Zielplattformen unterstützt.

Im Frontend wird der Quelltext zunächst lexikalisch analysiert. Ein Lexer, Scanner oder Tokenizer zerlegt ihn in Tokens, also lexikalische Einheiten wie Schlüsselwörter, Bezeichner, Zahlen, Zeichenketten und Operatoren. Leerraum und Kommentare können von einem Screener übersprungen werden. Tokens erhalten oft ihre Position, zum Beispiel die Zeilennummer, damit Fehler genauer gemeldet werden können. Zeichenfolgen ohne gültige Token-Zuordnung sind lexikalische Fehler; ein Beispiel ist der Bezeichner „3foo“, wenn Bezeichner nicht mit Ziffern beginnen dürfen.

Die syntaktische Analyse prüft, ob die Tokenfolge der Grammatik der Quellsprache entspricht, und wandelt sie in einen Syntaxbaum um. Der Parser erkennt zum Beispiel falsche Klammerung oder unzulässige Strukturen. Die semantische Analyse prüft darüber hinaus die statische Semantik: Eine Variable muss normalerweise vor ihrer Verwendung deklariert sein, und Zuweisungen müssen kompatible Datentypen besitzen. Dazu können Attributgrammatiken dienen. Das Ergebnis ist ein dekorierter oder attributierter Syntaxbaum. Bei Sprachen wie modernem C++ erschweren Mehrdeutigkeiten in der Grammatik die klare Trennung dieser Analysen.

Im Backend wird aus dem Syntaxbaum oder Zwischencode der Zielcode erzeugt. Dieser kann Maschinensprache, Objektcode oder ein anderer Zielcode sein. Eine Objektcode-Datei wird gegebenenfalls durch Linken mit Laufzeitbibliotheken und weiteren Objektdateien zu einer Bibliothek oder einem ausführbaren Programm verbunden. Moderne Compiler erzeugen den endgültigen Maschinencode allerdings häufig erst später: Bei C++ kann dies bei eingeschalteter globaler Optimierung beim Linken geschehen; bei C# und anderen .NET-Sprachen erzeugen JIT- oder NGEN-Compiler zur Laufzeit aus Common-Intermediate-Language-Code den Maschinencode; bei Java geschieht dies aus Java-Bytecode durch den Java-JIT-Compiler. Laufzeit-Codegenerierung ermöglicht unter anderem modulübergreifende Optimierungen, genaue Anpassungen an Befehlssatz und CPU sowie die Nutzung von Profiling-Informationen.

Compilerarten und Sonderformen

Ein nativer Compiler erzeugt Zielcode für die Plattform, auf der er selbst läuft. Ein Cross-Compiler läuft auf einer Plattform, erzeugt aber Code für eine andere Plattform, etwa ein anderes Betriebssystem oder eine andere Prozessorarchitektur. Das ist besonders bei eingebetteten Systemen sowie bei der Erstellung oder Portierung eines Betriebssystems nützlich.

Ein Single-Pass-Compiler liest den Quelltext nur einmal von vorne nach hinten und erzeugt dabei den Zielcode. Er ist üblicherweise schnell, kann aber nur einfache Optimierungen durchführen. Er setzt eine Programmiersprache ohne Vorwärtsbezüge voraus; verwendet werden darf also nichts, was erst weiter unten im Quelltext deklariert wird. Ein Multi-pass-Compiler verarbeitet den Quellcode in mehreren Durchläufen. Früher war dies vor allem wegen begrenzter Hauptspeicherkapazität nötig. Heute dienen mehrere Durchläufe insbesondere dazu, Vorwärtsreferenzen aufzulösen und aufwändige Optimierungen auszuführen.

Ein Transcompiler, Transpiler oder Quer-Übersetzer wandelt Quellcode einer Programmiersprache in Quellcode einer anderen um, zum Beispiel von Pascal in C. Dabei können Effizienzverluste, schwer lesbarer Code oder notwendige manuelle Nachbearbeitung entstehen; auch Bibliotheksaufrufe erschweren die automatische Umsetzung. Compiler-Compiler und Compilergeneratoren erzeugen automatisch Compilerteile oder vollständige Compiler. Just-in-time-Compiler übersetzen Quellcode oder Zwischencode erst während der Ausführung in Maschinencode. Programmteile werden dabei häufig erst übersetzt, wenn sie erstmals oder wiederholt ausgeführt werden; die Optimierungsstärke kann von der Nutzungshäufigkeit abhängen. Ein Compreter übersetzt den Quellcode zunächst in Zwischencode, der anschließend zur Laufzeit interpretiert wird. Damit verbindet er Eigenschaften von Compiler und Interpreter; auch Bytecode-Interpreter, etwa die virtuellen Maschinen von Java bis Version 1.2, gehören dazu.

Optimierung des Programmcodes

Compileroptimierung soll meist die Laufzeit verkürzen oder den Speicherbedarf verringern. Sie hängt unter anderem von der Hardware und der Zahl und Art der Prozessorregister ab. Eine Optimierung kann sich jedoch auch nachteilig auswirken, etwa wenn längerer Code zwar schneller läuft, aber länger in den Cache geladen werden muss. Optimierte Zielkonstrukte können außerdem so weit von der Quellsprache abweichen, dass interaktives Debuggen erschwert wird. Bei JIT-Compilern muss deshalb abgewogen werden, ob sich eine Optimierung lohnt; bei Ahead-of-time-Compilern werden sinnvolle Optimierungen meist bei der abschließenden Übersetzung angewendet. Das größte Optimierungspotenzial liegt häufig in einem besseren Algorithmus, den der Programmierer selbst auswählen muss.

Typische Verfahren sind:

• Beim Vertauschen von Variablen kann eine Hilfsvariable entfallen. Im Beispiel sinkt die Zahl der Maschinenbefehle von 6 auf 4, der Speicherbedarf für „hilf“ entfällt, dafür werden 2 statt 1 Register benötigt. Das funktioniert nur bei genügend Registern. Unabhängige Lese- und Schreibbefehle können auf Prozessoren mit mehreren Pipelines parallel ausgeführt werden.
• Konstantenfaltung berechnet Formeln bereits zur Übersetzungszeit. Aus „pi = 3.14159“ und „u = 2 * pi * r“ kann „u = 6.28318 * r“ werden; die Multiplikation „2 * pi“ entfällt zur Laufzeit.
• Toter Programmcode, der nie ausgeführt werden kann, wird entfernt. Im Beispiel „100 goto 900; 200 k=3; 900 i=7“ können die Anweisung „200 k=3“ und der dadurch überflüssige Sprung „100 goto 900“ entfallen, wenn kein GOTO auf 200 erfolgt.
• Unbenutzte Variablen benötigen weder Speicherplatz noch Zielcode. In „subroutine test (a,b); b = 2 * a; c = 3.14 * b; return b“ kann die Berechnung von „c“ entfallen, weil „c“ weder Parameter noch später benötigt oder ausgegeben wird.
• Schleifen können durch Registerhaltung, Zeiger statt Indexzugriffen, das Vorziehen schleifeninvarianter Berechnungen, das Zusammenlegen gleicher Schleifen, Loop Unrolling, das Herunterzählen bis 0, eine Prüfung am Schleifenende oder die vollständige Entfernung eines leeren Schleifenrumpfs optimiert werden. Verschachtelte Schleifen können, wenn die Logik es erlaubt, von der Schleife mit den wenigsten zu der mit den meisten Durchläufen angeordnet werden. Manche Verfahren sind bei modernen Prozessoren wirkungslos oder kontraproduktiv.
• Beim Inlining wird der Maschinencode kleiner Unterprogramme direkt an der Aufrufstelle eingefügt. Dadurch entfällt Aufrufaufwand; außerdem können weitere Optimierungen möglich werden.
• Werte können statt wiederholt aus dem Speicher aus Registern oder dem Stack verwendet werden. „volatile“ verhindert in C, C++ und Java gegebenenfalls diese Zwischenspeicherung, etwa bei Hardware-Ports oder Änderungen durch parallele Threads. Auch mögliche Änderungen über Zeiger können Registeroptimierung verhindern.
• Multiplikationen oder Divisionen mit einer Zweierpotenz können durch Schiebebefehle ersetzt werden. Beispielsweise kann „(n << 1) + (n << 2)“ schneller sein als „n * 6“. Eine Division durch eine Konstante kann auch durch eine Multiplikation mit ihrem Reziprokwert ersetzt werden.
• Nachweislich unnötige Laufzeitüberprüfungen, etwa eine Bereichsprüfung oder die Prüfung auf NULL, können entfallen. Speicherlesezugriffe lassen sich vorziehen und Schreibzugriffe verzögern, um parallele Funktionseinheiten besser auszulasten.

Auch die räumliche Anordnung des Codes beeinflusst die Laufzeit. Zusammenhängende Bereiche wie Schleifenrümpfe sollten möglichst auf wenigen Speicherseiten liegen. Diese Optimierung übernimmt der optimierende Linker manchmal durch eingefügte NOPs. Der Code wird dadurch größer, kann aber wegen weniger TLB-Cache-Einträge und Pagewalks schneller laufen. Moderne Compiler sollen außerdem die Verschachtelung von Befehlen ermöglichen. Auf einer Haswell-i7-CPU können bei der parallelisierten Mandelbrotberechnung 64 bis 128 Gleitkommaberechnungen einfacher Genauigkeit in 8 bis 16 Befehlen pro Kern und auf 2 Threads stattfinden; ein Haswell Core i7-5960X mit 8 Kernen erreicht bis zu 1024 parallele Berechnungen beziehungsweise 96 Mrd. Iterationen pro Sekunde, ein Haswell Xeon E7-8890 V3 bis zu 2304 beziehungsweise 180 Mrd. Iterationen pro Sekunde pro Sockel.

Beispiel: Ausdrücke mit ANTLR

Der Beispielcompiler wurde mit ANTLR erstellt und zeigt das Zusammenspiel von Lexer und Parser. Er verarbeitet Ausdrücke der Grundrechenarten und Vergleiche. Die Parsergrammatik erzeugt aus jeder Eingabezeile einen abstrakten Syntaxbaum (AST). Die Operatoren stehen darin als Präfixnotation vor ihren Operanden, sodass die Baumgrammatik die Ausdrücke anhand des Operators auswerten kann. Klammern und die Rangfolge der Operationen bleiben dabei korrekt erhalten. Unterstützt werden Addition, Subtraktion, Multiplikation, Division, Modulo, unäres Minus, Potenzen und Gleichheitsvergleiche. Bei Vergleichen bedeutet wahr 1 und falsch 0.

Der Lexer zerlegt nicht erkannte Ausdrücke durch rekursiven Abstieg weiter, bis nur noch Zahlen beziehungsweise Operatoren übrig sind. Die Grammatik definiert unter anderem „INT : '0'..'9'+“, „NEWLINE : '\r'? '\n'“ und ignoriert Leerzeichen, Tabulatoren und Zeilenenden als Whitespace.

Eingabe: „5 = 2 + 3“ „32 * 2 + 8“ „(2 * 2^3 + 2) / 3“

Die AST-Darstellung lautet: „(= 5 (+ 2 3))“ „(+ (* 32 2) 8)“ „(/ (+ (* 2 (^ 2 3)) 2) 3)“

Danach gibt der Compiler aus: „1.0“ „72.0“ „6.0“

Der erste Ausdruck ist somit wahr und wird als 1.0 ausgegeben; die beiden anderen Ausdrücke liefern die berechneten Ergebnisse.