https://wiki.freitagsrunde.org/index.php?action=history&feed=atom&title=Compilerbau_Ged%C3%A4chtnisprotokoll_WS201112 2026-05-30T16:16:38Z Versionsgeschichte dieser Seite in FreitagsrundenWiki MediaWiki 1.31.16 https://wiki.freitagsrunde.org/index.php?title=Compilerbau_Ged%C3%A4chtnisprotokoll_WS201112&diff=17716&oldid=prev 2012-03-09T17:05:01Z

<p>Die Seite wurde neu angelegt: „== Aufgabe 1 (8 Punkte) == Folgende uneindeutige Grammatik war gegeben: E -&gt; E E -- Applikation | E.id -- Selektion | (E) | a a) Jeweils …“</p> <p><b>Neue Seite</b></p><div>== Aufgabe 1 (8 Punkte) ==<br /> <br /> Folgende uneindeutige Grammatik war gegeben:<br /> <br /> E -&gt; E E -- Applikation<br /> | E.id -- Selektion<br /> | (E)<br /> | a<br /> <br /> a) Jeweils zwei mögliche Ableitungsbäume für: aaa und aa.x<br /> <br /> b) Grammatik umformen, sodass sie eindeutig wird. Dabei soll Selektion stärker binden als Applikation und Applikation soll linksassoziativ sein.<br /> Das heißt, es herrscht folgende &quot;gedachte Klammerung&quot;: (aa)a und a(a.x)<br /> <br /> == Aufgabe 2 (7 Punkte) ==<br /> <br /> Eine kontextfreie Grammatik war gegeben.<br /> <br /> a) Warum eignet sich die Grammatik nicht für einen LL(1)-Parser? <br /> <br /> ''Enthielt Linksrekursion und konkurrierende Produktionen mit gleichen Direktorsets (d.h. gleichen Anfängen).''<br /> <br /> b) Forme die Grammatik so um, dass sie durch einen LL(1)-Parser geparset werden kann und zeige, dass die Direktorsets jetzt disjunkt sind.<br /> <br /> <br /> == Aufgabe 3 (13 Punkte) ==<br /> <br /> Gegeben eine abstrakte Syntax, zB Let, Selektion. Außerdem waren Regeln für die Typprüfung gegeben (Kontexte Gamma, Typen tau...).<br /> <br /> Aufgabe: Schreibe in OPAL einen Typchecker, der die gegebenen Regeln für die abstrakte Syntax implementiert.<br /> <br /> == Aufgabe 4 (12 Punkte) ==<br /> <br /> Polymorphe Typprüfung / Unifikation:<br /> <br /> Abstrakter Syntaxbaum eines Ausdrucks war gegeben, dazu ein Kontext. Es musste mithilfe des Unifikationsalgorithmus der Typ des Ausdrucks berechnet werden.<br /> <br /> == Aufgabe 5 (8 Punkte) ==<br /> <br /> Lambda-Kalkül<br /> <br /> a) Berechne freie Variablen des Lambda-Ausdrücke<br /> <br /> 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.)<br /> <br /> c) Führe eine beta-Reduktion durch.<br /> <br /> == Aufgabe 6 (12 Punkte) ==<br /> <br /> Gegeben waren die Maschinenbefehle für die virtuelle Mikro-Opal-Maschine (siehe [http://docs.freitagsrunde.org/LV-Material/compilerbau-mst4.pdf]).<br /> <br /> 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).<br /> <br /> Dabei sollte darauf geachtet werden, dass die Stackgröße minimal bleibt. (Optimierung war 4 Punkte wert!) <br /> <br /> &quot;true&quot; und &quot;false&quot; sollten dabei jeweils durch eine auf dem Stack liegende &quot;1&quot; oder &quot;0&quot; repräsentiert werden.<br /> <br /> TYPE absy = true<br /> | false<br /> | not(a)<br /> | implies(b1,b2)<br /> <br /> FUN compile: absy -&gt; seq[opcode]<br /> <br /> Für implies(b1,b2) war folgende Wahrheitstabelle gegeben:<br /> <br /> {| class=&quot;wikitable&quot; style=&quot;text-align:center&quot;<br /> ! width=33% | b1<br /> ! width=33% | b2<br /> ! width=34% | Ergebnis<br /> |-<br /> | true<br /> | true<br /> | false<br /> |-<br /> | true<br /> | false<br /> | false<br /> |-<br /> | false<br /> | true<br /> | true<br /> |-<br /> | false<br /> | false<br /> | true<br /> |}</div>

Theresa