Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 1 / 1

Einführung

Wat jibt´s denn? Mit Computa kenn´ ick mir aus!

Guten Tag, darf ich Ihnen mal eine Frage stellen?

Kapitel 1

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 1 / 2

integers, reals, arrays, records, stacks, files, characters, ...

Was ist ein „Datentyp“?

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 1 / 3

Definition erforderlich!

Beachte: Nutzerdefinierte Datentypen

in vielen Programmiersprachen

„Ein Datentyp legt die Menge der Werte fest, die eine Variable annehmen kann.“

( Pascal User Manual)

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 1 / 4

?stacks = queues

alles sequences

Na ja, na ja, ...

Zugriffsmechanismen:

filo vs. fifo

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 1 / 5

Datentyp:• Menge von Objekten• Operationen über diesen Objekten

= Algebra

Datentypen sind

Algebren ?

!

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 1 / 6

Mathematik

Algebra

= universelle Algebra

= algebraische Struktur

------------------• Trägermenge• Operationenfamilie

Informatik

z.B.: real array benötigt

real, array, integer

------------------

Algebra

=> Begriff erweitern !

------------------• mehrere Trägermengen• Operationenfamilie

Algebra und Informatik

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 1 / 7

Homogene oder einsortige Algebra

• Gruppe• Monoid• Ring• Boolesche Algebra• Verband

Heterogene oder mehrsortige

Algebra

• Datentyp• Vektorraum

• endlicher Automat• Syntax einer Programmiersprache

• Semantik - “ -

Algebra und Informatik

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 1 / 8

Problem:Partialität vieler Operationen:Selektion, Division, Überlauf/Unterlauf,

Lesen aus leerem Keller,

Aufruf nichtdeklarierter Prozedur

mehrsortige, partielle Algebren

Theorie kompliziert

partielle Operation totale Operationerror

Algebra und Informatik

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 1 / 9

Datentyp „Zeichenkeller“ (stacks of characters):• (mindestens) drei Trägermengen

Char = {a, b, c, ..., z}Stack = Char *Bool = {true, false}

• vier Operationen zweckmäßig

push : Char Stack Stack top : Stack Char pop : Stack Stack empty? : Stack Bool

Beispiel

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 1 / 10

Definition der Operationen:Sei - leerer Keller

sx - Füllung (Verkettung) des Kellers s mit Zeichen x

push(x,s) = sx top(sx) = x pop(sx) = s true , falls s = empty?(s) = false , falls s

top() = ? pop() = ? Einführung von error-Elementen

Beispiel (Forts.)

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 1 / 11

Definition der Operationen:Sei - leerer Keller

sx - Füllung (Verkettung) des Kellers s mit Zeichen x

push(x,s) = sx top(sx) = x pop(sx) = s top() = char-err pop() = stack-err true , falls s = empty?(s) = bool-err, falls s = stack-err false , sonst

Beispiel (Forts.)

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 1 / 12

Trägermengen erweitern:

Charp = {a, b, c, ..., z}

Char = Charp {char-err}

Stack = Charp * {stack-err}

Bool = {true, false} {bool-err} Operationen - „strikt“ vervollständigen

push : Char Stack Stack top : Stack Char pop : Stack Stack empty? : Stack Bool

Beispiel (Forts.)

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 1 / 13

• Erweiterung um Boolesche Operationen oft nützlich:

vel : Bool Bool Bool et : Bool Bool Bool non : Bool Bool (alle strikt vervollständigt)• Ergänzung des Datentyps „Zeichenkeller“ um neue Sorte

Int möglich, um z.B. die „Kellertiefe“ zu erfassen:

depth : Stack Int• Dann evtl. zweckmäßig, Rechnen über Int hinzuzunehmen:

arithmetische ( +, - ) und Vergleichsoperationen < usw.

Algebra mit vier Trägermengen und Operationen zwischen ihnen

Beispiel (Forts.)

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 1 / 14

ZeichenkellerSignatur

Char Stack Bool

Int

top empty?non

vel

et

pop

depthpush

- <

+

Beispiel (Forts.)