G.Heyer Digitale Informationsverarbeitung 1 Ausdrücke bezeichnen Elemente eines Datentyps induktive Definition: 1. eine Konstante k vom Typ D ist ein Ausdruck

G.Heyer Digitale Informationsverarbeitung1

Ausdrücke

• bezeichnen Elemente eines Datentyps• induktive Definition:

1. eine Konstante k vom Typ D ist ein Ausdruck vom Typ D 2. eine Variable v vom Typ D ist ist ein Ausdruck vom Typ D

3. sind t1, ..., tn Ausdrücke der Typen D1, ..., Dn und ist f:D1 x ... x Dn -> D eine Nicht-Infix-Operation, so ist

f(t1,...,tn) ein Ausdruck vom Typ D 4. sind t1, t2 Ausdrücke der Typen D1, D2 und ist o:D1 x D2 -> D eine

Infix-Operation, so ist (t1) o (t2) ein Ausdruck vom Typ D• Wert eines Ausdrucks:

1. für eine Konstante k ist Wert(k) das durch k bezeichnete Element von D 2. für eine Variable v ist Wert(v) der in der Variablen gespeicherte Wert

3. Wert(f(t1,...,tn)) = f(Wert(t1), ..., Wert(tn)) 4. Wert((t1) o (t2)) = Wert(t1) o Wert(t2)


Klammerung

Vollständige Klammerung oft unnötig durch Festlegung der Bindungsstärke

1. einstellige Operatoren wie not, sin, cos, ...2. multiplikative Operatoren wie *, /, div, mod, ...3. additive Operatoren wie +, -, or, ...4. vergleichende Operatoren wie =, <>, <, ...

stärker

schwächer

Bei Operatoren gleicher Bindungsstärke wird Linksklammerung angenommen

x div y * y + x mod y steht für ((x div y) * y) + (x mod y)

+

div

x y y x y

* mod

Auswertungsbaum


Typkonversionbei zweistelligen Operatoren Operanden in der Regel vom selben Typ Ausnahmen: • Aufzählungstypen (Typverträglichkeit reicht, später) • REAL-INTEGER-Verträglichkeit:

überall, wo REAL erlaubt ist, ist auch INTEGER erlaubt

Bei gemischten Argumenten (etwa für div, mult) wird Konversion durchgeführt, Ergebnis stets REAL

Beispiel:

17.0 + 22*8.01.0 <> 1

Wert:

19.016.0TRUE

Bemerkung: in allen Teilausdrücken nur ausführbare Operationen verwenden! Der Ausdruck (A = 0) or (B/A > 0) kann zu Laufzeitfehler führen, falls A=0.


Pascal Anweisungen

Case-Anweisung

Verbund-Anweisung

Goto-Anweisung

Zuweisung

Prozedur-anweisung

bedingte Anweisung

wiederholdeneAnweisung

With-Anweisung

If-Anweisung

While-Anweisung

Repeat-Anweisung

For-Anweisung

einfacheAnweisung

strukturierteAnweisung


Wertzuweisung

Bezeichner Ausdruck:=

muß als Variabledeklariert sein

Typ muß Variablen-typ entsprechen

zu beachten: • Wertzuweisung bewirkt Änderung des Zustands im Speicher • Symbol “:=“ hat völlig andere Bedeutung als “=“

X := X + 1 bedeutet: nach Ausführung der Zuweisung ist Wert(X) = Wert (X) + 1, dabei ist Wert (X) der Wert von X vor Ausführung der Zuweisung X = X + 1 ist ein Ausdruck vom Typ BOOLEAN, der immer FALSE ist

• “:=“ wird gesprochen "ergibt sich aus" oder "wird zu"

alt

alt


Bedingte Anweisungen

Boolescher Ausdr. AnweisungIF THEN

AnweisungELSE

Mehrdeutigkeiten: IF B1 THEN IF B2 THEN A1 ELSE A2

Soll Folge von Anweisungen ausgeführt werden, so ist Verwendung einerVerbundanweisung (BEGIN ... END Klammerung) erforderlich

1) IF B1 THEN [ IF B2 THEN A1 ELSE A2 ] oder2) IF B1 THEN [ IF B2 THEN A1 ] ELSE A2 ?

B1TrueTrueFalseFalse

B2TrueFalseTrueFalse

1A1A2--

2A1

-A2A2

Pascal folgt Lesart 1: ELSE ergänzt immer letztes unergänztes IFLesart 2 besser: IF B1 THEN BEGIN IF B2 THEN A1 END ELSE A2


Case-Anweisung

Ausdruck FallCASE OF

AnweisungELSE

jeder Fall besteht aus Liste von Konstanten und AnweisungSemantik:

CASE A OF

bedeutet dasselbe wie:

IF A = k11 or ... or A = k1j THEN S1ELSE IF A = k21 or ... or A = k2n THEN S2 ... ELSE IF A = km1 or ... or A = kmi THEN Sm ELSE S

END

k11, ..., k1j: S1; k21, ..., k2n: S2;... km1, ..., kmi: Sm ELSE S END


Ein Programm mit Fallunterscheidungen

PROGRAM Case1;VAR Monat, Jahr, Tage: Integer; Schalt: Boolean;BEGINRead(Monat, Jahr);IF Jahr mod 4 = 0 THEN IF Jahr mod 100 = 0 THEN IF Jahr mod 400 = 0 THEN Schalt := True ELSE Schalt := False ELSE Schalt := TrueELSE Schalt:= False;CASE Monat OF 4, 6, 9, 11: Tage := 30; 2: IF Schalt THEN Tage := 29 ELSE Tage := 28 ELSE Tage := 31END;WriteLn( Monat, ' . ', Jahr, ' ------> ', Tage )END.


Schleifen

boolescherAusdruck

AnweisungWHILE DO

boolescherAusdruckREPEAT Anweisung

;

UNTIL

REPEAT C UNTIL B entspricht:

C; WHILE not B DO BEGIN C END

WHILE B DO A bedeutet dasselbe wie:

IF B THEN BEGIN A; WHILE B DO A END


FOR-Schleife

Bezeichner AusdruckFOR :=

AnweisungDO

TO

DOWNTO

Ausdruck

• Bezeichner ist deklarierte Variable, so daß succ und pred definiert sind• Anzahl der Schleifendurchläufe zu Beginn festgelegt:

für jeden Wert zwischen dem ersten und dem zweiten Ausdruck einmal• TO, DOWNTO geben an, ob inkrementiert oder dekrementiert wird• Auf Laufvariable in der Schleife nur lesend zugreifen!• Keine Annahmen über den Wert der Laufvariable nach Beendigung der

Schleife machen!

Beispiel: FOR Zeichen := 'a' TO 'z' DO WriteLn(Zeichen, ' ', Ord(Zeichen))


Bemerkungen

FOR-Schleifen terminieren, da die Anzahl der Schleifendurchläufe feststehtWHILE und REPEAT können nichtterminierende Programme

produzierenTerminierung oft schwierig zu beweisen: Beispiel Syrakusfunktion:

Es ist unbewiesen, ob diese Schleife für alle n verlassen wirdStrategie für Terminierungsbeweise: finde positiven Ausdruck, der bei

jedem Schleifendurchlauf kleiner, aber nie negativ wird:bei ggT etwa:

Wert von x + y nach jedem Schleifendurchlauf kleiner, aber nie negativ

WHILE n <> 1 DOIF odd(n) THEN n := 3*n+1 ELSE n := n div 2


11. Unterprogrammtechnik

Unterprogramme sind in sich geschlossene Programmeinheiten, deren Ausführung durch ihren Namen veranlaßt wird

Sie dienen insbesondere der Strukturierung größerer Programme2 Arten:

• Prozeduren: abstrahieren Anweisungsfolge zu neuer Anweisung• Funktionen: berechnen einen Wert eines bestimmten Typs

Vorteile der Verwendung von Unterprogrammen:• größere Lesbarkeit und Überschaubarkeit von Programmen• geringerer Schreibaufwand bei wiederkehrenden Aktionsfolgen• geringere Fehleranfälligkeit• einfachere Änderungsmöglichkeit


Lokale und globale Variable

Sichtbarkeitsregel:Für ein Unterprogramm UP gelten alle Deklarationen aus allen Programmen (einschließlich UP und HP) auf dem Weg zu UP im Schachtelungsbaum Deklarationen in UP heißen lokal, solche in übergeordneten Programmen global für UPBei Bezeichnungskollisionen gilt Deklaration des nächsten Unterprogramms

Unterprogramme können selbst Unterprogrammdeklarationen enthalten

HP

UP1 UP2 UP3

UP11 UP12 UP21 UP31 UP32

UP311

Schachtelungsbaum


Prozeduren

• Der Aufruf einer Prozedur in einem Programm ist eine Anweisung• Die in der Prozedur deklarierte Folge von Anweisungen wird abgearbeitet,

anschließend wird ins aufrufende Programm zurückgesprungen

Hauptprogramm

•••

UP1;•••

UP1BEGIN

•••

END;

Unter-programm


Gültigkeitsbereich und Lebensdauer

Gültigkeitsbereich eines Bezeichners: der statische Teil des Programms, in dem dieser Bezeichner in exakt gleicher Bedeutung verwendet werden darf.Lebensdauer: bezeichnet die dynamische Existenz eines Objekts während des Programmablaufs.Der Gültigkeitsbereich bezieht sich auf den Bezeichner (durch Übersetzer kontrolliert), die Lebensdauer auf den zur Laufzeit belegten Speicherplatz.Durch Ausführung eines Unterprogramms P entsteht eine Inkarnation. Zur Inkarnation gehören dynamisch (bis Ende der Ausführung von P): • ein Ausführungspunkt (Zeiger auf gerade auszuführenden Befehl) • Speicherplätze für alle Bezeichner von Variablen und Wertparameter • Bezüge auf die konkreten Referenzparameter.Nur in der jüngsten Inkarnation wandert der Ausführungspunkt weiter.Die Lebensdauer einer Variablen ist identisch mit der Existenz der zugehörigen Prozedur-Inkarnation.Zu Beginn der Lebensdauer ist der Wert einer Variablen undefiniert.


Prozedurparameter

formale Parameter: in der Deklaration eines Unterprogramms verwendet (Platzhalter für Werte)

aktuelle Parameter: beim Prozeduraufruf verwendete ArgumenteTypen:

• Eingabeparameter: Übermittlung von Werten an die Prozedur, call by value

• Ausgabeparameter: Übermittlung von Resultaten an aufrufendes Programm, call by reference • Ein/Ausgabeparameter: Mischform, call by reference

Referenz-parameter

Werte-parameter

formale Par. aktuelle Par.

Kennzeichnungdurch VAR

ohne VAR

Variable entspre-chenden Typs

Ausdrücke entspre-chenden Typs


Beispiel

Angabe des Typs formaler Parameter erforderlich,nur Typnamen, nicht Typdeklarationen erlaubt

PROCEDURE xyz(A: 1..Maxint) verboten, da Typdefinition vorkommt

korrekt:

TYPE Pos = 1..Maxint;...PROCEDURE xyz(A: Pos)

PROCEDURE Beispiel (V, W: REAL; VAR X: REAL); BEGIN ... END;

Deklaration in aufrufendem Programm:VAR A, B, C, D: REAL;

korrekte Aufrufe: Beispiel(A, D, B); Beispiel(A-1, A - 2*B, D); inkorrekt: Beispiel(A, B, 1.0)


Methoden der Parameterübergabe

a) Call by value- Werte der aktuellen Parameter bei Unterprogrammaufruf an formale Parameter gebunden- formale Parameter lokal im aufgerufenen Programm- keine Information geht an das aufrufende Programm zurück

b) Call by reference- Unterprogramm erhält bei Aufruf Zeiger auf Adresse des aktuellen Parameters- Alle Operationen werden im Speicherbereich des aufrufenden Programms ausgeführt- Veränderungen bleiben nach Beendigung des Unterprogramms sichtbar


c) Call by value-result

- Werte der aktuellen Parameter werden an formale Parameter gebunden- Berechnung verwendet formale Parameter lokal- Nach Prozedurende werden Werte der lokalen Parameter an aktuelle Parameter gebunden

procedure p (x,y: integer);begin

x := x + 1;y := y + 1;

end

begina := 1;p (a,a);

end

Call by reference: a = 3Call by value-result: a = 2 (falls x y, abhängig von der Reihenfolge

des Rückkopierens)


d) Call by name

- Bei Unterprogrammaufruf werden formale Parameter durch aktuelle Parameter textuell ersetzt- Bindung des formalen Parameters an Speicherplatz wird jeweils neu ermittelt- Zuweisungen an einen formalen Parameter können verschiedene Speicherplätze betreffen

Beispiel:

procedure swap(a, b: integer)var temp: integer;begintemp := a;a := b;b := temp;end.

für a, b sei call by name vereinbart.


Aufruf: Swap (i, a[i])

bewirkt Ausführung vontemp := i;i := a[i];a[i] := temp;

Seien vor dem Aufruf i = 3 und a[3] = 4,nach dem Aufruf gilt: i = 4 und a[4] =3 (a[3] bleibt unverändert)

Bei call by refence dagegen passiert das Erwartete(i=4 und a[3] = 3).

Documents

G.Heyer Digitale Informationsverarbeitung 1 Ausdrücke bezeichnen Elemente eines Datentyps induktive Definition: 1. eine Konstante k vom Typ D ist ein Ausdruck