PSS Gedächtnisprotokoll Klausur WS 0506: Unterschied zwischen den Versionen
(nicht umgeformte -> ursprüngliche) |
(Lösung Aufg. 2) |
||
| (17 dazwischenliegende Versionen von 7 Benutzern werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
| − | + | Die Bearbeitungszeit waren 90 Minuten. Alle Hilfmittel waren zugelassen (Kofferklausur) | |
| Zeile 16: | Zeile 16: | ||
== Aufgabe 2: Parser == | == Aufgabe 2: Parser == | ||
| − | |||
| − | |||
| − | |||
| − | |||
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''} | |
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 == | ||
| − | + | 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. |
| − | |||
| − | |||
== 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 | + | 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) | ||
| − | |||
| − | |||
| − | |||
| − | + | 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. | |
| − | |||
| − | |||
| − | |||
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.
