Mehrdeutigkeit in kontextfreien Grammatiken

Wenn eine kontextfreie Grammatik G hat mehr als einen Ableitungsbaum für eine Zeichenfolge w ∈ L(G)heißt es ein ambiguous grammar. Es gibt mehrere Ableitungen ganz rechts oder ganz links für eine Zeichenfolge, die aus dieser Grammatik generiert wird.

Problem

Überprüfen Sie, ob die Grammatik G mit Produktionsregeln -

X → X + X | X * X | X | ein

ist mehrdeutig oder nicht.

Lösung

Lassen Sie uns den Ableitungsbaum für die Zeichenfolge "a + a * a" herausfinden. Es hat zwei Ableitungen ganz links.

Derivation 1- X → X + X → a + X → a + X * X → a + a * X → a + a * a

Parse tree 1 - -

Derivation 2- X → X * X → X + X * X → a + X * X → a + a * X → a + a * a

Parse tree 2 - -

Da es zwei Analysebäume für eine einzelne Zeichenfolge "a + a * a" gibt, ist die Grammatik G ist nicht eindeutig.