Grammaire non contextuelle

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de production (ou simplement production) est de la forme

X\to w

X est un symbole non terminal et w 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 w, 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 syntaxe de la majorité des langages de programmation est en général spécifiée à l'aide de grammaires non contextuelles. On doit y ajouter des contraintes sémantiques par d'autres méthodes.

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

La forme de Backus-Naur (Backus Naur form) est la notation la plus communément utilisée pour décrire une grammaire non contextuelle décrivant un langage de programmation.


Définition[modifier | modifier le code]

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[modifier | modifier le code]

Exemple 1[modifier | modifier le code]

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 \ge 0 \} qui n'est pas un langage rationnel.

Exemple 2[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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

Un autre exemple[modifier | modifier le code]

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[modifier | modifier le code]

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)
S→ 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^nb^nc^m\mid n,m\ge0\}\cup\{a^nb^mc^m\mid n,m\ge0\}

Dans toutes les grammaires, les mots a^nb^nc^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[modifier | modifier le code]

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[modifier | modifier le code]

  • 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[modifier | modifier le code]

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

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[modifier | modifier le code]

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

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[modifier | modifier le code]

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

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\le 2 dans ces règles[1].

Grammaires étendues[modifier | modifier le code]

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.

Notes[modifier | modifier le code]

  1. 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, no 2,‎ 1992, p. 291–293. Une preuve et un exemple détaillé sont aussi donnés dans Autebert, Berstel Boasson (1997).

Bibliographie[modifier | modifier le code]

  • Jean-Michel Autebert et Luc Boasson, Transductions rationnelles : Application aux Langages Algébriques, Masson,‎ 1988 (ISBN 978-2-225-81504-1)
  • 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)

Voir aussi[modifier | modifier le code]