Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Grammaire ambigüe
Résumé
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.
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 :
Leftmostderivations jaredwf.svg|400px
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
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 | ε
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique