Übersetzerbau 1 vom 2024-02-29

• Prüfer: Prof. Philippsen
• Beisitzer: Florian Meyer
• Note: 1.0

Wir saßen im Büro an einem Tisch, links von mir Prof. Philippsen, rechts Florian. Prof. Philippsen hatte den Protokollzettel, Florian einen Ordner wo die Beispielblätter rausgenommen wurden. Beide haben je nach Thema auch abwechselnd Fragen gestellt.

Anfang hat etwas gehapert bis ich drauf gekommen bin, was die beiden jetzt genau haben wollen. Zwischendrin auch noch ein kurzer Hänger, ist Prof. Philippsen am Ende aber auch nicht extra drauf eingegangen. War auch generell sehr flott unterwegs, deswegen relativ viele Themen.

• Vorlesung und Präsenzübung besucht
• Projektübung gemacht (bzw vom Übungspartner machen lassen)
• Vor Klausur Folien nochmal durchgelesen
• Übungen nochmal durchgemacht und auf Papier gemalt

• (F)rage
• (A)ntwort

Codebeispiel ähnlich zu:

func main(): int
    var s: int;
    var a: int[10][20][30];

    ...

    foreach (x in a) do
        if x > 10 then
            return -1;
        end
    end

    return 0;
end

F: Wir wollen jetzt foreach in e2 übersetzen können, was müssen wir anpassen?

A: Im Lexer Token hinzufügen, Parser um die Produktionsregel für AST erweitern.

F: Welches Token im Lexer kommt denn dazu?

A: Naja, foreach halt.

F: Nur foreach?

A: Ah, in kommt noch dazu!

F: Wo im Lexer würden wir das foreach dann einbauen?

A: Als Alternative zu statement und dann…

F: …jaja und dann Klammer etc, was können wir dann auf der Abbildungsphase machen?

A: Code-Generierung müssen wir anpassen.

(hier war ich bisschen lost, am Ende gabs nen Tipp: Baum)

A: Ah, man das als Syntaxzucker transformieren und mit einer while abbilden.

F: Eine Schleife?

A: Ja?

F: Sicher, dass eine Schleife funktioniert?

A: Ne geht nicht direkt weil auch für mehrdimensionale Arrays, dann müssten wir entweder eine Schleife pro Dimension oder mittels flattening.

F: Falls wir das flatten wollen, wie berechnet man dann den 1-dimensionalen Index?

A: index_0 * length_1 * length_2 + index_1 * length_2 + index_3

F: Okay, scheinen Sie verstanden zu haben, dann gehen wir mal weiter

Codebeispiel ähnlich zu:

func foo(a: int): int
    func bar(b: int): int
        func bazz(c: int): int
            return c;
        end
        return bazz(b);
    end

    func quxx(d: int): int
        return bar(d);
    end

    return quxx(a);
end

F: Hier haben wir jetzt genestete Funktionen, was muss man da beachten?

A: Jeweils auch Kontext der textuell umschließenden Funktion sichtbar, realisiert wird das über einen SV-Verweis (statischer Vorgänger) im Aktivierungsrahmen.

F: Muss das zwingend im Stack-Frame stehen, oder geht das auch anders?

A: Displays, globales statisch allokiertes Array pro Modul. Je nach Verschachtelungstiefe steht dann dort der SV drin.

F: Und damit sparen wir uns dann Speicher, richtig?

A: Nein, Speicher gespart wird nicht, ist nur schneller.

F: Wieso wird kein Speicher eingespart? Dann müssen wir ja den SV-Verweis im Rahmen nicht mehr mitziehen.

A: Weil ein Eintrag im Display einen prev-Zeiger Eintrag auf den davor enthaltenen SV braucht, also sparen wir im Endeffekt keinen Speicher.

F: Und wieso machen wir das dann?

A: Weil nachschlagen schneller ist. Dann muss man die SV-Verkettung nicht ablaufen, sondern kann in O(1) im Display nachschauen.

F: Müssen wir noch was an der Namensanalyse ändern?

(Kurze Nachdenk- und Brabbelpause)

A: Muss jetzt auch wie bei Variablen mit Scopes passieren.

A: Sie haben vorhin was zu Aktivierungsrahmen gesagt, was ist denn hier besonders? Man bemerke, dass hier keine Rekursion stattfindet.

Codebeispiel ähnlich zu:

func foo(a: int): int
    return a * 4;
end

func bar(b: int): int
    return foo(10) + b;
end

func main(): int
    return bar(2);
end

A: Wenn wir Rekursion strikt ausschließen können, dann kann man den Aktivierungsrahmen einer Funktion auch statisch allokieren, liegt dann global.

F: Und wenn wir die Funktion jetzt aber mehrfach aufrufen wollen?

A: Geht dann ohne Probleme, Hauptsache sie ist nur ein mal gleichzeitig im Callstack aktiv.

F: Wie würde das dann mit Rekursion aussehen?

Callstack hingemalt und erklärt, Base-Pointer trennt Caller und Callee Seite. Je nach ABI werden Register gesichert, Rücksprungadresse hingelegt und Parameter sowie Platz für Ergebnis bereitgestellt.

F: Gut, Sie haben ja hier einen Base-Pointer, brauchen wir den?

A: Nicht unbedingt, kann man auch alles über den Stack-Pointer machen, vereinfacht uns aber so Zeug wie Arrays mit variabler Länger.

F: Was vereinfacht uns ein Base-Pointer noch?

A: Debugging.

F: Gutes Stichwort, wie macht man das denn? Im Spezifischen, wie setzt man Breakpoints?

A: Erstmal mit ptrace als Debugger melden. Breakpoints entweder mit Debug-Registern oder durch Einfügen von trap-Instruktion (zB 0xCC).

F: Bitte spezifischer, was macht der Debugger, was das Betriebssystem und was das zu debuggende Programm?

A: Debugger ptrace an Betriebssystem, dass wir zu debuggende Programm einsehen wollen. Sagen Betriebssystem, was es machen soll (zB Breakpoint einfügen, Single Step, Register ausgeben, etc).

F: Und was passiert jetzt genau wenn das Programm an den Breakpoint kommt?

A: Trap wird ausgelöst, weil invalide Instruktion. Als normales Programm behandeln wir das normalerweise nicht, deswegen wirds ans Betriebssystem weitergegeben. Das signalisiert dem entsprechend registrierten Debugger dann, dass Breakpoint erreicht wurde.

Codebeispiel ähnlich zu:

class A {
    int i;
}

class B : A { }

class C : B {
    int foo() {
        return i;
    }
}

F: Einfachvererbung, wie sieht dann die Namens- und Typanalyse aus?

A: Muss wegen qualifizierten Zugriffen zusammen passieren.

F: Wenn wir dann die Namenstabelle füllen, reicht dann ein Durchlauf?

A: Nein, weil Klassen Attribute vom Typ der jeweils anderen Klassen haben können.

F: Dann machen sie mal einen Durchlauf der Namensanalyse vor:

Codebeispiel ähnlich zu:

class Widget {
    int i;
}

class Button : Widget {
    ...
}

Bekomme Zettel mit Vorlage, trage jeweils Verweise von Token→Eintrag und Super-Verweise ein. Member in eigener Hashmap

F: Wenn jetzt ein Durchlauf nicht reichen würde, wie wüssten dann die Nachfolgenden Durchläufe was sie zu tun haben?

A: Jeweiligen Felder werden attributiert, was für einen Typ sie erwarten. Wenn das dann bei den nächsten Durchläufen nicht passt, wird Fehler geworfen.

Codebeispiel ähnlich zu:

class A {...}

class B : A {...}

class C : A {...}

class D : B, C {...}

F: Was ist hier das Problem?

A: Diamantenproblem, wenn D auf seinen A-Teil zugreifen will ist das entweder über Kontext von B oder C oder über virtual inheritence notwendig.

F: Wie funktioniert denn virtual inheritence?

A: Im Objekt Offset zum jeweiligen Teil speichern, A-Teil von B und C zeigen dann auf den selben Teil. Dann ist das A in beiden Kontexten das selbe.

F: Was muss die Sprache dann dafür bereitstellen?

A: Keine Ahnung. (Wollte hier wahrscheinlich noch auf den non-virtual Teil raus, dass die Sprache die Unterscheidungsmöglichkeit bieten muss. War aber schon sehr tief bei virtual inheritence drin. Wurde in der Besprechung auch nicht weiter bemeckert, ich schiebs ganz frech einfach mal auf die Müdigkeit und verdächtig leere Mate von Florian)

F: Jetzt wollen wir noch Registervergabe machen, was gibts denn da?

A: Darf ich färben?

F: Sehr gerne.

Codebeispiel ähnlich zu:

v0 <- a0
v1 <- a2
v2 <- v0 + v1
v3 <- v0 * v1
v4 <- v2 + v3
v5 <- v3 * v3

F: Wie gehen wir jetzt vor?

A: Lebensspannen rausfinden, machen wir bottom up.

F: Wieso bottom up? Top down geht doch auch.

A: Ja, aber wird kompliziert wenn ein Wert nicht verwendet wird, deswegen von unten. Dann Kollisionsgraphen zeichnen, Kanten wo Lebensspannen kollidieren.

Blatt mit Kollisionsgraph (Achtung: noch kein Interferenzgraph) wird vorgelegt

F: Was jetzt?

A: Register einmalen, Interferenzgraph bilden.

F: v3 darf nicht in r2

A: Kante malen.

F: Was sind die gestrichelten Kanten da?

A: Move-Kanten für Coalescing, vor jedem Anwenden von Grad<R schauen wir ob wir die zusammenführen können, sparen wir uns mov-Befehle

F: Zeit um.