Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Übersetzerbau 1
Inhaltsverzeichnis
Übersetzerbau 1
Allgemein
- (B)eisitzer: Florian Mayer
- (P)rüfer: Prof. Philippsen
- Note: 1.3
- Vorbereitung:
- Zusammenfassung geschrieben und die einzelnen Verfahren/Algorithmen gelernt. (Algorithmen lernen hat mehr geholfen als Zusammenfassung zu schreiben. Wie andere bereits sagen ist am Compiler arbeiten nicht sehr nützlich für die Prüfung, eher Folienwissen)
- Fazit:
- Ich war anfangs sehr nervös und trotz viel Vorbereitung habe ich mich dann doch an manchen Stellen verunsichern lassen. Ich hatte das Gefühl, dass Prof. Philippsen sehr schnell merkt, wenn man etwas nicht zu 100% verstanden hat und dann nochmal nachhakt, dafür ist die Bewertung aber dann doch sehr fair und die Atmosphäre war auch ganz entspannt.
- Im nachhinein denke ich, ich hätte mir mehr Zeit zum antworten lassen sollen. Ich habe immer direkt auf die Frage geanwortet und mich damit manchmal ziemlich verhaspelt, nachdem ich dann kurz nachgedacht habe bin ich fast immer auf die Lösung gekommen.
Prüfung
Erweiterung des e2-Compilers
B gibt Codeschnipsel, e2 mit for-Schleife:
... var i : int; for i := 0 to 12 do [1] if <something> then continue; end end ...
B: Wie muss man den e2-Compiler hierfür anpassen?
S: Neue Tokens im Lexer, neue Produktion im Parser
B: Welche Tokens braucht man?
S: FOR, TO
P: Fehlt noch was?
S: *Gehe nochmal drüber* Nein
P: CONTINUE
B: (Gibt weiteres Papier mit Ausschnitt der e2-Grammatik) Passen sie die Grammatik entsprechend an
S: neue Produktion if_statement: FOR i ASSIGN arith_expr TO arith_expr DO block END
und als Alternative in statement eintragen
B: Was muss dann noch gemacht werden?
S: Neue Klasse für den AST-Knoten erstellen
B: Wie geht es dann in der Analyse weiter?
S: Als nächstes Namensanalyse, der neue AST-Knoten wird analog zu den alten behandelt, keine Besonderheit. Dann Typanalyse, in der Typprüfung muss nur verglichen werden, dass die Typen der Variable und der to-Expression passen (und dann der Block).
(ich war mir hier manchmal nicht ganz sicher ob ich jetzt die Phasen auch allgemein erklären soll oder nur anhand der Schleifenerweiterung, ich denke er wollte einfach dass ich auf die Schleifen eingehe)
B: Was kommt nach der Analyse?
S: Abbildungsphase, zu erst Baumtransformationen auf dem AST für Syntaxzucker, dann überführung in Zwischencode für Optimierungen und andere Transformationen.
B: Syntaxzucker für if-Schleife? (Ich denke er hat mich falsch verstanden, weil ich nur generell erwähnen wollte, dass Syntaxzucker möglich ist)
S: Könnte man machen als while mit if
P: Geht das hier wirklich?
S: *nachdenken* … nein wegen continue
B: Wie sieht dann Abbildung aus?
S: Habe nach und nach den Code erarbeitet, habe mir da auch Zeit gelassen und wurde nicht bemängelt.
i = 0 jmp Lcond Lbody code (block) Linc: i = i + 1 Lcond: jle i 12 Lbody
Dann noch Umsetzung von continue
als jmp Linc
(Bin erst zu Lcond
gesprungen, Philippsen meinte dann da stimmt etwas nicht)
Java Generics
B gibt typisches Java-generics Beispiel (siehe z.B. pruefungen:hauptstudium:ls2:ueb1-2022-02_21#baumtransformationen)
B: Was macht Java damit?
S: Stichwort type-erasure, Generics werden entfernt, generische Typen durch Object ersetzt (führe ich auch gleichzeitig auf Papier durch). Erkläre dann, dass jetzt die Methode des Interfaces nicht mehr von der Klasse implementiert wird und füge Brückenmethode ein. Da war ich kurz verwirrt, weil die Methode den Rückgabetyp Integer hatte und hab dann da noch einen Cast eingefügt, den hab ich dann aber letztlich wieder gestrichen.
Codierung
B: Was passiert nun nachdem jegliche Optimierungen etc. in der Abbildungsphase durch sind?
S: Code für die Zielarchitektur wird erzeugt
B: Welche Teilprobleme gibt es dabei?
S: Code-Selektion, Registerzuteilung, Instruktionsanordnung
Code-Selektion
B: Welche Verfahren zur Code-Selektion kennen Sie?
S: Habe die Verfahren aufgezählt und etwas zu Grundblöcken erzählt, bei Baumtransformationen unterbricht B dann
B: Baumtransformationen schauen wir uns jetzt genauer an
B bringt Zettel mit Produktionsregeln und einem Ausdrucksbaum
B: Wie geht man hier jetzt vor?
S: Regeln top-down auflegen nach maximum-munch Prinzip (um Befehlsanzahl zu minimieren), dann bottom-up auswerten
B: Kann man auch anders Vorgehen als maximum-munch?
S: Ja, z.B. die Befehle gewichten und danach aussuchen
B: Okay, dann wenden sie jetzt mal die Regeln an
S: Ich zeichne die Teilbäume ein und notiere welche Regel passt. Habe währenddessen meinen Gedankengang erklärt, der war aber ziemlich unklar und hat dann nur für Nachfragen gesorgt, hat aber alles gestimmt.
P fragt dann nach wie man jetzt den Code bekommt, ich hatte das Gefühl ich bin ihm da nicht schnell genug auf den Punkt gekommen, aber mir kam es die ganze Zeit so vor als würde ich viel zu schnell durch die Themen fliegen
Dann zeige ich wie man bottom-up den Code generiert, bzw. wollten sie nur die Reihenfolge wissen, nicht die Generation sehen.
Registerzuteilung
B: Wie werden jetzt Register zugeteilt?
S: Ich erkläre erstmal, dass das nötig ist, weil Baumtransformationen von unendlich Registern ausgeht, dann erkläre ich Graphfärben.
B bringt Zettel mit Kollisionsgraph und einer Instruktionsfolge, die zum Graphen gehört
B: Wie erhält man den Graph
S: Lebensspannen aufstellen, Kollisionen feststellen, jede Kollision ist eine Kante, jede Lebensspanne ist ein Knoten.
P: Was sind Lebensspannen
S: * erkläre Lebensspannen *, wichtig war P, dass die Lebensspanne auch endet, wenn der Wert nicht mehr verwendet wird
B: Was hat es mit den gestrichelten Kanten auf sich?
S: Move-Kanten, können mit coalescing optimiert werden
B: Was mache ich als nächstes mit dem Kollisionsgraph
S: Interferenzgraph bilden, dazu einen Knoten für jedes reale Register einzeichnen und diese miteinander verbinden, man kann Kante mit realem Register einfügen um Sonderbedingungen auszudrücken (diese Variable nicht in dem Register)
B: Transferfrage: wie kann man Ausdrücken, dass ein Wert in einem bestimmten Register stehen muss
S: * etwas nachdenken * Der Knoten erhält eine Kante zu jedem anderen Register
B: Wie geht man jetzt vor beim Graphfärben?
S: * erkläre die Grad < R Regel und wie ich damit vorgehen würde *
P: Was machen Sie jetzt mit den Move-Kanten?
Ich war mir hier nicht ganz sicher wie das Graphfärben abläuft, ich dachte man färbt einfach und wenn man mag wird coalescing durchgeführt, P wollte aber darauf hinaus dass man zu erst coalescing macht, das habe ich dann erklärt und auch am Beispiel erklärt, welche Knoten jetzt verschmolzen werden können.
P: Wird nur am Anfang verschmolzen und die Move-Kanten dann vergessen?
S: * unsicher * ich denke man kann immer wieder prüfen ob coalescing möglich (ich denke das war falsch aber im nachhinein keine Ahnung)
Instruktionsanordnung
B: Wir schauen nun Instruktionsanordnung an, was macht man da?
S: Wir wollen die Pipeline der CPU bestmöglich ausnutzen, wegen Konflikten kann es zu Delays kommen, die Instruktionen sollen möglichst so angeordnet werden, dass wenige Delays entstehen, bzw. diese gut genutzt werden.
B bringt Zettel mit Abhängigkeitsgraph und anderen mit Instruktionsreihenfolge
B: Was zeigt der Graph
S: * erkläre Abhängigkeitsgraph *
B: Wie geht man jetzt vor bei list-scheduling?
S: Man nimmt wurzelknoten aus dem Graph bis keine mehr übrig
Hier fragt P nach wie man da genau vorgeht, ich habe das irgendwie undeutlich erklärt, dann sage ich nochmal, dass man eben immer den Wurzelknoten nimmt mit höchstem Delay
P: Was ist denn der Delay?
S: Für Blattknoten einfach ExecTime, für innere Knoten die Verzögerung zwischen ihm und Abhängigkeit + ExecTime
P: Wirklich + ExecTime?
(Er wollte wahrscheinlich darauf hinaus, dass es Verzögerung + Delay ist, ich habe mich davon leider verunsichern lassen und gesagt dass es nur Verzögerung ist, was natürlich falsch ist, das war ärgerlich)
P: Zeit um