Compilerbau I Übungen

Compilerbau I WS97/98
Übungen

Blatt 4

Abgabe: Montag, 17.11.1997

(ggf. Lösungen)

[Compilerbau-Homepage]

Aufgabe 1 (6 Pkt)

Konstruieren Sie einen erkennenden Kellerautomaten zu folgender kontextfreien Grammatik:

G=( {S,A}, {a,b}, P, S) mit P = { S::=aAA , A::=aS|bS|a }

Aufgabe 2 (4 Pkt)

Geben Sie zu der kontextfreien Grammatik

G = ( {S,A,B,C,D,E}, {a,b}, P, S)
mit P = { S::=AB|CA , A::=DE , B::=BC|AB , C::=aB|b , D::=epsilon, E::=A|a }

eine äquivalente kontextfreie Grammatik an, die keine nutzlosen Symbole, keine Kettenproduktionenund keine Epsilonproduktionen enthält.

Wegen der eingeschränkten Darstellungsfähigkeiten der Browser wurde epsilon ausgeschrieben. Gemeint ist das leere Wort

Aufgabe 3 (10 Pkt)

Sei folgende Grammatik gegeben:

G = {S,A,B,W,R,K}, {a,e,l,k,m,r,t,p,s,u,w,z}, P, S)
mit P = { S::=ApeK|BR , A::=epsilon|As , B::=tWlR W::=atze|aWe|epsilon , R::=wurm|ApeK , K::=epsilon|Kk }

(1P) Beschreiben Sie die erzeugte Sprache in der bereits öfter verwendeten Mengenschreibweise. (Bsp: {aⁿ|n < 24})
(3P) Geben Sie eine aequivalente epsilon-freie Grammatik an.
(6P) Leiten Sie in der epsilon-freien Version das Wort 'tatzelspekk' durch bottom-up-Analyse ab.

[Compilerbau-Homepage]

$IfI$ $Mathe$ $WWU$

Dietmar Lammers

Last modified: Thu Nov 13 12:51:46 MET 1997