Sitzung: Jeden Freitag in der Vorlesungszeit ab 16 Uhr c. t. im MAR 0.005. In der vorlesungsfreien Zeit unregelmäßig (Jemensch da?). Macht mit!

PSS Gedächtnisprotokoll Klausur WS 0506

Die Bearbeitungszeit waren 90 Minuten. Alle Hilfmittel waren zugelassen (Kofferklausur)


Aufgabe 1: Grammatikumformung

1. Forme die Grammatik so um, dass sie von einem recursive-descent-Parser geparst werden kann.

2. Entscheide und begründe, ob die umgeformte Grammatik und die ursprüngliche Grammatik die LL(1)-Eigenschaft erfüllen. Bilde die nötigen First-, Follow- und Directormengen.

S  -> E#
E  -> ide
   |  ide ( A )
A  -> P
   |  {Epsilon}
P  -> P , E
   |  E

Aufgabe 2: Parser

Gegeben folgende Grammatik mit Directormenge:

S  ->  T #
T  ->  ide
       | <T T'>
T' ->  {Epsilon}
       | _ T T' {Das _ war ein space}

Ein Wort der Sprache war: <<1 2 4> <1 4 5> 3> Das ganze repräsentierte einen n-ären Baum

DATA token ==
	Open
	Close
	space
	id(val:int)
	eof

1. Entwickle einen passenden Absy.

Lösung (Tutorium):

DATA absy ==    start(cont: absy)
                tup(args: seq[absy])
                single(val: int)


2. Schreibe einen Recursive-Descent-/Combinator-Parser ohne Fehlerbehandlung. Falls Combinator: Programmiere auch die Kombinatoren.

Lösung (Tutorium):

FUN parse: seq[token] -> absy
DEF parse(s) ==
    LET
        (E1, t0) == parseT(s)
        t1 == (shift(eof))(t0)
    IN
        start(E1) 

FUN parseT : seq[token] -> absy ** seq[token] 

DEF parseT(ide(n)::R) == (single(n), R) 

DEF parseT(Open::R) ==
    LET
        (t1, R1) == parseT(R)
        (t2, R2) == parseT1(R1)
    IN
         (tup(t1::t2), rt(R2))

FUN parseT1 : seq[token] -> seq[absy] ** seq[token] 

DEF parseT1(Close::R) == (<>, Close::R)

DEF parseT1(space::R) ==
    LET
        (t1, R1) == parseT(R)
        (t2, R2) == parseT1(R1)
    IN
        (t1::t2, R2) 

FUN shift : token -> seq[token] -> seq[token]
DEF shift(t)(ft::rt) == rt


Aufgabe 3: SECD

Der Ausdruck (λ x . x(2))(λ y . dup(y)) war mit der SECD-Maschine zu interpretieren, wobei dup eine triviale Operation war, die ihr Argument verdoppelte.

Ergebnis: 4.

Aufgabe 4: Codeerzeugung

int f(x:int, y:int){
	if(x==0)
		return y
	else
		return f(x-1, x*y)
}

1. Erzeuge Pseudocode für eine abstrakte stackbasierte Maschine und mache die Basisblöcke kenntlich.

2. Erläutere den Aufbau eines Stackframes. Warum werden die Komponenten in genau dieser Reihenfolge angeordnet?

Aufgabe 5: Unifikation

1. Zeige die Typkorrektheit von h. Gleichungen für jedes τ aufstellen. Umformungen begründen (Was wird hier gemacht?).

FUN _ o _ : (beta -> gamma) -> (alpha -> beta) -> (alpha -> gamma)
FUN length: string -> nat
FUN even?: nat -> bool

FUN h: string -> bool
DEF h(s) == o(even?)(length)(s)


apply(tau1)
	apply(tau2)
		apply(tau4)
			o(tau6)
			even?(tau7)
		length(tau5)
	s (tau3)

Zur Notation: Erst kommt ein Knoten, dann seine Kinder von links nach rechts.

Der Baum gehört zu h(s) und ist korrekt.