Grammaire ambigüe

Théorie des langages formels

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

modifier

Addition et soustraction

modifier

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

modifier

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

modifier

Exemple 1 — Le langage   est algébrique et inhéremment ambigu.

Chacun des langages   et   est algébrique. Le premier est par exemple engendré par la grammaire suivante :

S → Sc | T
T → aTb | ε

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

Les mots de   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[1]. D'autres exemples sont donnés dans le livre de Harrison[2] ou dans l'ouvrage de Carton[3]. 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ë.

Exemple 2 — Le langage de Goldstine est inhéremment ambigu.

C'est un exemple où cette méthode s'applique[3].

Exemple 3 — Le langage formé des mots  , où   et   sont des palindromes est inhéremment ambigu[4].

Alors que le langage des palindromes lui-même est inambigu.

Exemple 1' — Le langage des mots sur trois lettres  , et   formé des mots   tels que   ou   est inhéremment ambigu[4].

Ce langage est proche du premier exemple donné.

En résumé, les variantes de ces langages sont les suivants[6] :

Exemple 1" — Les langages   avec

  •   et  
  •   et  
  •   et  

sont algébriques et inhéremment ambigus.

Propriétés

modifier

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.

Propriété — Le problème suivant est indécidable : « Une grammaire donnée, est-elle ambiguë ? ».

La preuve donnée ci-dessous passe par le problème de correspondance de Post[7].

Degré d'ambiguïté

modifier

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.

Propriété — Il existe des langages inhéremment ambigus pour lesquels le degré d'ambiguïté de toute grammaire est infini[8].

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

Notes et références

modifier
  1. Hopcroft et Ullman 1969.
  2. Harrison 1978.
  3. a et b Carton 2014, sections 2.3.3 et 2.3.4.
  4. a b et c Berstel et Boasson 1990.
  5. Flajolet 1987.
  6. et Koechlin 2022.
  7. Hopcroft, Motwani et Ullman 2007.
  8. a et b Mateescu et Salomaa 1997 — Section 6.5 : « Ambiguity », p. 238-240.

Article connexe

modifier

Bibliographie

modifier
  • John E. Hopcroft et Jeffrey D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, (ISBN 0-201-02983-9, SUDOC 004772571).
  • Michael A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, , 594 p. (ISBN 0-201-02955-3, OCLC 266962302).
  • John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson Addison Wesley, , 3e éd., xvii+535 (ISBN 978-0-321-45536-9, 0201441241 et 0-321-45536-3)
  • Olivier Carton, Langages formels, calculabilité et complexité, Paris, Vuibert, coll. « Vuibert sup maths », , 256 p. [détail de l’édition] (ISBN 978-2-311-01400-6, présentation en ligne)
  • Alexandru Mateescu et Arto Salomaa, « Aspects of Classical Language Theory », dans G. Rozenberg et A. Salomaa (éditeurs), Handbook of Formal Languages, vol. 1 : Word, Language, Grammar, Springer,
  • Jean Berstel et Luc Boasson, « Context-Free Languages », dans G. Rozenberg, A. Salomaa (éditeurs), Handbook of Theoretical Computer Science, vol. B : Formal Models and Sematics, Elsevier et MIT Press, (ISBN 0-444-88074-7), p. 59-102
  • Philippe Flajolet, « Analytic models and ambiguity of context-free languages », Theoret. Comput. Sci., vol. 49,‎ , p. 283-309
  • Florent Koechlin, « New analytic techniques for proving the inherent ambiguity of context-free languages », dans 42e IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, coll. « Leibniz International Proceedings in Informatics (LIPIcs) » (no 250), (ISBN 978-3-95977-261-7, DOI 10.4230/LIPIcs.FSTTCS.2022.41, lire en ligne), p. 41:1–41:22.