Ê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 non contextuelle déterministe
Résumé
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.
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. 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. 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.
À 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.