====== Übersetzerbau 1 ======
  * "Grundlagen des Übersetzerbaus" uebbau WS 2012/2013
  * "Übungen zu Grundlagen des Übersetzerbaus"
  * ~ 30 min.
  * Prüfung oder benoteter Leistungsnachweis zu Programmiersysteme (7,5 ECTS)

**Prüfer:** Prof. Dr. Michael Philippsen \\
**Beisitz:** Dipl.-Inf. Stefan Kempf \\
Papier + Stift bereitgestellt \\
versch. Blätter mit Pseudo-Code für Prüfungsfragen vorhanden

===== foreach in Übungssprache einbauen =====

    int main()  {
        int ret;
        int[10][20][30] a;
         
        foreach (x in a) {
           if (x > 10) {
              ret = ret +x;
           } else {
              ret = 2 * ret + x;
           }
        }
    }

P: Wie würden sie das Konstrukt foreach hier in unseren Übungscompiler einbauen?

S: Zunächst muss man den Lexer anpassen. Dieser muss zwei weitere
Keywords zu eigenen Tokens erfassen. Nämlich "foreach" und
"in". Zuerst hatte ich das "in" vergessen, was mir aber dann beim
Parser aufgefallen ist. Im Parser muss man weitere Produktionen für
das "foreach"-Statement einfügen.

    foreach_stmt -> TKFOREACH ( in_expr ) block
    in_expr -> Id TKIN Id

Hier ist zu beachten, dass man auf der rechten Seite des "in" ein
Array stehen haben muss, was man aber im Parser nicht feststellen
kann. Dies muss man in der Semantischen Analyse herausfinden. Dort
muss man zunächst feststellen, dass die rechte Seite des ins
deklariert ist. Zu beachten ist auch, dass das "x" nirgends deklariert
wird. Man es also mit dem Elementtyp des Arrays deklarieren muss und
es nur innerhalb des Blocks sichtbar sein soll. In der Typphase muss
man feststellen, dass auf der rechten Seite auch ein Array steht.

Dann sollte hab ich gesagt, dass ich den Baum in eine "for"-Schleife
umbauen würde, weil die kann der Compiler schon. Für den
geschachtelten Array Zugriff, für den man 3 innere Schleifen bräuchte
hätte ich den Array Zugriff linearisiert. Hab also gemeint, dass ich
ein Array der Größe 10 * 20 * 30 hätte.

==== Zwischencode erzeugen ====

Dann sollte ich das "if"-"else" innerhalb der Schleife in Zwischencode
umwandeln:

      CBLT x, 10, L1
      CBRA L2
    L1:
      tmp1 <- ret + x
      ret  <- tmp1
      CBRA L3
    L2:
      tmp1 <- 2 * ret
      tmp2 <- tmp1 + x
      ret  <- tmp1
    L3:

Hier hab ich dann noch erwähnt, dass man die Bedinung noch umdrehen
kann um ein jump einzusparen. Es würde also dann ein "CBGE x, 10, L2"
stehen.


Ich sollte dann noch die Formel für den Array-Zugriff machen mit i,j,k

    (((i * 20 + j) * 30) + k) * sizeof(int)

Dafür sollte ich dann Zwischencode erzeugen.

    tmp1 <- i * 20
    tmp2 <- tmp1 + j
    tmp3 <- tmp2 * 30
    tmp4 <- tmp3 + k
    tmp5 <- tmp4 * sizeof(int)

Dafür sollte ich dann Code für eine Stackmaschiene bauen. Und hab dann
festgestellt, dass man 2 Plätze auf dem Stack braucht. Es war dann
danach gefragt, wie man mittels Graph färben herausfinden kann,
wieviele temporäre Slots man auf dem Stack braucht. Also braucht man
einen Konflikt/Inferenzgraphen. Das ist ähnlich zum normalen Färben
des Graphs. Man nimmt den Knoten mit dem Grösten Grad raus und gibt
ihm die erste Farbe. Und so weiter. In diesem Fall braucht man 3
temporäre Plätze, wenn i,j,k danach überschreiben darf.

==== Optimierung beim Tail-calls ====

    int g() {
        ....
        return;
    }
    
     int f(int x) {
        g();
    L2:
        return;
    }
    
    int main() {
       f(1);
     L1:
    }

P: Wie sieht der Stackframe aus, wenn "g" return macht. (Ohne Basepointer)

S: Den Stack Stück für Stück aufgebaut. 

    | 1 | &L1 | &L2 |

Er hat dann noch nach einer Optimierung gefragt die der Compiler
machen kann um den zweifachen "ret" Befehl am Ende von g zu
vermeiden. Die Lösung ist, dass man in f() kein call, sondern ein jump
macht, damit die eigene return Adresse oben auf dem Stack steht.

Note: 1.0