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

K (Kleinere Formatänderungen)
(Lösung Aufg. 2)
 
(5 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 20: Zeile 20:
 
  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 36: Zeile 36:
 
1. Entwickle einen passenden Absy.
 
1. Entwickle einen passenden Absy.
  
Lösung:  
+
Lösung (Tutorium):
 +
 
 +
DATA absy ==    start(cont: absy)
 +
                tup(args: seq[absy])
 +
                single(val: int)
  
DATA absy ==
 
  node(val:seq[absy])
 
  leaf(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 ==
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 Aufbau eines Stackframes. Warum werden die Komponenten in genau dieser Reihenfolge angeordnet?
 
2. Erläutere den Aufbau eines Stackframes. Warum werden die Komponenten in genau dieser Reihenfolge angeordnet?
Zeile 65: Zeile 103:
  
 
<pre>
 
<pre>
FUN _ o _ : (beta -> gamma) -> (alpha -> beta) -> (alpha -> beta)
+
FUN _ o _ : (beta -> gamma) -> (alpha -> beta) -> (alpha -> gamma)
 
FUN length: string -> nat
 
FUN length: string -> nat
 
FUN even?: nat -> bool
 
FUN even?: nat -> bool

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.