Projet OSCAR or FNC-2 system

Reports of FNC-2 Attribute Grammar System


Updated on Mon Mar 30 10:43:29 1998

[1]
Bernard Amilien. Interfaces graphiques interactives sous XWindows pour le système de traitement de grammaires attribuées FII . Rapport de stage, Institut d'Ingéniérie Informatique de Limoges, September 1992.

[2]
Bernard Amilien. Réalisation d'un complément interactif de trace de circularitédans le compilateur de grammaires attribuées FII . Rapport de stage de fin d'études, Institut d'Ingéniérie Informatique de Limoges, 1993.

[3]
Isabelle Attali and Didier Parigot. Integrating Natural Semantics and Attribute Grammars: the Minotaur System. Rapport de recherche 2339, INRIA, 1994. (Gzipped PostScript, 19 pages, 128408 bytes)
This papers describes the principles and the functionalities of the Minotaur system. Minotaur is a generic interactive environment based on the integration of the Centaur system and the FNC-2 system, two systems widely used to specify syntax and semantics of programming languages and generate efficient semantic tools from these specifications. We show how Attribute Grammars techniques can be adequate for evaluation of a quite large subclass of Natural Semantics specifications, including specifications of an arithmetic calculator, a tree transformation, a type-checker for an Algol-like language, ... For this subclass of Natural Semantics specifications, the Minotaur system automatically generates an incremental and efficient (in time and memory) evaluator which gives to Natural Semantics an industrial strength implementation.

[4]
Christine Ayrault. Implantation en C des structures de données du langage OLGA. rapport de DEA, University d'Orléans, September 1987.

[5]
Philippe Bazet. Pattern-matching en priorité spécifique sur des types avec constructeurs commutatifs. Rapport de DEA, Universitéde Paris 11, Orsay, September 1992.

[6]
Hervé Benvel. Réalisation d'un front-end pascal avec le système FNC-2. Rapport de DEA, Université de Paris 6, September 1993.

[7]
Joël Bonnet. Étude des principaux langages de description de grammaires attribuées et spécification d'un nouveau langage basé sur des grammaires abstraites. rapport de DEA, University d'Orléans, September 1986.

[8]
The COMPARE Consortium. Repport of toolselection taskforce. draft, Compare Consortium, august 1991. confidential. (Gzipped PostScript, 16 pages, 50842 bytes)

[9]
The COMPARE Consortium. Using pagode and fnc-2 in compare. draft, Compare Consortium, july 1994. confidential. (Gzipped PostScript, 10 pages, 81091 bytes)

[10]
Loïc Correnson, Etienne Duris, Didier Parigot, and Gilles Roussel. Composition symbolique. In journées du GDR de programmation, Rennes, November 1997. (Gzipped PostScript, 14 pages, 94080 bytes)

[11]
Loïc Correnson, Etienne Duris, Didier Parigot, and Gilles Roussel. Symbolic composition. Draft, INRIA, October 1997. ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/SC97a.ps.gz.
The deforestation of a functional program is a transformation which gets rid of intermediate data structures constructions that appear when two functions are composed. The descriptional composition, initially introduced by Ganzinger and Giegerich, is a deforestation method dedicated to the composition of two attribute grammars. This article presents a new functional deforestation technique, called symbolic composition, based on the descriptional composition mechanism, but extending it. An automatic translation from a functional program into an equivalent attribute grammar allows symbolic composition to be applied, and then the result can be translated back into a functional program (for instance, using the Jonhsson's transformation). This yields to a source to source functional program transformation. The resulting deforestation method provides a better deforestation than other existing functional techniques. Symbolic composition, completely dedicated to the declarative and descriptional features of attribute grammars is intrinsically more powerful than categorical-flavored transformations, whose recursion schemes are set by functors. These results lead us to believe that attribute grammars are a simple intermediate representation, particularly well-suited for program transformations.

[12]
Loïc Correnson, Etienne Duris, Didier Parigot, and Gilles Roussel. Symbolic composition. Draft, INRIA, July 1997. ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/SC97.ps.gz.
To be modular, functional programming widely uses function compositions. Usually, these compositions introduce intermediate data structures that could be discarded for efficiency. Transformations achieving these eliminations are called deforestation. To improve the power and the effectiveness of deforestation, several intermediate representations have been introduced, such as generic control operators and algebraic programming with fold, catamorphisms, and hylomorphisms. In the attribute grammar community there also exists a powerful and well-known deforestation-like transformation called descriptional composition. This paper show that descriptional composition forms the core of a new and a more efficient functional programming deforestation method. For this purpose, a translation from functional programs into attribute grammars is introduced. Descriptional composition combined with a kind of symbolic evaluation defines a powerful tool called symbolic composition. This new transformation deforests some programs for which functional deforestations fail. Finally, these results lead us to believe that attribute grammar notation is a simple and well-suited intermediate representation for data-structure-based transformations.

[13]
Loïc Correnson, Etienne Duris, Didier Parigot, and Gilles Roussel. Attribute grammars and functional programming deforestation. In Fourth International Static Analysis Symposium -- Poster Session, Paris, France, September 1997. (Gzipped PostScript, 16 pages, 88632 bytes)
The functional programming community is paying increasing attention to static structure-based transformations. For example, generic control operators, such as fold, have been introduced in functional programming to increase the power and applicability of a particular kind of static transformation, called deforestation, which prevents the construction of useless intermediate data structures in function composition. This is achieved by making the structure of the data more explicit in program specifications. We argue that one of the original concepts of Attribute Grammars is precisely to make data structures explicit in program specifications. Furthermore, there exists a powerful static deforestation-like transformation in their context. In this paper, we present similarities between deforestation methods, on the one hand with the functional approach, and on the other hand with the Attribute Grammars approach. In order to gain a grasp of these similarities, we first make a simple comparison: purely-synthesized Attribute Grammars and first order folds. In this context, deforestation transformations are equivalent. This allows us to highlight the limitations of the fold formalism and to present how the hylomorphism approach generalizes it; hylomorphisms and attribute grammars are surprisingly alike. Finally, we show how the inherited attribute notion in Attribute Grammars solves some transformation problems in higher order functional programs.

[14]
Loïc Correnson, Etienne Duris, Didier Parigot, and Gilles Roussel. Generic programming by program composition (position paper). In Workshop on Generic Programming, Marstrand, Sweden, June 1998. conjunction with MPC'98. (Gzipped PostScript, 13 pages, 70933 bytes)
Recently, generic programming becomes of a major interest in several programming paradigms. A recurrent idea to achieve genericity is to abstract computations from their representative data structures. This allows these generic specifications to be instantiated onto a large number of neighboring data structures. Moreover the program can be adapted when the data structures have to evolve. Polytypic programming, adaptive programming and generic attribute grammars are generic programming methods related to this approach. Their comparison leads us to propose a common framework for generic programming: automatic generation of programs that compute morphisms between data structures, and program composition. Thanks to this compositional approach, the complete specialization of generic programs could be advantageously delegated to some powerful and general deforestation method.

[15]
Loïc Correnson, Etienne Duris, Didier Parigot, and Gilles Roussel. Symbolic composition. Technical Report 3348, INRIA, January 1998. (Gzipped PostScript, 27 pages, 148776 bytes)
The deforestation of a functional program is a transformation which gets rid of intermediate data structures constructions that appear when two functions are composed. The descriptional composition, initially introduced by Ganzinger and Giegerich, is a deforestation method dedicated to the composition of two attribute grammars. This article presents a new functional deforestation technique, called symbolic composition, based on the descriptional composition mechanism, but extending it. An automatic translation from a functional program into an equivalent attribute grammar allows symbolic composition to be applied, and then the result can be translated back into a functional program. This yields a source to source functional program transformation. The resulting deforestation method provides a better deforestation than other existing functional techniques. Symbolic composition, that uses the declarative and descriptional features of attribute grammars is intrinsically more powerful than categorical-flavored transformations, whose recursion schemes are set by functors. These results tend to show that attribute grammars are a simple intermediate representation, particularly well-suited for program transformations.

[16]
Loïc Correnson, Etienne Duris, Didier Parigot, and Gilles Roussel. Composition symbolique. In Journées Francophones des Langages Applicatifs, Come, Italie, February 1998. (Gzipped PostScript, 22 pages, 103579 bytes)
La déforestation d'un programme fonctionnel est une transformation qui consiste à éliminer la construction des structures intermédiaires qui sont introduites par les compositions de fonctions. La composition descriptionnelle, initialement introduite par Ganzinger et Giegerich, est une méthode de déforestation spécifique, qui s'applique à la composition de deux grammaires attribuées. Cet article propose une nouvelle technique de déforestation, appelée composition symbolique, qui est une extension et une amélioration de la composition descriptionnelle. En traduisant automatiquement un programme fonctionnel en une grammaire attribuée équivalente, il est possible de lui appliquer la composition symbolique, et de traduire le résultat en un programme fonctionnel (par exemple, en utilisant la transformation de Johnsson). On obtient alors une transformation source à source de programmes fonctionnels. La méthode de déforestation ainsi obtenue donne de meilleurs résultats que les méthodes fonctionnelles existantes. La composition symbolique, complètement dédiée au caractère déclaratif et descriptionnel des grammaires attribuées est intrinsèquement plus puissante que les transformations basées sur les notions catégorielles, dont les schémas de récursions sont figés par des foncteurs. Ces résultats confirment que la notation des grammaires attribuées est une représentation intermédiaire simple et particulièrement adaptée aux transformations de programmes.

[17]
Loïc Correnson. Généricité dans les grammaires attribuées. Rapport de stage d'option, École Polytechnique, 1996. (Gzipped PostScript, 46 pages, 153743 bytes)

[18]
Loïc Correnson. Programmation polytypique avec les grammaires attribuées. Rapport de DEA, Université de Paris VII, September 1997. (Gzipped PostScript, 38 pages, 126320 bytes)

[19]
David Devillard. Amélioration de l'implantation en C des évaluateurs d'attributs produits par FNC-2. Rapport de DEA, Universitéd'Orléans, September 1990.

[20]
Olivier Durin. Traduction en OLGA d'une grammaire attribuée écrite en lisp. rapport de stage d'option, École Polytechnique, Palaiseau, July 1988.

[21]
Olivier Durin. Génération en le_lisp d'évaluateurs d'attributs spécifiés en olga. rapport de magistère, École Normale Supérieure, Paris, September 1989.

[22]
Etienne Duris, Didier Parigot, and Martin Jourdan. Mises à jour destructives dans les grammaires attribuées. Rapport de recherche 2686, INRIA, October 1995. (Gzipped PostScript, 12 pages, 97353 bytes)
In the functional language domain, there exist several works on the problem of garbage collection at compile time. In the context of Attribute Grammars, the memory optimisation problem spawned a number of works on the notion of attribute lifetime. We present a method which, in this context, allows to replace some function calls with their destructive counterpart. If we consider the functional program which is equivalent to a given attribute grammar, our technique can be seen as a static method for its update-in-place transformation. This method uses the results obtained on the attribute lifetime notion. One of its features is that it uses only classical static analysis methods for attribute grammars.

[23]
Etienne Duris, Didier Parigot, Gilles Roussel, and Martin Jourdan. Attribute grammars and folds: Generic control operators. Rapport de recherche 2957, INRIA, August 1996. (Gzipped PostScript, 29 pages, 176512 bytes)
Generic control operators, such as fold, have been introduced in functional programming to increase the power and applicability of data-structure-based transformations. This is achieved by making the structure of the data more explicit in program specifications. We argue that this very important property is one of the original concepts of attribute grammars. In this paper, we informally show the similarities between the fold formalism and attribute grammar specifications. We also compare their respective method to eliminate the intermediate data structures introduced by function composition (notion of deforestation or fusion): the normalization algorithm for programs expressed with folds and the descriptional composition of attribute grammars. Rather than identify the best way to achieve deforestation, the main goal of this paper is merely to intuitively present two programming paradigms to each other's supporting community and provide an unbiased account of their similarities and differences, in the hope that this leads to fruitful cross-fertilization.

[24]
Etienne Duris, Didier Parigot, Gilles Roussel, and Martin Jourdan. Grammaires attribuées et folds: Opérateurs de contrôle Génériques. In journées du GDR de programmation, Orléans, 1996. (Gzipped PostScript, 8 pages, 63271 bytes)
Les opérateurs de contrôle génériques tels que fold ont été introduits en programmation fonctionnelle pour augmenter la puissance et le champ d'application des transformations fondées sur la structure des données. Ceci est possible en rendant cette structure plus explicite dans la spécification des programmes. Nous considérons que cette caractéristique fondamentale est l'un des concepts de base des grammaires attribuées. Dans cet article, nous exposons informellement les similitudes qui existent entre le formalisme du fold et la spécification par grammaires attribuées. Nous comparons également leurs méthodes respectives d'élimination des structures intermédiaires introduites lors de la composition de fonctions (notion de déforestation ou de fusion) : l'algorithme de normalisation pour les programmes exprimés à l'aide de folds et la composition descriptionnelle pour les grammaires attribuées. Le but principal de cet article est de présenter intuitivement chacun de ces deux paradigmes, ainsi que leurs similitudes qui offrent des possibilités de fertilisation croisée.

[25]
Etienne Duris, Didier Parigot, Gilles Roussel, and Martin Jourdan. Grammaires attribuées et folds : opérateurs de contrôle génériques. In Journées Francophones des Langages Applicatifs, Dolomieu, France, January 1997. (Gzipped PostScript, 20 pages, 84868 bytes)
Les opérateurs de contrôle génériques tels que fold ont été introduits en programmation fonctionnelle pour augmenter la puissance et le champ d'application des transformations fondées sur la structure des données. Ceci est possible en rendant cette structure plus explicite dans la spécification des programmes. Nous considérons que cette caractéristique fondamentale est l'un des concepts de base des grammaires attribuées. Dans cet article, nous exposons informellement les similitudes qui existent entre le formalisme du fold et la spécification par grammaires attribuées. Nous comparons également leurs méthodes respectives d'élimination des structures intermédiaires introduites lors de la composition de fonctions (notion de déforestation ou de fusion) : l'algorithme de normalisation pour les programmes exprimés à l'aide de folds et la composition descriptionnelle pour les grammaires attribuées. Le but principal de cet article est de présenter intuitivement chacun de ces deux paradigmes, ainsi que leurs similitudes qui offrent des possibilités de fertilisation croisée

[26]
Etienne Duris, Didier Parigot, Gilles Roussel, and Martin Jourdan. Structure-directed genericity in functional programming and attribute grammars. Rapport de Recherche 3105, INRIA, February 1997. (Gzipped PostScript, 18 pages, 122262 bytes)
Generic control operators, such as fold, have been introduced in functional programming to increase the power and applicability of data-structure-based transformations. This is achieved by making the structure of the data more explicit in program specifications. We argue that this very important property is one of the original concepts of attribute grammars. In this paper, we present the similarities between the fold formalism and attribute grammars. In particular, we show the equivalence of their respective deforestation methods. Given these results and the fundamental role of deforestation in the concept of structure-directed genericity, first devised for attribute grammars with descriptional composition, we show how the fold operator with its fusion method allow to transport this concept in the area of functional programming.

[27]
Etienne Duris. Transformation de grammaires attribuées pour des mises à jour destructives. Rapport de DEA, Université d'Orléans, September 1994. (Gzipped PostScript, 90 pages, 190738 bytes)
Dans le domaine des langages fonctionnels, il existe un ensemble de travaux sur les problèmes de récupération de mémoire au moment de la compilation. Dans le domaine des grammaires attribuées, ce problème a donné lieu à l'étude de la notion de durée de vie des attributs. Dans ce rapport, nous étudions la possibilité de construire automatiquement la version ``destructive'' correspondant à une fonction de mise à jour applicative donnée. Par destructive, on entend le fait qu'elle puisse modifier physiquement la structure de son argument mis à jour, évitant ainsi de nombreuses allocations mémoire. D'autre part, nous devons déterminer sous quelles conditions un appel à une fonction de mise à jour applicative dans une grammaire attribuée peut être remplacé par un appel à sa version destructive. Ces optimisations permettent de réutiliser des structures de données complexes au lieu de les dupliquer. Dans ce cadre, nous fournissons des éléments de comparaison entre les travaux de Philip Wadler sur la déforestation et ceux de Gilles Roussel sur la méta-composition. Ces comparaisons sous forme d'observations peuvent constituer une amorce de rapprochement entre la programmation fonctionnelle et les grammaires attribuées.

[28]
Rémi Forax. Le langage chocolat. Rapport de stage de ma^itrise d'informatique, Université de Marne la Vallée, July 1997. (Gzipped PostScript, 25 pages, 54681 bytes)

[29]
José Garcia, Martin Jourdan, and Antoine Rizk. An implementation of PARLOG using high-level tools. In Commission of the European Communities--Directorate General XIII, editor, ESPRIT '87: Achievements and Impact, pages 1265-1275. North-Holland, Amsterdam, November 1987. Brussels.

[30]
Roberto Gomez Cardenas. Amélioration de l'implantation en C des évaluateurs d'attributs produits par FII . Rapport de DEA, Universitéde Paris 7, September 1991.

[31]
Martin Jourdan and Didier Parigot. The FNC-2 System User's Guide and Reference Manual. INRIA, Rocquencourt, 1.9 edition. (Gzipped PostScript, 348 pages, 733303 bytes)

[32]
Martin Jourdan and Didier Parigot. More on speeding up circularity tests for attribute grammars. rapport RR-828, INRIA, Rocquencourt, April 1988.

[33]
Martin Jourdan and Didier Parigot. The FNC-2 system: Advances in attribute grammar technology. In O. M. Tammepuu, editor, Procs. of the Soviet-French Symposium Informatika '89, pages 94-118, Tallinn, May 1989. See also: rapport RR-834, INRIA, Rocquencourt (April 1988).

[34]
Martin Jourdan and Didier Parigot. Techniques for Improving Grammar Flow Analysis. In Neil Jones, editor, European Symp. on Programming (ESOP '90), volume 432 of Lect. Notes in Comp. Sci., pages 240-255, Copenhague, 1990. Springer-Verlag. (Gzipped PostScript, 17 pages, 76745 bytes)
Grammar Flow Analysis (GFA) is a computation framework that can be applied to a large number of problems expressed on context-free grammars. In this framework, as was done on programs with Data Flow Analysis, those problems are split into a general resolution procedure and a set of specific propagation functions. This paper presents a number of improvement techniques that act on the resolution procedure, and hence apply to every GFA problem: grammar partitioning, non-terminals static ordering, weak stability and semantic stability. Practical experiments using circularity tests for attribute grammars will show the benefit of these improvements.

[35]
Martin Jourdan and Didier Parigot. Internals and Externals of the FNC-2 Attribute Grammar System. In Henk Alblas and Borivoj Melichar, editors, Attribute Grammars, Applications and Systems, volume 545 of Lect. Notes in Comp. Sci., pages 485-504. Springer-Verlag, Prague, 1991.
FNC-2 is a modern attribute grammar processing system aiming at expressive power, efficiency, ease of use and versatility. This paper provides the reader with a brief tour inside FNC-2, presenting the most important features of its ``engine'': efficient sequential exhaustive, parallel exhaustive and sequential incremental evaluation of strongly non-circular AGs. These methods are based on the visit-sequence paradigm; the first one makes use of extensive space optimizations. Then we describe the external features of the system--attribute coupled grammar view of an AG, specially-designed AG-description language, with provisions for true modularity, and complete environment--that make it really usable for developing large-scale applications. Experience with the system is briefly reported.

[36]
Martin Jourdan and Didier Parigot. Application development with the FNC-2 attribute grammar system. In Dieter Hammer, editor, Compiler Compilers '90, Lecture Notes in Computer Science, pages 85-94. Springer-Verlag, New York-Heidelberg-Berlin, October 1990 January 1992. Schwerin. (Gzipped PostScript, 15 pages, 71416 bytes)
FNC-2 is an advanced attribute grammar system aiming at production-quality, currently under development at INRIA. After a brief tour through its internals and a short presentation of its input language Olga, the talk will concentrate on how FNC-2 and its companions can be used to develop large language-processing applications. The key feature for enhancing programmers' productivity and supporting teamwork is FNC-2 constructs for modularity. This will be exemplified by the development of FNC-2 itself. Finally we'll present how FNC-2 can be combined with other tools under development at INRIA to form a complete, high-quality compiler production workbench.

[37]
Martin Jourdan, Carole Le Bellec, and Didier Parigot. The Olga Attribute Grammar Description Language: Design, Implementation and Evaluation. In Pierre Deransart and Martin Jourdan, editors, Attribute Grammars and their Applications (WAGA), volume 461 of Lect. Notes in Comp. Sci., pages 222-237, Paris, 1990. Springer-Verlag.
Olga is the input language of the FNC-2 attribute grammar processing system, currently under development at INRIA. As such, it is designed for the specification of attribute grammars and is specialized for this purpose. The features of Olga can be classified into those which make it a powerful general-purpose applicative language and those which make it a specialized AG-description language. A remarkable feature of Olga is its strong support for modularity. The paper discusses the design goals for Olga and presents the most important aspects of the language. It also includes comparisons with other existing languages, an overview of the implementation of Olga, namely the FNC-2 system, and an account of the experience gained in using Olga.

[38]
Martin Jourdan, Didier Parigot, Catherine Julié, Olivier Durin, and Carole Le Bellec. Design, implementation and evaluation of the FNC-2 attribute grammar system. In Conf. on Programming Languages Design and Implementation, pages 209-222, White Plains, NY, June 1990. Published as sl ACM SIGPLAN Notices, 25(6). (Gzipped PostScript, 14 pages, 80244 bytes)
FNC-2 is a new attribute grammar processing system aiming at expressive power, efficiency, ease of use and versatility. Its development at INRIA started in 1986, and a first running prototype is available since early 1989. Its most important features are: efficient exhaustive and incremental visit-sequence-based evaluation of strongly (absolutely) non-circular AGs; extensive space optimizations; a specially-designed AG-description language, with provisions for true modularity; portability and versatility of the generated evaluators; complete environment for application development. This paper briefly describes the design and implementation of FNC-2 and its peripherals. Then preliminary experience with the system is reported.

[39]
Martin Jourdan, Bruno Marmol, and Didier Parigot. Experiments with a Real Parallel Attribute Evaluator. En préparation pour soumission, 1994. (Gzipped PostScript, 10 pages, 83243 bytes)
We present a simple but effective method for constructing efficient attribute evaluators for the class of lordattribute grammars that run on tightly-coupled (shared-memory) multi-processor machines. We also give an account of how we implemented this method in practice. Lastly, we give some figures drawn from realistic experiments, i.e.actual implementation of parallel evaluators for meaningful AGs and their runs on meaningful source texts. The results we have obtained are quite satisfactory, since we observe a quasi-linear speedup with a number of processors varying up to a reasonable number, while the performance with one processor is already quite acceptable.

[40]
Martin Jourdan. A Survey of Parallel Attribute Evaluation Methods. In Henk Alblas and Borivoj Melichar, editors, Attribute Grammars, Applications and Systems, volume 545 of Lecture Notes in Computer Science, pages 234-255, New York-Heidelberg-Berlin, June 1991. Springer-Verlag. Prague.

[41]
Martin Jourdan. Des bienfaits de l'analyse statique sur la mise en oe uvre des grammaires attribuées. Mémoire d'habilitation, Département de Mathématiques et d'Informatique, Université d'Orléans, 1992. (Gzipped PostScript, 64 pages, 253337 bytes)

[42]
Jean-Philippe Jouve. Réalisation du décompilateur d'arbres attribués du système FNC-2 : ppat . Rapport de stage d'option, École Polytechnique, 1991. (Gzipped PostScript, 214 pages, 236395 bytes)

[43]
Catherine Julié and Didier Parigot. Space Optimization in the FNC-2 Attribute Grammar System. In Pierre Deransart and Martin Jourdan, editors, Attribute Grammars and their Applications (WAGA), volume 461 of Lect. Notes in Comp. Sci., pages 29-45, Paris, September 1990. Springer-Verlag. (Gzipped PostScript, 15 pages, 71879 bytes)
Memory space management for attribute evaluators is a vital requirement in practice. In fact, using attribute grammars (AGs) will very quickly meet the problem of memory space if it isn't taken into special consideration. We consider this problem for evaluators of the simple multi-visit class, also called l-ordered, because it is the largest possible AGs class for which we can find, at construction time, a method for memory space optimization. We present a new algorithm which decides, at generation time, if it is possible to store attribute instances in global stacks or global variables. The purpose of this approach is to reduce not only memory space, but also as much as possible the number of attributes to be stored in the nodes of the tree. This method is implemented in the new attribute grammar processing system, named FNC-2. Finally we present our first practical results which seem very promising.

[44]
Catherine Julié and Didier Parigot. Space Optimization in the FNC-2 Attribute Grammar System. Rapport de recherche 1165, INRIA, 1990.
Memory space management for attribute evaluators is a vital requirement in practice. In fact, using attribute grammars (AGs) will very quickly meet the problem of memory space if it isn't taken into special consideration. We consider this problem for evaluators of the simple multi-visit class, also called l-ordered, because it is the largest possible AGs class for which we can find, at construction time, a method for memory space optimization. We present a new algorithm which decides, at generation time, if it is possible to store attribute instances in global stacks or global variables. The purpose of this approach is to reduce not only memory space, but also as much as possible the number of attributes to be stored in the nodes of the tree. This method is implemented in the new attribute grammar processing system, named FNC-2. Finally we present our first practical results which seem very promising.

[45]
Catherine Julié. Optimisation de l'espace mémoire pour les compilateurs générés selon la méthode d'évaluation OAG: étude des travaux de kastens et propositions d'améliorations. rapport de DEA, Dépt. d'Informatique, University d'Orléans, September 1986.

[46]
Catherine Julié. Optimisation de l'espace mémoire pour l'évaluation de grammaires attribuées. PhD thesis, Université d'Orléans, September 1989.

[47]
Carole Le Bellec, Martin Jourdan, Didier Parigot, and Gilles Roussel. Specification and Implementation of Grammar Coupling Using Attribute Grammars. In Maurice Bruynooghe and Jaan Penjam, editors, Programming Language Implementation and Logic Programming (PLILP '93), volume 714 of Lect. Notes in Comp. Sci., pages 123-136, Tallinn, August 1993. Springer-Verlag. (Gzipped PostScript, 14 pages, 54522 bytes)
This paper introduces the notion of a coupling of two grammars, defined by associations between their non-terminals and terminals. We present an algorithm for automatically producing, from these associations, an attribute grammar which specifies the translation from one grammar to the other. The motivation for, and context of, this algorithm is our work aiming at improving modularity and reusability of attribute grammars. When it is combined with descriptional composition, we obtain what we consider to be the most declarative framework for this to date.

[48]
Carole Le Bellec. Spécification de règles sémantiques manquantes. rapport de DEA, Dépt. d'Informatique, University d'Orléans, September 1989.

[49]
Carole Le Bellec. La généricité et les grammaires attribuées. PhD thesis, Département de Mathématiques et d'Informatique, Université d'Orléans, 1993. (Gzipped PostScript, 211 pages, 343858 bytes)

[50]
Gilles Le Bâtard. Réalisation dans le système FNC-2 d'un traducteur vers ML. rapport de stage de maîtrise, IFI, Université de Marne-la-Vallée, July 1995.

[51]
Stéphane Leibovitsch. Relations entre la sémantique dénotationnelle et les grammaires attribuées. Rapport de DEA, Universitéde Paris VII, September 1996. (Gzipped PostScript, 51 pages, 113645 bytes)

[52]
Bruno Marmol. Évaluateurs d'attributs parallèles sur multi-processeurs à mémoire partagée. rapport de DEA, University d'Orléans, September 1990.
First (as far as I know) real implementation of a parallel attribute evaluator. (mj)

[53]
Bruno Marmol. La parallélisation et l'optimisation mémoire dans l'évaluation des grammaires attribuées. PhD thesis, Universitéd'Orléans, 1994. (Gzipped PostScript, 126 pages, 343283 bytes)

[54]
Didier Parigot, Etienne Duris, Gilles Roussel, and Martin Jourdan. Les grammaires attribuées : un langage fonctionnel déclaratif. In journées du GDR de programmation, Grenoble, November 1995. (Gzipped PostScript, 12 pages, 46895 bytes)
Bien que les Grammaires Attribuées aient été introduites il y a trente ans, leur manque de pouvoir d'expression les a confinées dans le domaine du traitement des langages de programmation. Dans cet article, nous montrons qu'il est possible d'étendre cette expressivité. Nous soutenons que les Grammaires Attribuées peuvent être utilisées pour décrire des calculs sur des structures qui ne sont pas uniquement des arbres, mais aussi des formes abstraites permettant de décrire des structures infinies. Afin d'atteindre cette expressivité, nous avons introduit deux nouvelles notions : les schémas de productions et les productions conditionnelles. Nous obtenons ainsi un langage dont le pouvoir d'expression est comparable à celui de la plupart des langages fonctionnels du premier ordre, avec un côté déclaratif beaucoup plus marqué. Nos extensions ne remettent pas en cause les bases du formalisme des Grammaires Attribuées sur lesquelles reposent la plupart des travaux concernant celles-ci, en particulier l'analyse statique et la génération d'évaluateurs. Ainsi, les résultats existants peuvent être appliqués directement à nos Grammaires Attribuées étendues, entre autre ceux permettant une implantation efficace (dans notre cas, en utilisant notre système FNC-2). L'intérêt de ces extensions est de redonner aux Grammaires Attribuées leur expressivité intrinsèque. De plus, elles nous permettent d'envisager de nouveaux axes de recherche en comparant nos techniques d'analyses à celles qui ont été développées dans des formalismes de même expressivité.

[55]
Didier Parigot, Etienne Duris, Gilles Roussel, and Martin Jourdan. Attribute grammars: a declarative functional language. Rapport de Recherche 2662, INRIA, October 1995. (Gzipped PostScript, 16 pages, 99960 bytes)
Although Attribute Grammars were introduced thirty years ago, their lack of expressiveness has resulted in limited use outside the domain of static language processing. In this paper we show that it is possible to extend this expressiveness. We claim that Attribute Grammars can be used to describe computations on structures that are not just trees, but also on abstractions allowing for infinite structures. To gain this expressiveness, we introduce two new notions: scheme productions and em conditional productions. The result is a language that is comparable in power to most first-order functional languages, with a distinctive declarative character. Our extensions deal with a different part of the Attribute Grammar formalism than what is used in most works on Attribute Grammars, including global analysis and evaluator generation. Hence, most existing results are directly applicable to our extended Attribute Grammars, including efficient implementation (in our case, using the FNC-2 system http://www-rocq.inria.fr/oscar/www/fnc2/ for more information.)

[56]
Didier Parigot, Etienne Duris, Gilles Roussel, and Martin Jourdan. Les grammaires attribuées : un langage fonctionnel déclaratif. In Journées Francophones des Langages Applicatifs, pages 263-279, Val-Morin, Québec, January 1996. (Gzipped PostScript, 18 pages, 73918 bytes)
Bien que les Grammaires Attribuées aient été introduites il y a trente ans, leur manque de pouvoir d'expression les a confinées dans le domaine du traitement des langages de programmation. Dans cet article, nous montrons qu'il est possible d'étendre cette expressivité. Nous soutenons que les Grammaires Attribuées peuvent être utilisées pour décrire des calculs sur des structures qui ne sont pas uniquement des arbres, mais aussi des formes abstraites permettant de décrire des structures infinies. Afin d'atteindre cette expressivité, nous avons introduit deux nouvelles notions : les schémas de productions et les productions conditionnelles. Nous obtenons ainsi un langage dont le pouvoir d'expression est comparable à celui de la plupart des langages fonctionnels du premier ordre, avec un côté déclaratif beaucoup plus marqué. Nos extensions ne remettent pas en cause les bases du formalisme des Grammaires Attribuées sur lesquelles reposent la plupart des travaux concernant celles-ci, en particulier l'analyse statique et la génération d'évaluateurs. Ainsi, les résultats existants peuvent être appliqués directement à nos Attribute Grammars étendues, entre autre ceux permettant une implantation efficace (dans notre cas, en utilisant notre système FNC-2). L'intérêt de ces extensions est de redonner aux Grammaires Attribuées leur expressivité intrinsèque. De plus, elles nous permettent d'envisager de nouveaux axes de recherche en comparant nos techniques d'analyses à celles qui ont été développées dans des formalismes de même expressivité.

[57]
Didier Parigot, Gilles Roussel, Martin Jourdan, and Etienne Duris. Dynamic Attribute Grammars. In Herbert Kuchen and S. Doaitse Swierstra, editors, Int. Symp. on Progr. Languages, Implementations, Logics and Programs (PLILP'96), volume 1140 of Lect. Notes in Comp. Sci., pages 122-136, Aachen, September 1996. Springer-Verlag. (Gzipped PostScript, 15 pages, 96012 bytes)
Although Attribute Grammars were introduced long ago, their lack of expressiveness has resulted in limited use outside the domain of static language processing. With the new notion of Dynamic Attribute Grammars defined on top of Grammar Couples, we show that it is possible to extend this expressiveness and to describe computations on structures that are not just trees, but also on abstractions allowing for infinite structures. The result is a language that is comparable in power to most first-order functional languages, with a distinctive declarative character. In this paper, we give a formal definition of Dynamic Attribute Grammars and show how to construct efficient visit-sequence-based evaluators for them, using traditional, well-established AG techniques (in our case, using the FNC-2 system)

[58]
Didier Parigot, Gilles Roussel, Martin Jourdan, and Etienne Duris. Dynamic Attribute Grammars. Rapport de recherche 2881, INRIA, May 1996. (Gzipped PostScript, 32 pages, 196959 bytes)
Although Attribute Grammars were introduced long ago, their lack of expressiveness has resulted in limited use outside the domain of static language processing. With the new notion of Dynamic Attribute Grammars defined on top of Grammar Couples, informally presented in a previous paper, we show that it is possible to extend this expressiveness and to describe computations on structures that are not just trees, but also on abstractions allowing for infinite structures. The result is a language that is comparable in power to most first-order functional languages, with a distinctive declarative character. In this paper, we give a formal definition of Dynamic Attribute Grammars and show how to construct efficient visit-sequence-based evaluators for them, using traditional, well-established AG techniques (in our case, using the FNC-2 system). The major contribution of this approach is to restore the intrinsic power of Attribute Grammars and re-emphasize the effectiveness of analysis and implementation techniques developed for them.

[59]
Didier Parigot. Un système interactif de trace des circularités dans une grammaire attribuée et optimisation du test de circularité. rapport de DEA, University de Paris-Sud, Orsay, September 1985.

[60]
Didier Parigot. Mise en oe uvre des grammaires attribuées: transformation, évaluation incrémentale, optimisations. thèse de 3ème cycle, University de Paris-Sud, Orsay, September 1987.

[61]
Didier Parigot. Transformations, Évaluation Incrémentale et Optimisations des Grammaires Attribués: Le Système FNC-2. PhD thesis, Université de Paris-Sud, Orsay, 1988.

[62]
Didier Parigot. Le programme scientifique. Technical report, INRIA, February 1997. (DVI, 24 pages, 90520 bytes)

[63]
Didier Parigot. Travaux de recherche effectués. Technical report, INRIA, February 1997. (DVI, 40 pages, 163256 bytes)

[64]
Étienne Planes. PPAT: un décompilateur d'arbres attribués pour le système FNC-2. rapport de DEA, Dépt. d'Informatique, University d'Orléans, September 1989.

[65]
Christophe Roudet. Visualisation graphique incrémentale par évaluation d'attributs. Stage de DEA informatique de l'ESSI, UniversitéNICE, 1994. (Gzipped PostScript, 90 pages, 370190 bytes)

[66]
Gilles Roussel, Didier Parigot, and Martin Jourdan. Coupling Evaluators for Attribute Coupled Grammars. In Peter A. Fritzson, editor, 5th Int. Conf. on Compiler Construction (CC' 94), volume 786 of Lect. Notes in Comp. Sci., pages 52-67, Edinburgh, April 1994. Springer-Verlag. (Gzipped PostScript, 16 pages, 58989 bytes)
Some years ago, the notion of attribute coupled grammars was introduced by Ganzinger and Giegerich, together with descriptional composition. The latter works essentially at the specification level, i.e., it produces an attribute grammar which specifies the composition of two attribute coupled grammars. We introduce a new approach to this composition of attribute coupled grammars. This composition no longer works at the specification level but at the evaluator level. It produces a special kind of attribute evaluator. For this purpose we have introduced the notion of coupling evaluator. The main advantage of this new approach, compared with descriptional composition, is that it is possible to build separately the coupling evaluator of each attribute coupled grammar; in other words it allows real separate compilation of AG modules. Another important advantage is that we do not need to check the attribute grammar class in order to construct the final sequence of evaluators; thus, this construction produces a new sort of evaluator.

[67]
Gilles Roussel, Didier Parigot, and Martin Jourdan. Static and Dynamic Coupling Attribute Evaluators. Rapport de recherche 2670, INRIA, October 1995. (Gzipped PostScript, 16 pages, 111986 bytes)
Several years ago, the notion of attribute coupled grammars was introduced by Ganzinger and Giegerich, together with their descriptional composition. The latter works essentially at the specification level, i.e., it produces an attribute grammar which specifies the composition of two attribute coupled grammars. We introduce a new approach to this composition of attribute coupled grammars. It no longer works at the specification level but rather at the evaluator level. It produces a special kind of attribute evaluator, called coupling evaluator. We present both a static version and a dynamic version of coupling evaluators. Both versions retain the good property of descriptional composition that intermediate trees are not physically constructed. In addition--and this is the main advantage of our approach, compared with descriptional composition---, it is possible to build separately the dynamic coupling evaluator of each attribute coupled grammar; in other words we achieve real separate compilation of AG modules.

[68]
Gilles Roussel. Élimination de suites de règles de copies dans les grammaires attribuées. 1992.

[69]
Gilles Roussel. Méta-composition des grammaires attribuées. rapport de magistère, École Normale Supérieure, Paris, September 1992.

[70]
Gilles Roussel. Algorithmes de base pour la modularité et la réutilisabilité des grammaires attribuées. PhD thesis, Département d'Informatique, Université de Paris 6, March 1994. (Gzipped PostScript, 148 pages, 461010 bytes)

[71]
Philippe Rouzier. Réalisation d'une interface entre les systèmes Centaur, FNC-2 et syntax. Rapport de stage de DESS ``Systèmes et communication homme-machine'', Université de Paris 11, September 1993. (Gzipped PostScript, 46 pages, 75066 bytes)

[72]
Aziz Souah. Système de transformation d'arbres attribués: étude des principaux systèmes et spécification d'un nouveau système. rapport de DEA, University d'Orléans, September 1987.

[73]
Aziz Souah. Contribution à la sémantique déclarative des systèmes de transformation d'arbres attribués. PhD thesis, Universitéd'Orléans, November 1990.

[74]
Souad Taouil. Étude et implantation des grammaires couplées par attributs dans le système FNC-2. rapport de DEA, Dépt. d'Informatique, University d'Orléans, September 1988.

[75]
Bruno Vivien. Etude et réalisation d'un compilateur E-LOTOS à l'aide du générateur de compilateurs SYNTAX/FNC-2. Diplome d'ingenieur CNAM en informatique, Conservatoire National des Arts et Métiers, De'cembre 1997.

[76]
Catherine Zylberman. Réalisation du constructeur d'arbre abstrait (ATC) du système de grammaire attribuée FNC-2 au dessus de l'analyseur lexico-syntaque lex-yacc. Rapport de stage de troisième année, Telecom Paris, 1990.