Kurs:Algorithmen und Datenstrukturen/Vorlesung/Syntax und Semantik

Aus Wikiversity




Syntax und Semantik[Bearbeiten]

In diesem Kapitel wird die Syntax und Semantik von imperativen Algorithmen behandelt.

Umsetzung in Programmiersprachen[Bearbeiten]

In realen imperativen Programmiersprachen gibt es fast immer diese Anweisungen, da imperative Algorithmen die Grundbausteine imperativer Programmiersprachen sind. While-Schleifen sind rekursiv definiert, ihre rekursive Auswertung braucht nicht zu terminieren. Bereits Programmiersprachen mit diesen Sprachelementen sind universell. Wir werden uns hier zunächst auf die Datentypen bool und int beschränken und können nun die Syntax imperativer Algorithmen festlegen.

Syntax[Bearbeiten]

<Programmname>:
var X,Y,...:int; P,Q,...:bool; (Variablen Deklaration)
input  (Eingabe Variablen)
   (Anweisungen)
output  (Ausgabe-Variablen)

Semantik[Bearbeiten]

Die Festlegung der formalen Bedeutung ist hier etwas komplexer als bei den funktionalen Algorithmen. Das Ziel ist aber das gleiche: Die Funktion zur Semantikfestlegung.

Die Bedeutung (Semantik) eines imperativen Algorithmus ist eine partielle Funktion:

Es gilt:

 Programme
 Wertebereich der Typen von 
 Wertebereich der Typen von 

Das bedeutet, dass der Algorithmus eine Transformation auf den gesamten initialen Zustand (geg. durch die Eingabe)definiert. Die Bedeutung gibt die Werte der Ausgabevariablen an.

Die Funktion Z ist nicht definiert, falls die Auswertung von nicht terminiert.

Charakterisierung[Bearbeiten]

Die Algorithmenausführung imperativer Algorithmen besteht aus einer Folge von Basisschritten, oder genauer gesagt Wertzuweisungen. Diese Folge wird mittels Selektion und Iteration basierend auf booleschen Tests über dem Zustand konstruiert. Jeder Basisschritt definiert eine Transformation des Zustands. Die Semantik des Algorithmus ist durch die Kombination all dieser Zustandstransformationen zu einer Gesamttransformation festgelegt.

Literatur[Bearbeiten]

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 3.3.2 zu finden.


Discussion