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: Unterschied zwischen den Versionen

(Aufgabe 2: Parser)
(Aufgabe 2: Parser)
Zeile 22: Zeile 22:
 
         | <T T'>
 
         | <T T'>
 
  T' ->  {Epsilon}
 
  T' ->  {Epsilon}
    | _ T T' {Das _ war ein ''space''}
+
        | _ T T' {Das _ war ein ''space''}
  
 
Ein Wort der Sprache war: <<1 2 4> <1 4 5> 3>
 
Ein Wort der Sprache war: <<1 2 4> <1 4 5> 3>

Version vom 10. Februar 2008, 13:41 Uhr

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:

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

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

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 -> beta)
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.