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.

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]

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