Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » ueb1-2015-03-31 (Übersicht)
Dies ist eine alte Version des Dokuments!
31.03.2015
- Grundlagen des Übersetzerbaus
- 30 Minuten
- Prüfer: Dipl.-Math. Jakob Krainz
- Beisitz: Prof. Dr. Michael Philippsen
- Papier und Stift bereitgestellt
- Ein Blatt mit ausgedrucktem Code vorbereitet
- Ein weiteres Blatt für die Anwendung von dynamischem Programmieren
Codebeispiel 1:
int func(int p1, int p2, int p3){ int x = (3*p1 + 4*p2)/(2*p2+ 3*p3);//[1] if(10 <= x < 101){//[2] x = p2; } }
P: Was haben wir in CB1 gemacht?
S: Entwurf und Implementierung moderner Compiler
P: Was gehoert zu einem Compiler dazu/
S: Lexer (generiert!), Parser (generiert!), AST-Besucher …
P: Bleiben wir gleich bei Lexer/Parser, warum wuerde man den Parser denn von Hand schreiben?
S: (Insert PHP Joke here) Um bessere Fehlermeldungen erzeugen zu koennen
P: Woraus werden Lexer/Parser denn generiert?
S: Syntax Beschreibung als Gramatiken
P: Woraus besteht ein Parser?
S: Generierte Tabelle + Stack
P: Was macht der Parser?
S: Shift/Reduce LALR(1) erklaeren
P: Gehen wir doch mal zu dem Codebeispiel, was macht der Parser da?
S: TKINT, TKNAME …
P: okay, dann Zeile [1], was macht der Parser daraus?
S: AST auf Papier skizieren, wichtig, Parser kann Typ des DIV nicht erkennen
P: Wie erkennt man, dass es eine Integer Division ist?
S: Bottom-Up Typpruefung (Prototyp erwaehnen)
P: Was brauchen wir noch vorher?
S: Variablen-Definitionen aufloesen.
P: Wie implementiert man das? Bzw, wie haben sie es Implementiert?
S: Stack aus Hashmaps
P: Was macht unser Compiler aus [2]?
S: Parser akzeptiert, Typfehler in Java, Akzeptiert in C.
P: Philippsen schaut komisch
S: Erklaere, dass in C Wahrheitstests Integer Werte zurueck liefern, Ausdruck hat somit nicht das erwartete Verhalten.
P: Und in Python?
S: keine Ahnung (Richtig waere: Python kennt range-Compares, sie machen, was man erwartet)
P: Jetzt wollen wir unserer Sprache das beibringen, was muessen wir denn aendern?
S: Lexer nicht, Parser nicht, „Fehler“ erst bei Typpruefung. Saubere Loesung durch Besucher mit Baumtransformation
if(10 <= x < 101){
zu
int x2 = x; if((10 <= x2) && (x2 < 101)){
Neue Variable einfuehren um doppelte auswertung von x2 zu verhindern
Codebeispiel 2:
int func(String a){ switch (a){ case "asf": b(); case "name": c(); default: d(); } }
P: Was macht ein Compiler denn aus einem switch-case?
S: Sprungtabelle, If, Binaere Suche aus If.
P: Was muss erfuellt sein, damit der Compiler das erzeugen kann?
S: Int-Werte, Sprungtabelle nur bei nicht zu grossen switch-cases, binaere Suche nur fuer lose gefuellte cases
P: Was koennen wir denn nun bei Strings machen?
S: Binaere Suche/If geht immer, ansonsten Strings hashen und dann wie Int behandeln
Codebeispiel 3:
int func(int a, int b){ int c = a + b; return c; } func(3,7);
P: So jetzt malen sie bitte mal den Stack fuer dies codebeispiel hin
S:
_______________ | ARG2 7 | ARG1 3 | RETURNADDR | FRAMEPOINTER | VAR1 (c)
P: Fehlt da noch was?
S: naja, vl Register sichern, aber wir haben hier eine leaf-function, die eigentlich keine Register braucht
P: Wofuer brauchen wir den Framepointer?
S: Um beim ASM schreiben nicht bekloppt zu werden
S: Durch Stackframes hangeln um an umliegende Argumente zu kommen, Arrays auf Stack mit dynamischer Groesse
P: Was ist mit dem Returnwert?
S: Returnwert in eax bei allen x86 calling conventions, calling conventions allgemein erklaeren, stack cleanup, Rueckgabe auf stack
P: Warum liegen Argumente in umgekehrter Reihenfolge auf dem Stack?
S: Macht variabele Argumentanzahl bei printf() einfacher
P: Was ist mit Structs?
S: Pointer (keine details gewusst)
Faire Pruefung, etwas ungewohnt, dass sich Pruefer und Beisitzer abgewechselt haben mit dem Fragen stellen