Ü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

• 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

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

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;
	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 access$0{..} // getB() because var is private
	static access$1{..} // setB() because var is private
	access$2{..} // getJ() because var is private
	access$3{..} // setJ() because var is private
	foo(){
		// ?? I think "Outer." could be omitted here
		Outer.a++; //"Outer." because public static
		// b++;
		int temp = Outer.getB();
		Outer.setB( temp+1 );

		this$0.i++; //"this$0" because public instance
		// j++;
		int temp = getJ();
		setJ( temp+1 );
	}
}
class Outer$Inner{
	Outer this$0; // needed e.g. for i++
	Outer$Inner( Outer outer ){
		this$0 = outer;
	}
	foo(){...}
}

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)

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

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

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

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.

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

• Transformationen
• Optimierung

• Code-Generierung
• …

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]“

Im Bereich 1.0 bis 3.0 Sehr zufrieden

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“)