Compilerbau/Kapitel 0: Einführung
Aus Halloserv Wiki
Inhaltsverzeichnis |
Inhalt
Ein Compiler ist ein Übersetzer von einer Quellsprache in eine Zielsprache. Die Quellsprache ist meistens eine höhere Programmiersprache (Java, C, Ocaml), die Zielsprache eine maschinennahe Programmiersprache (Assembler, ObjectCode, Maschienencode). Es gibt verschiedene Arten von Compilern: Batch-Compiler, integrierte Compiler (z.B. in Eclipse) und just-in-time Compiler (auf Bytecode-Ebene). Wir werden im Folgenden einen Batch-Compiler mit klassischer Pipeline-Architektur behandeln.
- Quellsprache 
Frontend -Zwischensprache Backend -Zielsprache [IMAGE]
Warum benutzt man eine Zwischensprache? Schreibt man einen Compiler für m Quellsprachen und n Zielsprachen, dann hat der minimale Compiler mit Zwischensprache m + n Programme. Frontend und Backend sind jeweils für eine Reihe von Funktionen zuständig:
- Transformation/Optimierung
von hier an plattformabhängig:
- Generierung von Assemblercode (abstrakt) / Auswahl der Instruktionen
- Scheduling
- Datenflussanalyse
- Registerallokation
- Codeausgabe
Im Folgenden werden die einzelnen Funktionen näher erläutert:
lexikalische Analyse
Die lexikalische Analyse enthält Lexer und Scanner und verwendet endlicher Automaten. Ihre Aufgabe ist die Aufteilung des Quellprogramms in Sinneinheiten (Symbole).
new Segment ( pi / 2 )
leads to:
Keyword(new)
Identifier("Segment")
Lparen
Identifier("pi")
Slash
Integer(2)
Rparen
syntaktische Analyse
Die syntaktische Analyse enthält den Parser, sie ermittelt die Struktur des Quellprogramms. Die syntaktische Struktur wird durch kontextfreie Grammatiken spezifiziert.
<expr> ::= Keyword("new") <ident> Lparen <param-list> rparen
| <expr> Slash <expr>
| <ident>
| <integer-literal>
<param-list> ::= <expr> <rest-list>
<rest-list> ::= Comma <expr> <rest-list>
Ergebnis: konstruiert Syntaxbaum (Ableitungsbaum) zu Liste von Symbolen, abtstrakter Syntaxbaum (AST). [IMAGE]
semantische Analyse
Die semantische Analyse behandelt folgende Fragen:
- Welche Definition gehört zu einem Vorkommen eines Bezeichner ?
- Welchen Typ hat ein Ausdruck?
- Wird eine Variable vor ihrer Initialisierung verwendet? (auch: Datenflussanalyse)
- Welche Exceptions werden von einem Methodenrumpf geworfen? (Pattern: Baumdurchlauf mit annotierten Knoten)
Datenflussanalyse
Eine Datenflussanalyse ist notwendig, da manche Optimierungen nur dann korrekt sind, wenn ein Programmen gewisse Eigenschaften erfüllt. Ein Beispiel hierfür ist die Lebendigkeitsanalyse.
Registerallokation
Bei der Registerallokation werden Zwischenergebnissen Maschinenregister zugeordnet. Bildet man diese Zuordnung auf ein Problem aus der Graphentheorie ab, kann man sie mittels einer Heuristik lösen.
Übersetzung in Zwischensprache
Dieses Kapitel ist auch als m/n Problem bekannt.
