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

Version vom 13. Februar 2006, 20:37 Uhr von Buchholz (Diskussion) (Weitergeführt, Design verändert)

Hier fehlen ggf. noch ein paar Informationen, mein Gedächtnis ist da etwas lückenhaft!


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 nicht umgeformte 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

DATA absy == node(val:seq[absy]) leaf(val:token)

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.

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

Aufgabe 3: SECD

(\x. x(2))(\y. dup(y))

Ergebnis 4

dup ist eine triviale Operation.

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.

2. Erläutere den Stackframe (überlappung und sowas)

Aufgabe 5: Unifikation

FUN _ o _ : (beta -> gamma) -> (alpha -> beta) -> (alpha -> beta)
FUN length: string -> nat
FUN even?: nat -> bool
FUN h: string -> bool
DEF h(s) == o(even?)(length)(s)
					apply (tau1)
			apply(tau2)			s (tau3)
		apply(tau4)	length(tau5)
	o(tau6)		even?(tau7)