Beisitzer: Kreutzer

Prüfer: Philippsen

Prüfungsdauer: 30min

Ich konnte zu wenig erklären warum Strukturen und Algorithmen so verwendet werden wie in der VL vorgestellt.

Detailwissen hat das aber glücklicherweise etwas kompensiert. Bin insgesamt mit einer unerwarteten sehr guten Note raus.

Erster Teil der Prüfung anhand e2-Code mit Klassen, so ungefähr:

class Super
   var a : int;
   func foo (....)
end

class Sub extends Super
    var b: int;
    func foo (k: Sub)
       ....
       .... k.a ....
       .....
    end 
    
    func bar (....)
end

/ ********* /

O o = new O();
O u = new U();

Wie muss unser Compiler erweitert werden, um das abzubilden?

• Lexer um Token erweitern
• Grammatiken erweitern für Parser

Blatt mit Grammatik bekommen. Was muss konkret hinzugefügt werden?

• mögliche global_declarations um class_declaration erweitern
• Regeln für class_declarations: CLASS identifier [EXTENDS identifier]? [variable_declaration]* [function_declaration]* END
• CLASS hinzufügen
• …

Warum sind Lexer und Parser überhaupt getrennt?

• Reguläre Ausdrücke vs. kontextfreie Grammatik

Kann ein Lexer die Arbeit des Parsers übernehmen?

• Nein, reguläre Ausdrücke können zB die Verschachtelungen nicht (wichtig: es geht nicht, auch nicht mit irgendwie komische Erweiterungen - ich hab mich da in die Nesseln gesetzt)

Was muss noch getan werden?

• Klassen für neue AST-Knoten

Wie wird das dann im Speicher umgesetzt? Bitte graphisch darstellen.

• Objekte und Klassendeskriptoren malen - alle Einträge erklären können!
• Verzeigerung für TypeCasts mit Oberklassen - ginge etwas effizienter mit Displays (dann durfte ich Displays erklären und es wurde noch gefragt, wo die dann liegen → im Klassendeskriptor)
• V-Tables in den Deskriptoren für Methoden und darüber die Verzeigerung zur richtigen Implementierung (je nachdem, ob Funktionen überschrieben wurden)
• Instanzvariablen in den Objekten, bei Ober- und Unterklassen jeweils am selben Offset (WICHTIG: erklären warum man das so macht. Da bin ich gewaltig ins Schwimmen gekommen. Auf dynamische und statische Typen eingehen)

Gehen wir zur letzten Phase, was macht man da?

• Code-Generierung: Code-Selektion, Register-Vergabe, Instruktionsreihenfolgen

Warum ist Instruktionsreihenfolge wichtig?

• ILP
• Effizienz bei Pipelining und Datenkonflikten /-abhängigkeiten

Muss Datenabhängigkeiten geachtet werden?

• Wenn das bei der Anordnung nicht berücksichtigt wird, wird es im Zweifel ineffizient, weil die Pipeline nicht ausgenutzt werden kann, aber funktioniert trotzdem

Wie kann denn der IR zu Maschinenbefehlen transformiert werden?

• Sethi-Ullman, Graham & Glanville und Dynamische Programmierung

Wie funktioniert das mit dynamischer Programmierung? (habe ein Stück IR Code bekommen)

• erst DAG generieren (angefangen den hin zu malen und habe dann einen Ausdrucksbaum bekommen)

Der Baum sieht jetzt anders aus - wieso?

• DAG zu Baum transformieren durch das auftrennen gemeinsamer Teilausdrücke

Warum braucht man den Baum?

• was sie hören wollten: das Verfahren mit dynamischer Programmierung funktioniert nicht auf DAG.

Dann machen Sie mal das Verfahren

• angefangen die Kosten der Blätter zu annotieren
• erklärt wie es bei den inneren Knoten funktioniert

Warum reichen denn 2 Register bei dem Befehl r ← r op r?

• Ergebnis kommt ins selbe Register wie erster Operand

Zeit ist rum.