PSS Gedächtnisprotokoll Klausur WS 0506: Unterschied zwischen den Versionen

Version vom 13. Februar 2006, 20:37 Uhr

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

Inhaltsverzeichnis

1 Aufgabe 1: Grammatikumformung
2 Aufgabe 2: Parser
3 Aufgabe 3: SECD
4 Aufgabe 4: Codeerzeugung
5 Aufgabe 5: Unifikation

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 nicht umgeformte 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

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

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.

2. Schreibe einen Recursive-Descent-/Combinator-Parser ohne Fehlerbehandlung. Falls Combinator: Programmiere auch die Kombinatoren.

Aufgabe 3: SECD

(\x. x(2))(\y. dup(y))

Ergebnis 4

dup ist eine triviale Operation.

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

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)			s (tau3)
		apply(tau4)	length(tau5)
	o(tau6)		even?(tau7)

@@ Zeile 1: / Zeile 1: @@
-Hier fehlen noch ein paar Informationen, mein Gedächtnis ist da etwas lückenhaft!
+Hier fehlen ggf. noch ein paar Informationen, mein Gedächtnis ist da etwas lückenhaft!
-Außerdem scheint mir einiges falsch..? naja vorallem die 2. Grammatik ist nicht identisch
-----
-<pre>
-.
-gegebene grammatik:
-S  ->  E #
-E  ->  ide
+== Aufgabe 1: Grammatikumformung ==
+. Forme die Grammatik so um, dass sie von einem '''recursive-descent'''-Parser geparst werden kann.
+. Entscheide und begründe, ob die umgeformte Grammatik und die nicht umgeformte Grammatik die LL(1)-Eigenschaft erfüllen. Bilde die nötigen First-, Follow- und Directormengen.
+ S  -> E#
+ E  -> ide
      |  ide ( A )
-A  ->  P
+ A  -> P
-     |
+     |  {Epsilon}
-P  ->  P , E
+ P  -> P , E
      |  E
+== Aufgabe 2: Parser ==
+DATA absy ==
+	node(val:seq[absy])
+	leaf(val:token)
+Gegeben folgende Grammatik mit Directormenge:
+ S  ->  T #
+ T  ->  ide
+        <T T'>
+ T' ->  {Epsilon}
+     |  _ T T' {Das _ war ein ''space''}
-.1
+Ein Wort der Sprache war: <<1 2 4> <1 4 5> 3>
-forme die grammatik so um, dass sie für einen
+Das ganze repräsentierte einen n-ären Baum
-top-down-parser geignet ist (--> LL(1)).
-.2
+ DATA token ==
-direktormengen aufstellen.
+ 	Open
-für die alte und die neue grammatik.
+ 	Close
+ 	space
+ 	id(val:int)
+ 	eof
+. Entwickle einen passenden Absy.
-.
+. Schreibe einen Recursive-Descent-/Combinator-Parser ohne Fehlerbehandlung. Falls Combinator: Programmiere auch die Kombinatoren.
-schreibe einen recursive-decent-parser (combinator/hand)
-ohne fehlerbehandlung für die grammatik:
-S  ->  T #
+== Aufgabe 3: SECD ==
-T  ->  < T T' >
-T' ->  ide
-    |
-???
+ (\x. x(2))(\y. dup(y))
-in der sprache war: <<1 2 4> <1 4 5> 3>
+Ergebnis 4
-das ganze repräsentierte einen n-ären baum
-DATA absy ==
+''dup'' ist eine triviale Operation.
-	node(val:seq[absy])
-	leaf(val:token)
+== Aufgabe 4: Codeerzeugung ==
-DATA token ==
+ int f(x:int, y:int){
-	Open
+ 	if(x==0)
-	Close
+ 		return y
-	space
+ 	else
-	id(val:int)
+ 		return f(x-1, x*y)
+ }
+. Erzeuge Pseudocode für eine abstrakte stackbasierte Maschine.
+. Erläutere den Stackframe (überlappung und sowas)
+== Aufgabe 5: Unifikation ==
-. SECD
+ FUN _ o _ : (beta -> gamma) -> (alpha -> beta) -> (alpha -> beta)
-(\x. x(2))(\y. dup(y))
+ FUN length: string -> nat
-ergebnis 4
+ FUN even?: nat -> bool
-dup ist triviale operation
-. codeerzeugung
+ FUN h: string -> bool
-int f(x:int, y:int){
+ DEF h(s) == o(even?)(length)(s)
-	if(x==0)
-		return y
-	else
-		return f(x-1, x*y)
-}
-erzeuge pseudocode für eine stackartige maschine
-erläutere den stackframe (überlappung und sowas)
-. unifikation
+ 					apply (tau1)
-length: string -> nat
+ 			apply(tau2)			s (tau3)
-even?: nat -> bool
+ 		apply(tau4)	length(tau5)
-h: string -> ???
+ 	o(tau6)		even?(tau7)
-h(s) == ???
-					eval
-			eval			s
-		eval	length
-	???		even?
-ergebnis war korrekt, aber das sah vllt. auch etwas anders aus..
-</pre>