Les différence principale entre la grammaire ambiguë et non ambiguë est que le Une grammaire ambiguë est une grammaire sans contexte pour laquelle il existe une chaîne qui peut avoir plus d'une dérivation la plus à gauche tandis qu'une grammaire non ambiguë est une grammaire sans contexte pour laquelle chaque chaîne valide a une dérivation la plus à gauche unique.

La grammaire fait référence aux règles syntaxiques des langues naturelles. En 1956, les informaticiens ont introduit un modèle mathématique de grammaire pour écrire le langage informatique. S'il est possible de dériver toutes les chaînes d'une langue en utilisant une certaine grammaire, alors on dit que la langue est générée à partir de cette grammaire. La grammaire sans contexte est un type de grammaire. Cette grammaire génère un langage sans contexte. La grammaire sans contexte peut être ambiguë ou non ambiguë. Pour une chaîne particulière, s'il y a deux ou plusieurs dérivations, cette grammaire est dite ambiguë. Pour une chaîne particulière, s'il n'y a qu'une seule dérivation la plus à gauche, cette grammaire est dite grammaire sans ambiguïté.

Grammaire ambiguë, Grammaire non ambiguë

Qu'est-ce que la grammaire ambiguë

Une grammaire est dite ambiguë s'il existe deux ou plusieurs dérivations pour une chaîne.

Figure 1: Grammaire ambiguë

Supposons qu'il existe une grammaire définie comme suit.

G= ({S}, {a+b, +, *}, P, S}. Les règles de production sont les suivantes. S -> S+S | S*S | a | b. Supposons qu'il soit nécessaire de générer la chaîne a+ a*b.

Considérez, S -> S+S

La substitution de « a » pour le plus à gauche S donnera ce qui suit.

S-> un +S

La substitution de S*S à S est la suivante.

S-> un + S*S

La substitution de 'a' pour le S le plus à gauche donnera la sortie ci-dessous.

S -> a+ a*S

La substitution de « b » pour le S donnera la sortie suivante.

S -> a + a * b

Il s'agit de la chaîne requise à générer.

Lors de l'utilisation de l'autre règle de production, cela donnera

S -> S* S

Appliquer S+S à l'extrême gauche S donnera ce qui suit.

S -> S+S * S

Remplacez « a » par le S le plus à gauche,

S -> un + S*S

En remplaçant « a » par le S le plus à gauche,

S -> un + un * S

La substitution de « b » pour S donnera la sortie suivante.

S -> a + a*b

Encore une fois, il a généré la chaîne requise. Par conséquent, il existe plusieurs dérivations pour générer la chaîne. C'est donc une grammaire ambiguë.

Qu'est-ce que la grammaire sans ambiguïté

Dans une grammaire ambiguë, une certaine chaîne a une dérivation unique à l'extrême gauche. Référez-vous aux règles de production suivantes.

S -> G | a, L -> LS | S

Considérez la règle S -> L. Remplacez LS au lieu de L.

S -> LS

Remplacez S, pour le premier L.

S -> S S

La substitution de 'a' pour le S le plus à gauche donnera la sortie ci-dessous.

S -> un S

En substituant « a » à S, vous obtiendrez ce qui suit.

S -> un un

Par conséquent, une chaîne a une dérivation unique à l'extrême gauche. C'est donc une grammaire sans ambiguïté.

Différence entre la grammaire ambiguë et non ambiguë

Définition

Une grammaire ambiguë est une grammaire sans contexte pour laquelle il existe une chaîne qui peut avoir plusieurs arbres de dérivation ou d'analyse les plus à gauche. La grammaire non ambiguë est une grammaire sans contexte pour laquelle chaque chaîne valide a une dérivation ou un arbre d'analyse unique à l'extrême gauche.

Nombre de dérivations les plus à gauche

Dans une grammaire ambiguë, une chaîne peut avoir deux ou plusieurs dérivations les plus à gauche mais, dans une grammaire non ambiguë, une chaîne a une dérivation unique à l'extrême gauche.

Conclusion

La grammaire sans contexte peut être ambiguë ou non ambiguë. La différence entre la grammaire ambiguë et non ambiguë est que la grammaire ambiguë est une grammaire sans contexte pour laquelle il existe une chaîne qui peut avoir plus d'une dérivation la plus à gauche tandis qu'une grammaire non ambiguë est une grammaire sans contexte pour laquelle chaque chaîne valide a une dérivation la plus à gauche unique.

Référence:

1. « Grammaire ambiguë ». Wikipédia, Wikimedia Foundation, 17 juillet 2018, disponible ici.2. « Conception du compilateur | Grammaire ambiguë. GeeksforGeeks, 10 février 2018, disponible ici.3. "Ambiguous Grammar", Neso Academy, 29 mars 2017, disponible ici.

Image de courtoisie:

1. "Leftmostderivations jaredwf" de Jaredwf sur Wikipedia anglais - Transféré de en.wikipedia à Commons par EdwardHades (domaine public) via Commons Wikimedia