====== Compilerbau 1 Prüfung 2024-02-29 ======
{{indexmenu>:pruefungen:hauptstudium:ls4:ueb1-2024_02_29-0#1|navbar}}
===== Allgemein=====
* (B)eisitzer: Tobias Heineken
* (P)rüfer: Prof. Philippsen
* Vorbereitung: Ich bin alle Vorlesungen (außer die über Mehrfachvererbung und Interfaces) nochmal durchgegangen und habe die dazugehörigen Übungen gemacht. Weil das in den Braindumps immer gesagt wurde, habe ich versucht die ganzen [[https://gitea.marco-ammon.de/Marco/UE1-Verfahren|Verfahren]] nochmal selber zu machen.
* Prüfungsatmosphäre: P und B saßen schräg links und rechts von mir. Die Atmosphäre war locker und die Zeit ist echt schnell rumgegangen. B hat immer sehr schnell nachgehakt wenn ich eine unklare Antwort gegeben hab. Das fand ich gut, weil die Prüfung dadurch mehr den Charakter eines Gesprächs/Diskussion hatte. B hat auch die ganze Zeit neue Blätter aus einem Umschlag geholt. Am Ende lagen bestimmt 10 Blätter vor mir.
* Die Benotung war sehr nett.
* Alle Angaben und Antworten sind sinngemäß.
===== Prüfung=====
==== Einstieg ====
B: *gibt Blatt mit e2-Codestück*
func main(): int
return foo(1, 2);
end
var g: int;
func foo(int a, int b): int
var i: int;
while i < b do
g = a * b + (a + b); # Variablen stimmen sicher nicht aber Form war so
i = i + 1;
end
return g;
end
B: Was macht denn der Compiler damit?
==== Analyse ====
A: Als erstes kommt die lexikalische Analyse, da wird die Zeichenfolge in Token umgewandelt
A: Danach kommt die syntaktische Analyse da wertet der Parser die Tokenfolge aus und bringt Struktur in das Programm
B: Was heißt denn Struktur?
A: AST *zeichnet Teile vom AST für Codeausschnitt hin*
B: Was kommt danach?
A: Die semantische Analyse mit der Namens- und Typanalyse
B: Was macht die Namensanalyse?
A: Ordnet die Bezeichner ihren Deklarationen zu
B: Wie funktioniert das?
A: Mit Sichtbarkeitsschachteln *Malt Sichtbarkeitsschachteln für main*
B: Was macht die Typanalyse?
A: Schaut ob das Programm typkonsistent ist, d.h. keine Typinvariante wird gebrochen. Das kann zur Übersetzungs- oder Laufzeit passieren.
B: Was ist bei e2 schlauer und warum?
A: Übersetzungszeit, weil wir alles was wir für die Typprüfung brauchen schon bei der Übersetzung wissen
B: Zeig die Typanalyse mal am Code.
A: Z.B. müssen die Parametertypen von foo zu den Argumenttypen des Funktionsaufrufes passen. Das wäre eine Typinvariante.
B: Beim e2-Compiler kommt zwischen Namens- und Typanalyse ja noch etwas anderes.
A: Ja, die Konstantenfaltung
B: Warum ist die denn wichtig?
A: Besonders für die Array-Deklaration, weil wir ja Konstanten brauchen, um die Größe des Arrays anzugeben.
==== Abbildung ====
B: Was kommt nach der Analyse?
A: Die Abbildungsphase mit Transformation und Optimierung
B: Was muss man bei der Transformation beachten?
A: Also bei Baumtransformationen wird ja ein Teil des AST durch einen anderen Teil ersetzt, z.B. für von syntaktischen Zucker.
B: Denk mal an die Namensanalyse. Was könnte jetzt wichtig werden?
A: Die neuen AST-Knoten haben jetzt ja nicht mehr die Informationen, die wir ihnen bei Namensanalyse gegeben haben. Deshalb muss nachattributiert werden.
B: Was kommt jetzt?
A: Jetzt wird in Zwischencode übersetzt.
B: Warum?
A: Für spätere Optimierung und überbrücken der semantischen Lücke zwischen Quell- und Zielsprache.
B: Was wäre denn aus Zwischencodeübersetzungssicht an dem Codeausschnitt interessant?
A: Die while-Schleife
B: Warum?
A: Weil wir die auf Sprünge abbilden müssen. *Malt*
jlt a, b, True
jmp False
True:
jlt a, b, True
False:
A: Wir können die Bedingung in den Kopf oder ans Ende schreiben. So ist es besser.
P: Warum ist das besser?
A: Wenn die Bedingung nur am Anfang stehen würde, müssten wir nach jedem Schleifendurchlauf wieder hochspringen und dann in den Block springen. Das wären dann zwei Sprünge pro Iteration.
B: Die erste Zeile in der while-Schleife ist auch interessant, warum?
A: Die Zwischencodeoperationen nehmen nur zwei Operanden. Deshalb müssen wir virtuelle Register nutzen, um die lange arithmetische Operation auszuwerten.
==== Codierung ====
B: Was kommt denn nach der Abbildungsphase?
A: Die Codierung mit der Codererzeugung mit der Codeselektion, Registervergabe und Instruktionsanordnung
B: Was macht denn die Codererzeugung?
A: Sucht für die Operationen des Zwischencodes entsprechende Operationen der Zielsprache raus. Es gibt Operationen der Zielsprache die besser passen und z.B. mehrere Operationen des Zwischencodes abbilden. Da kann man was die Performance des Programms rausholen
B: Mmh.
P: Passt schon.
B: Bei Zwischencodeoperationen geben wir ja immer eine neue Variable als Ziel an. Wie wäre das denn bei Zweiadresscode?
A: Da ist das Zielregister auch das erste Quellregister.
B: Welche Verfahren zur Codererzeugung kennen Sie denn?
A: getreg, Sethi-Ullman, Dynamische Programmierung, Baumtransformationen, Graham & Glanville
B: *Holt Blatt mit Operationen raus* Wie geht denn Graham-Glanville damit um?
L ri := Mx
S Mx := ri
C ri := c // bin mir nicht mehr ganz sicher damit
RoR ri := ri o rj
RoM ri := ri o rj
A: Erstmal werden die Produktionen aufgestellt *Malt hin*
ri -> Mx
Mx -> ri // Achtung falsch!
B: Warum passt es hier nicht?
A: Keine Ahnung
B: Wie würde es denn jetzt weitergehen?
A: Mit der Präfixnotation.
B: Hä, Präfixnotation??
A: Also erstmal stellen wir denn Abhängigkeitsgraphen für den Code auf. Danach schreiben wir die Präfixnotation. Diese werten wir mit einem LR-Parser aus.
B: Also was ist dann das Problem mit den beiden Produktionen?
A: (Jetzt dämmert es mir) Wir laufen in eine Endlosscheife, weil wir eine Speicherstelle mit einem Register ersetzen können und umgekehrt.
B: *Gibt Blatt mit Produktionen*
ri -> Mx
S -> := Mx ri
ri -> c
ri -> o ri rj
ri -> o ri rj
B: *Gibt Blatt mit neuen Operationen und Maschinencodedarstellung* Schreibe dafür bitte auch die Produktionen.
LEA ri := rj + rl lea (rj rl) ri // Bin mir beidem gar nicht mehr sicher
MULROM ri := rdx * Mx mulrom MEMORY rdx ri // Der Befehl hieß sicher anders aber das rdx ist auf jeden Fall vorgekommen
A: *Malt*
ri -> + rj rl
ri -> * rdx Mx
B: *Gibt IR-Code für Schleifeninhalt* Dann mach mal das Verfahren weiter
%v0 = MUL a$0 b$0;
%v1 = ADD a$0 b$0;
%v3 = ADD %v1 %v2;
g$0 = MOV %v3;
%v4 = ADD i$0 $1;
i$0 = MOV %v4;
A: *Malt Abhängigkeitsbaum für die ersten 4 Zeilen*
A: Nur die Wurzel darf Seiteneffekte haben. Deshalb müssten wir für die nächsten 2 Zeilen einen neuen Baum ausftellen.
:=
/ \
g +(v3)
/ \
(v0)* +(v1)
/ \ / \
a b a b
A: Jetzt wird der Baum in Präfixnotation hingeschrieben
P: Attacke!
:= g + * a b + a b
A: Das werten wir jetzt mit einem LR-Parser und den Produktionen aus
A: *Geht Ausdruck zeichenweise durch und sagt ob shift oder reduce angewendet werden muss*
B: *Stoppt bei der ersten Multiplikation* Ok, welche Instruktion würden Sie jetzt für die Multiplikation wählen? (Es gibt ja RoM, RoR und MULROM)
A: Also RoR würde ich nicht nehmen, weil die eine Instruktion mehr braucht, um den Operanden in ein Register zu laden?
B: Ok, und welche von den anderen beiden?
A: (keine Ahnung) Die erste Instruktion
B: Passt *Gibt neues Blatt mit fertigem Maschinencode mit zwei paar Lücken (einmal da wo die Multiplikation reinkommt)*
B: Was würden wir jetzt in die Lücke schreiben wenn wir MULROM nehmen
A: *schreibt* ''mulrom Mb, r1, r1''
B: Was ist jetzt mit dem rdx?
A: Ah ja da fehlt ''mov rdx r1'' davor
P: Zeit ist rum