Übersetzerbau 1 [12. April 2022]

Mayer und Prof. Philippsen saßen etwas entfernt von mir. Ich saß vor der Dokumentenkamera, hatte darauf die Zettel liegen und hab geschrieben bzw. gezeigt.

Stimmung war an sich ganz chillig (Phillipsen hat noch erzählt, dass sie zum erstenmal die AuD-Klausur am Vortag nicht komplett geschafft haben aufgrund von Corona-Fällen), minus das übliche aufgeregt sein bei Klausuren, aber ist halt immer so.

Ich habe hier nur Antworten notiert die relevant für den Verlauf sind.

M: Welche Phasen hat der Compiler?

M: Aus welchen Elementen besteht die Analysephase?

bei Parser dann Zwischenfrage:

M: Welche Problematiken gibt es bei kontextfreien Sprachen?

A: - Keine Linksrekursion bei LL-Parsern

- Shift-Reduce und Reduce-Recude Konflikt bei LR-Parser

M: Wie kann es zu Mehrdeutigkeiten kommen?

A: Wenn zwei Regeln angewendet werden können.

P: Sind diese Mehrdeutigkeiten ein Problem?

A: Nein, weil Auswerungsreihenfolge sowie Operatorpräzedenz vom Sprachstandard definiert werden.

M: Wozu braucht man AST-Transformationen und macht das nicht im Zwischencode?

Was er hören wollte war Syntax-Zucker

M: Was können Sie uns zum Besuchermuster erzählen?

A: Dient dazu mehrere Algorithmen auf eine Vererbungshierarchie anzuwenden. Es gibt dann zwei Vererbungshierarchien einmal die Ast-Knoten (Statement, Expression) und die Algorithmen die von Besucher erben

Soll ich das mal aufmalen?

M: Ja

Male grobes Klassendiagramm und erkläre; erwähne Double Dispatch

P: Wozu brauche ich jetzt dieses Double Dispatch?

A: Um mit einem virtuellen Methodenaufruf die konkrete Implementation des AST-Knoten zu erreichen und dann mit einem zweiten virtuellen Methodenaufruf die konkrete Implementaion des Besuchers.

Gibt Codebeispiel mit Generics in Java.

public interface A<T> {
  public T get(T t);
}
public class B implements A<String> {
  public String get(String t) {...}
}
-------------------
public interface A {
  // Platz zum kritzeln
}
public class B implements A {
  // Platz zum kritzeln
}

M: Wie geht Java damit um?

A: Type Erasure, bleibt aber als Metainformation in class-Datei.

Brückenmethode vormachen.

M: Kennen sie andere Umsetztungsmöglichkeiten aus anderen Sprachen?

A: Äh

Nachdem ich 10 sec geschwiegen habe:

P: Z.B. C++?

A: Ja templates werden für jede neue Typparameter neu instantziert.

M: Wie funktioniert die Übersetzung von Ablaufstrukturen?

A: If und While werden in Sprungbefehle übersetzt.

M: Demonstieren Sie das mal an einer While Schleife „while (cond) {X}“

Ich schreibe:

jump L1:
L2:
X
L1:
B(cond, L2, L3)
L3:

A: Hier springe ich jetzt ans ende zur Tail Condition

P: Warum nutzten sie keine Head-Condition

A: Weil ich dann weniger Sprünge habe.

P: (Er geht den Code ab und zählt die Sprünge bei Head und Tail Condiiton) Nein in beiden Fällen sind es n+1 Sprünge.

A: Ich überlege ein bisschen. Weil Head condition pro Iteration zwei Sprünge nacheinander ausführt (jump und jCC) was für Branch Prediciton und Pipeline schlechter ist:

L1:
jCC cond
X
jump L1

P: richtig

gibt Code Beispiel:

...
switch(something) {
  case 12:
    result += 1;
  case: 11:
    result *= 2;
    break;
  case 14:
    result += 3;
  default:
    result *= 4;
    break;
}
...

M: Wie kann man dieses switch übersetzten?

A: Als If-Kaskade.

Oder als Binärbaum.

P: Wirklich?

A: Äh, Achso da sind fall-throughs drin deshalb geht es nicht.

Man kann das auch noch mit einer Jump-Table übersetzen. Ich schreibe: jump table[something]

P: Wann würde man keine Jump-Table nehmen?

A: Wenn die Tabelle sehr groß werden würde. Wenn ich also viele Lücken habe, die man mit dem default Füllen müsste.

Gibt Beispiel mit rekursiven Methoden (habe ich aber nicht verwendet)

M: Was macht ein Aktivierungrahmen?

A: Sichert Argumente, lokale Variablen und Rückgabewerte

M: Was muss immer im Aktivierungsrahmen liegen?

A: Ach die Rücksprungadresse.

M: Muss das immer auf dem Stack liegen? Auch bei nicht rekursiven Funktionen?

Hier kam noch eine Frage (die ich nicht so ganz verstanden habe), habe das Ganze dann (unabsichtlich) in Richtung Aufbau des Aktivierungsrahmen gesteuert (deshalb wurde das Codebeispiel auch nicht verwendet).

Ich beginne Aktivierungsrahmen zu schreiben (ret. addr, rbp, Aktivierungsrahmen, callee-Save)

M: Was hat es mit den callee-save-Registern auf sich.

P: Sichert eine Funktion immer alle callee-save-Regs oder nur die, die sie verwendet?

A: Nur die die sie verwendet

P: Sicher?

A: Ja

Hier schweige ich 5 sec, Prüfer schweigen, also habe ich das Gefühl etwas falsch gemacht zu haben, (Nach der Prüfung wurde das aber nicht angesprochen), habe dann einfach gesagt:

Wenn die aktuelle Funktion wieder eine andere aufruft dann muss die sich darum kümmern, aber die aktuelle Funktion sichert nur callee-save-Regs die sie auch verwendet

P: Zeichen sie mal den Base Pointer ein. Brauch man den immer?

A: Zeigt unter saved rbp. Brauchen tut man ihn nicht, geht auch über rsp, feste Offsets…

P: Warum verwendet man den Base Pointer dann?

A: Fürs debuggen und für variable arrays

M: Wie geht die Instruktionsauswahl vor?

A: Ist eines der drei Teilprobleme der Codeauswahl.

Wir haben vier Algorithmen kennengelernt. …

M: Ok, bleiben wir bei der Baumtranformation. Wie funktioniert die?

A: Arbeitet auf Grundblöcken (Blöcke mit trivialem Kontrolfluss), Daraus werden Ausdrucksbäume erzeugt.

M: Das geht doch nicht immer?

A: Stimmt, Grundblöcke werden in einen DAG transformiert, dann in Wald zerschnitten

Für jeden Maschinenbefehlt wird eine Baumtransformation definiert und dann werden die Transformationen auf den Ausdrucksbaum angewendet.

M: Und wie wird dann der Code genertiert.

A: Die Muster werden top-down auf den Baum gelegt und dann bottom-up angewendet und der Code erzeugt.

Zeit rum