mathend000#
Def: G
mathend000# heißt eindeutig, falls
∀w∈L(G)
mathend000#
genau ein Ableitungsbaum (T, m)
mathend000# existiert.
Bsp: ist
{S→aSb| SS| ε}
mathend000# eindeutig?
(beachte: mehrere Ableitungen
S→R*w
mathend000# sind erlaubt,
und wg. Kontextfreiheit auch gar nicht zu vermeiden.)
Die naheliegende Grammatik für arith. Ausdr.
expr -> number | expr + expr | expr * expr
ist mehrdeutig (aus zwei Gründen!)
Auswege:
- Transformation zu eindeutiger Grammatik
(benutzt zusätzliche Variablen)
- Operator-Assoziativitäten und -Präzedenzen
Johannes Waldmann
2014-03-31