Pourquoi les grammaires ambiguës sont-elles mauvaises?

Je comprends que s'il existe 2 ou plusieurs arbres de dérivation gauche ou droit, alors la grammaire est ambiguë, mais je ne peux pas comprendre pourquoi elle est si mauvaise que tout le monde veut s'en débarrasser.

Considérez la grammaire suivante pour les expressions arithmétiques:

Selon celui de gauche, nous devrions interpréter $a-b-c$ comme $(a-b)-c$ , qui est l'interprétation habituelle. Selon celui de droite, nous devrions l'interpréter comme $a-(b-c) = a-b+c$ , ce qui n'est probablement pas ce qui était prévu.

Lors de la compilation d'un programme, nous voulons que l'interprétation de la syntaxe soit sans ambiguïté. La façon la plus simple de faire respecter cela est d'utiliser une grammaire sans ambiguïté. Si la grammaire est ambiguë, nous pouvons fournir des règles de départage, comme la priorité des opérateurs et l'associativité. Ces règles peuvent être exprimées de manière équivalente en rendant la grammaire non ambiguë d'une manière particulière.

Analyser les arbres générés à l'aide du générateur d'arbres syntaxiques .

Contrairement aux autres réponses existantes [ 1 , 2 ], il existe en effet un champ d'application, où les grammaires ambiguës sont utiles . Dans le domaine du traitement du langage naturel (NLP), lorsque vous voulez analyser le langage naturel (NL) avec des grammaires formelles, vous avez le problème que NL est intrinsèquement ambigu à différents niveaux [adapté de Koh18, ch. 6.4]:

• Ambuigité syntaxique:

  Peter a poursuivi l'homme dans la voiture de sport rouge

  Peter ou l'homme était-il dans la voiture de sport rouge?

• Ambuigité sémantique:

  Peter est allé à la banque

  Une banque pour s'asseoir ou une banque pour retirer de l'argent?

• Ambuigité pragmatique:

  Deux hommes portaient deux sacs

  Portaient-ils les sacs ensemble ou chaque homme portait-il deux sacs?

Différentes approches pour la PNL traitent différemment le traitement en général et en particulier ces ambiguïtés. Par exemple, votre pipeline peut ressembler à ceci:

1. Analyser NL avec une grammaire ambiguë
2. Pour chaque AST résultant: exécuter la génération de modèle pour générer des significations sémantiques ambiguës et exclure les ambiguïtés syntaxiques impossibles de l'étape 1
3. Pour chaque modèle résultant: enregistrez-le dans votre cache.

Vous faites ce pipeline pour chaque phrase. Plus il y a de texte, par exemple, dans le même livre que vous traitez, plus vous pouvez exclure les modèles superflus impossibles, qui ont survécu jusqu'à l'étape 3, des phrases précédentes.

Contrairement au langage de programmation, nous pouvons abandonner l'exigence que chaque phrase NL ait une sémantique précise. Au lieu de cela, nous pouvons simplement tenir en compte plusieurs modèles sémantiques possibles tout au long de l'analyse de textes plus grands. De temps en temps, des informations ultérieures nous aident à écarter les ambiguïtés précédentes.

Si vous voulez vous salir les mains avec des analyseurs capables de produire plusieurs dérivations pour une grammaire ambiguë, jetez un œil au framework grammatical . De plus, [Koh18, ch. 5] a une introduction montrant quelque chose de similaire à mon pipeline ci-dessus. Notez cependant que puisque [Koh18] sont des notes de cours, les notes pourraient ne pas être faciles à comprendre par elles-mêmes sans les cours.

Les références

[Koh18]: Michael Kohlhase. "Logic-Based Natural Language Processing. Winter Semester 2018/19. Lecture Notes." URL: https://kwarc.info/teaching/LBS/notes.pdf . URL de la description du cours: https://kwarc.info/courses/lbs/ (en allemand)

[Koh18, ch. 5]: Voir le chapitre 5, "Implémentation de fragments: cadres grammaticaux et logiques", dans [Koh18]

[Koh18, ch. 6.4] Voir le chapitre 6.4, "Le rôle de calcul des ambiguïtés", dans [Koh18]

Même s'il existe un moyen bien défini de gérer l'ambiguïté (les expressions ambiguës sont des erreurs de syntaxe, par exemple), ces grammaires posent toujours problème. Dès que vous introduisez une ambiguïté dans une grammaire, un analyseur ne peut plus être sûr que la première correspondance qu'il obtient est définitive. Il doit continuer à essayer toutes les autres façons d'analyser une déclaration, pour écarter toute ambiguïté. Vous n'avez pas non plus affaire à quelque chose de simple comme un langage LL (1), vous ne pouvez donc pas utiliser un analyseur simple, petit et rapide. Votre grammaire comporte des symboles qui peuvent être lus de plusieurs façons, vous devez donc être prêt à faire beaucoup de retours en arrière.

Dans certains domaines restreints, vous pourriez être en mesure de prouver que toutes les manières possibles d'analyser une expression sont équivalentes (par exemple, car elles représentent une opération associative). (a + b) + c = a + (b + c).

Est-ce que IF a THEN IF b THEN x ELSE ymoyenne

IF a THEN
    IF b THEN
        x
    ELSE
        y

ou

IF a THEN
    IF b THEN x
ELSE
    y

? AKA le problème de balancer autrement .

Prenez l'analyse la plus vexante en C ++ par exemple:

bar foo(foobar());

S'agit-il d'une déclaration foode fonction de type bar(foobar())(le paramètre est un pointeur de fonction renvoyant a foobar), ou d'une déclaration foode variable de type intet initialisée avec une valeur par défaut initialisée foobar?

Ceci est différencié dans les compilateurs en supposant le premier sauf si l'expression à l'intérieur de la liste de paramètres ne peut pas être interprétée comme un type.

lorsque vous obtenez une expression si ambiguë, le compilateur a 2 options

1. supposons que l'expression est une dérivation particulière et ajoutez un peu d'ambiguïté à la grammaire pour permettre à l'autre dérivation d'être exprimée.

2. erreur et exiger la désambiguïsation de toute façon

Le premier peut tomber naturellement, le second nécessite que le programmeur du compilateur connaisse l'ambiguïté.

Si cette ambiguïté reste non détectée, il est possible que 2 compilateurs différents utilisent par défaut des dérivations différentes pour cette expression ambiguë. Menant à un code non portable pour des raisons non évidentes. Ce qui amène les gens à supposer que c'est un bogue dans l'un des compilateurs alors qu'il s'agit en fait d'un défaut dans la spécification du langage.

Je pense que la question contient une hypothèse qui n'est au mieux que limite.

Dans la vraie vie, il est assez courant de simplement vivre avec des grammaires ambiguës, tant qu'elles ne sont pas (pour ainsi dire) trop ambiguës.

Par exemple, si vous examinez les grammaires compilées avec yacc (ou similaire, comme le bison ou le byacc), vous constaterez que plusieurs produisent des avertissements sur les "conflits de décalage / réduction N" lorsque vous les compilez. Quand yacc rencontre un conflit de décalage / réduction, cela signale une ambiguïté dans la grammaire.

Un conflit de changement / réduction, cependant, est généralement un problème assez mineur. Le générateur d'analyseur résoudra le conflit en faveur du «décalage» plutôt que de la réduction. La grammaire est parfaitement bien si c'est ce que vous voulez (et cela semble fonctionner parfaitement bien dans la pratique).

Un conflit de décalage / réduction survient généralement dans un cas de cet ordre général (en utilisant des majuscules pour les non-terminaux et des minuscules pour les terminaux):

A -> B | c
B -> a | c

Lorsque nous rencontrons un c, il y a une ambiguïté: devons-nous analyser le cdirectement comme un A, ou devons-nous l'analyser comme un B, qui à son tour est un A? Dans un cas comme celui-ci, yacc et autres choisiront la route la plus simple / la plus courte, et analyseront cdirectement la route en tant que A, plutôt que de suivre la route c-> B-> A. Cela peut être faux, mais si c'est le cas, cela signifie probablement que vous avez une erreur très simple dans votre grammaire, et vous ne devriez pas du tout autoriser l' coption comme possibilité A.

Maintenant, en revanche, nous pourrions avoir quelque chose de plus comme ceci:

A -> B | C
B -> a | c
C -> b | c

Maintenant, lorsque nous rencontrons un, cnous avons un conflit entre le fait de traiter le ccomme un Bou un C. Il y a beaucoup moins de chances qu'une stratégie de résolution automatique des conflits choisisse ce que nous voulons vraiment. Ni l'un ni l'autre n'est un "changement" - les deux sont des "réductions", c'est donc un "réduire / réduire le conflit" (que ceux qui sont habitués au yacc et autres reconnaissent généralement comme un problème beaucoup plus important qu'un conflit de décalage / réduction).

Donc, même si je ne suis pas sûr, j'irais jusqu'à dire que quiconque accueille vraiment l' ambiguïté dans sa grammaire, dans au moins certains cas, c'est suffisamment mineur pour que personne ne s'en soucie vraiment. Dans l'abstrait, ils pourraient aimer l'idée de lever toute ambiguïté - mais pas assez pour toujours le faire. Par exemple, une petite grammaire simple qui contient une ambiguïté mineure peut être préférable à une grammaire plus grande et plus complexe qui élimine l'ambiguïté (surtout lorsque vous entrez dans le domaine pratique de la génération effective d'un analyseur syntaxique à partir de la grammaire et que la grammaire produit un analyseur qui ne fonctionnera pas sur votre machine cible).