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

Abgabe bis 20.11., 12 Uhr, im Institutssekretariat

Aufgabe 5.1 (4 Punkte)

Ein Modul Queues sei durch

     DEFINTION MODULE Queues;
     TYPE Queue;		(* Folge von ...    *)
      ...
      ...
     PROCEDURE equal(q1,q2: Queue): BOOLEAN;
               (* Vor.: -
                  Erg.: Der Wert von "Beide Folgen sind gleich" *)
     END Queues.

wie üblich spezifiziert, allerdings mit der zusätzlichen Operation equal. Gesucht ist ein Implementierungsmodul mit der üblichen Dokumentierung. Als Repräsentation soll ein Feld dienen, das zirkulär verwendet wird: stößt man beim Weitergehen hinten an, so fährt man vorne fort.

Von den Prozeduren soll nur equal angegeben werden. (Beachte: Die Abstraktionsfunktion ist nicht injektiv.)

Frühere Versionen für Queues findet man hier: Queues.def, Queues.mod.


Aufgabe 5.2 (5 Punkte)

Ein Übersetzer arbeitet mit einer Symboltabelle, in der die im Programm vereinbarten Namen mit ihren zugehörigen Attributen (Typ, Adresse, ...) verzeichnet werden. Wir nehmen an, daß es sich um eine sehr einfache Sprache ohne Blockstruktur handele (z.B. ein einfacher Assembler). Zwischen den Anweisungen können an beliebiger Stelle Namensvereinbarungen der Form Identifier: eingeschoben werden, z.B. für Variable, Konstanten oder Sprungmarken. Der Sichtbarkeitsbereich eines Namens reicht von seiner Vereinbarung bis zum Programmende.

Der Übersetzer arbeitet ein vorgelegtes Quellenprogramm in einem Durchgang ab und erzeugt dabei das Objektprogramm. Sein Umgang mit der Symboltabelle wird durch folgendes Beispiel verdeutlicht:

BEGIN . erzeuge leere Symboltabelle
id: ... eintragen id mit Attributen
a: .... eintragen a mit Attributen
.
.
a ..... aufsuchen a, liefert Attribute
a: .... eintragen a scheitert!
b: .... eintragen b mit Attributen
id .... aufsuchen id, liefert Attribute
x ..... aufsuchen x scheitert!
.
.
END

Wenn das Programm keine weiteren Vereinbarungen enthält, sieht die Symboltabelle am Ende der Übersetzung so aus:

id .....
a .....
b .....

Gesucht ist die Spezifikation eines Moduls, das abstrakte Objekte vom Typ Symboltabelle verwaltet, und zwar als Definitionsmodul mit Invariante und Voraussetzungen/Effekten. Der Formalitätsgrad kann beliebig gewählt werden. (Wenn viel Umgangssprache verwendet wird: sorgfältig formulieren!)

Hinweis: Aus abstrakter Sicht sind die Tabelleneinträge gewisse Tupel und somit der Tabellenzustand eine Teilmenge eines gewissen kartesischen Produkts.


Aufgabe 5.3 (5 Punkte)

Entwickle einen iterativen Algorithmus zur Auswertung geklammerter arithmetischer Ausdrücke, der mit einem Operanden-Keller und einem Operator-Keller arbeitet. Es werde vorausgesetzt, daß beide Keller als abstrakte Objekte zur Verfügung stehen. Der Algorithmus soll Syntaxfehler erkennen und geeignet darauf reagieren.



11.11.1997, 11:11. Helau!