Notizen zu Übersetzerbau 1

Wahl zwischen Shift und Reduce, eg. bei Links- oder Rechtsassoziativität von Binären Ausdrücken, bei Grammatiken der Form

exp ::= exp OP exp | val ;;

wo die Eingabe

1 OP 2 OP 3

als

(1 OP 2) OP 3

oder

1 OP (2 OP 3)

zu interpretieren, weil es dem Parser offen steht 1 als exp oder val anzusehen.

Wahl zwischen Reduce und Reduce, eg. wenn es zwei Ableitungen gibt für die gleiche Eingabe:

a ::= b | c ;;
b ::= d;
c ::= d;

kann zu

a(b(d(...)))

oder

a(c(d(...)))

abgeleitet werden.

Ein LR-Parser kann mit einer Tabelle dargestellt werden. Die Tabelle stellt Zustände zu Parser-Aktionen und Zustandsübergängen gegenüber. Daher ist die Tabelle in zwei-geteilt.

Jeder Token in der Eingabe wird benutzt um zusammen mit dem Zustand im "Aktion"-Teil der Tabelle zu prüfen ob ein "Shift" (fügt ein Zustand zum Stack hinzu) oder "Reduce" (entfernt Zustände vom Stack mit Hilfe einer Regel) ausgeführt werden soll, bzw. ob es sich um ein Endzustand handelt. Jeder leere Tabelleneintrag stellt ein Fehler dar.

Nach einem Reduce wird in der zweiten Tabellenhälfte ("LHS GOTO"-Regeln) angegeben in welchen Zustand übergegangen soll, indem der Zustand und TOS-Nichtterminal als Schlüssel genommen wird.

Der Sinn einer Parser-Tabelle ist es die Implementierung des Parsers zu vereinfachen und indem die Tabelle als "generische" Eingabe an eine "Parser-Schleife" angesehen wird. Die Konstruktion dieser Tabellen wurde nicht in der Vorlesungen behandelt.

Da Sprachen wie Java virtuelle Funktionen nur Anhand vom Dynamischen-Typs Objekt auf dem diese Aufgerufen werden auswählen (sonst statische Typen), kann man im Visitor nicht direkt

public void visit(Bar f) {
    visit(f.child);
}

ausrufen mit der Hoffnung, dass die Richtige visit Funktion benutzt wird. Stattdessen hat jeder Knoten eine Funktion accept dass ein Visitor nimmt

#+begin_src c
    public void visit(Bar f) {
        f.child.accept(this);
    }

und dann visit aufruft,

public void accept(Visitor v) {
     v.visit(this);
}

damit nun der statische Typ gleich dem dynamischen Typen entspricht.

Arbeitet auf maximalen Grundblöcken gibt Befehle aus für jeden Befehl der Form \(\mathtt{x} \leftarrow \mathtt{y}\;\mathrm{op}\;\mathtt{x}\)

Algorithmus zum optimalen generieren von Code für Ausdrucksbäume (ohne Seiten-Effekte).

Annnahme: Befehle sind von der Art "RoM" (Register-Memory) oder "RoR" (Register-Register), bzw. "Move", "Load" und "Store". Beide letzteren schreiben Ergebnisse zurück in Register. Sollten beim Auswerten eines Ausdrucks nicht genug Register zur Verfügung stehen, werden diese aus- und später wieder eingelesen.

Jedem Konten im Baum wird eine Erschov-Zahl zugewiesen. Für linke Blattkoten (immer Register) 1 und für rechte (aus dem Speicher lesbar) 0. Für binäre Konten \(b(c_1, c_2)\) sei \(e_1 = \mathrm{erschov}(c_1)\) und \(e_2 = \mathrm{erschov}(c_2)\), dann \[ \mathrm{erschov}(b) = \begin{cases} \max(e_1, e_2) & \text{if } e_1 \neq e_2\\ e_1 + 1 & \text{sonst}\end{cases} \]

Bei Registerknappheit: Teilbäume mit höherem Registerbedarf (d.h. größerer Ershov-Zahl) werden als erstes ausgewertet, damit währenddessen weniger Ergebnisse kleinerer Bäume gespeichert werden, und ggf. in den speicher geschrieben und später wieder ausgelesen werden (spilling).

Der Algorithmus arbeitet nur auf Bäumen, aber ein Ausdrucksgraph kann auch ein DAG sein, wenn werte wieder-benutzt werden. In dem Fall wird der DAG in ein Wald aufgespalten und nacheinander ausgewertet.

Greedy (→ "Maximum Munch") verfahren um ein Ausdrucksbaum mit Verfügbaren (oft CISC) befehlen zu überdecken. Das Verfahren terminiert erfolgreich wenn es für jeden Einzelknoten ein Muster gibt, und jede Ersetzung verkleinert den Baum.

Mittels einer LR Grammatik werden IR Operationen in Präfixform in Maschinenbefehle übersetzt. Dabei werden immer "größere" Regeln bevorzugt und Shift/Reduce oder Reduce/Reduce Konflikte aufzulösen. Die Produkitionsregeln generieren den Output.

In einen Abhängigkeitsbaum wird jedem Konten mitgespeichert was die Kosten für die Auswertung in Abhänigkeit von der Anzahl der verfügbaren Register ist \(C_1\), \(C_2\), …, bzw. die Kosten wenn alle Register Verfügbar sind aber das Ergebnis zurückgeschrieben werden soll in den Speicher \(C_0\): \[ (C_0, [C_1, C_2, \dots]) \] \(C_0\) wird berechnet indem das Minimum aller restlichen \(C_i\) genommen wird, plus Kosten für Speicherung.

Die Lebensspanne einer Variable ist ein Intervall zwischen dem Beschreiben und dem letzten Auslesen. Überlappende Lebensspannen werden verschmolzen.

Bei der Registervergabe können mittels dem Lebensspannen von Variablen "Kollisionsgraphen" konstruiert werden um zu beschreiben welche Variablen zu einem Zeitpunkt in verschiedenen Registern leben müssen. Ein Interferenz Graph bestehend aus allen realen Registern und ggf. zusätzlichen Einschränkungen kann hierzu hinzugefügt werden, um Graphfärbung mit einer Farbzahl gleich der verfügbaren Registerzzahl als Verfahren für die Registervergabe zu benutzen.