PSS Gedächtnisprotokoll Klausur WS 0506: Unterschied zwischen den Versionen
(Lösung Aufg. 2) |
|||
| (20 dazwischenliegende Versionen von 7 Benutzern werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
| − | + | Die Bearbeitungszeit waren 90 Minuten. Alle Hilfmittel waren zugelassen (Kofferklausur) | |
| − | + | ||
| − | ---- | + | |
| − | < | + | == Aufgabe 1: Grammatikumformung == |
| − | 1. | + | 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?). | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | <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> | </pre> | ||
| + | Zur Notation: Erst kommt ein Knoten, dann seine Kinder von links nach rechts. | ||
| + | |||
| + | Der Baum gehört zu ''h''(''s'') und ist korrekt. | ||
Aktuelle Version vom 28. Februar 2012, 18:27 Uhr
Die Bearbeitungszeit waren 90 Minuten. Alle Hilfmittel waren zugelassen (Kofferklausur)
Inhaltsverzeichnis
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.
