"Compilerbau eine Einfuehrung 001.ps.gz" - читать интересную книгу автора

Compilerbau - eine Einf"uhrung

SS1998 Version 2.0.0

Prof. Dr. Michael J"ager

21. M"arz 1998

Inhaltsverzeichnis 1 Einf"uhrung 6

1.1 Wozu Compilerbau ? . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Phasenmodell eines Compilers . . . . . . . . . . . . . . . . . . 7

1.2.1 Verschr"ankung der Phasen . . . . . . . . . . . . . . . . 8 1.2.2 Arbeitsteilung bei der Compilerentwicklung . . . . . . 9 1.3 Bedeutung formaler Sprachbeschreibung . . . . . . . . . . . . 9

2 Einf"uhrung in Formale Sprachen 11

2.1 Mathematische Grundlagen . . . . . . . . . . . . . . . . . . . 11 2.2 Kontextfreie Grammatiken . . . . . . . . . . . . . . . . . . . 12

2.2.1 Ableitbarkeit . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.2 Notationsvarianten f"ur Grammatiken . . . . . . . . . . 16 2.3 EBNF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4 Transformation von EBNF in Grammatiken . . . . . . . . . . 18 2.5 Formale Sprachen und Compilerbau . . . . . . . . . . . . . . 20

3 Lexikalische Analyse (Scanner) 22

3.1 Lexikalische Elemente einer Programmiersprache . . . . . . . 22 3.2 Spezifikation der Token-Syntax . . . . . . . . . . . . . . . . . 24

3.2.1 Regul"are Sprachen . . . . . . . . . . . . . . . . . . . . 24 3.2.2 Regul"are Ausdr"ucke . . . . . . . . . . . . . . . . . . . 24

1

2 3.2.3 Regul"are Ausdr"ucke - UNIX-Notation . . . . . . . . . 25 3.3 Scanner-Implementierung . . . . . . . . . . . . . . . . . . . . 27 3.4 Systematische Scanner-Implementierung . . . . . . . . . . . . 31

3.4.1 Endliche Automaten / Endliche Akzeptoren . . . . . . 31 3.4.2 Darstellung von endlichen Automaten . . . . . . . . . 32 3.4.3 Automaten als Akzeptoren f"ur formale Sprachen . . . 33 3.4.4 Vom regul"aren Ausdruck zum nichtdeterministischen

Akzeptor - Thompson-Algorithmus . . . . . . . . . . . 34

3.4.5 Vom nichtdeterministischen zum deterministischen

Akzeptor . . . . . . . . . . . . . . . . . . . . . . . . . 36