Prof. Dr. H. Seidl

Skript zur Vorlesung

Compilerbau

Dieses Skript entstand w"ahrend der Vorlesung Compilerbau, die im Sommersemester 1997 an der Universit"at Trier gelesen wurde. LATEX-Version by Martin Toepfer / Frank Burch / Johannes Lehnert.

Inhaltsverzeichnis 1 Einf"uhrung 4

1.1 Vorgehen eines Compilers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Eine abstrakte Maschine f"ur C 6

2.1 Erster "Uberblick "uber die Architektur der CMa . . . . . . . . . . . . . . . . . 6

2.1.1 Datenstrukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.2 Maschinenzyklus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Einfache Ausdr"ucke und Zuweisungen . . . . . . . . . . . . . . . . . . . . . . 7

2.2.1 Arithmetische Ausdr"ucke . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.2 Vergleiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.3 Adressen und Inhalte von Variablen . . . . . . . . . . . . . . . . . . . 8 2.2.4 Wertzuweisung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Anweisungen und Anweisungsfolgen . . . . . . . . . . . . . . . . . . . . . . . 10 2.4 (Un-)bedingte und iterative Anweisungen . . . . . . . . . . . . . . . . . . . . 10

2.4.1 Bedingte Anweisungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4.2 Schleifen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4.3 switch-Anweisung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4.4 "Ubersetzung von break . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5 Speicherbelegung f"ur Variablen . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.5.1 Felder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5.2 Strukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.6 Zeiger und dynamische Speicherverwaltung . . . . . . . . . . . . . . . . . . . 15

2.6.1 Adress- und Dereferenzierungsoperatoren . . . . . . . . . . . . . . . . . 16 2.6.2 "Ubersicht "uber Schemata f"ur Ausdr"ucke . . . . . . . . . . . . . . . . . 17

1

INHALTSVERZEICHNIS 2

2.6.3 Freigabe dynamisch erzeugter Datenobjekte . . . . . . . . . . . . . . . 18 2.7 Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.7.1 Speicherorganisation f"ur Funktionen . . . . . . . . . . . . . . . . . . . 19 2.7.2 Bestimmung der Adressumgebung . . . . . . . . . . . . . . . . . . . . . 20 2.7.3 Betreten und Verlassen von Funktionen . . . . . . . . . . . . . . . . . 21 2.7.4 Zugriff auf Variablen und formale Parameter, R"uckgabe von Werten . 23 2.7.5 "Ubersetzung eines Programms . . . . . . . . . . . . . . . . . . . . . . 25

3 Lexikalische Analyse 26

3.1 Regul"are Ausdr"ucke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2 Endliche Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.3 Konstruktion eines "-NFA aus einem regul"aren Ausdruck . . . . . . . . . . . 28 3.4 Konstruktion eines NFA aus einem regul"aren Ausdruck . . . . . . . . . . . . . 29 3.5 Konstruktion von DFAs aus NFAs . . . . . . . . . . . . . . . . . . . . . . . . 31 3.6 Minimierung von deterministischen endlichen Automaten . . . . . . . . . . . 32 3.7 Implementierung eines DFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.8 Spezifikation von Symbolklassen . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.9 Generierung eines Scanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36