Eindeutigkeit

mathend000#Id 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