FSI Informatik/pruefungen/hauptstudium/ls2/ueb1-2015-03-31

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

 
<code java>
 	if(10 <= x < 101){
</code>
 
 	zu
 
<code java>
int x2 = x;  
if((10 <= x2) && (x2 < 101)){
</code>

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

_______________
| 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