Grammaire indexée

Une grammaire indexée se définit comme une grammaire algébrique, avec en plus des symboles spéciaux appelés indices, ou index, ou « flags » (indicateurs). Ces symboles supplémentaires servent à mémoriser l'application des règles dans le mot engendré, et d'obtenir par là-même un certain degré de parallélisme. Voici la définition formelle :

Une grammaire indexée est une structure G = ⟨N,T,F,P,S⟩, où

• N est l'ensemble des symboles non-terminaux ou variables
• T est un alphabet composé de symboles terminaux,
• F est un ensemble de symboles d'index ou d'indices,
• S ∈ N est l'axiome, et
• P est un ensemble fini de règles de production.

Chaque occurrence d'une variable de la grammaire, dans une production ou dans une dérivation, est munie d'une suite ${\displaystyle \sigma \in F^{*}}$ de symboles d'index, appelée une « pile d'index». L'occurrence d'une pile d'index ${\displaystyle \sigma }$ attaché à une variable ${\displaystyle A}$ est notée

${\displaystyle A[\sigma ]}$ ,

où les crochets ne font pas partie de l’alphabet. Les symboles terminaux ne sont pas dotés de piles.

On étend cette notation aux mots composés de symboles terminaux ou non-terminaux, en notant, pour une pile d'index ${\displaystyle \sigma }$ et un mot ${\displaystyle \alpha \in (N\cup T)^{*}}$ , par ${\displaystyle \alpha [\sigma ]}$ le mot obtenu en attachant ${\displaystyle \sigma }$ à chaque non terminal figurant dans ${\displaystyle \alpha }$ . Par exemple, pour${\displaystyle \alpha =aBCdE}$ , où ${\displaystyle a}$ et ${\displaystyle d}$ sont terminaux et ${\displaystyle B,C,E}$ sont non-terminaux, ${\displaystyle \alpha [\sigma ]=aB[\sigma ]C[\sigma ]dE[\sigma ]}$ .

Par définition les productions d'une grammaires indexée doivent être de l'une des formes suivantes :

1. ${\displaystyle A[\sigma ]\to \alpha [\sigma ]}$
2. ${\displaystyle A[\sigma ]\to B[f\sigma ]}$
3. ${\displaystyle A[f\sigma ]\to \alpha [\sigma ]}$

où ${\displaystyle A,B\in N}$ sont des variables, ${\displaystyle f\in F}$ est un symbole d'index, ${\displaystyle c\in F^{*}}$ est un mot d'index et ${\displaystyle \alpha \in (N\cup T)^{*}}$ est un mot formé de symboles terminaux et non terminaux. Cela signifie donc que les piles d'index sont soit inchangées, soit augmentées ou diminuées d'un symbole d'index, mais à une extrémité seulement, ce qui leur confère une propriété d'empilement ou dépilement. On trouve aussi la notation « ${\displaystyle .\!.}$  » à la place de ${\displaystyle \sigma }$ , ce qui donne l'écriture :

${\displaystyle A[..]\to \alpha [..]}$ , ${\displaystyle A[..]\to B[f..]}$ et ${\displaystyle A[f..]\to \alpha [..]}$

Une variante de la définition ajoute les symboles d'index en fin pile et non pas au début. Les dérivations sont similaires à celles d'une grammaire non contextuelle sauf pour le symbole d'index attaché aux variables. Lors de l'application d'une règle comme

A[σ] → B[σ]C[σ]

la pile d'index de A est copiée à la fois sur B et sur C. Les autres types de règles permettent d'empiler ou de dépiler des symboles d'index.

Formellement, on définit la relation de dérivation immédiate ou directe, notée ${\displaystyle \Rightarrow }$ sur l'ensemble des mots de (N[F^*]\cup T )^*(N[F^*]∪T)^* comme suit :

1. Pour une règle de la forme ${\displaystyle A[\sigma ]\to \alpha [\sigma ]}$ , on a ${\displaystyle \beta A[\phi ]\gamma \Rightarrow \beta \alpha [\phi ]\gamma }$ . En d'autres termes, la pile ${\displaystyle \phi }$ du membre gauche est recopiée dans chaque non terminal du membre droit.
2. Pour une règle de la forme ${\displaystyle A[\sigma ]\to \alpha [f\sigma ]}$ , on a ${\displaystyle \beta A[\phi ]\gamma \Rightarrow \beta \alpha [f\phi ]\gamma }$ . En d'autres termes, la pile ${\displaystyle \phi }$ du membre gauche est recopiée dans chaque non terminal du membre droit, mais augmentée au début par le symbole ${\displaystyle f}$ .
3. Pour une règle de la forme ${\displaystyle A[f\sigma ]\to \alpha [f\sigma ]}$ , on a ${\displaystyle \beta A[f\phi ]\gamma \Rightarrow \beta \alpha [\phi ]\gamma }$ . En d'autres termes, la pile ${\displaystyle f\phi }$ du membre gauche est recopiée dans chaque non terminal du membre droit, mais sans son premier symbole ${\displaystyle f}$ .

Comme d'usage, la relation de dérivation ${\displaystyle \Rightarrow ^{*}}$ est la clôture réflexive et transitive de la relation de dérivation immédiate. Le langage engendré par la grammaire est

${\displaystyle L(G)=\{w\in T^{*}\mid S\Rightarrow ^{*}w\}}$ .

Cela signifie que l'on part de l'axiome avec une pile d'index vide, et qu'à la fin de la dérivation, la pile d'index est à nouveau vide.

La définition qui précède est donnée par John Hopcroft et Jeffrey Ullman dans leur livre de 1979^[1].Historiquement, les grammaires indexées ont été introduites par Alfred Aho en 1968^[2] avec un formalisme différent.

Les piles d'index servent à mémoriser quelles règles ont été appliquées et dans quel ordre.

Une grammaire indexée pour les langages ${\displaystyle \{www\mid w\in \{a,b\}^{*}\}}$  :

${\displaystyle S[\sigma ]\to S[f\sigma ],\quad S[\sigma ]\to S[g\sigma ],\quad S[\sigma ]\to T[\sigma ]T[\sigma ]T[\sigma ]}$

${\displaystyle T[f\sigma ]\to aT[\sigma ],\quad T[g\sigma ]\to bT[\sigma ]}$

${\displaystyle T[]\to \varepsilon }$

Une dérivation de ${\displaystyle abbabbabb}$ est :

${\displaystyle S[]\Rightarrow S[f]\Rightarrow S[fg]\Rightarrow S[fgg]\Rightarrow T[fgg]T[fgg]T[fgg]}$

${\displaystyle \quad \Rightarrow aT[gg]bT[fgg]T[fgg]\Rightarrow abT[g]T[fgg]T[fgg]\Rightarrow abbT[]T[fgg]T[fgg]}$

${\displaystyle \quad \Rightarrow abbT[fgg]T[fgg]\Rightarrow \dotsb \Rightarrow abbabbT[fgg]\Rightarrow abbabbabb}$

L'exemple qui suit est donné dans le livre de Hopcroft et Ullman. Le langage engendré est ${\displaystyle \{a^{n}b^{n}c^{n}\mid n\geq 1\}}$ sur l'alphabet ${\displaystyle \{a,b,c\}}$ . La grammaire est :

${\displaystyle S[\sigma ]\to T[g\sigma ]}$

${\displaystyle T[\sigma ]\to T[f\sigma ],\quad T[\sigma ]\to A[\sigma ]B[\sigma ]C[\sigma ]}$

${\displaystyle A[f\sigma ]\to aA[\sigma ],\quad A[g\sigma ]\to a}$

${\displaystyle B[f\sigma ]\to bB[\sigma ],\quad B[g\sigma ]\to b}$

${\displaystyle C[f\sigma ]\to cC[\sigma ],\quad C[g\sigma ]\to c}$ .

Un exemple de dérivation est :

${\displaystyle S[]\Rightarrow T[g]\Rightarrow T[fg]\Rightarrow A[fg]B[fg]C[fg]}$

${\displaystyle \quad \Rightarrow aA[g]B[fg]C[fg]\Rightarrow aaB[fg]C[fg]\Rightarrow aabB[g]C[fg]\Rightarrow aabbC[fg]\Rightarrow aabbcC[g]\Rightarrow aabbcc}$

Un autre exemple est donné dans le chapitre « Aspects of Classical Language Theory » du Handbook of Formal Languages^[3]. Il s'agit du langage ${\displaystyle \{a^{n}b^{n^{2}}a^{n}\mid n\geq 1\}}$ . Le formalisme donné par ces auteurs est différent : à chaque symbole d'index (ou flag) est associé un ensemble de règles de production usuelles. Les piles d'index sont créées dans une première phase, et consommées dans une deuxième phase en les remplaçant par une quelconque des règles qui y sont attachées. La grammaire est la suivante :

${\displaystyle S\to Af_{1}}$

${\displaystyle A\to Af_{2},\quad A\to BCB}$

${\displaystyle f_{1}=\{B\to a,\ C\to b,\ D\to b\}}$

${\displaystyle f_{2}=\{B\to aB,\ C\to bCDD,\ D\to bD\}}$ .

Après l'introduction des indexes, on engendre les mots de la forme

${\displaystyle Bf_{2}^{n}f_{1}Cf_{2}^{n}f_{1}Bf_{2}^{n}f_{1}}$ .

L'élimination des indexes remplace les parties suivant la variable ${\displaystyle B}$ par ${\displaystyle a^{n+1}}$ et celle suivant C par ${\displaystyle b^{{n+1}^{2}}}$ .

Aucun des trois langages n'est algébrique, comme on peut le voir par le lemme d'itération pour les langages algébriques. Pour le deuxième langage, une grammaire plus simple est donnée plus bas.

Hopcroft et Ullman, dans les notes de leur livre (p. 394-395) considèrent que les langages indexés forment une classe « naturelle » de langages parce qu'ils admettent plusieurs définitions équivalents ; ce sont :

• les automates à piles emboîtées (en) uni-directionnels de Alfred Aho^[4] ;
• les macro-grammaires de Michael J. Fischer^[5] ;
• les automates à piles de piles de Sheila A. Greibach^[6] ;
• les langages d'une caractérisation algébrique de Thomas Maibaum (en)^[7]

Hayashi^[8] a généralisé le lemme d'itération pour les langages algébriques aux grammaires indexées. Dans la direction opposée, Gilman^[9] donne un lemme de réduction pour les langages indexés.

Gerald Gazdar (en)^[10] définit une deuxième classe de grammaires appelées maintenant grammaires indexées linéaires^[13]; elles sont définies par la propriété qu'au plus une variable dans le membre droit d'une règle peut recevoir la pile d'index, les autres ne reçoivent que la pile vide, alors que dans une grammaire indexée générale, toutes le variable obtiennent copie de la pile d'index. La définition formelle est semblable, sauf que les productions sont de l'une des formes :

1. ${\displaystyle A[\sigma ]\to \alpha []B[\sigma ]\beta []}$
2. ${\displaystyle A[\sigma ]\to \alpha []B[f\sigma ]\beta []}$
3. ${\displaystyle A[f\sigma ]\to \alpha []B[\sigma ]\beta []}$

Bien entendu, d'autres productions doivent être terminales, c'est-à-dire sans variables dans le membre droit de règle. Cette classe de grammaires définit une classe de langages strictement plus petite^[10], elle-même contenu dans la classe des langages "mildly context-sensitive" (en).

Le langage ${\displaystyle \{www\mid w\in \{a,b\}^{*}\}}$ par exemple ne peut être engendré par une grammaire linéaire, alors que les langages ${\displaystyle \{ww\mid w\in \{a,b\}^{*}\}}$ et ${\displaystyle \{a^{n}b^{n}c^{n}\mid n\geq 1\}}$ sur l'alphabet ${\displaystyle \{a,b,c\}}$ sont des langages indexés linéaires.

Si l'on autorise à la fois l'usage de productions en mode indexé et en mode indexé linéaire, la classe de langages n'augmente pas et reste celle des langages indexés^[14]

Les grammaires indexées dont les membres droits de règle ne comportent pas de variable ou une seule variable (les grammaires linéaires usuelles) sont par définition linéaires. Un tel exemple est la grammaire suivante pour le langage ${\displaystyle \{a^{n}b^{n}c^{n}\mid n\geq 1\}}$  :

${\displaystyle S[\sigma ]\to T[\sigma ],\quad S[\sigma ]\to aT[f\sigma ]c}$

${\displaystyle T[f\sigma ]\to T[\sigma ]b}$

${\displaystyle T[]\to \varepsilon }$

Le mot ${\displaystyle aabbcc}$ s'obtient par la dérivation suivante :

${\displaystyle S[]\Rightarrow aS[f]c\Rightarrow aaS[ff]cc\Rightarrow aaT[ff]cc\Rightarrow aaT[f]bcc\Rightarrow aaT[]bbcc\Rightarrow aabbcc}$

Les langages engendrés par des grammaires indexées linéaires forment une sous-famille des langages indexés. Une grammaire indexée linéaire peut être convertie en une grammaire indexée de manière pas très compliquée^[15].

Vijay-Shanker et Weir^[16] montrent que les grammaires indexées linéaires sont équivalentes d'autres formalismes^[17] :

• les Combinatory Categorial Grammars (en)
• les grammaires d'arbres adjoints, et
• les Head grammar (en) ou grammaires à dérivation en tête de Carl Pollard.

D'autres familles de langages plus larges sont engendrées par des formalismes proches ; ce sont des Linear Context-free Rewriting Systems (en), ou desgrammaires minimalistes (en). L'analyse syntaxique peut être réalisée en temps polynomial^[18].

Une autre forme de grammaires distribuées, introduite par Peter Staudacher en 1993^[11], est la classe des grammaires indexées distribuées qui se distingue des autres modèles par le mode de propagation des indexes.

Alors que, dans le modèle classique, la totalité de la pile d'index est transférée sur les non-terminaux lors de l'opération de réécriture, les grammaires distribuées divisent la pile d'index en segments qui sont distribués à des non-terminaux sélectionnés.Le schéma général d'une règle de distribution est dans le cas du partage en deux groupes :

${\displaystyle X[f_{1}\dotso f_{i}f_{j}\dotso f_{n}]\to \alpha Y[f_{1}\dotso f_{i}]\beta Z[f_{j}\dotso f_{n}]\gamma }$

où ${\displaystyle \alpha }$ , ${\displaystyle \beta }$ , et ${\displaystyle \gamma }$ sont des mots arbitraires. Dans le cas de trois groupes, la règle s'écrit :

${\displaystyle X[f_{1}\dotso f_{i}f_{j}\dotso f_{k}f_{l}\dotso f_{n}]\to \alpha Y[f_{1}\dotso f_{i}]\beta Z[f_{j}\dotso f_{k}]\gamma W[f_{l}\dotso f_{n}]\eta }$

De même pour des ordres supérieurs. Lorsque la partition est en une seule classe, on retrouve les grammaires indexées linéaires ; les langages indexés distribués forment donc une classe contenant les langages indexés linéaires.

• Grammaire linéaire
• symboles non-terminaux