PRÜFUNGSPROTOKOLL

Fach: Grundlagen des Übersetzerbaus (= Übersetzerbau 1)
Prüfer: Prof. Dr. Philippsen
Beisitzer: M. Sc. Marius Kamp
Datum: März 2016

P = Prüfer, B = Beisiter, S=Student.

Vor der Prüfung bin ich intensiv die Folien durchgegangen und habe während der Prüfung davon profitiert. Vom Übungsbetrieb hab ich recht wenig gemacht. Wenn es umgekehrt gewesen wäre, dass ich intensiv den Compiler gebaut hätte, ohne zu wissen, was in den Folien steht, wäre die Prüfung viel schwieriger gewesen.

(Ich bekomme einen Codeschnipsel vorgelegt) P: Was macht denn ein Compiler damit?
S: Also erst mal kommt die lexikalische Analyse - der Lexer. Der wirft die ganzen Kommentare raus, einzeilige wie mehrzeilige. Sonst bräuchte ich in der Grammatik vom Parser noch Regeln für die Kommentare und das würde nur nerven. Leerzeichen, Tabulatoren und Zeilenumbrüche macht er auch noch raus. Der Lexer verwandelt die Eingabe in Token, die der Parser später dann einliest. Der Lexer baut auch noch die Namenstabelle auf.

B: In welche Tokenfolge verwandelt er denn diesen Codeschnipsel?
(Ich bekomme eine ganz normale Methode vorgelegt, sowas wie
int foo (int x) { … )
S: TKINT, TKID, TK(, TKINT, TKID
P: Ja danke, das reicht uns schon. Was passiert denn danach?
S: (es ist wichtig immer schnell zu antworten und wenn es nur eine Rückfrage ist) Danach im Codebeispiel oder danach im Compiler?
P: Danach im Compiler, nach der lexikalischen Analyse.
S: Danach kommt der Parser.

P: Wie funktioniert denn so ein Parser?
S: Der liest die Tokenfolge ein, die der Lexer erstellt hat. Wir haben in der Vorlesung den LR-Parser besprochen. Der heißt so, weil er von links nach rechts durchgeht. Dabe hatte der einen lookahead von 1, schaut also immer ein Zeichen voraus. Der Parser hat einen Stack und shiftet sich die Token auf den Stack. Dazu hat er noch eine Grammatik. Wenn er eine Regel der Grammatik auf etwas auf dem Stack anwenden kann, macht er reduce. So geht er die ganze Eingabe durch. Wenn alles gepasst hat, kann er alles auf program reduzieren.

P:Und macht der sonst noch irgendwas?
S: Wie? Ach ja genau, der Parser baut auch noch den Baum auf.
P: Wie bzw wann baut er den denn auf? Davor? Danach? Dazwischen?
S: Immer dann, wenn er reduce anwendet, baut er parallel dazu den Baum auf(noch genauer erklärt).
B: Male uns doch mal den Syntaxbaum zu diesem Code:
if ( (x >0) && (y <0) ){ z=1; }

S:      IF
        /    \
  condition   block
     /           \
 AND         ASSIGN
 /   \
>    <

B: Ja danke, das reicht uns schon.

B: Wenn der Parser dann den Baum gemacht hat, ist der dann fertig oder passiert noch was mit dem Baum?
S: Es kommen noch die Typprüfung und die Prüfung der Bezeichner, ob die denn auch alle deklariert wurden beziehungsweise hier gültig sind. Bei der Typprüfung verwendet man Prototypen. Die werden von links nach rechts durchgereicht. Prototypen sind toll, denn wenn es einen Methodenaufruf gibt, kann ich damit alle Argumente prüfen ob sie denn den richtigen Typ haben. Wenn nicht kann ich genau sagen „Argument Nummer soundso müsste laut Prototyp diesen Typ haben, hat aber jenen“. Ohne Prototypen gäbe es eine weit weniger hilfreiche Fehlermeldung wie „irgendwas an den Argumenten ist falsch“.
P: Diese Typprüfung und diese Deklarationsprüfung - in welcher Reihenfolge finden die denn statt?
S: Erst Typen, dann Deklarationen (Achtung, das ist falsch).
P: Wie machen Sie denn da die Typprüfung? (zeigt im Programm auf „int z=1;“)
S: Ich schaue halt nach welchen Typ z - dann prüfe ich ob das mit der 1 verträglich ist.
P: Woher wissen Sie denn welchen Typ z hat? Wo schauen sie das denn nach?
S: AHHH, dann hab ich s falsch gesagt, Stimmt. Ich muss ERST die Deklarationsprüfung machen, damit ich dann in der Typprüfung immer den Typ nach schlagen kann. (dann alles noch genauer erklärt)

B: Gut. Wir wollen in den Übungscompiler jetzt noch was neues einbauen. Ein switch-case. Wir machen ein vereinfachtes switch-case. Man fällt NICHT von einem case in den nächsten und braucht kein break. (wenn ich mich richtig erinnere gab es auch kein default) (ich bekomme einen Zettel mit ungefähr folgendem Schnipsel)

int foo(int x, int y){
switch(x){
case 1: return 0;
case 2: return 1;
case 3: return 2;
case 42: return x;
}
}

B: Was müssen wir denn jetzt am Compiler anpassen?
S: Also erst mal braucht der Lexer neue Token. ein TKSWITCH, ein TKCASE, wir brauchen noch ein Doppelpunkt-Token, ich weiß nicht ob das schon drin ist.
P: Wenn wir noch keins haben machen wir halt eins rein. OK. Wie gehts weiter?
S: Dann muss man noch die Grammatik vom Parser anpassen, damit der das auch versteht. (dann irgendwelches Zeugs erzählt, aus ihren Gesichtern hab ich gelesen, dass sie noch auf was bestimmtes warten. Dann hab ich irgendwann gesagt: )
Das switch-case reduziert dann in der Grammatik auf eine Anweisung.
P: JAAA, genau!
P: Gut wir haben Lexer und Parser umgestellt - muss sonst noch irgendwas angepasst werden?
S: (Richtig wäre gewesen, dass man jetzt noch Klassen erzeugen muss, damit es im Baum überhaupt so ein switch-case geben kann. Und das muss dann in den Interfaces eingetragen werden - also das was man im Übungsbetrieb dauernd macht. Obwohl es eine einfache Frage ist, stand ich da auf dem Schlauch.)
B: Was machen wir denn jetzt damit?
S: (immer schnell antworten) Naja, man baut es halt ein. Ich verstehe nicht,was gemeint ist?
B: Wie könnte der Übungscompiler damit umgehen?
S: Ach so, ja ich könnte es auf etwas abbilden, was der schon kann. Da es nur wenige case-Anweisungen sind, könnte man das mit ner if-Kaskade machen. (weiß nicht mehr wie es genau weiter ging, irgendwann habe ich dann den table-switch erklärt.)
S: Also es gibt da den table-switch. Den nimmt man, wenn die Selektoren in den case-Anweisungen alle schon der Reihe nach durchgehen, also case10, case11, case 12, case 13 . Dann macht man sich eine Tabelle, in die ich immer das Sprungziel eintrage. Wenn dann zur Laufzeit ein x rein kommt, prüfe ich erst ob es kleiner ist als der kleinste Selektor oder größer ist als der größte Selektor, wenn ja springe ich default an. Wenn nicht ziehe ich den kleinsten Selektor ab und das Ergebnis ist dann der Index in meine Tabelle. Wenn also eine 10 rein kommt ziehe ich 10 hab und bekomme 0, ich schlage in der Tabelle also an der ersten Stelle nach. Wenn eine 12 rein kommt ziehe ich 10 ab und bekomme 2, schlage also am Index 2 in der Tabelle nach. Wenn meine Selektoren wenige Lücken haben, kann ich dort in der Tabelle immer das default-Sprungziel eintragen.

P: Könnte man auch so was machen wie „case y: return 0;“ ?
S: (Nein das geht nicht. Stellt euch mal vor ihr NUR sowas wie case x, casey, case z, dann könntet ihr auch ja nicht mal für ein Verfahren entscheiden, wie ihr das switch-case intern abbilden könnt. Ich bin dann etwas rum geeiert, und eigentilch bin ich sogar drauf gekommen, als ich gesagt habe, dass ich das ja gar nicht sortieren kann. Wenn ich also case 20, case 1, case 8, case y habe und ich will die sortieren weiß ich ja gar nicht wo ich das y einsortieren soll. Aber darauf hat Philippsen dann reagiert mit:)
P: HALT HALT HALT!! Jetzt werfen Sie ja alles durcheinander! (sagt er total vorwurfsvoll)
Das mit dem Sortieren, das war doch was andres…
S: Stimmt, das war der lookup-switch.
P: Genau - wie funktioniert denn der?
S: Den verwende ich, wenn ich große Lücken habe. Wenn ich das mit table-switch machen würde hätte ich sonst eine Tabelle, in der fast überall default drin steht. Also nehme ich dann den lookup-switch. Da baue ich mir erst mal solche Zweiertupel aus match(=die case-Selektoren) und offset. Dann sortiere ich die nach match. Wenn dann zur Laufzeit ein x rein kommt gehe ich die durch und schaue wo es matcht. In den Folien habe wir alle in O(n) abgeklappert, aber weil ich ja sortiert habe kann ich da was optimieren mit ner binären Suche. Dann schaue ich, ob ich etwas finde. Wenn nicht springe ich default an. Wenn doch, lese ich aus dem Zweiertupel den Offset. Das ist der Wert den ich je nach Vorzeichen auf den PC addieren oder subtrahieren muss, um an die richtige Stelle zu kommen und dann mache ich es und gehe dahin.
P: Genau so funktioniert er.

(Dann sind wir immer und immer wieder drauf gekommen, ob man denn „case y:“ machen kann. Ich bin dann nicht mehr drauf gekommen. Einmal hatte ich es ja schon gesagt, als P mich dann so unterbrochen hatte. Dadurch bin ich dann nicht mehr drauf gekommen, weil ich dachte dass das falsch ist.)

B: Zu welchem Codegenerierungsverfahren passt denn dieser Zettel?
S: (immer schnell antworten) Was soll ich damit jetzt machen?
P (lacht): Also, wenn Marius Ihnen so einen Zettel reicht, dann gibt es da ein ganz bestimmtes Code-Generierungsverfahren, das er da im Sinn hat. Welches könnte das denn sein? Wir haben da ja verschiedene kennen gelernt.
(ich kann mich jetzt an den Zettel nicht mehr erinnern, ich verwende mal den aus den Folien):
reg → const MOV #c, R
reg → mem MOV a, R
mem → := mem reg MOV R, a
(die genauen Regeln sind eh egal es geht nur ums Prinzip)
S: (ich wusste es gleich, nur der Name wollte mir nicht sofort einfallen. Immer schnell antworten:) Also AST-Transformation ist es schon mal nicht, denn ich sehe ja keine Regeln für den AST.
P: (lacht) Genau, das ist schon mal weg. Was bleibt also noch?
S: Jetzt bleiben ja nur noch zwei. Dynamisches Programmieren sieht auch anders aus. Bleibt also nur noch Graham-Glanville. STIMMT, es sieht TOTAL nach Graham-Glanville aus! (beide müssen lachen, denn jetzt wo nur noch GG übrig ist, sieht es für mich plötzlich „total“ danach aus.)
P: (lacht) Ja was sieht denn da so sehr danach aus?
S: Diese Regeln (ich zeige auf die linke Hälfte).
P: Also gut. Wie funktioniert das jetzt? Wie funktioniert GG?
S: Aus den vorherigen Stufen des Compilers habe ich diesen Baum, den muss ich jetzt erst mal in preorder ausgeben, damit alles in einer Zeile steht.
B: Machen Sie das doch mal bitte für a+b*c, erst den Baum, dann preorder.
S:

       +
     /    \
   a       *
          /   \
          b   c
          

B: Genau und jetzt?
S: Das wird zu +a*bc
B: Und jetzt?
S: (Erklärt, dass es da halt einen Stack gibt, und man da shift / reduce machen kann. Entsprechend diesen Regeln die da stehen. Immer wenn ich reduce mache gebe ich den zu dieser Regel gehörenden Assemblercode aus. Dann hatten wir noch kurz, ob er denn die gesamte Eingabe kennt oder nur eine begrenzte Vorrausschau und ich habe kurz überlegt und gesagt, dass es wohl nur eine begrenzte Vorausschau hat. ) (irgendwann kam dann noch folgende Frage, ich weiß nicht mehr wie wir drauf gekommen sind:)
P: Was Sie da angesprochen haben sind ja reduce-reduce-Konflikte. Warum gibt es die denn überhaupt?
S: (kurz überlegt) Weil die Grammatik mehrdeutig ist.
P: Was gibt es denn noch für Konflikte?
S: shift-reduce.
P: Was passiert da?
S: Man bevorzugt wenn möglich immer größere Regeln. Deswegen shiftet man unter Umstände viel - wenn Hoffnung auf etwas größeres besteht.
B: Warum bevorzugt man größere Regeln?
S: Damit der Code effizienter wird. Ich ziele damit zum Beispiel auf diese komplexen Adressierungsbefehle für Arrays, die ja viel schneller sind als die einfachen Adressierungsbefehle.

P: Dieses GG-Verfahren arbeitet das jetzt eigentlich auf virtuellen oder realen Registern?
S: Man nimmt zur Vereinfachung unendliche viele Register an. Es arbeitet also auf virtuellen Registern. Später kommt noch eine Zuteilungsphase, die das ganze auf reale Register abbildet.
P: Gut. Gibt es noch irgendwelche Phasen?
S: Man kann dann noch unabhängige Instruktionen umsortieren, damit die Pipeline besser läuft.

P: Gut. Bleiben wir bei den Registern. Wie funktioniert das mit der Registerzuteilung genau?
S:Ich schaue mir das Programm an und analysiere die Lebensspannen. Etwas ist lebendig, wenn ich einen Wert habe, den ich später noch mal brauche. Dann muss der erhalten bleiben und darf nicht überschrieben werden. Dann schaue ich, wie sich die Lebensspannen alle überlagern und fertige so einen Graphen an.
P: Haben Lebensspannen Löcher?
S: Ein virtuelles Register kann mehrere Lebensspannen haben, dazwischen entstehen dann Löcher.
P: Das war keine Antwort auf meine Frage.
S: Nein eine Lebensspanne hat keine Löcher. Die fängt irgendwo an und hört irgendwo auf und das wars.
P: Was ist denn so ein Knoten in dem Graph?
S: Ein Knoten ist eine Lebensspanne. Dann gibt es da noch Kanten. Die gehen zu anderen Lebensspannen, die zur gleichen Zeit lebendig sind. Lebensspannen die durch eine Kante verbunden sind dürfen nicht ins gleiche Register. Es gibt noch eine andere Sorte von Kanten - Move-Kanten. Das sind Kopieroperationen und wenn ich diese im selben realen Register abbilde, fällt die Kopieroperation weg. Ich versuche dann immer Knoten entlang diesen move-Kanten zu verschmelzen.
P: Dieses Verschmelzen - mache ich das die ganze Zeit oder nur am Anfang?
S: (Habe gesagt, dass ich das Beispiel in den Folien so in Erinnung habe, dass wir die ganze Zeit verschmolzen haben. Das war auch richtig. Ich hatte aber noch nie so explizit drüber nach gedacht und bin dann ins Schlingern geraten. )
P: Und wie teile ich jetzt die realen Register zu?
S: Da gibt es diese Grad-kleiner-R-Regel (anschließend hab ich die erklärt, das steht ja gut in den Folien drin, brauch ich hier nicht noch mal aufschreiben)
[…] P: Wo kommen diese Knoten hin die Sie da entfernen?
S: In den Keller.
[…]
P: Klappt das denn immer mit dieser Regel?
S:(hab das Beispiel aus den Folien erklärt, mit den vier Knoten die als Viereck angeordnet sind und mit R=2 geht das nicht)
P: (will die Sache beschleunigen) Gut, gut was mach ich also?
S:Ich lege trotzdem einen Knoten in den Keller und markiere ihn als Spill-Knoten. Später sehe ich dann dass ich den doch färben kann und freue mich.
P: Dieser Spill-Knoten - kommt der in den gleichen Keller oder in einen anderen?
S: Der kommt in den gleichen Keller,wird aber als Spill-Knoten markiert.
P: Und wenn ich so einen Spill-Knoten dann habe und beim Färben stelle ich fest, dass ich den tatsächlich nicht färben kann - was dann?
S: Dann lagere ich den Inhalt in den Hauptspeicher aus. Bei jedem Zugriff muss man dann den Wert aus dem Hauptspeicher laden und das ist teuer. Man kann ja aber noch was optimieren indem man die Lebensspanne aufteilt.
P: Wie macht man das denn?
S: (Das wusste ich zwar aber ich konnte es nicht so recht erklären. Schlagt besser in den Folien nach, denn darauf wurde zum Schluss dann noch herum geritten).