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

 

Aufgabe 1 (3 + 3 Punkte)

Ausdrücke, die durch die folgende Grammatik generiert werden, können Zuweisungen enthalten (S und E sind Nichtterminale, :=, +, (, ) und id sind Terminale).

S -> E
E -> E := E | E + E | ( E ) | id
 

Die Semantik dieser Ausdrücke ist wie in C. Das heißt, b:=c is ein Ausdruck, der b den Wert von c zuweist; der r-Wert dieses Ausdrucks ist der gleiche wie der von c. Weiterhin weist a:=(b:=c) den Wert von c zuerst b und dann a zu.

1. Konstruieren Sie eine Attributgrammatik zur Überprüfung, daß die linke Seite einer Zuweisung ein l-Wert ist. Benutzen Sie dazu ein ererbtes Attribut side des Nichtterminals E, um anzuzeigen, ob der durch E generierte Ausdruck auf der linken oder rechten Seite einer Zuweisung erscheint.
2. Erweitern Sie die Attributgrammatik aus (a) um ein synthetisiertes Attribut je Nichtterminal, um P-Code für die Ausdrucksauswertung zu erzeugen. Die aktuelle Adreßumgebung steht dabei in einem ererbten Attribut rho des Wurzelknotens zur Verfügung.

Aufgabe 2 (1 + 4 + 3 Punkte)

Gegeben sei die Attributgrammatik G mit

VN = {S,A,B},   VT = {a,b,c},
Syn(S) = {z},   Inh(S) = {}
Syn(A) = {z},   Inh(A) = {i}
Syn(B) = {x,y}, Inh(B) = {i,j}
 
S -> A   mit  S.z = A.z,  A.i = 0
A -> aB  mit  B.i = A.i,  B.j = B.x,  A.z = B.y
B -> b   mit  B.x = B.i,  B.y = B.j
B -> c   mit  B.x = 0,    B.y = B.i
 

1. Zeichnen Sie die produktionslokalen Abhängigkeitsgraphen.
2. Weisen Sie nach, daß G l-ordered ist durch Bestimmen geeigneter totaler Ordnungen T(X) für jedes X aus V_N.
3. Schreiben Sie ein Programmschema (Besuchsplan), das es gestattet, die Attributexemplare in einem Baum auszuwerten.