Grundlagen des Übersetzerbaus 2022-02-21

• Prüfer: P (Philippsen)
• Beisitzer: B
• Student: S

Sehr entspannte Atmosphäre, auch wenn Prof. Philippsen ab und zu einen etwas strengeren Ton mit dem Beisitzer hatte (aber das ist ja nicht mein Problem). Die Fragen waren echt fair, bis auf ein paar Detailfragen wo man denk ich einfach Glück haben muss. Das Resultat war eine 1,3. Ich sollte anmerken, dass sowohl die Codeausschnitte, als auch die mündliche Rede meistens vermutlich nicht 1:1 dem tatsächlichen entspricht, aber semantisch sollte es aufs gleiche raus kommen :)

Eingestiegen sind wir mit der Frage nach den einzelnen Phasen und Unterphasen des Übersetzers. Zufriedenstellend war folgende Antwort:

• Analysephase
  • lexikalische analyse
  • syntaktische analyse
  • semantische analyse
• Abbildungsphase
  • Transformationen
  • Optimierungen
• Codierungsphase
  • Codeerzeugung
  • Assemblieren/Linken

B: Was genau tut der Lexer?

S: Lexikalische Analyse, d.h. anhand von regulären Ausdrücken einen Tokenstrom generieren

B: Wie kann man den debuggen, wenn man keinen Debugger zur Hand hat?

S: Die Implementierung des Lexers selber oder die Grammatik?

B: Beides

S: Ausdrücke schreiben, die Fehler hevorrufen und diese so minimal halten wie möglich um den Fehler zu identifizieren, man könnte…

P: das reicht schon

B: Wie könnte man die Codeerzeugung debuggen?

S: Wenn Zwischencode vorhanden ist kann man den serialisieren und bei Fehlerhafter Ausgabe Ein- und Ausgabe vergleichen. Wenn es keine Ausgabe gibt: selbe Vorgehensweise, Stück für Stück Eingabe verkleinern bis man den Fehler lokalisiert hat, dann kann man in der Erzeugung selber schauen warum genau die Eingabe zu einem Fehler führt.

B: sehr gut. Kann man die semantische Analyse weglassen?

S: Das kommt auf die Sprache an, an sich fehlt erstmal nur die semantische Fehlererkennung. Die meisten Sprachen verwenden aber zumindest primitive Typen oder Variablen die Deklerationen haben, da ist dann eine Übersetzung ohne Namensanalyse gar nicht mehr möglich. Hat man eine Objektorientierte Sprache oder auch nur Funktionsüberladungen muss die Typanalyse auch stattfinden, damit die Namensanalyse funktionieren kann..

B: Dann zeig uns doch mal wie die Namensanalyse bei dem Beispiel an den markierten Stellen aussehen würde:

func main() : int
   # Stelle 1
   f(h(), h(), g);
 end
 
 func f(a:int, b:int, x:int):int
   var x:int;
   if a == b then
     x := 3;
     # Stelle 2
     return x*a;  
   else
     x := 5;
     return 2*a + b * x;
 end
 
 func h() : int
     return 3;
 end
 
 var g:int;

Antwort: Stelle 1:

• Erste Schachtel: main, f, h, g
• Zweite Schachtel: (leer)

Stelle 2:

• Erste Schachtel: main, f, h, g
• Zweite Schachtel: a, b, x
• Dritte Schachtel: x

P: Sie haben bei der zweiten Stelle 3 Schachteln benutzt, könnte man nicht aucch 2 benutzen?

S: Nein, die Parameter müssen in eine eigene Schachtel, damit sie von lokalen Variablen im Funktionskörper überdeckt werden können.

P: Würde danach die Typanalyse statt finden?

S: In E2 ja, da die Typanalyse und Namensanalyse getrennt zu sehen sind

B: * Gibt Code mit Funktionsüberladungen der Funktion f * Hier immer noch?

S: Nein, hier muss für die Namensanalyse bekannt sein, welche Typen die Parameter von f haben um die Verwendungen zu unterscheiden. Hier muss also die Namens und Typanalyse miteinander verbunden werden.

B: * gibt e2 Code *

type p1: {a:int, b:int, c:int}
type p2: {a:int, b:int, c:int}
type p3: {a:int, b:int, c:p2}
 
var points : p3[50];
func main():int
    var i:int;
    i = 0;
    while i < 50 do
       points[i].c.b := i;
    end
end

B: Was sehen Sie hier und was muss gemacht werden, dass das übersetzt werden kann?

S: Da sieht für mich nach einer E2-Erweiterung um Records aus. Existiert damit Vererbung?

B: Nein, langweilige Records ohne Vererbung

S: Lexer um Token erweitern, Parser um Grammatikregeln, AST-Knoten und Typprüfung erweitern. Da ist es dann nicht mehr möglich Namens und Typanalyse zu trennen, weil für Namensanalyse der Typ eines Eintrags in points nötig ist um zu wissen was mit c gemeint ist. In der Codeerzeugung könnte man die Records als Speicherverbund auf dem Stack speichern.

B: ähhh ja, das war alles was ich fragen wollte

B: * gibt Javacode *

abstract class A<T>{
   public T f(T obj);
}
class B extends A<String>{
  public String f(String obj){
    return " " + obj;
  }
}

B: welche Besonderheiten sind hier wichtig?

S: Java benutzt Baumtransformationen um Generics für jede Benutzung zu instaziieren

P: wirklich?

S: Ah ne, das war C++, Java führt eine Type erasure durch und Ersetzt in A jede Verwendung von T durch Object.

B: Malen Sie das mal auf

S:

abstract class A{
   public Object f(Object obj);
}

B: perfekt. Und was passiert in B?

S: gar nichts

P: falsch, das würde zu einem Compilerfehler führen, sehen Sie warum?

S: Ah ja klar, dann würde B nichtmehr f implementieren weil sich die Methoden überladen…

P: Was passiert dann?

S: Ich kann Ihnen sagen was C++ tut, für Java weiß ich es nicht mehr

P: Schade

B: Welche Codeerzeugungsverfahren kennen Sie?

S: Sethi Ullman, Baumtransformationen, Graham & Glanville, Dynamische Programmierung

B: was tun die so warum arbeiten die so?

S: Sethi Ullman attributiert den Baum der Zwischensprache mit der Ershov Zahl und steigt immer in den Zweig mit den höchsten Registbedarf in einem zweiten Durchlauf ab um Code zu generieren, Baumtransformationen bilden Maschinenbefehle auf Transformationsregeln für Teilbäume mit Emittierung des Maschinencodes ab, Graham & Glanville arbeitet als LR Parser auf der Präfixnotation des Baums mit einer eigenen Grammatik und Dynamische Programmierung bestimmt Kostenfaktoren für einzelne Teilbäume und Befehle und kann somit ein Optimum nach einer Kostenmetrik finden.

B: warum gibt es verschiedene und sind die optimal?

S: optimal wäre Sethi Ullman, der arbeitet aber nur auf simplen RISC Befehlen (schreib ich währendessen auf), Graham & Glanville und Baumtransformationen sind allgemein nicht optimal, sie approximieren das Optimum mit der maximal munch Heuristik und arbeiten mit virtuellen Registern, es findet also keine Registervergabe statt, die liese sich durch Graphfärben danach durch führen. Dynamische Programmierung funktioniert auch auf CISC Instruktionssätzen und ist optimal bezüglich der Metrik.

P: Sind Sie sich sicher, dass Sethi Ullman immer optimal arbeitet?

S: Das haben Sie so gesagt in der Vorlesung :P

P: Richtig. Aber vllt hab ich davor noch etwas gesagt, bezüglich der Datenstruktur auf der sie arbeiten :P

S: Ah ja genau. Die arbeiten auf der Baum bzw. Waldpräsentation des DAG des Zwischencodes.

P: wie wird denn der Zwischencode in einen DAG gebracht?

B: * gibt Beispiel von E2-Code ich forme ihn in einen DAG *

B. * gibt Musterlösung des DAGs *

B: Wie wird der jetzt in einen Baum umgeformt?

S: Knoten mit Eingangsgrad > 1 werden als eigener Baum ausgelagert und durch Referenz im Ursprungsbaum ersetzt, Im Code wird das durch Load/Store Operationen umgesetzt. Diese Transformation kann die Optimalität beeinträchtigen.

B: betrifft das auch Dynamische Programmierung?

S: * überlege * ne die sollte mit Tiefen oder Breitensuche auch auf dem DAG arbeiten können.

P: wie erhalte ich denn den DAG?

S: Indem ich den Zwischencode anhand der Abhängigkeiten transformiere, wie ich das vorhin gezeigt hab

P: aber der kann ja dann bsp. bei einer Schleife eben schon zyklen enthalten

S: Oh da haben Sie aber Recht….

P: Arbeitet der Übersetzer denn hier wirklich auf dem KOMPLETTEN Zwischencode??

S: aso ne, er arbeitet auf Grundblöcken die keine Zyklen enthalten (da Code zwischen den einzelnen Sprüngen)

B: Was ist denn die Ershov Zahl?

S: Maß des Registerverbrauchs für Sethi Ullman, die Berechungsvorschrift gibt an, dass ein linkes Blatt 1 bekommt, ein rechtes 0, auf Grund der Form der Maschinenbefehle, ein innerer Knoten bekommt wenn die Kinder alle die gleiche Zahl haben, diese Zahl + 1, ansonsten das maximum der Kinderzahlen.

P: Warum +1 bei gleicher Zahl der Kinder?

S: Da dann beide Operanden in einem Register stehen. Das linke braucht n zur Berechnung, eins muss während der Berechnung von rechts das Ergebnis halten, rechts braucht auch n Register und daher werden insgesammt n+1 benötigt.

B: Dann malen Sie doch noch bei dem Beispiel die Ershov Zahlen auf

S: * male von unten nach oben die Zahlen hin und erkläre währendessen die Regeln nochmal *

P: Zeit um

Dass man danach gefragt wird wie man sich einschätzt find ich dann doch sehr gemein, aber das Resultat war ja super. Abzug hats hauptsächlich wegen dem Java Teil gegeben,