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

$X\to \alpha$

où $X$ est un symbole non terminal et $\alpha$ est une chaîne composée de terminaux et/ou de non-terminaux. Le terme « non contextuel » provient du fait qu'un non terminal $X$ peut être remplacé par $\alpha$, 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 $G$ est composée

• d'un alphabet fini $V$ de symboles non terminaux ou variables
• d'un alphabet fini $A$, disjoint de $V$, de symboles terminaux ou lettres terminales
• d'un élément $S$ de $V$ appelé l'axiome
• d'un ensemble fini ${\mathcal {P}}\subset V\times (V\cup A)^{*}$de règles de dérivations ou productions.

Une règle $(X,\alpha )\,$ est en général écrite sous la forme $X\to \alpha$. La variable $X$ et le mot $\alpha$ sont appelés respectivement le membre gauche et le membre droit de la règle. On étend cette notation et on écrit $u\to v$ lorsque $v$ résulte de $u$ par le remplacement, dans $u$, d'un membre gauche de règle (qui est donc une variable) par son membre droit, donc s'il existe des mots $x,y$ et une règle $X\to \alpha$ telle que $u=xXy$ et $v=x\alpha y$. On note ${\xrightarrow {*}}$ la fermeture réflexive et transitive de cette relation. Lorsque $u{\xrightarrow {*}}v$, on dit que $u$ dérive en $v$.

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

$L(G)=\{w\in A^{*}\mid S{\xrightarrow {*}}w\}.$

Exemples

Exemple 1

Voici une grammaire algébrique simple :

$S\to aSb\mid \varepsilon$

La barre verticale sert à grouper les règles qui ont le même symbole non terminal en membre gauche, et $\varepsilon$ dénote le mot vide. Cette grammaire engendre le langage : $\{a^{n}b^{n}\mid n\geq 0\}$ qui n'est pas un langage rationnel.

Exemple 2

Voici une grammaire algébrique qui engendre les expressions arithmétiques en trois variables $x$, $y$ et $z$, correctement parenthésées :

$S\to x\mid y\mid z\mid S+S\mid S-S\mid S*S\mid S/S\mid (S)$

Cette grammaire peut par exemple engendrer $(x+y)*x-z*y/(x+x)$ .

Exemple 3

La grammaire suivante engendre le langage composé des mots en $a$ et en $b$, et dont le nombre de $a$ est différent du nombre de $b$ :

$S\to U\mid V$

$U\to TaU\mid TaT$

$V\to TbV\mid TbT$

$T\to aTbT\mid bTaT\mid \varepsilon$

$T$ produit les mots ayant le même nombre de $a$ et de $b$, $U$ produit les mots avec plus de $a$ que de $b$, et $V$ produit les mots ayant moins de $a$ que de $b$.

Exemple 4

Les langages de Dyck ou langages de parenthésages corrects sont des langages algébriques.

Un autre exemple

Les grammaires non contextuelles ne sont pas limitées aux langages formels en mathématiques. Le linguiste indien Pānini décrivit le sanskrit avec une grammaire non contextuelle.

Dérivations et arbres de dérivation

Il existe deux manières de décrire comment un mot a été engendré à partir d'une grammaire donnée, la première consiste à lister la suite des applications des règles, la deuxième synthétise cette liste en un arbre, appelé arbre de dérivation.

La première méthode liste la suite des mots (en commençant par le symbole de départ, l'axiome, et en finissant par le mot recherché). Les mots intermédiaires, contenant des variables, sont parfois appelés proto-phrases (sentential forms en anglais) ou mot du langage étendu. En plus de ces mots, on liste les règles appliquées pour passer d'un mot au suivant. Si de plus on utilise la stratégie consistant à « toujours remplacer le non-terminal le plus à gauche », alors il suffit en fait de donner la liste des règles appliquées. La dérivation obtenue s'appelle une dérivation gauche du mot. Par exemple, pour la grammaire suivante :

$(1)\quad S\to S+S$

$(2)\quad S\to a$

la chaîne « $a+a+a$ » admet une dérivation gauche représentée par la liste [ (1), (1), (2), (2), (2) ]. De manière analogue, une dérivation droite est la liste des règles employées lorsque l'on remplace systématiquement le non-terminal le plus à droite en premier. Dans l'exemple précédent, une dérivation droite est [ (1), (2), (1), (2), (2)].

La distinction entre dérivation gauche et dérivation droite est importante en pratique car elle permet dans la plupart des analyseurs syntaxiques de tenir compte des priorités des opérations. Les analyseurs LL produisent des dérivations gauches, et les analyseurs LR des dérivations droite (en fait des réductions, c'est-à-dire déterminent d'abord la dernière règle appliquée).

Une dérivation impose de plus une structure hiérarchique de la chaîne dérivée. La structure de la chaîne « a + a + a », par exemple, est, pour une dérivation gauche :

S→S+S (1)

S→S+S+S (1)

S→a+S+S (2)

S→a+a+S (2)

S→a+a+a (2)

{ { { a }_S + { a }_S }_S + { a }_S }_S

où { ... }_S indique une sous-chaîne reconnue comme appartenant à S. Cette hiérarchie peut aussi être vue comme un arbre :

           S
          /|\
         / | \
        /  |  \
       S   +   S
      /|\      |
     / | \     |
    S  +  S    a 
    |     |
    a     a 

Cet arbre est appelé arbre de dérivation, arbre d'analyse ou arbre de syntaxe concrète (en opposition à l'arbre syntaxique abstrait) de la chaîne. La dérivation gauche présentée plus haut et la dérivation droite définissent le même arbre de dérivation. Ceci est normal car les deux dérivations sont deux parcours en profondeur de l'arbre de dérivation, le premier obtenu en choisissant le nœud le plus à gauche, le deuxième en choisissant le nœud le plus à droite. Il y a bijection entre les dérivations gauches et les dérivations droites.

Dans notre exemple, il y a une autre dérivation gauche possible

S→ S + S (1)vS→ a + S (2)

S→ a + S + S (1)

S→ a + a + S (2)

S→ a + a + a (2)

qui définit l'arbre syntaxique suivant :

           S 
          /|\
         / | \
        /  |  \
       S   +   S
       |      /|\
       |     / | \
       a    S  +  S
            |     |
            a     a 

Une grammaire est ambiguë lorsqu'au moins un mot engendré par la grammaire possède au moins deux arbres de dérivation distincts, sinon, c'est une grammaire inambiguë ou non ambiguë. Un langage est inambigu ou non ambigu s'il possède une grammaire inambiguë. Il est appelé inhéremment ambigu si toutes les grammaires qui l'engendrent sont ambiguës.

Un exemple de langage inhéremment ambigu est le langage:

$\{a^{n}b^{n}c^{m}\mid n,m\geq 0\}\cup \{a^{n}b^{m}c^{m}\mid n,m\geq 0\}$

Dans toutes les grammaires, les mots $a^{n}b^{n}c^{n}$ ont deux dérivations distinctes. La preuve se fait au moyen du lemme d'Ogden.

Dans l'analyse syntaxique de mots engendrés par une grammaire ambiguë, il faut faire usage de techniques d'analyse non déterministe et/ou de techniques adaptées (backtracking, règles de désambiguïsation,...)

Formes normales

Un langage algébrique peut être engendré par des grammaires algébriques de formes variées. Deux grammaires sont dites équivalentes lorsqu'elles engendrent le même langage.

Grammaire réduite et propre

• Une grammaire réduite est une grammaire où toute variable est utile, c'est-à-dire figure dans au moins une dérivation d'un mot du langage. On peut toujours réduire une grammaire, c'est-à-dire supprimer, de manière effective, les variables inutiles.
• Une grammaire est propre lorsqu'aucun membre droit de règle n'est égal au mot vide ou à une variable. On peut rendre une grammaire propre, à condition que le langage engendré ne contienne pas le mot vide, ou alors autoriser la seule $\varepsilon$-règle $S\to \varepsilon$, où $S$ est l'axiome, avec la condition supplémentaire que $S$ ne figure dans aucun membre droit de règle.

Forme normale de Chomsky

Une grammaire est en forme normale de Chomsky si toutes ses règles sont de l'une des formes

$X\to YZ$
$X\to a$

où $X,Y,Z$ sont des variables, et $a$ est une lettre. Toute grammaire peut être mise en forme normale de Chomsky, au mot vide près. Cette forme normale sert par exemple dans la définition d'un algorithme d'analyse syntaxique: c'est l'algorithme CYK. Il permet de décider, en temps polynomial, si un mot est dans le langage généré par cette grammaire.

Forme normale de Greibach

Une grammaire est en forme normale de Greibach si les membres droits de toutes ses règles commencent par une lettres, et ne sont suivies éventuellement que par des variables, formellement

$X\to aY_{1}\cdots Y_{k}$
$X\to c$

où $X,Y_{1},\ldots ,Y_{k}$ sont des variables et $a,b$ sont des lettres. Par exemple, la grammaire

$S\to aSS\mid b$

qui engendre le langage de Lukasiewicz est en forme normale de Greibach. La forme quadratique de Greibach impose de plus qu'il y ait au plus deux variables dans chaque membre droit de règle (ce qui est le cas ici). Toute grammaire peut être mise sous forme quadratique de Greibach, au mot vide près.

Forme normale bilatère de Greibach

La forme normale de Greibach bilatère est une forme bilatère de la forme normale de Greibach: les membres droits des règles sont soit des lettres terminales, soit commencent et finissent par des lettres terminales et ne contiennent au plus deux variables. Toutes les règles sont de la forme

$X\to aY_{1}\cdots Y_{k}b$
$X\to c$

où $X,Y_{1},\ldots ,Y_{k}$ sont des variables et $a,b,c$ sont des lettres. Toute grammaire peut être mise sous forme normale bilatère, et on peut même la supposer sous forme quadratique, c'est-à-dire que $k\leq 2$ dans ces règles.

Grammaires étendues

On rencontre, surtout dans les applications, une forme de grammaires étendues: les membres droits des règles peuvent être des expressions rationnelles. Il en est ainsi dans la forme normale de Backus étendue. Plus précisément, notons $P(X)$ l'ensemble des membres droits de règles dont le membre gauche est $X$.

• Dans la définition usuelle des grammaires algébriques, les ensembles $P(X)$ sont finis pour toute variable $X$.
• Dans les grammaires étendues, les ensembles $P(X)$ sont des langages rationnels qui sont donnés par des expressions régulières.
• Dans une généralisation de ces grammaires, les ensembles $P(X)$ sont eux-mêmes des langages algébriques.

On peut montrer que les deux extensions des grammaires engendrent toujours des langages algébriques.

Analyse syntaxique

Les grammaires algébriques sont suffisamment simples pour permettre la création d'analyseurs syntaxiques efficaces (contrairement aux grammaires contextuelles) en temps polynomial en la taille de la grammaire et la longueur du mot à analyser. Un tel analyseur a pour tâche de déterminer, pour un mot donné, si et comment il peut être engendré à partir de la grammaire. L'algorithme CYK et l'analyseur d'Earley sont des exemples de tels algorithmes. Les analyseurs LR et les analyseurs LL opèrent en temps linéaire en la longueur du mot à analyser, et sont employés dans la pratique. En revanche, ils ne permettent d'analyser que des familles plus restrictives de grammaires algébriques.

Bibliographie

Par sa nature fondamentale, de nombreux ouvrages d'informatique théorique contiennent au moins une section sur les grammairnes algébriques. Plusieurs livres ont également été traduits en français.

Ouvrages en français

• Alfred Aho, Monica Lam, Ravi Sethi et Jeffrey Ullman, Compilateurs : principes, techniques et outils : Avec plus de 200 exercices, Pearson, 2007, 2^e éd., 928 p. (ISBN 9782744070372 et 2744070378)
• Pierre Wolper, Introduction à la calculabilité, Dunod, 2006, 3^e éd. (ISBN 2-10-049981-5).
• Jean-Michel Autebert, Langages algébriques, Masson, 1987 (ISBN 978-2-225-81087-9)
• Jean-Michel Autebert et Luc Boasson, Transductions rationnelles : Application aux Langages Algébriques, Masson, 1988 (ISBN 978-2-225-81504-1)
• Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)
• Jean-Michel Autebert, Jean Berstel et Luc Boasson, « Context-free languages and pushdown automata », dans G. Rozenberg, A. Salomaa (éditeurs), Handbook of Formal Languages, vol. 1 : Word, Language, Grammar, Springer Verlag, 1997 (ISBN 978-3540604204), p. 111-174

Ouvrage en allemand

• (de) Katrin Erk et Lutz Priese, Theoretische Informatik : eine umfassende Einführung, Berlin, Springer, 2008 (ISBN 9783540763192, OCLC 244015158).

Ouvrages en anglais

• (en) Seymour Ginsburg, The Mathematical Theory of Context Free Languages, McGraw-Hill, 1966, ix+ 232 — Le premier livre sur les langages algébriques.
• (en) Alfred V. Aho et Jeffrey D. Ullman, The theory of parsing, translation, and compiling, vol. 1 : Parsing, Englewood Cliffs, NJ, Prentice-Hall, 1972, xii+543 (ISBN 0-13-914556-7)
• (en) Alfred V. Aho et Jeffrey D. Ullman, The theory of parsing, translation, and compiling, vol. 2 : Compiling, Englewood Cliffs, NJ, Prentice-Hall, 1973, xii+460 (ISBN 0-13-914564-8)
• (en) Michael A. Harrison, Introduction to Formal Language Theory, Reading, Mass., Addison-Wesley, 1978 (ISBN 0201029553, OCLC 266962302).
• (en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, 521 p. (ISBN 9780201441246 et 0201441241).
• (en) Peter Linz, An Introduction to Formal Languages and Automata, Jones & Bartlett Learning, 2001, 410 p. (ISBN 9780763714222 et 0763714224).

Cours

• Anca Muscholl, « Langage hors-contexte »
• Jean-François Perrot, « Les grammaires « context-free" et la hiérarchie de Chomsky »
• Jean Privat, « Grammaires non contextuelles »
• Jacques Désarménien, « Grammaires non contextuelles »

Voir aussi

• Grammaire formelle
• Hiérarchie de Chomsky
• Parser packrat