Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Übersetzerbau 1

Inhaltsverzeichnis

Übersetzerbau 1

Setting

Kreutzer 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, minus das übliche aufgeregt sein bei Klausuren, aber ist halt immer so. Sie hatten teilweise sehr detaillierte Fragen gestellt (z.B. zur Methodenauswahl). Alles in allem aber gut machbar.

Ich persönlich hatte beim lernen immer mehr Bock am Compiler rumzuschrauben :D das ist aber leider für die Prüfung keine gute Vorbereitung. Besser die Folien *detailliert* durchschauen und für die Anwendung mancher Konzepte (z.B Aktivierungsrahmen oder Graphfärben) Übungsaufgaben nochmal machen.

Obacht: Prof. Philippsen fragt am Ende, was man sich selbst geben würde und wo es denn gehakt hat. Hab dann gesagt, bei der Methodenauswahl. Hier ist er auch recht direkt und sagte „ja da hatten sie keine Ahnung“ (ich mein stimmt halt auch :D), An einer anderen Stelle hatte es noch gehakt, hat sich aber knapp nicht negativ aufs Ergebnis ausgewirkt.

Prüfung

Erstes Stück Papier bekommen Codeschnipsel e2 mit überladung

func main()
	var foo : int;
	foo := foo(1, 2);
	# Die Parameter der beiden Aufrufe sahen in Wirklichkeit anders aus.
	# Wichtig ist die Frage, wie die Methodenauswahl geschieht.
	foo := foo(1, 2, 3);
	foo := foo(10.5, 2, 10.5);
end

func foo(p1 : int, p2 : real, p3 : int): real
	return p1 * p2 * p3;
end

func foo(p1 : real, p2 : int, p3 : real): int
	return ((p1 * p2 * p3) as int);
end

K: Was muss man im Compiler machen damit das geht?

A:

  • Lexer und Parser passen so wie sie sind
  • Namens- und Typanalyse müssen angepasst werden (Auswahl anhand des Typen)

K: Wie sieht denn die Namenstabelle genau aus?

A:

main :: () : i
foo :: (i, r, i) : r
foo :: (r, i, r) : i

K: Gibt es da nicht einen Konflikt?

A: An sich ja, weil es den Namen foo zweimal gibt. Allerdings muss man halt jetzt den Typen des Symbols in die Gleichheit mit einbeziehen

K: Wie geht das?

A: Gleichheit auf Symbol überschreiben. Ist halt langsam, eigentlich will man Hashmaps. Man könnte den Typen in den Hash mit einbeziehen

K: Wie sieht das jetzt in der Funktion aus?

A: Sichtbarkeitsschachteln hingemalt

0 (global)               1 (Parameter)   2 (Variablen)
main :: () : i                           foo :: int
foo :: (i, r, i) : r
foo :: (r, i, r) : i

Auf der linken Seite der Zuweisung ist es klar das foo auf Ebene 2. Bei den rechten Seiten muss man aufpassen. Da passt ja das foo auf Ebene 2 nicht. Man darf aber nicht direkt nen Fehler werfen, sondern muss erst schauen ob auf den äußeren Ebenen noch ein Symbol mit passendem Typen liegt.

K: Wie wird jetzt die Methode genau ausgewählt

Hier gab es länger Fragen wie genau die Methodenauswahl funktioniert. Auf Nachfrage sollte das hier mit der gleichen Semantik wie in Java geschehen. Ich wusste leider nicht genau wie das in Java funktioniert und hatte sowas gesagt wie der speziellere Typ der weniger Typkonvertierungen braucht wird ausgewählt. Das hat allerdings nicht gereicht.

K: Was passiert als nächstes im Compiler?

A: Übersetzung in Zwischensprache wegen

  • semantischer Lücke zu Zielarchitektur
  • Einfacheres hinzufügen von mehr Backends

K: Muss man hier noch was anpassen?

A: In unserem Compiler war die Funktionsauswahl in IR über Strings, heißt man braucht z.B. durch Name Mangling unterschiedliche Namen für die verschiedenen foo Varianten

K: Wie sieht so ein Funktionsaufruf jetzt tatsächlich zur Laufzeit aus?

A: Hängt ein bisschen vom Abstraktionsniveau ab. Hab dann angefangen Aktivierungsrahmen wie aus der Vorlesung zu erklären. Also bei nem Aufruf wird ein Aktivierungsrahmen aufgebaut, da steht dann Stuff drin.

K: Kann man die Rahmen statisch allozieren?

A: Ja, wenn es keine Rekursion gibt, dann kann jede Funktion maximal einmal aktiv sein. Ansonsten muss man immer neue Rahmen aufbauen können, die haben dann Stapelcharakter.

Wichtig ist, dass alles notwendige in dem Aktivierungsrahmen deklariert ist, also Rücksprungadresse, Parameter, lokale Variablen und insbesondere der Verweis auf den Vorgängerrahmen. Hier hatte ich mich erst etwas verrannt und die Rücksprungadresse auf den Vorgänger zeigen lassen, aber der Vorgängerrahmen ist halt ein extra Feld. Die Rücksprungadresse zeigt auch nicht auf den Rahmen, sondern in die Mitte der Funktion.

P: Sie haben ja den Rückgabewert als Teil des Callee-Aktivierungsrahmen und gerade haben sie gesagt der Aktivierungsrahmen wird aufgeräumt sobald der Callee zurückkehrt.

A: Caller und Callee einigen sich auf einen Ort für die Übergabe, auf x86/SysV zum Beispiel RAX

P: Das wär jetzt mit Register, wie geht das nur mit Stack.

A: In Wirklichkeit ist dieser Rahmen ja zweigeteilt, es gibt den Teil den der Aufrufer bereitstellt (Parameter, Platz für Rückgabewert, Rücksprungadresse), in der Mitte liegt der Vorgängerrahmenzeiger (Deutsch ist schon toll :D) und danach erst die lokalen Variablen Callees (hab dazu außerdem nen kleinen Stack hingemalt)

K: Wie ist das mit Caller- und Callee-Save-Registern

A: Sowohl Caller- als auch Callee- rechnen ja irgendwas aus. Am liebsten in Registern, weil ist schneller. Jetzt braucht der Caller Werte die in einem Register stehen eventuell nach dem Funktionsaufruf noch, und da ist die Frage wer von beiden das sichert.

K: Woher weiß man jetzt welche Variable in welchem Register steht?

A: Durch Registerzuteilung

Da sollte ich auf einem neuen Zettel Lebensspannen ausrechen, hab jeweils dazu gesagt dass es die Lebensspanne einer Zuweisung ist, nicht der Variable und halt erklärt wie man vorgeht, von unten nach oben. Außerdem dass man unterschiedliche Variablen ins gleiche Register packen kann, wenn deren Lebensspannen nicht interferieren.

Dann kam ne Frage zu Coalescing, was das bringt (mov einsparen) und warum man aufpassen muss (Lebensspannen werden verbunden, beeinträchtigt evtl Färbbarkeit)

Dann halt das Verfahren erklärt

  • Kollisions- und Interferenzgraph aufbauen
  • was es mit Move-Kanten und Coalescing auf sich hat
  • Warum die Register mit im Graph sind (kriegen direkt ne Farbe, und man kann
  • modellieren, dass manche Werte nicht in ein bestimmtes Register dürfen)
  • Wie man das mit Grad<R Regel färbt und wann man Coalescing betreibt

Zeit rum