[CB-Logo]
Compilerbau I WS97/98
Übungen

Blatt 7

Abgabe: Montag, 15.12.1997

(ggf. Lösungen)

[Compilerbau-Homepage]

Aufgabe 1 (3 Pkt)

Zeigen Sie, daß für eine reduzierte kontextfreie Grammatik G gilt:
G ist genau dann eine LR(k) Grammatik, wenn
  1. nicht gilt: S -->+ S
  2. die kanonische Kollektion Jk konsistent ist.

Aufgabe 2 (10 Pkt)

Gegeben seien die Grammatiken
  1. G1 = ( {S,A}, {a,+,(,)} { S::=S+A|A, A::=(S)|a(S)|a }, S )
  2. G2 = ( {S,A}, {1,a}, { S::=1Sa|A, A::=aA|a }, S )
Beweisen oder widerlegen Sie, daß die Grammatiken eindeutig sind.

Aufgabe 3 (7 Pkt)

Schreiben Sie ein Programm, das als Eingabe die LR(1)-Tabellen und ein Wort w erwartet, und mit Hilfe der Tabellen das Wort parsed, und testen Sie es mit den Tabellen aus dem Script Seite 92/98 (G=({S},{a,b},{S::=SaSb|epsilon},S)) und den Worten w1=aabb, w2=abab, w3=abbb
Abgegeben werden sollte ein gut dokumentierter Sourcecode und der Testlauf mit Ausgabe der Einzelschritte. Email ist möglich.


(Es ist vermutlich einfacher, die beiden Tabellen in eine Tabelle zusammenzufassen.)
[Compilerbau-Homepage]
IfI Mathe WWU
Dietmar Lammers
Last modified: Tue Dec 2 14:51:32 MET 1997