Funktionsweise und Phasen eines Compilers

Ein Compiler ist ein Computerprogramm, das ein in einer Quellsprache geschriebenes Programm in eine andere Programmiersprache übersetzt. Er erzeugt ein entsprechendes Programm, das die Maschine interpretieren kann. Gewöhnlich ist die zweite Sprache eine Maschinensprache, sie kann aber auch reiner Text sein. Dieser Übersetzungsvorgang wird als Kompilation bezeichnet.¹

Ein Compiler ist ein Programm, das den Quellcode eines Programms von einer Hochsprache in eine andere, niederschwelligere Sprache (in der Regel Maschinensprache) übersetzen kann. Auf diese Weise kann ein Entwickler ein Programm in einer Sprache entwerfen, die der menschlichen Denkweise viel näher kommt, und es dann für einen Computer in eine besser handhabbare Form kompilieren.

Der Build-Prozess

Es ist der Prozess, durch den Anweisungen, die in einer bestimmten Programmiersprache geschrieben wurden, in Maschinensprache übersetzt werden. Neben einem Übersetzer benötigen Sie möglicherweise andere Programme, um aus einem Objektprogramm ein ausführbares Programm zu erstellen. Ein Quellprogramm kann in verschiedene Dateien aufgeteilt und in Modulen gespeichert werden. Die Aufgabe, das Quellprogramm zusammenzuführen, wird oft einem separaten Programm namens Präprozessor anvertraut. Der Präprozessor kann auch Abkürzungen, Makroaufrufe und Quellsprachen-Anweisungen erweitern.

Normalerweise besteht die Erstellung eines ausführbaren Programms (eine typische .exe für Microsoft Windows oder DOS) aus zwei Schritten. Der erste Schritt heißt Kompilierung (im eigentlichen Sinne) und übersetzt den in einer Programmiersprache geschriebenen Quellcode in eine Datei, die Code auf niedrigem Niveau speichert (in der Regel Objektcode, noch nicht direkt Maschinensprache). Der zweite Schritt heißt Linken (Binden), bei dem der generierte Low-Level-Code aller Dateien und Unterprogramme, die zum Kompilieren angewiesen wurden, verknüpft wird. Zudem wird der Funktionscode aus den Compiler-Bibliotheken hinzugefügt, um die Kommunikation des ausführbaren Programms mit dem Betriebssystem zu ermöglichen. Schließlich erfolgt die Übersetzung des Objektcodes in Maschinencode und die Erzeugung eines ausführbaren Moduls.

Diese beiden Schritte können getrennt durchgeführt werden, wobei das Ergebnis der Erfassungsphase in Objektdateien gespeichert wird (eine typische .obj für Microsoft Windows, DOS oder Unix), die später zusammengeführt werden. Alternativ kann direkt eine ausführbare Datei erstellt werden, sodass die Kompilierungsphase nur temporär gespeichert wird. Ein Programm könnte Teile enthalten, die beispielsweise in verschiedenen Sprachen geschrieben wurden (C, C++ und Assembler), die getrennt kompiliert und dann zu einem einzigen ausführbaren Modul zusammengeführt werden könnten.

Phasen des Prozesses

Der Übersetzungsprozess besteht intern aus mehreren Stufen oder Phasen, die verschiedene logische Operationen durchführen. Es ist sinnvoll, sich den Übersetzer als aus separaten Teilen bestehend vorzustellen, die in der Praxis jedoch oft als gemeinsam integrierte, kodierte Operationen geschrieben werden.

Analysephase

Lexikalische Analyse

Hauptartikel: Lexer

Die lexikalische Analyse ist der erste Schritt. Hier wird das Quellprogramm von links nach rechts gelesen und in lexikalische Komponenten (Tokens) gruppiert, welche Sequenzen von Zeichen mit einer bestimmten Bedeutung sind. Zusätzlich werden Leerzeichen, Leerzeilen, Kommentare und andere unnötige Informationen aus dem Quellprogramm entfernt. Es wird auch überprüft, ob die Symbole der Sprache (Schlüsselwörter, Operatoren, ...) korrekt geschrieben sind.

Da die Aufgaben, die vom lexikalischen Analysator durchgeführt werden, ein Spezialfall der Mustererkennung sind, werden Spezifikationsmethoden wie reguläre Ausdrücke und endliche Automaten benötigt. Da der lexikalische Analysator jedoch ein Übersetzer ist, der den Quellcode verwaltet und dieser Vorgang oft einen erheblichen Zeitaufwand bedeutet, muss er so effizient wie möglich arbeiten.

Parsing (Syntaxanalyse)

Hauptartikel: Parser

In diesem Stadium werden die Zeichen oder lexikalischen Komponenten hierarchisch in grammatikalische Phrasen gruppiert, die der Compiler zur Synthese der Ausgabe verwendet. Es wird geprüft, ob das Ergebnis der vorherigen Phase syntaktisch korrekt ist (gemäß der Grammatik der Sprache). Im Allgemeinen wird die grammatikalische Struktur der Sätze des Quellprogramms durch eine Analyse ermittelt.

Die hierarchische Struktur wird in der Regel mithilfe von Rekursion ausgedrückt. Zum Beispiel können die folgenden Regeln als Teil der Definition von Ausdrücken dienen:

• Jeder Bezeichner ist ein Ausdruck.
• Jede Zahl ist ein Ausdruck.
• Wenn Ausdruck₁ und Ausdruck₂ Ausdrücke sind, dann sind auch:
  • Ausdruck₁ + Ausdruck₂
  • Ausdruck₁ * Ausdruck₂
  • (Ausdruck₁)

Regeln 1 und 2 sind Grundregeln (nicht rekursiv), während Artikel 3 Ausdrücke in Bezug auf andere Ausdrücke definiert.

Die Trennung zwischen lexikalischer Analyse und Syntaxanalyse ist etwas willkürlich. Ein Faktor zur Unterscheidung ist, ob eine Konstruktion der Quellsprache von Natur aus rekursiv ist oder nicht. Lexikalische Konstruktionen erfordern keine Rekursion, während syntaktische Strukturen diese oft benötigen. Rekursion ist nicht erforderlich, um Bezeichner zu erkennen, die in der Regel Zeichenfolgen aus Buchstaben und Ziffern sind, die mit einem Buchstaben beginnen. Normalerweise werden Bezeichner erkannt, indem die Eingabe betrachtet wird, bis ein Zeichen gefunden wird, das weder Buchstabe noch Ziffer ist, und alle bis dahin gelesenen Zeichen in einer lexikalischen ID zusammengefasst werden. Diese Art der Analyse ist jedoch nicht stark genug, um Sätze oder Ausdrücke zu analysieren. Zum Beispiel können wir Klammern in Ausdrücken oder Wörter in Sätzen wie begin und end nicht korrekt zuordnen, ohne eine Art hierarchische Verschachtelung am Eingang zu berücksichtigen.

Semantische Analyse

Die Phase der semantischen Analyse prüft das Quellprogramm auf semantische Fehler und sammelt Informationen für die spätere Phase der Codegenerierung. Sie nutzt die hierarchische Struktur der Sätze, die durch die syntaktische Analyse bestimmt wurde, zur Identifizierung der Operatoren und Operanden in Ausdrücken.

Eine wichtige Komponente der semantischen Analyse ist die Typprüfung. Hier prüft der Compiler, ob jeder Operator Operanden hat, die laut Spezifikation der Quellsprache erlaubt sind. Zum Beispiel verlangen Definitionen vieler Programmiersprachen, dass der Compiler einen Fehler meldet, wenn eine reelle Zahl als Index einer Matrix verwendet wird. Die Spezifikationssprache kann jedoch Beschränkungen für Operanden festlegen, zum Beispiel wenn ein binärer arithmetischer Operator auf eine reelle Zahl und eine Ganzzahl angewendet wird. Es wird auch geprüft, ob die definierte Größe der Regelung korrekt ist.

Synthesephase

Ziel ist es, den Objektcode zu generieren, der dem Quellprogramm entspricht. Objektcode wird nur generiert, wenn das Quellprogramm frei von Analysefehlern ist. Das bedeutet jedoch nicht zwangsläufig, dass das Programm korrekt läuft, da es logische Missverständnisse enthalten kann. Normalerweise ist der Objektcode verschiebbarer Maschinencode oder Assembler-Code. Für jede der verwendeten Variablen werden Speicherplätze ausgewählt. Dann wird jede der Zwischenanweisungen in eine Folge von Maschinenanweisungen übersetzt, die dieselbe Ausführung bewirken. Ein entscheidender Aspekt ist die Zuordnung von Variablen zu Registern.

Erzeugung von Zwischencode

Nach der syntaktischen und semantischen Analyse generieren Compiler eine explizite Zwischendarstellung des Quellprogramms. Man kann dies als ein Programm für eine abstrakte Maschine betrachten. Diese Zwischendarstellung muss zwei wichtige Eigenschaften haben: Sie sollte leicht zu produzieren und einfach in das Zielprogramm zu übersetzen sein.

Die Zwischendarstellung kann viele Formen annehmen. Es gibt eine Form namens Drei-Adress-Code, die wie der Assembler einer Maschine ist, in der jede Speicherstelle wie ein Register agieren kann. Der Drei-Adress-Code besteht aus einer Folge von Anweisungen, von denen jede höchstens drei Operanden hat. Diese Darstellung hat mehrere Eigenschaften:

• Erstens: Jede Anweisung hat höchstens einen Operator zusätzlich zur Zuweisung, sodass der Übersetzer die Reihenfolge der Operationen festlegen muss.
• Zweitens: Der Übersetzer muss temporäre Namen vergeben, um die berechneten Werte zu speichern.
• Drittens: Einige Anweisungen im Drei-Adress-Code haben weniger als drei Operanden, wie zum Beispiel die Zuweisung.

Code-Optimierung

Die Phase der Code-Optimierung dient dazu, den Zwischencode zu verbessern, damit der resultierende Maschinencode schneller ausgeführt wird. Diese Phase der Synthese ist besonders wichtig, wenn der Übersetzer ein Compiler ist (ein Interpreter kann den Objektcode kaum optimieren). Es gibt große Unterschiede im Ausmaß der Optimierung zwischen verschiedenen Compilern. In sogenannten optimierenden Compilern wird ein erheblicher Teil der Zeit in dieser Phase verbracht. Es gibt jedoch auch einfache Optimierungen, die die Ausführungszeit deutlich verbessern, ohne die Kompilierung zu stark zu verlangsamen.

Struktur der wichtigsten Daten

Die Wechselwirkung zwischen den Algorithmen der Compiler-Phasen und den unterstützenden Datenstrukturen ist sehr stark. Entwickler bemühen sich, diese Algorithmen so effektiv wie möglich zu implementieren, ohne zu viel Komplexität hinzuzufügen. Idealerweise sollte ein Compiler in der Lage sein, ein Programm in einer zum Umfang proportionalen Zeit zu kompilieren.

Komponenten oder lexikalische Tokens

Wenn ein lexikalischer Analysator ein Token erkennt, stellt er dieses in der Regel als symbolisches Zeichen dar, d. h. als Wert eines aufgezählten Datentyps. Manchmal ist es auch nötig, die ursprüngliche Zeichenfolge oder andere daraus abgeleitete Informationen zu speichern, wie den Namen eines Bezeichners oder den Wert einer Zahl.

In den meisten Sprachen muss der lexikalische Analysator nur ein Token zur Zeit generieren. In diesem Fall reicht eine einfache globale Variable aus. In anderen Fällen (wie bei FORTRAN) wird ein Array oder Vektor von Tokens benötigt.

Syntaxbaum

Wenn der Parser einen Syntaxbaum erzeugt, basiert dieser in der Regel auf einer Struktur aus Zeigern (Pointern), die während des Parsens dynamisch zugewiesen werden. Der gesamte Baum kann in einer einzelnen Variablen gespeichert werden, die auf den Wurzelknoten zeigt. Jeder Knoten im Baum ist ein Datensatz, dessen Felder die vom Parser und der semantischen Analyse gesammelten Informationen enthalten. Zum Beispiel kann der Datentyp eines Ausdrucks als Feld im entsprechenden Knoten des Syntaxbaums gespeichert werden.

Um Platz zu sparen, können diese Felder manchmal dynamisch zugewiesen oder in anderen Strukturen wie der Symboltabelle gespeichert werden. Tatsächlich kann jeder Knoten im Syntaxbaum je nach Art der Sprachstruktur unterschiedliche Attribute erfordern. In diesem Fall kann jeder Knoten durch einen Datensatz dargestellt werden, der nur die für diesen Fall notwendigen Informationen enthält.

Tabelle der Symbole

Diese Datenstruktur verwaltet Informationen zu Bezeichnern für Funktionen, Variablen, Konstanten und Datentypen. Die Symboltabelle interagiert mit nahezu allen Phasen des Compilers: Die lexikalische Analyse, der Parser und der Semantikanalysator tragen Bezeichner ein, der semantische Analysator fügt Datentypen hinzu, und die Phasen der Codegenerierung und Optimierung nutzen diese Informationen, um den passenden Objektcode auszuwählen.

Da häufig auf die Symboltabelle zugegriffen wird, müssen Operationen wie Einfügen, Löschen und Suchen effizient sein, vorzugsweise in konstanter Zeit. Eine Standard-Datenstruktur hierfür ist die Hash-Tabelle, obwohl auch Baumstrukturen verwendet werden können. Manchmal werden mehrere Tabellen in einer Liste oder einem Stapel verwaltet.

Tabelle der Literale

Schnelles Suchen und Einfügen ist auch für die Literaltabelle wichtig, die Konstanten und verwendete Zeichenfolgen speichert. Eine Literaltabelle muss Löschungen verhindern, da die Daten global im Programm verwendet werden und eine Konstante oder ein String nur einmal in der Tabelle erscheinen sollte. Die Literaltabelle ist wichtig, um die Größe eines Programms zu reduzieren, indem Konstanten und Strings wiederverwendet werden. Sie ist auch notwendig, damit der Codegenerator Adressen für die Literale im Objektcode aufbauen kann.

Intermediate Code (Zwischencode)

Je nach Art des Zwischencodes (z. B. Drei-Adress-Code oder P-Code) und den durchgeführten Optimierungen kann dieser Code als Liste, Array von Strings, temporäre Textdatei oder in verwandten Strukturen gespeichert werden. In Compilern, die komplexe Optimierungen durchführen, sollte die Darstellung eine einfache Reorganisation ermöglichen.

Intermediate Code-Generierung

Nach der syntaktischen und semantischen Analyse generieren Compiler eine explizite Zwischendarstellung des Quellprogramms. Man kann dies als eine Darstellung für eine abstrakte Maschine betrachten. Diese Zwischendarstellung muss leicht zu produzieren und einfach in das Zielprogramm zu übersetzen sein.

Die Zwischendarstellung kann viele Formen annehmen. Eine davon ist der „Drei-Adress-Code“, der wie Assemblersprache für eine Maschine funktioniert, in der jeder Speicherplatz als Register agieren kann. Der Drei-Adress-Code besteht aus einer Folge von Anweisungen mit höchstens drei Operanden. Der Quellprogramm-Code (1) kann im Drei-Adress-Code wie folgt erscheinen:

temp1 := entarea1(60)

temp2 := id3 * temp1(2)

temp3 := id2 + temp2

id1 := temp3

Diese Darstellung hat mehrere Eigenschaften. Erstens hat jede Anweisung höchstens einen Operator zusätzlich zur Zuweisung. Wenn diese Anweisungen vom Compiler generiert werden, muss dieser entscheiden, in welcher Reihenfolge sie durchgeführt werden (z. B. Multiplikation vor Addition). Zweitens muss der Compiler temporäre Namen erzeugen, um die berechneten Werte zu speichern. Drittens haben einige Anweisungen weniger als drei Operatoren, wie die erste und letzte Anweisung.

Code-Optimierung

Die Phase der Code-Optimierung versucht, den Zwischencode zu verbessern, damit der Maschinencode schneller ausgeführt wird. Einige Optimierungen sind trivial. Zum Beispiel erzeugt ein natürlicher Algorithmus für den Zwischencode (2) Anweisungen basierend auf dem Baum der semantischen Analyse, obwohl es einen besseren Weg gibt, dieselben Berechnungen durchzuführen:

temp1 := id3 * 60.0 (3)

id1 := id2 + temp1

An dem einfachen Algorithmus ist nichts falsch, da das Problem in der Optimierungsphase gelöst werden kann. Das heißt, der Compiler kann schlussfolgern, dass die Umwandlung von 60 von Real zu Integer einmalig während der Kompilierung durchgeführt werden kann, sodass die Operation entreal entfällt. Darüber hinaus wird temp3 nur einmal verwendet, um seinen Wert an id1 zu übergeben. Daher ist es effizienter, temp3 durch id1 zu ersetzen, wodurch der letzte Satz entfällt und man den Code (3) erhält.

Es gibt viele Variationen im Ausmaß der Optimierung. Bei einem „optimierenden Compiler“ wird ein erheblicher Teil der Zeit in dieser Phase verbracht. Es gibt jedoch einfache Optimierungen, die die Ausführungszeit deutlich verbessern, ohne die Kompilierung zu stark zu verlangsamen.

Temporäre Dateien

Frühere Computer verfügten nicht über genügend Speicher, um ein vollständiges Programm während der Kompilierung zu speichern. Dieses Problem wurde mithilfe von temporären Dateien gelöst, um Zwischenergebnisse der Übersetzung zu speichern oder „on the fly“ zu kompilieren, wobei nur genügend Informationen aus früheren Teilen des Quellprogramms behalten wurden, um die Übersetzung fortzuführen.

Speicherbeschränkungen sind heute ein viel kleineres Problem, und eine ganze Kompilationseinheit kann im Speicher gehalten werden, besonders wenn die Sprache eine separate Kompilierung erlaubt. Dennoch ist es gelegentlich nützlich, wenn Compiler während bestimmter Phasen temporäre Dateien generieren, typischerweise für die Adresskorrektur während der Codegenerierung.