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.

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