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

(Weitergeführt, Design verändert)
(Lösung Aufg. 2)
 
(18 dazwischenliegende Versionen von 7 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
−
Hier fehlen ggf. noch ein paar Informationen, mein Gedächtnis ist da etwas lückenhaft!
+
Die Bearbeitungszeit waren 90 Minuten. Alle Hilfmittel waren zugelassen (Kofferklausur)
  
  
Zeile 5: Zeile 5:
 
1. Forme die Grammatik so um, dass sie von einem '''recursive-descent'''-Parser geparst werden kann.
 
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.
+
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#
 
  S  -> E#
Zeile 16: Zeile 16:
  
 
== Aufgabe 2: Parser ==
 
== Aufgabe 2: Parser ==
−
 
−
DATA absy ==
 
−
node(val:seq[absy])
 
−
leaf(val:token)
 
  
 
Gegeben folgende Grammatik mit Directormenge:
 
Gegeben folgende Grammatik mit Directormenge:
 
  S  ->  T #
 
  S  ->  T #
 
  T  ->  ide
 
  T  ->  ide
−
         <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>
Zeile 39: Zeile 35:
  
 
1. Entwickle einen passenden Absy.
 
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.
 
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 ==
 
== Aufgabe 3: SECD ==
  
−
(\x. x(2))(\y. dup(y))
+
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
+
Ergebnis: 4.
−
 
 
−
''dup'' ist eine triviale Operation.
 
  
 
== Aufgabe 4: Codeerzeugung ==
 
== Aufgabe 4: Codeerzeugung ==
Zeile 57: Zeile 95:
 
  return f(x-1, x*y)
 
  return f(x-1, x*y)
 
  }
 
  }
−
1. Erzeuge Pseudocode für eine abstrakte stackbasierte Maschine.
+
1. Erzeuge Pseudocode für eine abstrakte stackbasierte Maschine und mache die Basisblöcke kenntlich.
  
−
2. Erläutere den Stackframe (überlappung und sowas)
+
2. Erläutere den Aufbau eines Stackframes. Warum werden die Komponenten in genau dieser Reihenfolge angeordnet?
  
 
== Aufgabe 5: Unifikation ==
 
== Aufgabe 5: Unifikation ==
 +
1. 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)
  
−
FUN _ o _ : (beta -> gamma) -> (alpha -> beta) -> (alpha -> beta)
 
−
FUN length: string -> nat
 
−
FUN even?: nat -> bool
 
  
−
FUN h: string -> bool
+
apply(tau1)
−
DEF h(s) == o(even?)(length)(s)
+
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.
  
−
apply (tau1)
+
Der Baum gehört zu ''h''(''s'') und ist korrekt.
−
apply(tau2) s (tau3)
 
−
apply(tau4) length(tau5)
 
−
o(tau6) even?(tau7)
 

Aktuelle Version vom 28. Februar 2012, 18:27 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 (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.

Abgerufen von „https://wiki.freitagsrunde.org/index.php?title=PSS_Gedächtnisprotokoll_Klausur_WS_0506&oldid=17603“