PSS Gedächtnisprotokoll Klausur WS 0506: Unterschied zwischen den Versionen

Aktuelle Version vom 28. Februar 2012, 18:27 Uhr

Die Bearbeitungszeit waren 90 Minuten. Alle Hilfmittel waren zugelassen (Kofferklausur)

Inhaltsverzeichnis

1 Aufgabe 1: Grammatikumformung
2 Aufgabe 2: Parser
3 Aufgabe 3: SECD
4 Aufgabe 4: Codeerzeugung
5 Aufgabe 5: Unifikation

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

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)

Zur Notation: Erst kommt ein Knoten, dann seine Kinder von links nach rechts.

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

@@ Zeile 1: / Zeile 1: @@
-Hier fehlen noch ein paar Informationen, mein Gedächtnis ist da etwas lückenhaft!
+Die Bearbeitungszeit waren 90 Minuten. Alle Hilfmittel waren zugelassen (Kofferklausur)
-Außerdem scheint mir einiges falsch..? naja vorallem die 2. Grammatik ist nicht identisch
-----
-<pre>
+== Aufgabe 1: Grammatikumformung ==
-.
+. Forme die Grammatik so um, dass sie von einem '''recursive-descent'''-Parser geparst werden kann.
-gegebene grammatik:
+. 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 #
+ S  -> E#
-E  ->  ide
+ E  -> ide
      |  ide ( A )
-A  ->  P
+ A  -> P
-     |
+     |  {Epsilon}
-P  ->  P , E
+ 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
+. Entwickle einen passenden Absy.
+Lösung (Tutorium):
+ DATA absy ==    start(cont: absy)
+                 tup(args: seq[absy])
+                 single(val: int)
-.1
-forme die grammatik so um, dass sie für einen
-top-down-parser geignet ist (--> LL(1)).
-.2
+. Schreibe einen Recursive-Descent-/Combinator-Parser ohne Fehlerbehandlung. Falls Combinator: Programmiere auch die Kombinatoren.
-direktormengen aufstellen.
-für die alte und die neue grammatik.
+Lösung (Tutorium):
-.
+ FUN parse: seq[token] -> absy
-schreibe einen recursive-decent-parser (combinator/hand)
+ DEF parse(s) ==
-ohne fehlerbehandlung für die grammatik:
+     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
-S  ->  T #
-T  ->  < T T' >
-T' ->  ide
-    |
-???
-in der sprache war: <<1 2 4> <1 4 5> 3>
+== Aufgabe 3: SECD ==
-das ganze repräsentierte einen n-ären baum
-DATA absy ==
-	node(val:seq[absy])
-	leaf(val:token)
-DATA token ==
-	Open
-	Close
-	space
-	id(val:int)
-. 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.
-(\x. x(2))(\y. dup(y))
-ergebnis 4
-dup ist triviale operation
-. codeerzeugung
+Ergebnis: 4.
-int f(x:int, y:int){
-	if(x==0)
-		return y
-	else
-		return f(x-1, x*y)
-}
-erzeuge pseudocode für eine stackartige maschine
-erläutere den stackframe (überlappung und sowas)
-. unifikation
+== Aufgabe 4: Codeerzeugung ==
-length: string -> nat
+ int f(x:int, y:int){
-even?: nat -> bool
+ 	if(x==0)
-h: string -> ???
+ 		return y
-h(s) == ???
+ 	else
-					eval
+ 		return f(x-1, x*y)
-			eval			s
+ }
-		eval	length
+. Erzeuge Pseudocode für eine abstrakte stackbasierte Maschine und mache die Basisblöcke kenntlich.
-	???		even?
-ergebnis war korrekt, aber das sah vllt. auch etwas anders aus..
+. Erläutere den Aufbau eines Stackframes. Warum werden die Komponenten in genau dieser Reihenfolge angeordnet?
+== Aufgabe 5: Unifikation ==
+. 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.