ALP III - Übungsblatt 8

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

Abgabe bis 8.1., 12.30 Uhr

Aufgabe 8.1 (8 Punkte)

Unter Verwendung von

     tree * ** ::= Leaf* | Node** (tree * **)(tree * **)

seien Operatorbäume wie folgt spezifiziert:

     operator == char
     operand  == num

     abstype optree
     with atom :: operand  -> optree
          expr :: operator -> optree -> optree -> optree
          eval :: optree -> operand

     optree == tree operand operator         || MODELL

     atom o       = Leaf o                   || SEMANTIK
     expr o e1 e2 = Node o e1 e2
     eval(Leaf o) = o
     eval(Node o e1 e2) = (func o)(eval e1)(eval e2)

     func '+' = +
     func '-' = -
     func '*' = *
     func '/' = div

a) Entwickle ein entsprechendes Definitionsmodul Optrees für den imperativen Umgang mit Operatorbäumen!

b) Entwickle ein zugehöriges Implementierungsmodul, das die Bäume als Geflechte verwaltet!

Aufgabe 8.2 (4 Punkte)

Bäume des folgenden Typs person stellen den Stammbaum einer Person dar:

	person ::= Unbekannt | Kind name person person

Entwickle eine Funktion

	stammbaum :: person -> [char]

mit der man den Stammbaum einer Person auf dem Bildschirm mit geeigneten Einrückungen (rekursiv) und Beschriftung anzeigen kann, z.B. so:

	Anna
	  Mutter: Eva
	  Vater : Dirk
	            Vater : Sven

Aufgabe 8.3 (5 Punkte)

Aus einem Baum wird eine Liste gewonnen mittels Traversieren:

	list :: tree* -> [*]

Syntaxanalyse ist ein "konstruierendes Traversieren" - aus einer Liste wird eine syntaktische Struktur herauspräpariert und in einem Baum festgehalten:

	parse :: [*] -> tree*

Wir betrachten eine Sprache mit folgender Syntax (Startsymbol ist Pedigree):

Pedigree = ? | Letter Pedigree Pedigree .
Letter = a | b | ..... | z .

a) Verfasse eine Funktion parse für diese Sprache! Beachte, daß nicht jede Zeichenkette aus Buchstaben und Fragezeichen syntaktisch korrekt ist; z.B. ist nur die erste dieser drei Zeichenketten korrekt:

	a?bc???     ab?c?     a??b

b) Verfasse eine Funktion list zur Ausgabe der erzeugten Bäume in Anlehnung an Aufgabe 2!

Aufgabe 8.4 (3 Punkte)

Ein Wald von Bäumen sei wie folgt definiert:

	forest* ::= F[(*,forest*)]

Verfasse eine Funktion list :: forest* -> [*], die einen Wald mit Breitensuche traversiert und die in den besuchten Knoten aufgefundene Information in einer Liste zusammenstellt!

16.12.1997