Theoretische Informatik

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.


Turingmaschine, Kellerautomat

Chomsky-Hierarchie

Typ 0 allgemein äquivalenter Automat
Typ 1 kontextsensitiv nichtdeterministischer linear beschränkten Turingmaschine
Typ 2 kontextfrei nichtdeterministischer Kellerautomat
Typ 3 regulär (nicht)deterministischer endlicher Automat

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.

Natürliche Sprachen
Syntax Lehre vom Satzbau, Anordnung der Zeichen
Semantik Bedeutungslehre, Beziehung zwischen Zeichen und Bezeichnetem
Pragmatik Lehre von der Verwendung sprachlicher Konstrukte in Handlungssituationen - Beziehung zwischen Zeichen und Zeichenbenutzer

Semantik von Programmiersprachen

Scanner und Parser

  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??

Übersetzer

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

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

Cookies helfen bei der Bereitstellung von Inhalten. Durch die Nutzung dieser Seiten erklären Sie sich damit einverstanden, dass Cookies auf Ihrem Rechner gespeichert werden. Weitere Information
Falls nicht anders bezeichnet, ist der Inhalt dieses Wikis unter der folgenden Lizenz veröffentlicht: CC Attribution-Noncommercial-Share Alike 4.0 International