Dein Fortschritt:
0 / 0 Aufgaben
1
Rechenausdrücke für einen Parser
13 BEAFB I–IIEin Taschenrechner-Programm prüft Rechenausdrücke, bevor es sie auswertet. z steht für eine beliebige Zahl. Die Syntax wird durch die Grammatik G festgelegt:
N = {A}
T = {z, +, *, (, )}
Startsymbol: A
Produktionsregeln:
A → A+A | A*A | (A) | z
T = {z, +, *, (, )}
Startsymbol: A
Produktionsregeln:
A → A+A | A*A | (A) | z
- Wenden Sie G an: Geben Sie eine Linksableitung von
(z+z)*zan. (3 BE) - Zeigen Sie mit zwei Ableitungsbäumen, dass G für
z+z*zmehrdeutig ist, und erläutern Sie die Folge für den Wert von 1 + 2 · 3. (4 BE) - Begründen Sie, dass L(G) nicht regulär ist. (3 BE)
- Die Entwickler ersetzen G durch A → A+P | P, P → P*F | F, F → (A) | z. Erläutern Sie, warum mit dieser Grammatik * stärker bindet als +. (3 BE)
Hinweise
Hinweis zu Aufgabe a)
Linksableitung: Immer das am weitesten links stehende A ersetzen. Beginnen Sie mit A → A*A.
Hinweis zu Aufgabe b)
Einmal steht + an der Wurzel, einmal *. Welcher Teil wird jeweils zuerst ausgerechnet?
Hinweis zu Aufgabe c)
Denken Sie an Ausdrücke wie ((((z)))) mit beliebig vielen Klammern.
Hinweis zu Aufgabe d)
Leiten Sie z+z*z mit der neuen Grammatik ab. Kann * an der Wurzel stehen, wenn ein + außerhalb von Klammern vorkommt?