Quelltext der Seite PSS Gedächtnisprotokoll Klausur WS0910

== Aufgabe 1 (11 Punkte) ==

 E -> E + A 
    | E - A 
    | A
 A -> ( E ) 
    | ide

Grammatik umformen und originale und umgeformte Grammatiken auf LL(1) prüfen (mit DirectorSets)

== Aufgabe 2 (13 Punkte) ==

Absy (2 Punkte) und Parser ohne Fehlerbehandlung (11 Punkte) für Java Methodenaufrufe

Beispielsatz: x.f(y.g(y,a),b)

Originale und umgeformte Grammatiken waren vorgegeben, aber ohne semantische Aktionen

Falls Kombinatorparser, musste man die Standardkombinatoren ( ; | ), read, shift, usw. nicht hinschreiben

== Aufgabe 3 (6 Punkte) ==

Typcheck von where-Ausdruck:  (...) where (v == ...)

Gegeben war:

  DATA Expr == where(e1:Expr, ide:denotation, e2:Expr)
               ...

 FUN typecheck : expr ** env -> result

 DATA result == avail(t:Type)
                nil

und die Lambda Kalkül Regel:

 gamma, v:t2 |- e1:t1 , gamma |- e2:t2
 --------------------------------------
 gamma |- where(e1:t1, v:t2, e2:t2) : t1

== Aufgabe 4 (7 Punkte) ==

Unifikation:

 FUN lengthOne : seq[alpha] -> bool
 FUN filter : (alpha -> bool) ** seq[alpha] -> seq[alpha]

 DEF f == \\s. filter(lengthOne)(s)

Baum für f (als Abstraktion) war vorgegeben und musste auf Typkorrektheit geprüft werden.  D.h. Typgleichungen angeben und Unifikation durchführen.

== Aufgabe 5 (7 Punkte) ==

SECD ausführen für den Ausdruck:  (\\x.add(x 2))(4)

== Aufgabe 6 (4+1+1 = 6 Punkte) ==

1) Stack Machine Code für Funktion generieren:

 int f(n) {
  if(n < 2) {
    return n;
  } else {
    return 3 * f(n - 2);
  }
 }

Angegeben war Pseudocode-Befehle wie load<n>, lt, ret, goto-on-false L, mul, sub, call L

2) 2 Varianten von Code für eine while-Schleife angegeben: einmal Naive Variante und einmal aus der VL Besprochene Optimierung

Gefragt war welche Variante besser war.

3) 2 Varianten von Code für einen mathematischen Ausdruck war vorgegeben.  Einmal naive Variante, einmal mit dem tieferen Baum zuerst ausgeführt.  Gefragt war welche Variante besser ist.

== Mögliche Lösungen ==

== Aufgabe 3 ==

 DATA Expr == where(e1:Expr, ide:denotation, e2:Expr)
 
 
 FUN typecheck : expr ** env -> result
 
 
 DATA result == avail(t:Type)
                nil
 
 
 DEF typecheck(where(expr1,name,expr2), envi )== 
 		LET
 		result1 == typecheck(expr2,envi)
 		IN
 		IF result1 nil? THEN
 		 	result1
 		ELSE
 		typecheck(expr1,def(name,t(result1),envi))
                FOO