====== Ü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 SV|...|0(unten)| \\ SV-Verweis stackFrameBar1 zeigt auf Start von stackFrameFoo1 \\ von kommt man an "int i" |max.(oben)|...|stackFrameFoo1 "int i" level 2|...|stackFrameZoo1 SV level 3|stackFrameBar2 SV level 3|...|0(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")