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

${\displaystyle X\to \alpha }$

où ${\displaystyle X}$ est un symbole non terminal et ${\displaystyle \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 ${\displaystyle X}$ peut être remplacé par ${\displaystyle \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.

Par opposition est contextuelle une règle de la forme

${\displaystyle c~+X\to c+\alpha }$

en raison de la partie gauche de la règle qui stipule un contexte pour X. Une telle règle signifie que X, dans le cas (contexte) où il est précédé du symbole terminal ${\displaystyle c}$ et du littéral ${\displaystyle +}$, peut être remplacé par ${\displaystyle \alpha }$.

Ainsi, dans une grammaire non contextuelle, un symbole non terminal est toujours seul dans la partie gauche de toute règle, ce qui signifie que son environnement syntaxique (ou contexte) n'est pas considéré.

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 ${\displaystyle G}$ est composée :

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

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

${\displaystyle u{\stackrel {*}{\to }}v}$,

on dit que ${\displaystyle u}$ dérive en ${\displaystyle v}$.

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

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

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 ${\displaystyle w}$ de ${\displaystyle A\cup V}$ qui dérivent de l'axiome ${\displaystyle S}$, qu'ils contiennent ou non des variables.

Exemples

Exemple 1

Considérons la grammaire algébrique suivante :

${\displaystyle {\begin{array}{l}S\to aSb\\S\to \varepsilon \end{array}}}$

où ${\displaystyle \varepsilon }$ dénote le mot vide. Cette grammaire engendre le langage ${\displaystyle \{a^{n}b^{n}\mid n\geq 0\}}$ qui n'est pas un langage rationnel.

On peut aussi utiliser une barre verticale pour regrouper les règles avec le même symbole non terminal comme membre gauche et écrire la grammaire sous la forme condensée suivante :

${\displaystyle S\to aSb\mid \varepsilon }$.

Exemple 2

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

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

Cette grammaire engendre par exemple ${\displaystyle (x+y)*x-z*y/(x+x)}$ .

Exemple 3

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

${\displaystyle S\to U\mid V}$

${\displaystyle U\to TaU\mid TaT}$

${\displaystyle V\to TbV\mid TbT}$

${\displaystyle T\to aTbT\mid bTaT\mid \varepsilon }$

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

Exemple 4

Les langages de Dyck ou les langages des mots bien parenthésés sont des langages algébriques.

Un autre exemple

Les grammaires non contextuelles ne sont pas limitées aux langages formels en mathématiques. Elles sont également utilisées en linguistique, même si les grammaires contextuelles sont souvent mieux adaptées. Un exemple étonnant est fourni par le travail du linguiste indien Pānini, actif au IV^e siècle av. J.-C. Il a décrit la grammaire du sanskrit dans un système hautement formalisé, avec près de 4000 règles. Ces règles sont présentées dans une notation proche de la forme de Backus-Naur^[1].

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 :

${\displaystyle (1)\quad S\to S+S}$

${\displaystyle (2)\quad S\to a}$

${\displaystyle (3)\quad S\to 1}$

la chaîne « ${\displaystyle 1+a+a}$ » admet donc plusieurs dérivations. La dérivation représentée par la liste [ (1), (1), (2), (3), (2) ] est obtenue de la manière suivante :

${\displaystyle S}$

${\displaystyle S+S}$ ((1) appliquée à S)

${\displaystyle S+S+S}$ ((1) appliquée au deuxième S)

${\displaystyle S+a+S}$ ((2) appliquée au deuxième S)

${\displaystyle 1+a+S}$ ((3) appliquée au premier S)

${\displaystyle 1+a+a}$ ((2) appliquée à S)

dans cette dérivation, les caractères non terminaux sont remplacés sans ordre spécifique.

Pour obtenir une dérivation gauche, on remplace toujours le non-terminal le plus à gauche. La dérivation gauche de la chaîne « ${\displaystyle 1+a+a}$ » est donc obtenu de cette façon :

${\displaystyle S}$

${\displaystyle S+S}$ ((1) appliquée à S)

${\displaystyle 1+S}$ ((3) appliquée au premier S)

${\displaystyle 1+S+S}$ ((1) appliquée à S)

${\displaystyle 1+a+S}$ ((2) appliquée au premier S)

${\displaystyle 1+a+a}$ ((2) appliquée à S)

ce qui donne la liste [ (1), (3), (1), (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), (3)], obtenue de cette façon:

${\displaystyle S}$

${\displaystyle S+S}$ ((1) appliquée à S)

${\displaystyle S+a}$ ((2) appliquée au dernier S)

${\displaystyle S+S+a}$ ((1) appliquée à S)

${\displaystyle S+a+a}$ ((2) appliquée au dernier S)

${\displaystyle 1+a+a}$ ((3) appliquée au premier S)

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.

{ { { 1 }_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
       |      /|\
       |     / | \
       1    S  +  S
            |     |
            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.

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:

${\displaystyle \{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 ${\displaystyle 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 ${\displaystyle \varepsilon }$-règle ${\displaystyle S\to \varepsilon }$, où ${\displaystyle S}$ est l'axiome, avec la condition supplémentaire que ${\displaystyle 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

• ${\displaystyle X\to YZ}$
• ${\displaystyle X\to a}$,

où ${\displaystyle X,Y,Z}$ sont des variables, et ${\displaystyle a}$ est une lettre. Si le langage engendré contient le mot vide, on ajoute la règle

• ${\displaystyle S\to \varepsilon }$,

où ${\displaystyle S}$ est l’axiome.

Toute grammaire peut être mise en forme normale de Chomsky. Cette forme normale sert par exemple dans la définition d'un algorithme d'analyse syntaxique, l'algorithme CYK, qui décide, en temps polynomial, si un mot est dans le langage engendré 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 lettre, et ne sont suivies éventuellement que par des variables, formellement

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

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

${\displaystyle 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 entre ces dernières que des variables. Toutes les règles sont de la forme

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

où ${\displaystyle X,Y_{1},\ldots ,Y_{k}}$ sont des variables et ${\displaystyle 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 ${\displaystyle k\leq 2}$ dans ces règles^[2].

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 ${\displaystyle P(X)}$ l'ensemble des membres droits de règles dont le membre gauche est ${\displaystyle X}$.

• Dans la définition usuelle des grammaires algébriques, les ensembles ${\displaystyle P(X)}$ sont finis pour toute variable ${\displaystyle X}$.
• Dans les grammaires étendues, les ensembles ${\displaystyle 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 ${\displaystyle 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.

Notes

1. Language in India.
2. Ce résultat est assez peu connu. Il a été prouvé par G. Hotz. Une preuve est donnée dans : Joost Engelfriet, « An elementary proof of double Greibach normal form », Information Processing Letters, vol. 44, n^o 2,‎ 1992, p. 291–293. Une preuve et un exemple détaillé sont aussi donnés dans Autebert, Berstel Boasson (1997).

Bibliographie

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

Ouvrages en français

• Alfred Aho, Monica Lam, Ravi Sethi et Jeffrey Ullman (trad. de l'anglais), Compilateurs : principes, techniques et outils : Avec plus de 200 exercices, Paris, Pearson, 2007, 2^e éd., 928 p. (ISBN 978-2-7440-7037-2 et 2744070378)
• Pierre Wolper, Introduction à la calculabilité : cours et exercices corrigés, Paris, Dunod, 2006, 3^e éd., 224 p. (ISBN 2-10-049981-5).
• Jean-Michel Autebert, Langages algébriques, Masson, 1987, 278 p. (ISBN 978-2-225-81087-9)
• Jean-Michel Autebert et Luc Boasson, Transductions rationnelles : Application aux Langages Algébriques, Masson, 1988, 133 p. (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, 485 p. (ISBN 978-3-540-76319-2, 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, 594 p. (ISBN 0-201-02955-3, OCLC 266962302).
• (en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, 2^e éd., 521 p. (ISBN 978-0-201-44124-6 et 0201441241).
• (en) Peter Linz, An Introduction to Formal Languages and Automata, Jones & Bartlett Learning, 2001, 410 p. (ISBN 978-0-7637-1422-2 et 0763714224, lire en ligne).

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

• Parser packrat
• Récursivité gauche
• Forme normale de Greibach
• Forme normale de Chomsky
• Analyse LL, grammaire LL
• Algorithme CYK

• Portail de l'informatique théorique