Grammaire non contextuelle déterministe
De Wikipedia, l'encyclopédie encyclopedia
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.