Dieses Kapitel ist (und bleibt vermutlich auch noch länger) nicht wirklich überschaubar strukturiert und der Inhalt lässt mehr als zu Wünschen übrig. Ich habe das alles noch nie unterrichtet und schreibe es nur auf, damit ich beim Lernen noch weiß, was ich alles gemacht habe.

• Formale Sprachen - Sprachbeschreibung, Spracherkennung, Reguläre Sprachen, Kontextfreie Sprachen, Kontextsensitive Sprachen (XML)
• Grenzen der Berechenbarkeit
• Automatensimulator
• Stapel / Keller

Turingmaschine, Kellerautomat

Chomsky-Hierarchie

Eine Sprache ist allgemein genau dann, wenn sie von einer deterministischen (oder nichtdeterministischen) Turingmaschine erkannt wird.

Eine Sprache ist kontextsensitiv genau dann, wenn sie von einer linear beschränkten nichtdeterministischen Turingmaschine erkannt wird.

1. Syntax analyse
2. Scanner: aus Zeichenfolgen lexikalische Einheiten bilden und als Tokenfolge aufzubereiten
3. Scanner-Automat: nutzt endlichen Automat zur Erkennung der lexikalischen Einheiten
4. Parser: Tokenfolge auf syntaktische Korrektheit prüfen (evtl. Tokenfolge aufbereiten)
5. Parser-Automat: nutzt Kellerautomaten zur syntaktischen Analyse der Tokenfolge
6. Interpreter: führt Anweisungen Schritt für Schritt aus

Eine präzise Interpreter-Beschreibung kann somit zur Festlegung der Semantik der Elemente der Programmiersprache benutzt werden (Interpreter-Semantik).

Transformationsregeln??

transformieren Programme der Ausgangs-Programmiersprache (Quellsprache) in eine andere Sprache (Zielsprache).

Eine präzise Übersetzer-Beschreibung kann zur Festlegung der Semantik