Grammaire ambiguë - Ambiguous grammar

En informatique , une grammaire ambiguë est une grammaire sans contexte pour laquelle il existe une chaîne qui peut avoir plus d'une dérivation ou arbre d'analyse le plus à gauche , tandis qu'une grammaire non ambiguë est une grammaire sans contexte pour laquelle chaque chaîne valide a un unique le plus à gauche arbre de dérivation ou d'analyse. De nombreuses langues admettent à la fois des grammaires ambiguës et non ambiguës, tandis que certaines langues n'admettent que des grammaires ambiguës. Toute langue non vide admet une grammaire ambiguë en prenant une grammaire non ambiguë et en introduisant une règle dupliquée ou un synonyme (la seule langue sans grammaire ambiguë est la langue vide). Une langue qui n'admet que des grammaires ambiguës est appelée une langue intrinsèquement ambiguë , et il existe des langues sans contexte intrinsèquement ambiguës . Les grammaires sans contexte déterministes sont toujours sans ambiguïté et constituent une sous-classe importante de grammaires sans ambiguïté ; il existe cependant des grammaires non ambiguës non déterministes.

Pour les langages de programmation informatique , la grammaire de référence est souvent ambiguë, en raison de problèmes tels que le problème d' autre pendant . Si elles sont présentes, ces ambiguïtés sont généralement résolues en ajoutant des règles de priorité ou d'autres règles d'analyse contextuelle , de sorte que la grammaire globale de la phrase est sans ambiguïté. Certains algorithmes d'analyse (tels que les analyseurs Earley ou GLR ) peuvent générer des ensembles d'arbres d'analyse (ou « forêts d'analyse ») à partir de chaînes qui sont syntaxiquement ambiguës .

Exemples

Langue banale

L'exemple le plus simple est la grammaire ambiguë suivante pour le langage trivial, qui se compose uniquement de la chaîne vide :

A → A | ε

… ce qui signifie qu'une production peut être soit à nouveau elle-même, soit la chaîne vide. Ainsi, la chaîne vide a des dérivations les plus à gauche de longueur 1, 2, 3, et même de n'importe quelle longueur, selon le nombre de fois que la règle A → A est utilisée.

Ce langage a aussi la grammaire univoque, consistant en une seule règle de production :

A → ε

… ce qui signifie que la production unique ne peut produire que la chaîne vide, qui est la chaîne unique dans la langue.

De la même manière, toute grammaire pour une langue non vide peut être rendue ambiguë en ajoutant des doublons.

Chaîne unaire

Le langage régulier des chaînes unaires d'un caractère donné, disons 'a'(l'expression régulière a*), a la grammaire sans ambiguïté :

A → aA | ε

…mais a aussi la grammaire ambiguë :

A → aA | Aa | ε

Celles-ci correspondent à produire un arbre associatif à droite (pour la grammaire non ambiguë) ou à autoriser à la fois l'association à gauche et à droite. Ceci est détaillé ci-dessous.

Addition et soustraction

La grammaire sans contexte

A → A + A | A - A | une

est ambigu car il y a deux dérivations les plus à gauche pour la chaîne a + a + a :

     UNE → A + A      UNE → A + A
     → a + A      → A + A + A (le premier A est remplacé par A+A. Le remplacement du second A donnerait une dérivation similaire)
     → a + A + A      → a + A + A
     → a + a + A      → a + a + A
     → un + un + un      → un + un + un

Autre exemple, la grammaire est ambiguë car il existe deux arbres d'analyse pour la chaîne a + a − a :

Dérivations les plus à gauche jaredwf.svg

Le langage qu'il génère, cependant, n'est pas intrinsèquement ambigu ; ce qui suit est une grammaire non ambiguë générant le même langage :

A → A + a | A − a | une

Pendant d'autre

Un exemple courant d'ambiguïté dans les langages de programmation informatique est le problème d' autre pendant . Dans de nombreuses langues, l' instruction elsedans une instruction If–then(–else) est facultative, ce qui donne aux conditionnels imbriqués plusieurs façons d'être reconnus en termes de grammaire sans contexte.

Concrètement, dans de nombreuses langues, on peut écrire des conditionnels sous deux formes valides : la forme if-then et la forme if-then-else - en effet, rendant la clause else facultative :

Dans une grammaire contenant les règles

Statement → if Condition then Statement |
            if Condition then Statement else Statement |
            ...
Condition → ...

certaines structures de phrases ambiguës peuvent apparaître. L'expression

if a then if b then s else s2

peut être analysé comme

if a then begin if b then s end else s2

ou comme

if a then begin if b then s else s2 end

selon que le elseest associé au premier ifou au second if.

Ceci est résolu de diverses manières dans différentes langues. Parfois, la grammaire est modifiée pour qu'elle ne soit pas ambiguë, par exemple en exigeant une endifinstruction ou en la rendant elseobligatoire. Dans d'autres cas, la grammaire est laissée ambiguë, mais l'ambiguïté est résolue en rendant la grammaire globale de l'expression contextuelle, par exemple en associant an elseau plus proche if. Dans ce dernier cas, la grammaire est sans ambiguïté, mais la grammaire sans contexte est ambiguë.

Une grammaire sans ambiguïté aux multiples dérivations

L'existence de plusieurs dérivations de la même chaîne ne suffit pas à indiquer que la grammaire est ambiguë ; seules plusieurs dérivations les plus à gauche (ou, de manière équivalente, plusieurs arbres d'analyse) indiquent une ambiguïté.

Par exemple, la grammaire simple

S → A + A
A → 0 | 1

est une grammaire univoque pour le langage { 0+0, 0+1, 1+0, 1+1 }. Alors que chacune de ces quatre chaînes n'a qu'une seule dérivation la plus à gauche, elle a deux dérivations différentes, par exemple

S  A + A ⇒ 0 + A ⇒ 0 + 0

et

S ⇒ A + A ⇒ A + 0 ⇒ 0 + 0

Seule la première dérivation est la plus à gauche.

Reconnaître les grammaires ambiguës

Le problème de décision de savoir si une grammaire arbitraire est ambiguë est indécidable car on peut montrer qu'il est équivalent au problème de correspondance Post . Au moins, il existe des outils mettant en œuvre une procédure de semi-décision pour détecter l'ambiguïté des grammaires hors contexte.

L'efficacité de l'analyse grammaticale sans contexte est déterminée par l'automate qui l'accepte. Les grammaires déterministes sans contexte sont acceptées par les automates à refoulement déterministes et peuvent être analysées en temps linéaire, par exemple par l' analyseur LR . Il s'agit d'un sous-ensemble des grammaires sans contexte qui sont acceptées par l' automate à refoulement et peuvent être analysées en temps polynomial, par exemple par l'algorithme CYK . Les grammaires sans contexte non ambiguës peuvent être non déterministes.

Par exemple, la langue des palindromes de longueur paire sur l'alphabet de 0 et 1 a la grammaire sans contexte sans ambiguïté S → 0S0 | 1S1 | . Une chaîne arbitraire de ce langage ne peut pas être analysée sans lire d'abord toutes ses lettres, ce qui signifie qu'un automate à refoulement doit essayer des transitions d'état alternatives pour s'adapter aux différentes longueurs possibles d'une chaîne semi-analysée. Néanmoins, la suppression de l'ambiguïté de la grammaire peut produire une grammaire déterministe sans contexte et permettre ainsi une analyse plus efficace. Les générateurs de compilateur tels que YACC incluent des fonctionnalités permettant de résoudre certains types d'ambiguïté, par exemple en utilisant les contraintes de précédence et d'associativité.

Langages intrinsèquement ambigus

L'existence de langues intrinsèquement ambiguës a été prouvée avec le théorème de Parikh en 1961 par Rohit Parikh dans un rapport de recherche du MIT.

Alors que certaines langues sans contexte (l'ensemble de chaînes pouvant être générées par une grammaire) ont à la fois des grammaires ambiguës et non ambiguës, il existe des langues sans contexte pour lesquelles aucune grammaire sans contexte non ambiguë ne peut exister. Un exemple de langage intrinsèquement ambigu est l'union de avec . Cet ensemble est hors-contexte, puisque l'union de deux langages hors-contexte est toujours hors-contexte. Mais Hopcroft & Ullman (1979) donnent une preuve qu'il n'y a aucun moyen d'analyser sans ambiguïté les chaînes dans le sous-ensemble commun (non sans contexte) .

Voir également

Les références

  1. ^ Willem JM Levelt (2008). Une introduction à la théorie des langages formels et des automates . Éditions John Benjamins. ISBN 978-90-272-3250-2.
  2. ^ Scott, Elizabeth (1er avril 2008). "Analyse de style SPPF à partir des reconnaisseurs Earley" . Notes électroniques en informatique théorique . 203 (2) : 53-67. doi : 10.1016/j.entcs.2008.03.044 .
  3. ^ Tomita, Masaru. " Un algorithme d'analyse efficace sans contexte augmenté ." Linguistique informatique 13.1-2 (1987): 31-46.
  4. ^ Hopcroft, John ; Motwani, Rajeev ; Ullman, Jeffrey (2001). Introduction à la théorie des automates, aux langages et au calcul (2e éd.). Addison-Wesley. Théorème 9.20, pp. 405-406. ISBN 0-201-44124-1.
  5. ^ Axelsson, Roland; Heljanko, Keijo; Lange, Martin (2008). "Analyser les grammaires sans contexte à l'aide d'un solveur SAT incrémentiel" (PDF) . Actes du 35e Colloque international sur les automates, les langages et la programmation (ICALP'08), Reykjavik, Islande . Notes de cours en informatique . 5126 . Springer-Verlag. p. 410-422. doi : 10.1007/978-3-540-70583-3_34 .
  6. ^ Knuth, DE (juillet 1965). "Sur la traduction des langues de gauche à droite" (PDF) . Informations et contrôle . 8 (6) : 607-639. doi : 10.1016/S0019-9958(65)90426-2 . Archivé de l'original (PDF) le 15 mars 2012 . Consulté le 29 mai 2011 .
  7. ^ Hopcroft, John ; Motwani, Rajeev ; Ullman, Jeffrey (2001). Introduction à la théorie des automates, aux langages et au calcul (2e éd.). Addison-Wesley. p. 249-253. ISBN 0-201-44124-1.
  8. ^ Parikh, Rohit (janvier 1961). Dispositifs générateurs de langage . Rapport d'avancement trimestriel, Laboratoire de recherche en électronique, MIT.
  9. ^ p.99-103, Section 4.7

Remarques

Liens externes

  • dk.brics.grammar - un analyseur d'ambiguïté grammaticale.
  • CFGAnalyzer - outil d'analyse des grammaires sans contexte en ce qui concerne l'universalité du langage, l'ambiguïté et des propriétés similaires.