Wikipédia

Grammaire non contextuelle déterministe

En informatique théorique, et particulièrement dans la théorie des grammaires formelles, les grammaires context-free déterministes ( DCFG ) ou grammaires non contextuelles déterministes sont un sous-ensemble des grammaires non contextuelles. Ce sont les grammaires non contextuelles qui peuvent être dérivées d'automates à pile déterministes, et ils engendrent les langages non contextuels déterministes. Les DCFG sont toujours inambigües et ils constituent une sous-classe importante des grammaires non contextuelles ; il existe cependant des CFG inambigües qui ne sont pas déterministes.

Les DCFG sont d'un grand intérêt pratique, car ils peuvent être analysés en temps linéaire et en fait un analyseur peut être généré automatiquement à partir de la grammaire par un générateur d'analyseurs. Ils sont donc largement utilisés en informatique. Diverses formes restreintes des DCFG peuvent être analysées par des analyseurs plus simples et moins gourmands en ressources, et sont donc souvent utilisées. Ces classes de grammaires sont désignées par le type d'analyseur qui les analyse, et les exemples paradigmatiques sont LALR, SLR et LL.

Histoire modifier

Dans les années 1960, des recherches théoriques en informatique sur les expressions régulières et les automates finis ont conduit à établir que les grammaires non contextuelles sont équivalentes aux automates à pile[1],[2],[3]. Les premiers langages de programmation étaient en cours de développement à l'époque (voir histoire des langages de programmation ) et l'écriture de compilateurs était difficile. L'utilisation de grammaires non contextuelles a permis d'automatiser la partie d'analyse du compilateur. Les grammaires non contextuelles déterministes étaient particulièrement utiles car elles pouvaient être analysées séquentiellement par un automate à pile déterministe, ce qui était une exigence en raison des contraintes de mémoire de l'ordinateur[4]. En 1965, Donald Knuth a conçu les analyseurs LR (k) et a prouvé qu'il existe une grammaire LR (k) pour chaque langage déterministe non contextuel[5]. Cet analyseur nécessitait encore beaucoup de mémoire. En 1969, Frank DeRemer a introduit les analyseurs LALR et simple LR, tous deux basés sur l'analyseur LR et ayant un besoin en mémoire ontsidérablement plus petit au prix d'une moindre puissance de reconnaissance du langage. L'analyseur LALR est l'alternative la plus efficace[6]. Ces deux analyseurs sont depuis largement utilisés dans les compilateurs de nombreux langages informatiques. Des recherches récentes ont identifié des méthodes par lesquelles des analyseurs LR canoniques peuvent être implémentés avec des exigences en tables considérablement réduites par rapport à l'algorithme de construction de tables de Knuth[7].

Références modifier

  1. ↑ Noam Chomsky, « Context Free Grammars and Pushdown Storage », Quarterly Progress Report, MIT Research Laboratory in Electronics, vol. 65,‎ , p. 187–194
  2. ↑ R. James Evey, « Application of Pushdown-Store Machines », 1963 AFIPS Proceedings of the Fall Joint Computer Conference,‎ , p. 215–227
  3. ↑ Marcel-Paul Schützenberger, « On Context-Free Languages and Push-Down Automata », Information and Control, vol. 6,‎ , p. 246–264 (DOI 10.1016/s0019-9958(63)90306-1)
  4. ↑ Arto Salomaa, Derrick Wood et Sheng Yu (éditeurs), A Half-Century of Automata Theory, World Scientific Publishing, , p. 38–39
  5. ↑ Donald E. Knuth, « On the translation of languages from left to right », Information and Control, vol. 8, no 6,‎ , p. 607–639 (DOI 10.1016/S0019-9958(65)90426-2, lire en ligne [archive du ], consulté le )
  6. ↑ Franklin L. DeRemer, « Practical Translators for LR(k) languages » [archive du ], MIT, PhD Dissertation,
  7. ↑ Xin Chen, Measuring and extending LR(1) parsing, University of Hawaii PhD dissertation, 2009.

Voir également modifier

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Grammaire_non_contextuelle_déterministe&oldid=198041799 ».