Ü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

  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.

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.

  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