Publications on FNC-2 Attribute Grammar system

© Copyright Notice:
The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Updated on Fri Jun 25 14:16:07 MET 1999

[1]

Loic Correnson. Equational Semantics. Informatica (Solvenia), 1999. (Gzipped PostScript, 11 pages, 84407 bytes)

Attribute grammars are well-designed to construct complex algorithms by composing several ones together. Actually, there exists a powerful transformation called descriptional composition which highly simplifies the composition of two attribute grammars by removing useless intermediate constructions. However, most of non-linear algorithms can not be expressed with attribute grammars. Thus, many compositions can not be simplified by the decriptional composition. In this paper, we present Equational Semantics, a formalism largely inspired by attribute grammars but where non-linear algorithms can be encoded. More precisely, instead of being restricted to one input static tree as it is the case for attribute grammars, an algorithm encoded with Equational Semantics may use dynamically constructed trees. This formalism consists in an very poor abstract syntax. We present its semantics and some of its transformations such as partial evaluation and decriptionnal composition (also called deforestation).

[2]

Loïc Correnson, Etienne Duris, Didier Parigot, and Gilles Roussel. Declarative program transformation: a deforestation case-study. accepted at PPDP'99 and early version, 1999. (Gzipped PostScript, 17 pages, 102270 bytes)

Software engineering has to reconcile modularity with efficiency. One way to grapple with this dilemma is to automatically transform a modular-specified program into an efficient-implementable one. This is the aim of deforestation transformations which get rid of intermediate data structure constructions that occur when two functions are composed. Beyond classical compile time optimization, these transformations are undeniable tools for generic programming and software component specialization. Despite various and numerous research works in this area, general transformation methods cannot deforest some non-trivial intermediate constructions. Actually, these recalcitrant structures are built inside emph accumulating parameters and then, they follow a construction scheme which is independent from the function scheme itself. Known deforestation methods are too much tied to fixed recursion schemes to be able to deforest these structures. In this article, we show that a fully declarative approach of program transformation allows new deforestation sites to be detected and treated. We present the principle of the symbolic composition, based on the attribute grammar formalism, with an illustrative running example stemming from a typical problem of standard functional deforestations.

[3]

Loïc Correnson, Etienne Duris, Didier Parigot, and Gilles Roussel. Equational semantics. accepted at SAS'99 and early version, 1999. (Gzipped PostScript, 15 pages, 112513 bytes)

In the context of functional programming, semantic methods are commonly used to drive program transformations. However, classical semantic domains often rely on recursive objects which embed the control flow of recursive functions. As a consequence, transformations which have to modify the control flow are difficult to define. We propose in this paper a new semantic domain where the control flow is defined implicitly, and thus can be modified. This new theoretical and practical framework allows to homogeneously define and extend powerful transformations related to partial evaluation and deforestation.

[4]

Loic Correnson. Equational Semantics. In D. Parigot and M. Mernik, editors, Second Workshop on Attribute Grammars and their Applications, WAGA'99, pages 205-222, Amsterdam, The Netherlands, March 1999. INRIA rocquencourt. (PostScript, 18 pages, 206610 bytes)

Attribute grammars are well-designed to construct complex algorithms by composing several ones together. Actually, there exists a powerful transformation called descriptional composition which highly simplifies the composition of two attribute grammars by removing useless intermediate constructions. However, most of non-linear algorithms can not be expressed with attribute grammars. Thus, many compositions can not be simplified by the decriptional composition. In this paper, we present Equational Semantics, a formalism largely inspired by attribute grammars but where non-linear algorithms can be encoded. More precisely, instead of being restricted to one input static tree as it is the case for attribute grammars, an algorithm encoded with Equational Semantics may use dynamically constructed trees. This formalism consists in an very poor abstract syntax. We present its semantics and some of its transformations such as partial evaluation and decriptionnal composition (also called deforestation).

[5]

Didier Parigot and Marjan Mernik, editors. Second Workshop on Attribute Grammars and their Applications WAGA'99, Amsterdam, The Netherlands, March 1999. ETAPS'99, INRIA rocquencourt. Satellite event of ETAPS'99.

[6]

Loic Correnson, Etienne Duris, Didier Parigot, and Gilles Roussel. Equational semantics. submit, INRIA, October 1998. (Gzipped PostScript, 13 pages, 81455 bytes)

Many methods exist to perform program transformations, but most of them are dedicated to few programming languages. We propose a new formalism able to encode an abstract representation of the operational semantics of a program. With this formalism, we define simple transformations that lead to complex ones such as deforestation or partial evaluation in several programming languages. Though highly theoretical and language-independent, this method can be implemented and especially interfaced with real programming languages. For instance, a prototype dealing with a simple higher-order functional programming language has been implemented (with a call-by-value operational semantics). This prototype produces some more powerful transformations than other known functional methods, especially with deforestation on functions with accumulative parameters.

[7]

Loic Correnson, Etienne Duris, Didier Parigot, and Gilles Roussel. How to deforest in accumulative parameters?. Technical Report 3608, INRIA, January 1999. (Gzipped PostScript, 23 pages, 143925 bytes)

Software engineering has to reconcile modularity with efficiency. One way to grapple with this dilemma is to automatically transform a modular-specified program into an efficient-implementable one. This is the aim of deforestation transformations which get rid of intermediate data structures constructions that appear when two functions are composed. Nevertheless, existing functional methods cannot deforest non-trivial intermediate constructions that are processed by symbolic composition. This new deforestation technique is based on the descriptional composition dedicated to attribute grammars. In this paper, we present the symbolic composition, we outline its counterpart in terms of classical deforestation methods and we sketch a way to embed it in a functional framework.

[8]

Loïc Correnson, Etienne Duris, Didier Parigot, and Gilles Roussel. A generic framework for genericity. English version of, 1998. (Gzipped PostScript, 7 pages, 65289 bytes)

Recently, generic programming becomes of a major interest in several programming paradigms. A recurrent idea to achieve genericity is to specify algorithms on their convenient data structure, and to allow these specifications to be instantiated onto a large number of neighboring data structures. Polytypic programming, shapely types and generic attribute grammars are generic programming methods related to this approach. A framework for generic programming is proposed to embed these methods. It consists in tools for automatic generation of morphisms between data structures, and for program composition. Thanks to this compositional approach, the complete specialization of generic programs could be advantageously delegated to a general and powerful mechanism of ``symbolic composition'', which performs deforestation and partial evaluation.

[9]

Loïc Correnson, Etienne Duris, Didier Parigot, and Gilles Roussel. Schéma générique de développement par composition. In Approches Formelles dans l'Assistance au Développement de Logiciel AFADL'98, Poitiers - futuroscope, 1998. (Gzipped PostScript, 14 pages, 72890 bytes)

Depuis peu, la programmation générique suscite un intérêt grandissant dans différents paradigmes de programmation. Un principe souvent utilisé pour obtenir de la généricité est d'abstraire les calculs d'un programme par rapport à leur structure de données. Cette approche permet à ces spécifications génériques d'être instanciées pour un grand nombre de structures de données voisines. De plus, le programme peut ainsi être automatiquement adapté lorsque les structures de données évoluent. La programmation polytypique, la programmation adaptive et les grammaires attribuées génériques sont des méthodes formelles de programmation génériques qui adoptent cette approche. La comparaison de ces méthodes nous a conduit à proposer un schéma commun de développement de programmes génériques. Cette méthode est basée sur deux concepts fondamentaux : la génération automatique de morphismes entre structures de données, et l'instanciation formelle des programmes génériques par composition, assistée par des outils de spécialisation.

[10]

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.

[11]

Loïc Correnson, Etienne Duris, Didier Parigot, and Gilles Roussel. Symbolic composition. Technical Report 3348, INRIA, January 1998. rejected. (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.

[12]

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.

[13]

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)

[14]

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.

[15]

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.

[16]

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.

[17]

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.

[18]

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

[19]

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.

[20]

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.

[21]

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)

[22]

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.

[23]

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é.

[24]

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.)

[25]

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é.

[26]

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.

[27]

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.

[28]

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.

[29]

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.

[30]

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.

[31]

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.

[32]

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.

[33]

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.

[34]

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.

[35]

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.

[36]

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.

[37]

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.

[38]

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).

[39]

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

[40]

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.

[41]

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.

[42]

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.