Prof. Dr. R. Laue
WS0203
Informatik III
Übungsblatt 9
Abgabe: 19.12.02 vor der Vorlesung
URL:
/axel/informatik3_ws0203_blatt9.html
Dieses Übungsblatt ist in Zweiergruppen
zu bearbeiten.
Aufgabe 23 attributierte Grammatik (6 Punkte)
Die Ausdrücke, die folgende
Grammatik akzeptiert, dürfen, wie in C, Zuweisungen innerhalb von
Zuweisungen enthalten.
S -->E
E --> E=E
E --> E*E
E --> (E)
E --> identifier
E --> E[ziffer]
E --> ziffer
Man konstruiere eine attributierte Grammatik,
die entscheiden kann, ob ein Ausdruck (=E) ein "l-value" ist.
Man benutze dazu ein vererbtes Attribut "seite". Unter l-value versteht man einen Ausdruck, der als linke
Seite einer Zuweisung auftauchen darf. D.h. es gibt einen zugehörigen
Speicherplatz.
Aufgabe 24 EQN (2+2+3 Punkte)
Das UNIX Textformatierungsprogramm EQN hat u.A. folgende Beschreibung
PRODUKTION
|
SEMANTIK
|
S --> B
|
B.ps = 10
S.ht = B.ht
|
B --> B1 B2
|
B1.ps = B.ps
B2.ps = B.ps
B.ht = max(B1.ht, B2.ht)
|
B --> B1 sup B2
|
B1.ps = B.ps
B2.ps = shrink(B.ps)
B.ht = disp(B1.ht, B2.ht)
|
B-->text
|
B.ht = text.h * B.ps
|
dabei stellt das nicht Terminal Symbol B (wie box) eine Formel dar. Die
Produktion B->B1B2 erlaubt das aneinander hängen von boxen. Bei B
--> B1 sup B2 wird die zweite box verkleinert und als Index angehängt.
Das Attribut ps (point size) geht in die Berechnung der Höhe einer Formel
ein. In der Regel zu B-->text wird die Höhe als Pordukt aus der normalisierten
Höhe (=text.h was vom token text mit geliefert wird) und der point size
errechnet. Die Funktion shrink sorgt dafür, dass die point size bei
boxen im Index um 35% kleiner ist. disp verschiebt die box nach unten und
berechnet deren Höhe.
a) zeigen Sie dass die Grammatik links-attributiert ist.
b) welche Attribute sind abgeleitet, welche vererbt?
c) man füge die semantischen Regeln so in die rechten Seiten der Produktionen
ein, dass ein Keller zur Verarbeitung von Ausdrücken ausreicht.