Übersetzerbau Musterlösungen SS97

Prüfung aus Übersetzerbau, 20.06.1997

[ 1. Beispiel , 2. Beispiel , 3. Beispiel , 4. Beispiel ]

Bitte schicken Sie Korrekturen, Verbesserungsvorschläge und weitere Fragen, die in den Kommentaren zu den Beispielen nicht behandelt werden an mich: nino@complang.tuwien.ac.at. Genauer erklärte Musterlösungen kommen Ihren Kollegen zugute und wir freuen uns immer über gute Ergebnisse.

Erstes Beispiel (20%)

Gegeben sei folgende Grammatik (Das Startsymbol ist DEF):

[Bild]

Bestimmen Sie die First- und Follow-Mengen aller Nonterminale.

Lösung:

Nonterminal	`First`-Menge	`Follow`-Menge
DEF	{`class`,`interface`}	{$}
CLASS	{`class`}	{$}
INTERFACE	{`interface`}	{$}
EXTENDS	{`extends`,}	{`implements`,"`{`"}
IMPLEMENTS	{`implements`,}	{"`{`"}
FIELDS	{`field`}	{"`}`"}

Häufigste Fehler:

"$" in allen Follow-Mengen
"field" in Follow(FIELDS)

Zweites Beispiel (25%)

Quadrupel-Code

[Bild]

Erzeugen Sie für das obige Programmstück Quadrupel-Code nach der Kontrollflußmethode. Ein INTEGER ist 4 Byte groß. Die Untergrenze aller Indexbereiche ist 0. Optimieren Sie den Code NICHT.

Lösung:

        if i < 5 goto L1
        goto IFFALSE
L1:     if j < 8 goto WBEGIN
        goto IFFALSE
WBEGIN: t1 := i * 8
        t2 := t1 + j
        t3 := t2 * 4
        t4 := t3 + adr(a)
        t5 := @t4
        if t5 < 12 goto WTRUE
        goto WFALSE
WTRUE:  t6 := i * 8        (* 1 *)
        t7 := t6 + j
        t8 := t7 * 4
        t9 := t8 + adr(a)
        @t9 := k
        t10 := k * 4
        t11 := t10 + adr(b)
        t12 := @t11
        k := t12
        t13 := k * 4       (* 2 *)
        t14 := t13 + adr(b)
        @t14 = 1
        goto WBEGIN
WFALSE: goto IFEND
IFELSE: k := 0
IFEND:  (* ENDE *)

Häufigste Fehler:

Trotz aller Warnungen in der Angabe und in der Fragestunde haben wieder viele, wie auch bei der letzten Prüfung, den Quadrupel-Code "kaputtoptimiert". Bitte gehen Sie bei Beispielen dieser Art strikt nach dem Skriptum vor, da Sie sonst leicht Fehler machen können. Die Liste der beliebtesten "Optimierungen":

(* 1 *) Hier wurde die Berechnung von a[i,j] aus der WHILE-Bedingung weiterverwendet. Obwohl dies keinen falschen Code erzeugt, wurden Punkte abgezogen (1 Punkt pro fehlendem Befehl), da explizit keine Optimierung durchgeführt werden sollte.
(* 2 *) Hier wurde von vielen Leuten die zuvor berechnete Adresse von b[k] weiterverwendet, obwohl sich k inzwischen geändert hat! Ein großer Fehler, da der erzeugte Code falsch ist. Er entspricht nicht dem angegebenen Programmstück
```
        k := b[k]
        b[k] := 1
```
sondern diesem:
```
        k1 := k      
        k := b[k]
        b[k1] := 1
```
Sie sehen also, daß "Optimierungen" dieser Art nicht nur nicht der vorgeschriebenen Vorgangsweise im Skriptum entsprechen, sondern auch die Semantik des erzeugten Codes ändern können.

Weitere beliebte Fehler waren "wegoptimierte" Sprungbefehle (besonders jener am Ende des THEN-Zweigs des IF-Befehls) und invertierte Sprünge (bei der IF-Bedingung). Schwierigkeiten bereitete einigen auch die Indexberechnung bei zweidimensionalen Arrays. Auch hier empfiehlt es sich, strikt nach dem Skriptum vorzugehen (Kapitel 7, "Indizierte Variablen"):

Für a[i,j] wird die Formel im Skriptum zu (i*8+j)*4 + adr(a), da i₁ = i, i₂ = j, n₂ = 8 und w = 4 ist.

Drittes Beispiel (25%)

Reguläre Definitionen:

a) (10%)

Geben Sie eine Reguläre Definition für Ausdrücke an, die folgendermaßen definiert sind: eine Ziffer n von 0 bis 5, gefolgt von höchstens n Großbuchstaben, falls n gerade (oder 0) ist und höchstens n Kleinbuchstaben, falls n ungerade ist (ohne Umlaute), das ganze beliebig oft wiederholt. Beispiel: 3ab4AAA002BB15. (0 ist hier die Ziffer Null, nicht Buchstabe O)

b) (15%)

Geben Sie eine Reguläre Definition für Bit-Ketten an, deren Länge ein Vielfaches von 8 ist (8, 16, 24 ...), mit gerader Parität in jedem 8-Bit-Block (gerade Anzahl von 1ern, oder nur 0en), an. Beispiel: 00010010 01110010 00001111.

Lösung a):

  K = [a-z]?
  G = [A-Z]?
  EXPR = ( 0 | 1 K | 2 G G | 3 K K K | 4 G G G G | 5 K K K K K ) +

Anmerkungen zu a):

Die Schwierigkeit bei diesem Beispiel lag in der Tatsache, daß die Regulären Definitionen nicht mächtig genug sind um gewisse Aufgabenstellungen elegant zu bewältigen - wie hier die Interpretation der Ziffer oder bei b) das Zählen der 1er. Wer sich darüber im Klaren ist, merkt sofort, daß dieses Beispiel nur durch getrennte Behandlung der einzelnen Fälle zu lösen ist. Einigen war anscheinend die Möglichkeit eine Option anzugeben (mit ?) nicht bekannt, weshalb sie statt einem Fall pro Ziffer jede mögliche Anzahl von nachfolgenden Buchstaben angeben mußten.

Lösung b):

  U2 = 01 | 10
  G2 = 00 | 11
  U4 = U2 G2 | G2 U2
  G4 = U2 U2 | G2 G2
   B = U4 U4 | G4 G4
EXPR = ( B )+

Oder auch

  G4 = 0000 | 0011 | 0101 | 0110 | 1001 | 1010 | 1100 | 1111
  U4 = 0001 | 0010 | 0100 | 0111 | 1000 | 1011 | 1101 | 1110
   B = U4 U4 | G4 G4
EXPR = ( B )+

Oder gar

   B = 00000000 | 00000011 | 00000101 | ...
EXPR = ( B )+

... wobei alle Möglichkeiten aufgezählt werden (nicht empfehlenswert) oder eindeutig beschrieben werden (mit Erklärung, was da stehen sollte). Auch diese Lösung ist korrekt.

Anmerkungen zu b):

Einigen Leuten dürfte es schwer gefallen sein, wie auch bei a) damit klarzukommen, daß es - wie auch im "echten Leben" - nicht immer "schöne" Lösungen gibt. Denken Sie daran, daß Sie in erster Linie eine korrekte Lösung finden sollen und es nicht unbedingt sinnvoll ist, bei einer Prüfung unter Zeitdruck nach "besseren" Lösungen zu suchen.

Anmerkungen zu Regulären Definitionen allgemein:

Beachten Sie, daß hier Rekursionen nicht erlaubt sind! Eine Reguläre Definition kann sich nur auf zuvor definierte Namen von Regulären Definitionen beziehen!

Viertes Beispiel (30%)

Attributierte Grammatik.

Folgende Grammatik beschreibt verschachtelte Flächen mit Position und Farbe (Grauton):

[Bild]

Die 4 Zahlen nach flaeche sind die Eckpunkte x1,y1,x2,y2 für die gilt: x2>=x1 und y2>=y1. Die Zahl nach grau gibt den Helligkeitswert an (Weiß = 1, Schwarz = 0). Die Flächen überschneiden sich nicht. Erweitern Sie die Grammatik zu einer attributierten Grammatik, die im Attribut grau von S den durchschnittlichen Helligkeitswert der gesamten Fläche berechnet (Summe aller Teilflächen multipliziert mit ihren Helligkeitswerten, dividiert durch die Gesamtfläche). Mit inum.val und rnum.val erhalten Sie die Zahlenwerte. Achten Sie darauf, daß Sie keine Bereiche doppelt zählen. Beispiel:

Lösung (je eine/mehrere Regel(n) mit Kommentaren):

F -> schwarz    { F.g := 0 }
F -> weiss      { F.g := 1 }
F -> grau rnum  { F.g := rnum.val }

Hier werden die Helligkeitswerte initialisiert und nach oben im Attribut g weitergegeben.

FARBE -> F    { FARBE.v := FARBE.s * F.g }

Hier sind wir in einem Reckteck ohne Teilflächen. Wir benötigen also den Helligkeitswert (wird in F.g synthetisiert) und die Fläche des Rechtecks, die wir von FARBE bekommen werden und können nun einen Wert berechnen, der der Helligkeit dieser rechteckigen Fläche multipliziert mit ihrer Fläche entspricht. Alternativ dazu könnte man die Multiplikation auch in der nächsten Regel durchführen.

FLAECHE -> flaeche inum1 inum2 inum3 inum4 FARBE
           {
             FLAECHE.s := (inum2.val - inum1.val)
                        * (inum4.val - inum3.val)
             FARBE.s := FLAECHE.s
             FLAECHE.v := FARBE.v
            }

In dieser Regel wird die Fläche des angegebenen Rechtecks berechnet und zur nach unten weitergegeben, damit dort die Berechnung des Attributs v durchgeführt werden kann. Bisher funktioniert das nur für Rechtecke ohne enthaltene Teilflächen, wir müssen also noch die nachfolgende Regel für diesen Fall implementieren.

FARBE -> "(" F FLAECHEN ")"
         {
           FARBE.v := (FARBE.s - FLAECHEN.s)
                      * F.g + FLAECHEN.v
         }

Wir gehen hier davon aus, daß wir die Gesamtfläche der enthaltenen Teilflächen in FLAECHEN.s synthetisiert haben, sowie deren Helligkeitswerte gewichtet mit den Flächen (deren Größe) in FLAECHEN.v bekommen. Somit können wir den gewichteten Gesamt-Helligkeitswert für die umgebende Fläche und die enthaltenen Flächen berechnen. Dazu ziehen wir die Gesamtfläche der Teilflächen von der umgebenden Fläche ab, um keine Bereiche doppelt zu zählen.

FLAECHEN -> FLAECHE { FLAECHEN.s := FLAECHE.s; FLAECHEN.v := FLAECHE.v }

FLAECHEN -> FLAECHEN2 FLAECHE
                    {
                      FLAECHEN.s := FLAECHEN2.s + FLAECHE.s
                      FLAECHEN.v := FLAECHEN2.v + FLAECHE.v
                    }

Hier werden die Größen einer Liste von Teilflächen sowie deren gewichtete Helligkeitswerte aufsummiert.

Es fehlt nur mehr die endgültige Berechnung der durchschnittlichen Helligkeit der gesamten Fläche. Wir benötigen dazu die Gesamtfläche (das ist jene der auf der obersten Ebene definierten, also des umgebenden Rechtecks) sowie den gewichteten Helligkeitswert für diese Fläche.

S -> FLAECHE  { S.grau := FLAECHE.v / FLAECHE.s }

Anmerkungen:

Man könnte dieses Beispiel auf eine leicht veränderte Weise lösen, indem man z.B. nicht mit einer gewichteten Helligkeit arbeitet, sondern nur mit der pro Fläche berechneten durchschnittlichen.

Bei dieser Prüfung war die attributierte Grammatik anscheinend viel leichter als bisher, da fast alle Teilnehmer relativ gut damit zurecht kamen. Fehler gab es u.a. bei der Berechnung der Fläche und manchmal wurden Attribute nicht bei allen Produktionen fuer ein Nonterminal berechnet.

Marinos Yannikos
Letzte Änderung: Dienstag, 24.06.1997, 17:55 Uhr.