Voir la source de 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
:<math>X\to \alpha</math>

où <math>X</math> est un symbole non terminal et <math>\alpha</math> est une chaîne composée de terminaux et/ou de non-terminaux. Le terme « non contextuel » provient du fait qu'un non terminal <math>X</math> peut être remplacé par <math>\alpha</math>, sans tenir compte du contexte où il apparaît. Un [[langage formel]] est '''[[langage algébrique|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

<math>c~+X\to c+\alpha</math>

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 <math>c</math> et du littéral <math>+</math>, il peut être remplacé par <math>\alpha</math>.  

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 [[langage de programmation|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''' <math>G</math> est composée :
* d'un alphabet fini <math>V</math> de ''symboles non terminaux'' ou ''variables'' ;
* d'un alphabet fini <math>A</math>, disjoint de <math>V</math>, de ''symboles terminaux'' ou ''lettres terminales'' ;
* d'un élément <math>S</math> de <math>V</math> appelé l'''axiome'' ;
* d'un ensemble fini <math>\mathcal {P}\subset V\times (V\cup A)^*</math>de ''règles de dérivations'' ou ''productions''.

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

Le '''langage engendré''' par la grammaire <math>G</math>, noté <math>L(G)</math>, est l'ensemble des mots terminaux (ne contenant plus de variables) qui dérivent de l'axiome <math>S</math>, soit
:<math>L(G)=\{w\in A^*\mid S\stackrel{*}\to w\}</math>.
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 <math>w</math> de <math>A\cup V</math> qui dérivent de l'axiome  <math>S</math>, qu'ils contiennent ou non des variables.

== Exemples ==

=== Exemple 1 ===

Considérons la grammaire algébrique suivante :
:<math>\begin{array}{l}
S \to aSb \\
S \to \varepsilon
\end{array}</math>
où <math>\varepsilon</math> dénote le mot vide. Cette grammaire engendre le langage 
<math> \{ a^n b^n \mid n \ge 0 \} </math>
qui n'est pas un [[langage régulier|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 :

<math>S \to aSb \mid\varepsilon</math>.

=== Exemple 2 ===

Voici une grammaire algébrique qui engendre les expressions arithmétiques en trois variables <math>x</math>, <math>y</math> et <math>z</math>, correctement parenthésées :
:<math>S \to x \mid y \mid z \mid S + S \mid S - S \mid S * S \mid S/S \mid (S)</math>

Cette grammaire engendre par exemple <math>( x + y ) * x - z * y / ( x + x )</math> .

=== Exemple 3 ===

La grammaire suivante engendre le langage composé des mots en <math>a</math> et en <math>b</math>, et dont le nombre de <math>a</math> est différent du nombre de <math>b</math> :
:<math>S \to U \mid V</math>
:<math>U \to TaU \mid TaT</math>
:<math>V \to TbV \mid TbT</math>
:<math>T \to aTbT \mid bTaT \mid \varepsilon</math>
<math>T</math> produit les mots ayant le même nombre de <math>a</math> et de <math>b</math>, <math>U</math> produit les mots avec plus de <math>a</math> que de <math>b</math>, et <math>V</math> produit les mots ayant moins de <math>a</math> que de <math>b</math>.

=== Exemple 4 ===

Les [[langage de Dyck|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 {{-s-|IV}}. 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]]<ref>[http://www.languageinindia.com/feb2004/panini.html Language in India].</ref>.

== 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 :
:<math> (1)\quad  S \to S + S</math>
:<math> (2)\quad  S\to a</math>
:<math> (3)\quad  S\to 1</math>
la chaîne « <math>1+a+a</math> » 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 :
: <math>S</math>
: <math>S+S</math> ((1) appliquée à S)
: <math>S+S+S</math> ((1) appliquée au deuxième S)
: <math>S+a+S</math> ((2) appliquée au deuxième S)
: <math>1+a+S</math> ((3) appliquée au premier S)
: <math>1+a+a</math> ((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 « <math>1+a+a</math> » est donc obtenu de cette façon :
: <math>S</math>
: <math>S+S</math> ((1) appliquée à S)
: <math>1+S</math> ((3) appliquée au premier S)
: <math>1+S+S</math> ((1) appliquée à S)
: <math>1+a+S</math> ((2) appliquée au premier S)
: <math>1+a+a</math> ((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:
: <math>S</math>
: <math>S+S</math> ((1) appliquée à S)
: <math>S+a</math> ((2) appliquée au dernier S)
: <math>S+S+a</math> ((1) appliquée à S)
: <math>S+a+a</math> ((2) appliquée au dernier S)
: <math>1+a+a</math> ((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 [[analyse syntaxique|analyseurs syntaxiques]] de tenir compte des priorités des opérations. Les [[Analyse LL|analyseurs LL]] produisent des dérivations gauches, et les [[Analyse LR|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 }<sub>S</sub> + { a }<sub>S</sub> }<sub>S</sub> + { a }<sub>S</sub> }<sub>S</sub>
où { ... }<sub>S</sub> 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 [[arbre enraciné|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 '''[[grammaire ambigüe|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:
:<math>\{a^nb^nc^m\mid n,m\ge0\}\cup\{a^nb^mc^m\mid n,m\ge0\}</math>
Dans toutes les grammaires, les mots <math>a^nb^nc^n</math> 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 <math>\varepsilon</math>-règle <math>S\to\varepsilon</math>, où <math>S</math> est l'axiome, avec la condition supplémentaire que <math>S</math> ne figure dans aucun membre droit de règle.

=== Forme normale de Chomsky ===
{{loupe|Forme normale de Chomsky}}
Une grammaire est en ''forme normale de [[Noam Chomsky|Chomsky]]'' si toutes ses règles sont de l'une des formes
*<math>X\to YZ</math>
*<math>X\to a</math>,
où <math>X,Y,Z</math> sont des variables, et <math>a</math> est une lettre. Si le langage engendré contient le mot vide, on ajoute la règle
*<math>S\to \varepsilon</math>,
où <math>S</math> 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'[[CYK (algorithme)|algorithme CYK]], qui décide, en [[Complexité des algorithmes|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 
:<math>X\to aY_1\cdots Y_k</math><br><math>X\to b</math>
où <math>X,Y_1,\ldots, Y_k</math> sont des variables et <math>a,b</math> sont des lettres. 
Par exemple, la grammaire
:<math>S\to aSS\mid b</math>
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
:<math>X\to aY_1\cdots Y_k b</math><br><math>X\to c</math>
où <math>X,Y_1,\ldots, Y_k</math> sont des variables et <math>a,b,c</math> 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 <math>k\le 2</math> dans ces règles<ref>Ce résultat est assez peu connu. Il a été prouvé par G. Hotz.  Une preuve est donnée dans : {{Article|prénom=Joost|nom1=Engelfriet
|titre=An elementary proof of double Greibach normal form |périodique=Information Processing Letters
|année=1992|volume=44|numéro=2|pages=291–293}}. Une preuve et un exemple détaillé sont aussi donnés dans {{harvsp|Autebert, Berstel Boasson (1997)|réf=ABB}}.</ref>.

=== 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 [[Extended Backus-Naur Form|forme normale de Backus étendue]]. Plus précisément, notons <math>P(X)</math> l'ensemble des membres droits de règles dont le membre gauche est <math>X</math>.
*Dans la définition usuelle des grammaires algébriques, les ensembles <math>P(X)</math> sont finis pour toute variable <math>X</math>.
*Dans les grammaires étendues, les ensembles <math>P(X)</math> sont des [[langage rationnel|langages rationnels]] qui sont donnés par des [[expression régulière|expressions régulières]]. 
*Dans une généralisation de ces grammaires, les ensembles <math>P(X)</math> sont eux-mêmes des [[langage algébrique|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'[[Analyse syntaxique|analyseurs syntaxiques]] efficaces (contrairement aux [[grammaire contextuelle|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'[[analyse Earley|analyseur d'Earley]] sont des exemples de tels algorithmes. Les [[analyse LR|analyseurs LR]] et les [[analyse LL|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 ==
{{Références}}

== 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
<!-- Dragon -->
* {{Ouvrage | langue = fr | auteur1 = Alfred Aho | auteur2 = Monica Lam | auteur3 = Ravi Sethi | auteur4 = Jeffrey Ullman | titre = Compilateurs : principes, techniques et outils | sous-titre = Avec plus de 200 exercices | éditeur = Pearson | lieu =  | numéro édition = 2 |année = 2007 | pages totales = 928 | isbn = 9782744070372 | isbn2 = 2744070378}} 
<!-- Wolper -->
* {{ouvrage|auteur=Pierre Wolper | titre=Introduction à la calculabilité|numéro d'édition=3|éditeur= Dunod |année=2006|isbn=2-10-049981-5}}.
<!-- Autebert -->
* {{Ouvrage| auteur=Jean-Michel Autebert| titre=Langages algébriques| éditeur=Masson| année=1987 
|isbn=978-2-225-81087-9}}  
<!-- Autebert Boasson -->
* {{Ouvrage | auteur=Jean-Michel Autebert et Luc Boasson
  | titre=Transductions rationnelles : Application aux Langages Algébriques | éditeur=Masson| année=1988
  | isbn=978-2-225-81504-1 }}  
<!-- Carton -->
* {{Langages formels, calculabilité et complexité}} <!-- l’id autogénéré devrait suffire : Carton2008 -->
<!-- ABB -->
* {{Chapitre| auteurs = Jean-Michel Autebert, Jean Berstel et Luc Boasson
 | titre chapitre = Context-free languages and pushdown automata
 | auteurs ouvrage = G. Rozenberg, A. Salomaa (éditeurs)
 | titre ouvrage = Handbook of Formal Languages| éditeur = Springer Verlag| année = 1997| volume = 1
 | titre volume = Word, Language, Grammar
 | passage = 111-174| isbn = 978-3540604204
 | id = ABB
}}
;Ouvrage en allemand
<!-- Erk Priese -->
* {{Ouvrage | langue = de | auteur1 = Katrin Erk  | auteur2 = Lutz Priese | titre = Theoretische Informatik : eine umfassende Einführung | éditeur = Springer | lieu = Berlin | année = 2008 | pages totales =  | isbn = 9783540763192 | oclc = 244015158}}.
;Ouvrages en anglais
<!-- Ginsburg  (1966) -->
* {{Ouvrage | langue = en | auteur = Seymour Ginsburg |titre = The Mathematical Theory of Context Free Languages |éditeur=McGraw-Hill |lieu=|année=1966|pages totales =ix+ 232}} — Le premier livre sur les langages algébriques.
<!-- Aho et Ullman (1972-73)-->
*{{Ouvrage | langue = en | auteur1 = Alfred V. Aho | auteur2 = Jeffrey D. Ullman | titre = The theory of parsing, translation, and compiling |volume=1|titre volume=
Parsing | éditeur = Prentice-Hall | lieu = Englewood Cliffs, NJ | année = 1972 | pages totales = xii+543 | isbn = 0-13-914556-7 }}
*{{Ouvrage | langue = en | auteur1 = Alfred V. Aho | auteur2 = Jeffrey D. Ullman | titre = The theory of parsing, translation, and compiling |volume=2|titre volume= Compiling | éditeur = Prentice-Hall | lieu = Englewood Cliffs, NJ | année = 1973 | pages totales = xii+460 | isbn =0-13-914564-8}}
<!-- Harrison (1978) -->
* {{Ouvrage | langue = en | auteur = Michael A. Harrison | titre = Introduction to Formal Language Theory | éditeur = Addison-Wesley | lieu = Reading, Mass.| année = 1978 | pages totales =  | isbn = 0201029553 | oclc = 266962302}}.
<!-- Hopcroft (2001) -->
* {{Ouvrage | langue = en | auteur1 = John E. Hopcroft | auteur2 = Rajeev Motwani | auteur3 = Jeffrey D. Ullman | titre = Introduction to Automata Theory, Languages, and Computation | éditeur = Addison Wesley | numéro d’édition = 2 |lieu =  | année = 2001 | pages totales = 521 | isbn = 9780201441246 | isbn2 = 0201441241
|id=HMU}}.
<!-- Linz (2001)  -->
* {{Ouvrage | langue = en | auteur = Peter Linz | titre = An Introduction to Formal Languages and Automata | éditeur = Jones & Bartlett Learning | lieu =  | année = 2001 | pages totales = 410 | isbn = 9780763714222 | isbn2 = 0763714224}}.
; Cours
* {{Lien web| auteur= Anca Muscholl | titre=Langage hors-contexte |url =www.labri.fr/perso/anca/Langages/cours/cfl.pdf}} 
* {{Lien web| auteur= Jean-François Perrot  | titre= Les grammaires « context-free" et la hiérarchie de Chomsky  |url=https://pages.lip6.fr/Jean-Francois.Perrot/inalco/Automates/Cours18.html}}
* {{Lien web| auteur= Jean Privat  | titre=
 Grammaires non contextuelles |url = http://info.uqam.ca/~privat/INF5000/05-grammaire.pdf}}
* {{Lien web| auteur=Jacques Désarménien  | titre= Grammaires non contextuelles |url=
www-igm.univ-mlv.fr/~desar/Cours/automates/ch4.pdf}}

== Voir aussi ==

* [[Parser packrat]]
* [[Récursivité gauche]]
* [[Forme normale de Greibach]]
* [[Forme normale de Chomsky]]
* [[Analyse LL]]
* [[Algorithme CYK]]

{{Palette|Langages formels grammaires et automates}}
{{Palette Informatique théorique}}

{{Portail|informatique théorique}}

[[Catégorie:Grammaire]]
[[Catégorie:Langage formel]]
[[Catégorie:Linguistique générative]]