Vorherige Seite Zur Übersicht Nächste Seite | Blatt 7 als PDF


U. Kastens, M. Jung

Vorlesung Übersetzer I WS 1999/2000 - Übungsblatt 7

Ausgabe: 28.01.2000 -- Abgabe: 07.02.2000, 9:00 Uhr (in der Vorlesung)

Aufgabe 21 (Source-To-Source-Übersetzung mit PTG)

Im Verzeichnis /homes/info-fa2/compiler/aufgaben/blatt7/aufg21 befindet sich eine Eli-Spezifikation, um aus Programmen in der Sprache von Aufgabe 19 ein C++-Programm zu erzeugen. Dabei wird das Werkzeug PTG (Pattern-based Text Generator) aus Eli benutzt, mit dem man einen Satz von Funktionen zur Textausgabe erzeugen kann. Die Erzeugung der Zielbäume mit Funktionen, die aus den Kontexten des Strukturbaums aufgerufen werden, entspricht genau dem auf Folie 59 beschriebenen Schema.

Kopieren Sie die Spezifikationen in ein eigenes Verzeichnis. Fügen Sie in aufg21.lido an den gekennzeichneten Stellen Aufrufe von PTG-Funktionen für die Transformation der Ausdrücke ein und ergänzen Sie die Datei aufg21.ptg um passende PTG-Spezifikationen. Sie können ihre Ergänzungen mit folgender Anforderung an Eli überprüfen:

aufg21.specs :exe :warning>

Testen Sie anschließend den mit Eli erzeugten Übersetzer mit der Eingabedatei aufg21.in1:

aufg21.in1 +cmd=(aufg21.specs :exe) :stdout >
Hinweis:
Sie brauchen C++ nicht zu beherschen, um diese Aufgabe zu lösen. Die Ausgabe des Übersetzers für aufg21.in1 könnte beispielsweise wie in aufg21.out1.cc aussehen.

Aufgabe 22 (Optimierung: Verbessernde Transformation manuell anwenden)

Optimieren Sie das folgende C-Programm, indem Sie möglichst viele verbessernde Transformationen gemäß Folie 62 anwenden, ohne die Bedeutung des Programms zu verändern. Erläutern Sie, welche Transformation Sie an welcher Stelle vorgenommen haben, und geben Sie zusätzlich den resultierenden Programmtext ab.

/* A. N. Faengers erstes C-Programm */
#include <stdio.h>

int next (int x) { return x + 1; }

void main (void) {
   int a, b, c, d;
   int x, y, z;
   int i;
   
   c = 7;
   b = 1001 / (11 * c);
   d = -13;
   a = c;
   
   for (i = 0; i < 1000; i++) {
      x = (b + a) / 25;
      z = 27 * i;
      y = (a + b) % 25;
      printf("x = %d, y = %d, z = %d\n", x, y, z);
      if (a < b) d = next(d);
      else d = next(next(d));
      x = 2 * x;
   }
   printf("d = %d\n", d);
}
Hinweis: Dieser Quelltext ist auch unter aufg22.c zu finden.

Aufgabe 23 (Registerzuteilung für Ausdrücke (Sethi,Ullman))

Geben sie für folgende Ausdrücke den Ausdrucksbaum an. Teilen Sie nach dem Verfahren von Sethi/Ullmann Register aus dem Vorrat (R1, R2) zu und geben Sie die Auswertungsreihenfolge sowie ggf. den Spillcode in Pseudo-Assembler an.

Beispiel:

        a + b * c         Pseudo-Assembler dafür           
                  
        + Reg: 2          load R1, b                    
       / \                load R2, c                    
      a   * Reg: 2        *    R1, R2  // Ergebnis b * c in R1
         / \              load R2, a                    
        b   c             +    R2, R1  // Ergebnis a + b * c in R2
a)
d + ((a + b) * c)

b)
(a + b + c) * (d + e)

c)
(e + f) + ((a + b) * (c + d))

Aufgabe 24 (Registerzuteilung für Grundblöcke (Belady))

Gegeben sei die folgende Anweisungsfolge:

     
          a := x;
          b := y;
          c := a * b;
          d := c / a;
          e := z;
          f := b + d;
          g := a - f;
          h := e + b;
          i := u;
          j := g + h;
          k := i * j;
a)
Stellen Sie die Lebensdauer der Werte als Intervallgraph (Folie 69 und folgende) dar, und bestimmen Sie den Registerbedarf. Ordnen Sie im Graphen die Register den jeweiligen Variablen zu.

b)
Nehmen Sie an, daß ein Register zu wenig zur Verfügung steht. Bestimmen Sie, welche Werte zwischengespeichert werden und ordnen Sie die Register den Variablen zu.


Vorherige Seite Zur Übersicht Nächste Seite | Blatt 7 als PDF