Différence entre grammaire ambiguë et non ambiguë
Share
le différence principale entre la grammaire ambiguë et non ambiguë est que la La grammaire ambiguë est une grammaire dépourvue de contexte pour laquelle il existe une chaîne pouvant avoir plusieurs dérivations à l'extrême gauche, tandis qu'une grammaire non ambiguë est une grammaire dépourvue de contexte pour laquelle chaque chaîne valide possède une dérivation à l'extrême gauche unique..
La grammaire fait référence aux règles syntaxiques dans les langues naturelles. En 1956, les informaticiens ont introduit un modèle mathématique de grammaire pour écrire en langage informatique. S'il est possible de dériver toutes les chaînes d'une langue en utilisant une certaine grammaire, il est 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 existe deux dérivations ou plus, cette grammaire est dite ambiguë. Pour une chaîne particulière, s'il existe une seule dérivation unique la plus à gauche, cette grammaire est dite grammaticale sans ambiguïté..
Zones clés couvertes
1. Quelle est la grammaire ambiguë
- Définition, exemple
2. Qu'est-ce que la grammaire sans ambiguïté?
- Définition, exemple
3. Différence entre grammaire ambiguë et non ambiguë
- Comparaison des différences clés
Mots clés
Grammaire ambiguë, grammaire non ambiguë
Quelle est la grammaire ambiguë
Une grammaire est dite ambiguë s’il existe deux dérivations ou plus 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
En remplaçant 'a' par le plus à gauche, S donnera ce qui suit.
S-> a + S
La substitution de S * S à S est la suivante.
S-> a + S * S
En remplaçant 'a' par le plus à gauche S donnera le résultat ci-dessous.
S -> a + a * S
En substituant 'b' au S donnera le résultat suivant.
S -> a + a * b
C'est la chaîne requise pour générer.
En utilisant l’autre règle de production, cela donnera
S -> S * S
Appliquez S + S à l'extrême gauche, S donnera les valeurs suivantes.
S -> S + S * S
Remplacer 'a' par le plus à gauche S,
S -> a + S * S
En remplaçant 'a' par le plus à gauche S,
S -> a + a * S
En substituant 'b' à S, vous obtiendrez le résultat suivant.
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 non ambiguë?
Dans une grammaire ambiguë, une certaine chaîne a une dérivation unique la plus à gauche. Se référer aux règles de production suivantes.
S -> L | a, L -> LS | S
Considérons la règle S -> L. Remplacez LS au lieu de L.
S -> LS
Substitut S, pour le premier L.
S -> S S
La substitution de 'a' au S le plus à gauche donnera le résultat ci-dessous.
S -> a S
En remplaçant "a" par S, on obtiendra ce qui suit.
S -> a a
Par conséquent, une chaîne a une dérivation unique la plus à gauche. Donc, c'est une grammaire sans ambiguïté.
Différence entre grammaire ambiguë et non ambiguë
Définition
Une grammaire ambiguë est une grammaire sans contexte pour laquelle il existe une chaîne pouvant avoir plusieurs arbres de dérivation ou d'analyse 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 la grammaire ambiguë, une chaîne peut avoir deux dérivations ou plus à l'extrême gauche, mais dans la grammaire non ambiguë, une chaîne possède une dérivation unique à l'extrême gauche..
Conclusion
La grammaire sans contexte peut être ambiguë ou non ambiguë. La différence entre grammaire ambiguë et non ambiguë réside dans le fait que la grammaire ambiguë est une grammaire sans contexte pour laquelle il existe une chaîne pouvant avoir plusieurs dérivations à l'extrême gauche, tandis qu'une grammaire non ambiguë est une grammaire sans contexte pour laquelle chaque chaîne valide possède une dérivation à gauche unique..
Référence:
1. «Grammaire ambiguë». Wikipedia, Wikimedia Foundation, 17 juillet 2018, disponible ici..
2. “Conception du compilateur | Ambiguous Grammar. ”GeeksforGeeks, 10 février 2018, disponible ici.
3. “Ambiguous Grammar”, Neso Academy, 29 mars 2017, disponible ici..
Courtoisie d'image:
1. “Leftmostderivations jaredwf” de Jaredwf sur Wikipedia anglais - Transféré de en.wikipedia à Commons par EdwardHades (Domaine public) via Commons Wikimedia
