Grammaire ambigüe

Modèle:Article principal En informatique théorique et en théorie des langages, une grammaire ambiguë ou ambigüe est une grammaire algébrique qui admet un mot avec deux dérivations gauches distinctes ou — de manière équivalente — deux arbres de dérivation distincts. L'ambiguïté ou l'inambiguïté est une propriété des grammaires, et non des langages. De nombreux langages admettent à la fois des grammaires ambiguës et inambigües, alors que d'autres ne possèdent que des grammaires ambiguës. Un langage pour lequel toutes les grammaires sont ambiguës est appelé inhéremment ambigu (ou intrinsèquement ambigu), les autres sont appelés langages inambigus.

La grammaire de référence de langages de programmation est parfois ambigüe à cause de constructions qui conduisent à des problèmes comme le problème du dangling else. De telles ambiguïtés sont généralement levées en ajoutant des règles de précédence ou d'autres règles, contextuelles celles-là, qui rendent la grammaire finale inambigüe.

Exemples

Addition et soustraction

La grammaire algébrique définie par la règle suivante

A → A + A | A - A | a

est ambiguë parce que le mot a + a - a possède deux dérivations gauches distinctes :

A → A - A → A + A - A → a + A - A → a + a - A → a + a - a

et

A → A + A → a + A → a + A - A → a + a - A → a + a - a

Dans la première, c'est la règle A → A + A qui est utilisée dans la deuxième étape ; dans la seconde, c'est au contraire la règle A → a qui est employée.

Ces dérivations donnent deux arbres de dérivation distincts :

Le langage lui-même est inambigu (c'est-à-dire n'est pas inhéremment ambigu) puisqu'il est engendré par exemple par la grammaire inambiguë que voici :

A → A + a | A − a | a

Palindromes

Le langage des palindromes est inambigu. Il est engendré (sur l'alphabet a,b par exemple), par la grammaire inambiguë, définie par la règle suivante :

A → aAa | bAb | a | b | ε

Langages algébriques inhéremment ambigus

Chacun des langages $L_1=\{a^m{b}^m{c}^n|m,n\ge 0\}$ et $L_2=\{a^m{b}^n{c}^n|m,n\ge 0\}$ est algébrique. Le premier est par exemple engendré par la grammaire suivante :

S → Sc | T

T → aTb | ε

$L$ est algébrique comme réunion de ces deux langages algébriques.

Les mots de $L_1\cap L_2$ posent problème. On peut prouver, à l'aide du lemme d'Ogden (la démonstration est faite sur la page correspondante), qu'il n'existe pas de grammaire inambiguë pour le langage. D'autres exemples sont donnés dans le livre de Harrison ou dans l'ouvrage de Carton. Une autre méthode pour démontrer l'ambiguïté inhérente d'un langage est de passer par la fonction génératrice qui énumère le nombre de mots de longueur donnée du langage. D'après le théorème de Chomsky-Schützenberger, cette série est algébrique pour un langage engendré par une grammaire inambiguë. Modèle:Théorème C'est un exemple où cette méthode s'applique. Modèle:Théorème Alors que le langage des palindromes lui-même est inambigu. Modèle:Théorème Ce langage est proche du premier exemple donné. Modèle:Démonstration

En résumé, les variantes de ces langages sont les suivants : Modèle:Théorème

Propriétés

Les langages algébriques déterministes possèdent toujours une grammaire inambiguë. Ils constituent une sous-classe stricte de la famille des langages inambigus. Le langage des palindromes ci-dessus fournit un exemple de langage algébrique non déterministe mais qui est inambigu.

Modèle:Théorème La preuve donnée ci-dessous passe par le problème de correspondance de Post.

Modèle:Démonstration/débutOn réduit le problème de correspondance de Post au problème de l'ambiguïté.

Soit Modèle:Math une instance du problème de correspondance de Post (PCP) sur un alphabet Modèle:Math. On introduit un nouvel alphabet Modèle:Math formé de Modèle:Math lettres n'appartenant pas à Modèle:Math. On définit, sur l'alphabet Modèle:Math les deux langages :

Modèle:Math

Modèle:Math.

L'instance du PCP Modèle:Math admet une solution si et seulement si Modèle:Math. Le langage Modèle:Math est engendré par la grammaire avec les règles suivantes :

Modèle:Math

Il est facile de voir que cette grammaire est ambiguë si et seulement si Modèle:Math ; et que cette intersection est ne se réduit pas au mot vide si et seulement si Modèle:Math admet une solution. La réduction est le calcul de la grammaire ci-dessus depuis l'instance du PCP Modèle:Math. Ceci prouve que le problème de l'ambiguïté est indécidable.

Degré d'ambiguïté

Le degré d'ambiguïté d'un mot w engendré par une grammaire est le nombre de dérivations gauches, différentes, qui permettent d'aboutir au mot w. Le degré d'ambiguïté d'une grammaire est le maximum (éventuellement infini) des degrés des mots engendrés par cette grammaire. Modèle:Théorème

La décidabilité de l'énoncé suivant est un problème ouvert (en 1977) : « Étant donnée une grammaire, son degré d'ambiguité est-il fini ? »

Article connexe

• Amphibologie

Bibliographie

• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage
• Modèle:Carton2
• Modèle:Chapitre
• Modèle:Chapitre
• Modèle:Article
• Modèle:Chapitre.