Grammaire indexée

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

Une grammaire indexée est une généralisation d'une grammaire non contextuelle où les symboles non terminaux sont munis de listes d'indicateurs ou symboles d'index (aussi appelés « flags » en anglais}. Le langage engendré par une grammaire indexée est appelé un langage indexé. Les grammaires indexées sont plus puissantes que les grammaires algébriques, et moins générales que les grammaires contextuelles. Elles sont en revanche équivalentes à d'autres familles de grammaires génératives, comme les grammaires d'arbre adjoints.

Définition[modifier | modifier le code]

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ù

Chaque occurrence d'une variable de la grammaire, dans une production ou dans une dérivation, est munie d'une suite de symboles d'index, appelée une « pile d'index». L'occurrence d'une pile d'index attaché à une variable est notée

,

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 et un mot , par le mot obtenu en attachant à chaque non terminal figurant dans . Par exemple, pour , où et sont terminaux et sont non-terminaux, .

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

sont des variables, est un symbole d'index, est un mot d'index et 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 «  » à la place de , ce qui donne l'écriture :

, et

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 sur l'ensemble des mots de (N[F^*]\cup T )^*(N[F*]∪T)* comme suit :

  1. Pour une règle de la forme , on a . En d'autres termes, la pile du membre gauche est recopiée dans chaque non terminal du membre droit.
  2. Pour une règle de la forme , on a . En d'autres termes, la pile du membre gauche est recopiée dans chaque non terminal du membre droit, mais augmentée au début par le symbole .
  3. Pour une règle de la forme , on a . En d'autres termes, la pile du membre gauche est recopiée dans chaque non terminal du membre droit, mais sans son premier symbole .

Comme d'usage, la relation de dérivation est la clôture réflexive et transitive de la relation de dérivation immédiate. Le langage engendré par la grammaire est

.

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.

Exemples[modifier | modifier le code]

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

Un premier exemple[modifier | modifier le code]

Une grammaire indexée pour les langages  :

Une dérivation de est :

Un deuxième exemple[modifier | modifier le code]

L'exemple qui suit est donné dans le livre de Hopcroft et Ullman. Le langage engendré est sur l'alphabet . La grammaire est :

.

Un exemple de dérivation est :

Un troisième exemple[modifier | modifier le code]

Un autre exemple est donné dans le chapitre « Aspects of Classical Language Theory » du Handbook of Formal Languages [3]. Il s'agit du langage . 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 :

.

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

.

L'élimination des indexes remplace les parties suivant la variable par et celle suivant C par .

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.

Propriétés[modifier | modifier le code]

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 :

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.

Grammaires indexées linéaires[modifier | modifier le code]

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 :

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 par exemple ne peut être engendré par une grammaire linéaire, alors que les langages et sur l'alphabet 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]

Exemple[modifier | modifier le code]

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  :

Le mot s'obtient par la dérivation suivante :

Puissance d'expression[modifier | modifier le code]

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] :

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

Grammaires indexées distribuées[modifier | modifier le code]

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 :

, , et sont des mots arbitraires. Dans le cas de trois groupes, la règle s'écrit :

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.

Articles liés[modifier | modifier le code]

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Indexed grammar » (voir la liste des auteurs).
  1. (en) John E. Hopcroft et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, (ISBN 0-201-02988-X), section 14.3, p. 389-390. Cette section ne figure plus dans la deuxième édition, datant de 2003.
  2. (en) Alfred Aho, « Indexed grammars—an extension of context-free grammars », Journal of the ACM, vol. 15, no 4,‎ , p. 647–671 (DOI 10.1145/321479.321488, lire en ligne)
  3. Alexandru Mateescu et Arto Salomaa, « Aspects of Classical Language Theory », dans G. Rozenberg, A. Salomaa (éditeurs), Handbook of Formal Languages, vol. 1 : Word, Language, Grammar, Springer Verlag, (ISBN 978-3-540-60420-4, DOI 10.1007/978-3-642-59136-5), p. 175-252, ici p. 244.
  4. (en) Alfred Aho, « Nested Stack Automata », Journal of the ACM, vol. 16, no 3,‎ , p. 383–406 (DOI 10.1145/321526.321529)
  5. Michael J. Fischer, « Grammars with Macro-Like Productions », Proc. 9th Ann. IEEE Symp. on Switching and Automata Theory (SWAT),‎ , p. 131–142
  6. (en) Sheila A. Greibach, « Full AFL's and Nested Iterated Substitution », Information and Control, vol. 16, no 1,‎ , p. 7–35 (DOI 10.1016/s0019-9958(70)80039-0, lire en ligne)
  7. (en) Thomas S. E. Maibaum, « A Generalized Approach to Formal Languages », J. Computer and System Sciences, vol. 8, no 3,‎ , p. 409–439 (DOI 10.1016/s0022-0000(74)80031-0, lire en ligne)
  8. (en) Takafumi Hayashi, « On Derivation Trees of Indexed Grammars - An Extension of the uvxyz Theorem », Publication of the Research Institute for Mathematical Sciences, vol. 9, no 1,‎ , p. 61–92 (DOI 10.2977/prims/1195192738, lire en ligne)
  9. (en) Robert H. Gilman, « A Shrinking Lemma for Indexed Languages », Theoretical Computer Science, vol. 163, nos 1–2,‎ , p. 277–281 (DOI 10.1016/0304-3975(96)00244-7, arXiv 9509205, lire en ligne)
  10. a et b Gerald Gazdar, « Applicability of Indexed Grammars to Natural Languages », dans U. Reyle et C. Rohrer, Natural Language Parsing and Linguistic Theories, D. Reidel Publishing Company, coll. « Studies in linguistics and philosophy » (no 35), (ISBN 1-55608-055-7), p. 69–94
  11. a et b Staudacher, Peter, « New frontiers beyond context-freeness: DI-grammars and DI-automata. », Sixth Conference of the European Chapter of the Association for Computational Linguistics (EACL '93),‎ , p. 358–367 (lire en ligne)
  12. David J. Weir et Aravind K. Joshi, « Combinatory Categorial Grammars: Generative Power and Relationship to Linear Context-Free Rewriting Systems », dans Proc. 26th Meeting Assoc. Comput. Ling., (lire en ligne), p. 278–285
  13. D'après Staudacher (1993, p.361 Section 2.2)[11], la dénomination "linear indexed grammars" n'est pas utilisée ans l'article de Gazdar de 1988, mais est apparu plus tard, dans une communication de Weir et Joshi (1988)[12].
  14. Gazdar 1988, p. 89.
  15. Gazdar 1988, Appendix, p.89-91.
  16. (en) K. Vijay-Shanker et David J. Weir, « The Equivalence of Four Extensions of Context-Free Grammars », Mathematical Systems Theory, vol. 27, no 6,‎ , p. 511–546 (DOI 10.1007/bf01191624, lire en ligne)
  17. (en) Mark Steedman, The Syntactic Process, MIT Press, , 330 p. (ISBN 9780262194204).
  18. Johan F. A. K. van Benthem et Alice ter Meulen, Handbook of Logic and Language, Elsevier, , 2e éd. (ISBN 978-0-444-53727-0, lire en ligne), p. 404.