Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » ueb1-2015-03-31

31.03.2015

  • Grundlagen des Übersetzerbaus (Doppelprotokoll, Prüfungen waren direkt nacheinander und sehr sehr ähnlich)
  • 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 Grammatiken

P: Woraus besteht ein Parser?

S: Generierte Tabelle + Stack, Operationen shift/reduce

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 skizzieren, 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. E-Parser weist es zurück, kurz erklärt wieso.

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 (da selbst drauf zu kommen war gefühlt ein Pluspunkt)

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? (Übersprungen in Prüfung 2)

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: (Prüfung 2) Nach ganz viel draufstumpen: Für dynamische Arrays (C99 war der entscheidende Tipp…)

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. Gab zwischendurch mehrfach Missverständnisse, die dann aber irgendwie aufgelöst wurden. Wenn erkannt wird, dass man das Thema drauf hat, wird auch frühzeitig abgebrochen und das nächste Thema angesprochen.