Quelltext der Seite 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?).

<pre>
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)
</pre>
Zur Notation: Erst kommt ein Knoten, dann seine Kinder von links nach rechts.

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