Compilerbau: Lexikalische Analyse & Endliche Automaten
Lerne die Grundlagen des Compilerbaus: Von Quellcode zu Tokens, die Funktionsweise von Lexern (Scannern) und der Unterschied zwischen NFA und DFA.
VOM QUELLCODE ZUR MASCHINE
Lexikalische Analyse & Automaten
Dein Name | Informatik Klasse 10
01-06
INHALTSVERZEICHNIS
Was ist ein Compiler?
Der Aufbau (Phasen)
Die Lexikalische Analyse
Theorie: Endliche Automaten
NFA vs. DFA
Optimierung & Fazit
Der Dolmetscher zwischen Mensch und Maschine.
print('Hello!')
010101101001
Lexikalische Analyse (Scanner)
Syntaktische Analyse (Parser)
Semantische Analyse
Code-Generierung
if (x == 10)
[IF]
[LPAREN]
[ID:x]
[EQ]
[NUM:10]
[RPAREN]
WIE ERKENNT DER PC WÖRTER?
Theorie: Endliche Automaten (Identifier: [a-zA-Z_]...)
Nicht-Deterministischer EA (NFA)
Mehrere Wege für das gleiche Zeichen möglich
Spontan-Übergänge (ϵ) erlaubt
Vorteil: Intuitiv für Menschen
Nachteil: Computer muss 'raten'
Deterministischer EA (DFA)
Eindeutige Wege für jedes Zeichen
Kein Raten nötig – pure Logik
Vorteil: Extrem schnell (O(n))
Key Message: Compiler wandeln NFA ➔ DFA
Minimierung (Aufräumen)
Automatisch generiert
Speicheroptimiert
ZUSAMMENFASSUNG
Code ➜ Tokens (Lexer)
RegEx ➜ NFA ➜ DFA ➜ Min-DFA
"Ohne Theorie keine Praxis."
Vielen Dank.
- informatik
- compilerbau
- lexikalische-analyse
- endliche-automaten
- nfa-dfa
- lexer
- programmierung