PSS Gedächtnisprotokoll Klausur WS 0506: Unterschied zwischen den Versionen
(→Aufgabe 2: Parser) |
(→Aufgabe 2: Parser) |
||
| Zeile 22: | Zeile 22: | ||
| <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> | ||
Version vom 10. Februar 2008, 13:41 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:
DATA absy == node(val:seq[absy]) leaf(val:int)
2. Schreibe einen Recursive-Descent-/Combinator-Parser ohne Fehlerbehandlung. Falls Combinator: Programmiere auch die Kombinatoren.
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 -> beta) 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.
