Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Übersetzerbau 1   (Übersicht)

Übersetzerbau 1

  • „Grundlagen des Übersetzerbaus“ uebbau WS 2011 2012
  • „Übungen zu Grundlagen des Übersetzerbaus“
  • ~ 30 min.
  • Prüfung oder benoteter Leistungsnachweis zu Programmiersysteme (7,5 ECTS)

Prüfer: Prof. Dr. Michael Philippsen
Beisitz: Dipl.-Math. Jakob Krainz
Papier + Stift bereitgestellt
versch. Blätter mit Pseudo-Code für Prüfungsfragen vorhanden

Notation:

  • Ich verwende manchmal englische Wörter aus Bequemlichkeit.
  • Alles nur Pseudo-Code, also evtl. falsch !
  • „P:“ Frage/Erklärung vom „P“rüfer
  • „S:“ Antwort/Erklärung vom „S“tudent
  • „note:“ persönl. Hinweise, nicht aus Prüfungs-Gespräch

notes Organisatorisches

Sicherheitshalber immer klären, ob die richtige Vorlesung geprüft wird. ( Wurde hier auch gefragt. ) Fast alle Antworten der Prüfungs-Fragen unten sind hier klarer und systematischer als man das in mündl. Prüfung hinbekommt. Wenn man Pseudo-Code vorgelegt/hingeschrieben/diktiert bekommt und dann dazu Fragen beantworten soll:

  • einfach ruhig bleiben und nicht hetzen
  • erst mal richtig zuhören und nicht gleich Code scannen
  • dann kurz Übersicht verschaffen und sich auch Offensichtliches evtl. nochmal bewusst anschaun wie z.B.:
    • Funktions-/Variablen-Deklarationen
    • Typen
    • Sichtbarkeits-Modifier
    • Input-/Output-Params (wenn kein Param.-typ und -modifier, evtl. von call-by-ref ausgehen)
    • Return-value

Innere Klassen in Java

P: Gegeben: Blatt mit Pseudo-Code
Class „Outer“ „Inner“
Gesucht: Übersetzung durch javac

class Outer{
	public static int a;
	private static int b;

	public int i;
	private int j;

	class Inner {
		foo() {
			a++;
			b++;
			i++;
			j++;
		}
	}
}

S: Class „Outer“ „Outer$Inner“

class Outer {
	public static int a;
	private static int b;

	public int i;
	private int j;
	
	static int access$0() {
		return b; // getB() because var is private
	} 

	static int access$1(int b) {
		Outer.b = b; // setB() because var is private
	} 

	static int access$2(Outer o) {
		return o.j; // getJ() because var is private
	}

	static int access$3(Outer o, int j) {
		return o.j = i; // setJ() because var is private
	}

}

class Outer$Inner{
	Outer this$0; // needed e.g. for i++

	Outer$Inner(Outer outer) {
		this$0 = outer;
	}

	void foo() {
		Outer.a++; //"Outer." because public static

		// b++;
		Outer.access$1(Outer.access$0() + 1);

		this$0.i++; //"this$0" because public instance

		// j++;
		Outer.access$3(this$0, Outer.access$2(this$0) + 1);
	}
}

SV-Verweis

P: Sowas wie „this$0“ hatten wir schon mal, was denn?
S: SV-Verweis statischer Vorg.-Verweis für Sprachen mit Verschachtelten Func.-Decl. z.B. Pascal Pseudo-Code hingeschrieben und erklärt:

foo(){
	int i; // in stackFrameFoo1
	...
	bar(){
		int j = i;
		// Zugriff auf "int i" braucht SV-Verweis auf stackFrameFoo1
		// hat z.B. level 1
		...
	}
	zoo(){
		bar(); // => stackFrameBar2
	}
	bar(); // => stackFrameBar1
	zoo(); // => stackFrameZoo1
}
main(){
	foo(); // => stackFrameFoo1
}

2 Zeichnungen vereinfachter Stack (max. bis 0)

max.(oben)stackFrameFoo1 „int i“stackFrameBar1 SV0(unten)

SV-Verweis stackFrameBar1 zeigt auf Start von stackFrameFoo1
von kommt man an „int i“

max.(oben)stackFrameFoo1 „int i“ level 2stackFrameZoo1 SV level 3stackFrameBar2 SV level 30(unten)

nesting-level in Symbolen der Symbol-Tabelle (siehe Vorl. und auch Übungs-Compiler)
SV-Verweis stackFrameZoo1 zeigt auf Start von stackFrameFoo1
SV-Verweis stackFrameBar2 zeigt auf Start von stackFrameZoo1
hat gleiches nesting-level
⇒ übernimmt SV-Verweis von stackFrameZoo1

Stack-Frame

P: Stack-Frame Aufbau. S: Zeichnung vereinfachter Stack (max. bis 0) Erklärung: je nach Architektur, hier x86

|max.(oben)|...|params|RIP|old ebp-addr.|local vars|...|...|0(unten)|
                                        ^              ^
                                     new ebp          esp
                                     

Vollst. Antwort siehe:
ue1-07.pdf S.31 PPM stack-frame
stack-frame = Keller-rahmen ~ Methoden-schachtel ~ Prozedur-Rahmen ~ Activation Record

Compiler-Komponenten und deren Zusammenspiel am Bsp. assert

P: Ausgehend von Übungs-Compiler-Sprache,
neues Feature einbauen:

  • „assert expr;“
  • „assert expr: string;“

Erklären, was alles an Compiler anpassen um Feature zu unterstützen.

S: Wie ist das in Java nochmal, ist das ein „normales“ assert, das runtime-exception wirft, nicht sowas wie boost's „static_assert“ ?

P: ja, normales assert.

S: note: ich wollte extra „assert“-Statement in der Zwischen-Sprache einführen und es dann bei der Codierung in Assembler in „if(!expr) then throw …“ übersetzen. Von den Prüfern kam dann der Vorschlag, es evtl. gleich bei der semant. Analyse in ein if-Statement zu übersetzen, damit alle Optimierungen für if-Statements auch mitverwendet werden.

Analyse-Phase

  • lexer z.B. neues Keyword-Token
  • parser z.B. neue Grammatik-Regel
  • semant.Analysator/Visitors z.B.

Abbildungs-Phase

  • Transformationen
  • Optimierung

Codierungs-Phase

  • Code-Generierung

Bsp. einer Transformation/Optimierung, die die semantische Äquivalenz nur scheinbar erhält

Bsp. aus Orientierungs-Folien
http://www.informatik.studium.uni-erlangen.de/studierende/vertiefung.shtml
http://www2.informatik.uni-erlangen.de/teaching/orientierungsvorlesung.pdf S.3 bis 7

Programmoptimierung am Beispiel (Fortran)

  • (A) nicht-optimiert
subroutine tricky(a,b,n,m,k)
  integer n,m,k
  real a[m], b[m]
  
  do i=1,n
    a[i] = b[k]+a[i]+100000.0 //(1) runtime-errors possible here
  end do
  
  return
  • (B) optimiert

subroutine tricky(a,b,n,m,k)

  integer n,m,k
  real a[m], b[m]
  
  C = b[k]+100000.0 //(2) runtime-errors possible here
  do i=1,n
    a[i] = a[i]+C
  end do
  
  return

P: Die Funktion kennen sie evtl. noch. Diese Funktion hat 2 Arrays und überschreibt das eine Array in einer Schleife … Hier ist die optimierte Variante. Berechnung ist soweit die gleiche, Array wird in Schleife überschrieben … Ist das so OK oder gibts hier Probleme ?

S: note: hab glaub ich nur 2 entdeckt, die anderen wurden mir mit viel hints aus der Nase gezogen 4 Fehler (Details siehe Orientierungs-PDF)

  • 2 numerische:
    • Überlauf (Orientierungs-PDF S.4):
      • bei (A) „b[k]+a[i]“ ⇒ Auslöschung mögl.
      • bei (B) „b[k]+100000.0“ ⇒ overflow mögl.
    • Wertveränderung (Orientierungs-PDF S.5):
      • Reihenfolge geändert bei float/real ⇒ andere Rundung mögl.
      • (A) „b[k]+a[i]+100000.0“
      • (B) „a[i]+b[k]+100000.0“
  • 2 logische/mit anderen beobachtbaren Zuständen:
    • Speicherbereichsverletzung (Orientierungs-PDF S.6):
      • Bei (1) und (2) theoret. Overflow und indexOutOfBounds(b[k] ⇒ k) mögl. .
      • (1) wird aber nur ausgeführt, falls n>0, (2) wird IMMER ausgeführt.
    • Aliase/Teil-Aliase (Orientierungs-PDF S.7):
      • Falls a[] call-by-ref
      • und deref(a) = deref(b) (a & b zeigen auf/referenzieren gleiches Array)
      • ⇒ b wird auch in Schleife überschrieben
      • ⇒ bei i==k wird „b[k]“ mit evtl. neuen Wert überschrieben
      • ⇒ für alle i>k evtl. anderes „b[k]“

Bewertung/Note

Im Bereich 1.0 bis 3.0 Sehr zufrieden ^_^

Feedback

Wichtige Basics kamen teilweise etwas zu zögerlich. Gelerntes erklären und ausformulieren am besten mit Lernpartner vor der mündl. Prüfung üben. („aktives Wissen“)