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.

Définitions formelles

Une grammaire algébrique est composée :

  • d'un alphabet fini de symboles non terminaux ou variables ;
  • d'un alphabet fini , disjoint de , de symboles terminaux ou lettres terminales ;
  • d'un élément de appelé l'axiome ;
  • d'un ensemble fini de règles de dérivations ou productions.

Une règle est en général écrite sous la forme . La variable et le mot sont appelés respectivement le membre gauche et le membre droit de la règle. On étend cette notation et on écrit lorsque résulte de par le remplacement, dans , d'un membre gauche de règle (qui est donc une variable) par son membre droit, donc s'il existe des mots et une règle telle que et . On note la fermeture réflexive et transitive de cette relation. Lorsque

,

on dit que dérive en .

Le langage engendré par la grammaire , noté , est l'ensemble des mots terminaux (ne contenant plus de variables) qui dérivent de l'axiome , soit

.

On appelle langage algébrique ou langage non contextuel un langage qui peut être engendré par une grammaire algébrique. Le « langage élargi » engendré par la grammaire est constitué de tous les mots de qui dérivent de l'axiome , qu'ils contiennent ou non des variables.

Other Languages