| |
|
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 intern für die Datenverwaltung benötigt, was aber an der Kernaufgabe eines Compilers vorbeigeht.
Es lassen sich im wesentlichen zwei Phasen unterscheiden, eine Analysephase, die den Quelltext analysiert und daraus einen Baum erzeugt, sowie die Synthesephase, die daraus das Zielprogramm erzeugt.
Ein Scanner benutzt gelegentlich einen separaten Screener, um Whitespace und Kommentare zu entfernen.
Die Optimierung erfolgt in Abhängigkeit von den Eigenschaften der Hardware, insbesondere wieviele Register der Prozessor 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.
Im Folgenden betrachten wir einige Optimierungsmöglichkeiten eines Compilers. Dabei handelt es sich naturgemäss nur um Feintuning an einem bestehenden Programm. Erheblich mehr Optimierungspotential kann aber darin bestehen, dass man den programmierten Algorithmus (manuell) optimiert bzw. durch einen besseren ersetzt.
Wenn man zum Beispiel in einer höheren Programmiersprache den Inhalt von 2 Variablen vertauscht, dann benötigt man eine Hilfsvariable:
{| cellpadding="5" cellspacing="0" align="center" border="1"
|+Reduzierung von Assemblerinstruktionen
!style="background:#efefef;" |
{|
|align="center" |höhere
|-
|align="center" |Programmiersprache
|}
!style="background:#ffdeaa;" |Assembler ohne Optimierung
!colspan="2" style="background:#ffdecf;" |Assembler mit Optimierung
|-
|align="center" |t = a
|
{|
|a --> Register 1
|-
|Register 1 --> t
|}
|a --> Register 1
|-
|align="center" |a = b
|
{|
|b --> Register 2
|-
|Register 2 --> a
|}
|b --> Register 2
|-
|align="center" |b = t
|
{|
|t --> Register 3
|-
|Register 3 --> b
|}
|
{|
|Register 1 --> b
|-
|Register 2 --> a
|}
|-
|}
Mit Optimierung benötigt man nur 4 Assemblerbefehle anstatt 6, 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.
Die Berechnung des Kreisumfangs mittels
Wenn der Compiler erkennen kann, dass ein Teil des Programmes niemals durchlaufen wird, dann lässt er diesen Teil bei der Übersetzung weg.
Wird eine Variable nicht benötigt, dann wird sie auch nicht berechnet.
Insbesondere Schleifen versucht man zu optimieren, indem man
Zusammenhängender Code - z.B. eine Schleife - sollte zur Laufzeit möglichst auf einer Page im Hauptspeicher liegen. Dies kann man evtl. dadurch erreichen, dass man geeignete Leeranweisungen ("NOPs") dem Programmcode hinzufügt. Dadurch wird der Programmcode zwar größer, aber wegen des reduzierten Pagings wird das Programm schneller ausgeführt.
Aufbau eines Compilers
Analysephase
Lexikalische Analyse
Die lexikalische Analyse zerteilt die Eingabe in zusammengehörende Token verschiedener Klassen, z. B. Schlüsselwörter, Bezeichner, Zahlen und Operatoren. Diese Komponente heißt Scanner. Syntaktische Analyse
Die syntaktische Analyse überprüft, ob die Eingabe der Syntax der Quellsprache entspricht und wandelt dabei die Eingabe in einem Baum um. Dieser Teil wird auch als Parser bezeichnet.Semantische Analyse
Die semantische Analyse überprüft die statische Semantik, also Rahmenbedingungen wie dass eine Variable deklariert werden muss, bevor sie verwendet wird oder die Typkompatibilitkompatibilität von Zuweisungen.Synthesephase
Die Synthesephase erzeugt aus dem in der Analysephase erstellten Baum den Programmcode der Zielsprache.Programmoptimierung
siehe unten.Codegenerierung
Bei der Codegenerierung wird endgültig eine Objektdatei oder ein ausführbares Programm erzeugt. Programmoptimierung
Üblicherweise bietet ein Compiler Optionen für verschiedene Optimierungen mit dem Ziel, die Laufzeit oder den Speicherplatzbedarf des Zielprogramms zu verkleinern. Reduzierung von Assemblerinstruktionen
Formelauswertung bereits bei der Kompilierung
optimiert der Compiler zu "u = 6.28 * r". Die Multiplikation "2 * pi" wird während der Übersetzung ausgeführt und reduziert so die Laufzeit. pi = 3.14
u = 2 * pi * r
Eliminierung toten Programmcodes
Beispiel: ...
Wenn in diesem Programm niemals ein GOTO auf das Label 200 erfolgt, dann kann auf die Anweisung "200 k=3" verzichtet werden. goto 900
200 k=3
900 i=7
...
Erkennung von nicht benötigten Variablen
Beispiel: subroutine test (a,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 entfällt die Anweisung "c = 3.14 * b". b = 2 * a
c = 3.14 * b
return
Optimierung von Schleifen
Reduzierung von Paging zur Laufzeit
Bedeutende Compiler