Kurs:Algorithmen und Datenstrukturen/Vorlesung/Syntax und Semantik

Syntax und Semantik

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

Umsetzung in Programmiersprachen

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

<Programmname>:
var X,Y,...:int; P,Q,...:bool; (Variablen Deklaration)
input $X_1,...,X_n;$ (Eingabe Variablen)
$\alpha$   (Anweisungen)
output $Y_1,...,Y_m$ (Ausgabe-Variablen)

Semantik

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:

$[[PROG]]W_1\cdot ...\cdot W_n\to V_1\cdot ...\cdot V_m$

$[[PROG]](w_1,...,w_n)=(Z(Y_1),...,Z(Y_m))$

$wobeiZ=[[\alpha ]](Z_0),$

$Z_o(X_i)=w_i,i=1,..,n$

$und{Z}_0(Y)=\mathrm{\perp },fuerVariablenY\ne X_i(i=1,...,n)$

Es gilt:

$PROG$ Programme
$W_1,...,W_n$ Wertebereich der Typen von $X_1,...,X_n$
$V_1,...,V_m$ Wertebereich der Typen von $Y_1,...,Y_m$

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.

$[[PROG]](w_1,...,w_n)=Z(Y_1,...,Z(Y_m))$

$wobeiZ=[[\alpha ]](Z_0),$

$Z_o(X_i)=w_i,i=1,..,n$

$und{Z}_0(Y)=\mathrm{\perp },fuerVariablenY\ne X_i(i=1,...,n)$

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

Charakterisierung

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

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.