Phasen eines Compilers

aus www.iwiki.de, der freien Wissensdatenbank

Inhaltsverzeichnis 1 Allgemein 2 Frontend 2.1 Lexikalische Analyse 2.2 Syntaktische Analyse 2.3 Semantische Analyse 3 Backend 3.1 Zwischencodeerzeugung 3.2 Programmoptimierung 3.3 Codegenerierung

Allgemein

Compiler werden in verschiedene Phasen gegliedert, die jeweils verschiedene Teilaufgaben das Compilers übernehmen. 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 das Zielprogramm erzeugt.

Frontend

Im Frontend wird der Code analysiert, strukturiert und auf Fehler geprüft. Hier werden hochsprachenabhängige Analysen und evtl. Fehlerkorrekturen durchgeführt. Das Frontend ist unabhängig von den Architekturen (X86, RISC, ARM...) und deshalb für alle identisch.

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.

Aufgaben der lexikalischen Analyse sind:

• Erkennen der Grundbausteine der Quelle (Tokens | Atome )
• Umwandeln der Tokens in eine Interndarstellung
• Erkennen und Behandeln lexikalischer Fehler
• Entfernen irrelevanter Quellcode-Bestandteile (z.B. von Kommentaren )

Ein Beispiel:
position := anfangswert + zuwachs * 60;
Die lexikalische Analyse liefert einen TOKEN-STROM:

1. Token Bezeichner "position"
2. Token Zuweisungssymbol ":="
3. Token Bezeichner "anfangswert"
4. Token plus "+"
5. Token Bezeichner "zuwachs"
6. Token mal "*"
7. Token Zahl "60"
8. Token Semikolon ";"

Entfernt werden Leerzeichen, Tabs, Kommentare, überflüssige LF/CR.

Syntaktische Analyse

Die syntaktische Analyse überprüft, ob der eingelesene Quellcode tatsächlich ein Programm der zu übersetzenden Quellsprache ist, d. h. der Syntax (Grammatik) der Quellsprache entspricht. Dabei wird die Eingabe in einen Syntaxbaum umgewandelt. Dieser Teil wird auch als Parser bezeichnet.

Aufgaben der syntaktischen Analyse

• Erkennen syntaktischer Strukturen ( Bestandteile = Tokens | Atome )
• Erkennen syntaktischer Fehler und Fehlerdiagnose
• Fehlerbehandlung, um die Analyse fortsetzen zu können
• Aufbau der Symboltabelle

Ein Beispiel:

<zuweisung> ::= <bezeichner> := <ausdruck> <ausdruck> ::= <ausdruck> + <ausdruck>

|<ausdruck> - <ausdruck>

|<ausdruck> * <ausdruck>

|<ausdruck> / <ausdruck>

|(<ausdruck>)

|<bezeichner>

|<zahl>

<bezeichner> ::= a

| b

<zahl> ::= 0

| 1

z.B.: a := a + 1 - b

Semantische Analyse

Die semantische Analyse überprüft die statische Semantik, also über die syntaktische Analyse hinausgehende Bedingungen an das Programm. 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 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.

Beispiele für statische Überprüfungen:

• Typüberprüfungen
• Ãœberprüfungen des Kontrollflusses (goto, break)
• Eindeutigkeitsprüfungen (z.B. switch -Anweisung)
• Gültigkeitsprüfungen (scope)
• Auf Namen bezogene Ãœberprüfungen (PROCEDURE a; ... END a; in Modula-2 )

Backend

Das Backend erzeugt aus dem vom Frontend erstellten attributierten Syntaxbaum den Programmcode der Zielsprache. Da es abhängig von der Zielarchitektur ist, muss das Backend für jede Architektur angepasst sein.

Zwischencodeerzeugung

Viele moderne Compiler erzeugen aus dem Syntaxbaum einen Zwischencode, der schon relativ maschinennah sein kann und führen auf diesem Zwischencode z. B. Programmoptimierung durch. Das bietet sich besonders bei Compilern an, die mehrere Quellsprachen oder verschiedene Zielplattformen unterstützen. Hier kann der Zwischencode auch ein Austauschformat sein.

Programmoptimierung

Ü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, z. B. wie viele und welche Register der Prozessor des Computers zur Verfügung stellt.

Ein Beispiel:

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

Einsparung von Maschinenbefehlen

Höhere Programmiersprache	Maschinenbefehle ohne Optimierung	Maschinenbefehle mit Optimierung
t = a	a → Register 1 Register 1 → t	a → Register 1
a = b	b → Register 1 Register 1 → a	b → Register 2
b = t	t → Register 1 Register 1 → b	Register 1 → b Register 2 → a

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 CPU|Prozessor zur Verfügung stehen. Die Speicherung von Daten in Registern statt im Hauptspeicher ist eine häufig angewendete Möglichkeit der Optimierung.

Codegenerierung

Bei der Codegenerierung wird entweder direkt aus dem Syntaxbaum oder aus dem Zwischencode der Programmcode der Zielsprache erzeugt. Falls die Zielsprache eine 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.