Grammaire non contextuelle

En linguistique et en informatique théorique, une grammaire algébrique, ou grammaire non contextuelle, aussi appelée grammaire hors-contexte ou grammaire « context-free » est une grammaire formelle dans laquelle chaque règle de production est de la forme

est un symbole non terminal et est une chaîne composée de terminaux et/ou de non-terminaux. Le terme « non contextuel » provient du fait qu'un non terminal peut être remplacé par , sans tenir compte du contexte où il apparaît. Un langage formel est non contextuel (ou hors contexte, ou encore algébrique) s'il existe une grammaire non contextuelle qui l'engendre.

Les grammaires algébriques sont suffisamment puissantes pour décrire la partie principale de la syntaxe de la plupart des langages de programmation, avec au besoin quelques extensions. La forme de Backus-Naur est la notation la plus communément utilisée pour décrire une grammaire non contextuelle décrivant un langage de programmation. Dans la hiérarchie de Chomsky, ces grammaires sont de type 2.

Si on trouve plusieurs termes pour nommer une grammaire algébrique, c'est que le terme anglais « context-free » est malcommode à traduire. Tous les termes donnés plus haut sont employés et équivalents.

Other Languages