PSS Gedächtnisprotokoll Klausur WS 0506
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.