Transformations evaluation incrémentale et optimisations des grammaires attribuées, le système FNC-2 / Didier Parigot ; sous la direction de Marie-Claude Gaudel

Bibliogr. p. 299-307

Thèse de doctorat informatique 1988 université Paris XI

Ce mémoire présente un ensemble de travaux consacrés aux Grammaires Attribuées (GAs). Son objectif est de montrer qu'il est maintenant possible de concevoir un système de traitement de GAs ayant de grandes qualités, tant en puissance d'expression qu'en efficacité des évaluateurs produits. Les nombreux travaux de recherche sur ce sujet ont mis l'accent sur les points critiques de cette méthode et ont proposé des solutions s'avérant être souvent un compromis entre l'efficacité des évaluateurs et la puissance d'expression. Les travaux présentés ici proposent pour ces points cruciaux des solutions qui permettent, dans une large mesure, d'améliorer ce compromis.Nos premiers travaux portent sur le problème de la transformation des GAs Fortement Non-Circulaires (FNC) en GAs 1-ordonnées. Cette transformation permet, grâce aux propriétés intrinsèques de la classe des GAs 1-ordonnées, de produire des évaluateurs efficaces aussi bien en temps d'exécution qu'en occupation mémoire, tout en gardant la grande puissance d'expression caractéristique de la classe des GAs FNC. Notre contribution a été de montrer que le risque d'exponentialité de la GA 1-ordonnée résultante peut être évité en pratique pour un grand nombre de GA FNC.Deuxièmement, nous introduisons une méthode d'évaluation incrémentale basée sur une extension de la méthode récursive associée naturellement aux GAs FNC. Cette méthode est directement applicable aux GAs Doublement Non -Circulaires et, grâce à nos travaux décrits ci-dessus, transposable sans perte d'efficacité aux GAs FNC.La troisième partie traite du coût fort élevé des tests d'appartenance, étapes préliminaires des constructeurs d'évaluateurs. Nous montrons qu'à l'aide d'optimisations de ces algorithmes de caractérisation, le temps de construction devient, en pratique, tout à fait raisonnable.Ensuite, nous présentons quelques possibilités pour améliorer les évaluateurs, principalement sur le plan de l'occupation mémoire, ainsi qu'un outil d'aide à l'écriture de GAs FNC. Cet outil de trace de circularités fortes permet de comprendre rapidement les causes de ces circularités indésirables.Enfin, nous présentons le nouveau système de traitement de GAs, nommé FNC-2, qui se veut à la fois puissant, efficace et d'utilisation facile et souple. Si la puissance et l'efficacité découlent principalement des travaux décrits ci-dessus, la spécification d'un nouveau langage d'écriture de GAs, OLGA, permet souplesse et facilité d'utilisation.