URL:         /axel/informatik3_ws9899_blatt5.html
Dieses  Übungsblatt ist alleine zu bearbeiten.
 

Aufgabe 13 (8 + 3 Punkte)
In Aufgabe 10 wurde  für den Taschenrechner aus Aufgabe 8 eine Grammatik definiert. Nun soll für diese Grammatik ein Top Down Parser geschrieben werden. Dazu ist die verwendete Grammatik nochmal anzugeben (es muß nicht die Originallösung aus Aufgabe 10 sein, die Grammatik soll Punkt vor Strich beachten).  Bitte geben Sie ein instruktives Beispiel  für die Funktion Ihres Parsers an. (3 Punkte)

Aufgabe 14 (6 + 3 Punkte)
Eine Grammatik heißt -frei wenn es keine -Regeln ( alleine auf der rechten Seite) gibt, oder die einzige -Regel die Form S -->  hat, und das Startsymbol nie auf der rechten Seite einer Regel auftaucht. Man schreibe einen Algorithmus der eine Grammatik in eine  äquivalente -freie Grammatik umwandelt. (6 Punkte) Wenden Sie den Algorithmus auf die Grammatik mit der einzigen Regel { S --> aSbS | bSaS | } an. (3 Punkte)

Aufgabe 15 (6 + 3 Punkte)
Eine Grammatik heißt zykelfrei, wenn es keine Ableitung A ===> A für irgendein Nichtterminalsymbol A gibt.
Man schreibe einen Algorithmus der eine Grammatik in eine  äquivalente zykelfreie Grammatik umwandelt. (5 Punkte) Wenden Sie den Algorithmus auf die Grammatik mit der einzigen Regel { S --> SS | (S) | } an. (3 Punkte)