Ambiguïté dans les grammaires sans contexte

Si une grammaire sans contexte G a plus d'un arbre de dérivation pour une chaîne w ∈ L(G), ça s'appelle un ambiguous grammar. Il existe plusieurs dérivations les plus à droite ou à gauche pour une chaîne générée à partir de cette grammaire.

Problème

Vérifiez si la grammaire G avec les règles de production -

X → X + X | X * X | X | une

est ambiguë ou non.

Solution

Découvrons l'arbre de dérivation de la chaîne "a + a * a". Il a deux dérivations les plus à gauche.

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 -

Puisqu'il y a deux arbres d'analyse pour une seule chaîne "a + a * a", la grammaire G c'est ambigu.