Übersetzerbau 1

• „Grundlagen des Übersetzerbaus“ WS 2012/2013 (7,5 ECTS) ~ 30 min

Prüfer: Prof. Dr. Michael Philippsen
Beisitz: Dipl.-Inf. Thorsten Blaß
Papier + Stift bereitgestellt, versch. Blätter mit Pseudo-Code für Prüfungsfragen vorhanden

 short x = 10;                      // (2.1)
 void foo() {
    int a = readInt();              // (1)
    int b[][] = new int[40][40]; 
    for (int i = 0; i < 10; ++i) {
       short x = x + 10;            // (2.2)
       b[10+i][11-i-2] = 3*4;       // (3)
    }
 }

Angangs ging es nur um die Zeile „int a = readInt()“ (1) und wie das übersetzt wird. Wo man an der Stelle anfängt war mehr oder minder freigestellt, ich habe ganz vorne angefangen mit Lexer, Parse, Syntax, etc. Irgendwann kam noch die Frage, wie wir das readInt in unserem Übungscompiler implementiert hatten. Der Teil war laut Prüfer zum „Aufwärmen“, also einfach mal erzählen was einem dazu einfällt.

Danach ging es um die Zeile innerhalb der for-Schleife (2.1 und 2.2). Es war der Syntaxbaum gefragt und, welches x an dieser Stelle verwendet wird. Nicht sicher ob ich die eigentliche Antwort dann auch richtig verstanden hab, aber die Erklärung lief darauf hinaus, dass es Definitionssache der Sprachbeschreibung ist. Z.B. wäre möglich, dass x in jedem Durchlauf auf einen alten Wert von x zugreift und einmal ganz am Anfang mit 0 initialisiert wird.

Beim Thema Definitionstabelle kamen wir dann auf deren Umsetzung. Zum einen wie wir das in der Übung gemacht haben (geschachtelte Hashtabellen), und warum das „schön“ war (leichtere Implementierung). An der Stelle lag dann das Beispiel aus der Vorlesung vor mit der Hashtabelle und dem durchgefädelten Stack. Gefragt wurde, warum diese Variante eigentlich der aus der Übung vorzuziehen ist (u.a. nicht dauern neue Tabellen erzeugen) und was man machen müssten, wenn eine Variable nicht 2-mal definiert werden darf (also keine Überdeckung in inneren Blöcken).

Anschließend gingen wir über zum Arrayzugriff (3). Gewollt war der AST für die Zeile. Gefragt war dann die Anwendung von DP mit 2 Registern und die Frage was eigentlich optimiert wird (es wird nicht die Codegröße optimiert sondern die Kosten für die Anweisungen) sowie was an dem Verfahren eigentlich Dynamische Programmierung ist (Teilausdrücke können wieder verwendet werden).

Anhand vom AST sollte dann noch kurz Registerverteilung durch Graph Färben erklärt werden, wobei es wirklich nur um die Theorie ging, da wir bei DP schon nach 3 Knoten abgebrochen haben. Wichtig war was eine Lebensspanne ist und was eine Kante im Interferenzgraphen wirklich bedeutet. In dem Zusammenhang hatte ich erwähnt, dass man mit diesen Kanten auch garantieren kann, dass eine Variable sicher in ein Register kommt. Herr Philippsen hat dann gefragt, was passiert wenn man ganz viele Int und Float Register hat, die Variablen also auf diese zwei Typen verteilet werden müssen. Die Antwort an der Stelle war, dass man statt einem Graphen insgesamt 2 Graphen verwendet, einen für Int und einen für Float, das spart eine Menge Kanten.

In den letzten 5 Minuten ging es noch um die Transformation von Inneren Klassen in Java. Gegeben war eine reguläre nicht statische Innere Klasse die auf private Instanzvariablen zugegriffen hat (also access-Methoden). Irgendwo weiter unten wurde auch mit instanceof auf die innere Klasse zugegriffen (Name der Inneren anpassen). Die Aufgabe war eigentlich absolut Standard, keine extra Fragen oder ungewöhnlichen Fälle.

Wie schon in anderen Protokollen erwähnt, es geht sehr viel um Verständnis. D.h. warum wendet man ein Verfahren überhaupt an, warum die einzelnen Teilschritte. Eigentlich komplett durchgeführt habe ich von den Verfahren eigentlich keines. Und die Atmosphäre ist echt super, die Prüfer sind wirklich nett drauf ;)