FreitagsrundenWiki - Benutzerbeiträge [de]

PSS Gedächtnisprotokoll Klausur WS 0506

2006-02-15T16:28:46Z

84.190.198.225: /* Aufgabe 4: Codeerzeugung */

Hier fehlen ggf. noch ein paar Informationen, mein Gedächtnis ist da etwas lückenhaft! 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:

DATA absy ==
node(val:seq[absy])
leaf(val:token)

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.

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 tau aufstellen. Umformungen begründen (Was wird hier gemacht?).

<pre>
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)
</pre>
Zur Notation: Erst kommt ein Knoten, dann seine Kinder von links nach rechts.

Der Baum gehört zu h(s) und ist korrekt.

PSS Gedächtnisprotokoll Klausur WS 0506

2006-02-15T16:27:52Z

84.190.198.225:

Hier fehlen ggf. noch ein paar Informationen, mein Gedächtnis ist da etwas lückenhaft! 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:

DATA absy ==
node(val:seq[absy])
leaf(val:token)

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.

2. Erläutere den Stackframe (überlappung und sowas)

== Aufgabe 5: Unifikation ==
1. Zeige die Typkorrektheit von h. Gleichungen für jedes tau aufstellen. Umformungen begründen (Was wird hier gemacht?).

<pre>
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)
</pre>
Zur Notation: Erst kommt ein Knoten, dann seine Kinder von links nach rechts.

Der Baum gehört zu h(s) und ist korrekt.

PSS Gedächtnisprotokoll Klausur WS 0506

2006-02-15T16:24:44Z

84.190.198.225: /* Aufgabe 5: Unifikation */

Hier fehlen ggf. noch ein paar Informationen, mein Gedächtnis ist da etwas lückenhaft!

== 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:token)

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.

2. Erläutere den Stackframe (überlappung und sowas)

== Aufgabe 5: Unifikation ==
1. Zeige die Typkorrektheit von h. Gleichungen für jedes tau aufstellen. Umformungen begründen (Was wird hier gemacht?).

<pre>
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)
</pre>
Zur Notation: Erst kommt ein Knoten, dann seine Kinder von links nach rechts.

Der Baum gehört zu h(s) und ist korrekt.

PSS Gedächtnisprotokoll Klausur WS 0506

2006-02-15T16:22:35Z

84.190.198.225: /* Aufgabe 2: Parser */

Hier fehlen ggf. noch ein paar Informationen, mein Gedächtnis ist da etwas lückenhaft!

== 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:token)

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.

2. Erläutere den Stackframe (überlappung und sowas)

== Aufgabe 5: Unifikation ==
1. Stelle die Gleichungen auf

<pre>
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)
</pre>
Zur Notation: Erst kommt ein Knoten, dann seine Kinder von links nach rechts.

Der Baum gehört zu h(s) und ist korrekt.

PSS Gedächtnisprotokoll Klausur WS 0506

2006-02-15T16:22:18Z

84.190.198.225: /* Aufgabe 2: Parser */

Hier fehlen ggf. noch ein paar Informationen, mein Gedächtnis ist da etwas lückenhaft!

== 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:token)

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.

2. Erläutere den Stackframe (überlappung und sowas)

== Aufgabe 5: Unifikation ==
1. Stelle die Gleichungen auf

<pre>
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)
</pre>
Zur Notation: Erst kommt ein Knoten, dann seine Kinder von links nach rechts.

Der Baum gehört zu h(s) und ist korrekt.

PSS Gedächtnisprotokoll Klausur WS 0506

2006-02-15T16:21:47Z

84.190.198.225: /* Aufgabe 2: Parser */

Hier fehlen ggf. noch ein paar Informationen, mein Gedächtnis ist da etwas lückenhaft!

== 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:token)

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.

2. Erläutere den Stackframe (überlappung und sowas)

== Aufgabe 5: Unifikation ==
1. Stelle die Gleichungen auf

<pre>
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)
</pre>
Zur Notation: Erst kommt ein Knoten, dann seine Kinder von links nach rechts.

Der Baum gehört zu h(s) und ist korrekt.