View
102
Download
0
Category
Preview:
Citation preview
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.)
Recommended