Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Übersetzerbau 1
Inhaltsverzeichnis
Übersetzerbau 1
- „Grundlagen des Übersetzerbaus“ WS 2012/2013 (7,5 ECTS) ~ 30 min
Prüfer: Prof. Dr. Michael Philippsen
Beisitz: Dipl.-Inf. Tobias Werth
Papier + Stift bereitgestellt, verschiedene Blätter mit Pseudo-Code für Prüfungsfragen vorhanden.
Prüfer P, Student S.
Code
class ExceptionA { } class ExceptionB { } class ExceptionA1 { public int foo() { return 4711; } class ExceptionA2 { public int foo() { return 4_2; } class Example { public static void main() { if (x > y && x - 7 > 0) { // if } else { // else } switch (argv[0]) { case "foo" : throw new ExceptionA(); case "bar" : throw new ExceptionA(); case "bla" : throw new ExceptionA(); } try { // .. } catch (A1 | A2 e) { e.foo() } } }
Vom Prinzip her, nicht exakt.
Lexer
P: Wie implementiert man 4_2 im Compiler, neue Schreibweise für 42?
S: Erklärt was ein Lexer ist (DFA) und wie er funktioniert (längsten Match verwenden, aus Eingabe entfernen, Aktion ausführen). Lexer erweitern, Regex für Zahlen nun [0-9][0-9_]*, keine sonstigen Änderungen nötig.
Parser
P: Was ist ein Parser und wie funktioniert er?
S: Kellerautomat, Grammatik, Produktionen, shift-, reduce-Operationen erklärt.
P: Warum wird Parser und Lexer nicht zusammengefasst?
S: Schneller (DFA schneller als Kellerautomat), weniger Zeichen (Token vs. String) machen Parser einfacher und schneller, Kommentarbehandlung im Parser komplexer.
Zwischencode
P: Wie sieht der Zwischencode für das if aus?
S: Baumstruktur der if-Bedingung gemalt (vgl. Übung), dann folgender Code
CBGT x, y, t1 CBRA f0 CLABEL t1 CBGT x, 7, t0 CBRA f0 CLABEL t0 // if CBRA out // else CLABEL f0
Compiler erweitern
P: Neues Feature in Java 7: switch über Strings. Wie baut man das in den Compiler ein?
S: Parser anpassen, so dass Strings nach „case“ erlaubt sind; dann in der semantischen Analyse prüfen ob da ein String ist, Code-Generierung anpassen.
P: (Unterbrechung) Wie baut man ein Switch-Case allgemein?
S: if-else-Kette, Tableswitch, Lookupswitch, binäre Suche; allgemeine Struktur des Switch-Case aufgemalt.
P: (weiter) Wie bildet man das auf den existierenden Switch-Case Fall ab?
S: Naiv einfach die Werte vergleichen, oder besser mit Hashtable. Dann in den Cases noch auf Kollisionen prüfen.
P: Was macht man wenn ein break fehlt?
S: Keine Ahnung. [In der Besprechung die Antwort bekommen: Zwei Switch-Case, das erste hat überall breaks und löst per Hashtable die Fälle auf und setzt einen Variable auf die case-„Nummer“. Das zweite mit den Nummern im Case und dann mit ohne/breaks pro Fall.]
Methodenauswahl
P: Neues Feature in Java 7, (A1 | A2 e) im catch, warum funktioniert dieser Aufruf nicht?
S: Müsste doch eigentlich gehen. Methodenauswahl wird statisch durchgeführt, aber Klassen A1 und A2 sind ja bekannt. [Antwort in der Besprechung, hätte man auch so machen können, aber in Java 7 wird die gemeinsame Oberklasse verwendet, und falls die Methode da nicht vorhanden ist, schlägt das fehl.]
P: Wie funktioniert Methodenselektion?
S: Passende Signatur, zugreifbar (public/private), Instanz- oder Klassenmethode, (nach Nachfrage) spezifischste Methode wird gewählt.
P: Wie bestimmt man die spezifischste Methode.
S: Konnte ich nicht genau definieren.
P: Zeigen sie doch mal ein Beispiel wo das nicht eindeutig ist.
S:
void foo(Object x, Foo b) {} void foo(Foo x, Object b) {} Foo a, b; foo(a, b);
Registervergabe
P: Wie funktioniert die Registervergabe?
S: Lebensspannen, Graphfärben, Grad < R Regel, Optimierung für Grad >= R (nicht nur bei Grad = R den Knoten bei der Färbung nochmal probieren (wie es in der Vorlesung erklärt war), sondern immer probieren)
P: Was bedeutet eine Kante im Graphen?
S: Kollision zwischen Lebensspannen, die symbolischen Register können nicht im selben realen Register gespeichert werden.
P: Was macht man bei Zuweisungen?
S: Registerverschmelzung, beim Graphfärben verschmelzen. Heuristiken dafür genannt und erklärt (siehe Folien).
P: Was macht man bei der Registerfärbung wenn man int und float Register hat?
S: int und float Register getrennt färben, da sie unabhängig sind.
Vorbereitung
Ca. eine Woche, Stoffzusammenfassung, Übungen nochmal angeschaut, Compiler nochmal angeschaut (und im Semester selbst gebaut).
Fazit
Atmosphäre sehr angenehm, Fragen kamen vor allem von Tobias. Note: sehr gut