Compilerbau Gedächtnisprotokoll WS201112

Aufgabe 1 (8 Punkte)

Folgende uneindeutige Grammatik war gegeben:

E -> E E      -- Applikation
   | E.id     -- Selektion
   | (E)
   | a

a) Jeweils zwei mögliche Ableitungsbäume für: aaa und aa.x

b) Grammatik umformen, sodass sie eindeutig wird. Dabei soll Selektion stärker binden als Applikation und Applikation soll linksassoziativ sein. Das heißt, es herrscht folgende "gedachte Klammerung": (aa)a und a(a.x)

Aufgabe 2 (7 Punkte)

Eine kontextfreie Grammatik war gegeben.

a) Warum eignet sich die Grammatik nicht für einen LL(1)-Parser?

Enthielt Linksrekursion und konkurrierende Produktionen mit gleichen Direktorsets (d.h. gleichen Anfängen).

b) Forme die Grammatik so um, dass sie durch einen LL(1)-Parser geparset werden kann und zeige, dass die Direktorsets jetzt disjunkt sind.

Aufgabe 3 (13 Punkte)

Gegeben eine abstrakte Syntax, zB Let, Selektion. Außerdem waren Regeln für die Typprüfung gegeben (Kontexte Gamma, Typen tau...).

Aufgabe: Schreibe in OPAL einen Typchecker, der die gegebenen Regeln für die abstrakte Syntax implementiert.

Aufgabe 4 (12 Punkte)

Polymorphe Typprüfung / Unifikation:

Abstrakter Syntaxbaum eines Ausdrucks war gegeben, dazu ein Kontext. Es musste mithilfe des Unifikationsalgorithmus der Typ des Ausdrucks berechnet werden.

Aufgabe 5 (8 Punkte)

Lambda-Kalkül

a) Berechne freie Variablen des Lambda-Ausdrücke

b) Führe in einem Lambda-Ausdruck alpha-Substitutionen durch, sodass alle Variablen unterschiedlich heißen. (Im gegebenen Ausdrucken gab es verschiedene Variablen mit Namen a, die an verschiedenen Stellen gebunden waren.)

c) Führe eine beta-Reduktion durch.

Aufgabe 6 (12 Punkte)

Gegeben waren die Maschinenbefehle für die virtuelle Mikro-Opal-Maschine (siehe [1]).

Aufgabe: Schreibe in Opal einen Codegenerator, der aus der folgenden abstrakten Syntax eine Sequenz von Maschinenbefehlen macht, d.h. implementiere die Funktion compile (siehe unten).

Dabei sollte darauf geachtet werden, dass die Stackgröße minimal bleibt. (Optimierung war 4 Punkte wert!)

"true" und "false" sollten dabei jeweils durch eine auf dem Stack liegende "1" oder "0" repräsentiert werden.

TYPE absy =   true
           | false
           | not(a)
           | implies(b1,b2)

FUN compile: absy -> seq[opcode]

Für implies(b1,b2) war folgende Wahrheitstabelle gegeben:

b1	b2	Ergebnis
true	true	false
true	false	false
false	true	true
false	false	true