WS 97/98: Algorithmen und Programmierung III - Übungsblatt 6

Abgabe bis 27.11., 12.30 Uhr

Aufgabe 6.1 (7 Punkte)

In blockstrukturierten Programmiersprachen gibt es geschachtelte Sichtbarkeitsbereiche mit eventuellen Namensverdeckungen. Hier ein Programmfragment in einer Modula-ähnlichen Sprache:

     VAR   i: int;
           b: bool;
     PROC  p;
           VAR c: char;
               b: real;
           BEGIN ... c
                 ... b
                 ... i ...
           END p;
     BEGIN ... b
           ... c ...  {Fehler!}
     END

Den Umgang des Übersetzers mit den im Programm vorkommenden Namen kann man sich im Modell wie folgt vorstellen: Für jeden Block gibt es eine eigene Symboltabelle. Die Tabellen werden in einer kellerähnlichen Tabellenfolge verwaltet. Beim Eintritt in einen Block wird eine leere Tabelle eingekellert, und beim Blockaustritt wird die oberste Tabelle ausgekellert. Eintragungen werden ausschließlich in der obersten Tabelle vorgenommen. Beim Suchen von Einträgen kann es allerdings erforderlich sein, auch weiter unten im Keller liegende Tabellen zu befragen. Somit kann man wie folgt spezifizieren:

     DEFINITION MODULE Symbolkeller;
          (* Modell: Folge von Tabellen gemäß der Spezifikation 
                     der Symboltabelle aus Aufgabe 5.2, anfangs leer. *)
          (* Inv.: - *)
     TYPE Name = ...
          Attribute = ...
     PROCEDURE blockanfang;
     PROCEDURE blockende(): BOOLEAN;
     PROCEDURE eintragen(n: Name;     a: Attribute): BOOLEAN;
     PROCEDURE aufsuchen(n: Name; VAR a: Attribute): BOOLEAN;
     PROCEDURE leer(): BOOLEAN;
     END Symbolkeller.


a) Vervollständige diese Spezifikation durch Angabe der Voraussetzungen und Effekte!

b) Entwickle eine Implementierung, die nicht von der Symboltabelle aus Aufgabe 5.2 Gebrauch macht! Vielmehr soll eine kellerähnliche Folge von Einträgen geführt werden, in die spezielle Blocktrennungsmarkierungen eingestreut sind. Für das obige Programmbeispiel könnte man etwa den folgenden Schnappschuß vorfinden:

     Namen:	 *  i  b  p  *  c  b
     Attribute:  ......

Das Implementierungsmodul soll wie üblich dokumentiert werden. Erforderlich sind Invariante, Abstraktion und Voraussetzungen/Effekte.


Aufgabe 6.2 (5 Punkte)

Entwickle eine iterative Prozedur für die Türme von Hanoi!


17.11.1997