Übersetzerbau	WS 98/99 Heckmann Pape
12. Übungsblatt

 

Aufgabe 1 (1 + 2 + 3 + 1 Punkte)

Gegeben sei die Attributgrammatik G mit

VN = {S,A,B},   VT = {a},
Syn(S) = Syn(B) = {s},  Inh(A) = {i},  sonst keine Attribute
 
S  ->  AB   mit  S.s = B.s+1,   A.i = B.s
S  ->  A    mit  S.s = 1,       A.i = 0
B0 ->  B1a  mit  B0.s = B1.s+1, A.i = B1.s
B  ->  A    mit  B.s = 1,       A.i = 0
A  ->  a
 

1. Zeichnen Sie die produktionslokalen Abhängigkeitsgraphen.
2. Leiten Sie daraus die Brüdergraphen ab, und weisen Sie nach, daß es sich um eine Einpaß-Attributierte Grammatik handelt.
3. Schreiben Sie ein Programmschema (Besuchsplan), das es gestattet, die Attributexemplare in einem Baum auszuwerten.
4. Was bedeutet der Wert von s an der Wurzel?

Aufgabe 2 (3 + 4 + 1 Punkte)

Betrachten Sie die Operatoren var (nullstellig), not (einstellig), and (zweistellig), or (zweistellig) und die Muster

m1 = not (not (_))
m2 = not (and (_, _))
m3 = not (or (_, _))
 

1. Bestimmen Sie einen nichtdeterministischen Baumautomaten, der diese Muster erkennt.
2. Machen Sie den Automaten aus (a) deterministisch.
3. Zeigen Sie eine Berechnung des deterministischen Automaten aus (b) an dem Baum

    
   not (not (and (not (not (var)), not (var))))

   Welche Mustertreffstellen werden gefunden?