Second Workshop on Attribute Grammars and their Applications WAGA'99

Amsterdam, The Netherlands

March 26, 1999

Editors: Didier Parigot and Marjan Mernik

Proceedings

Publisher: INRIA Rocquencourt France


[1]
Josef Grosch. Using attribute grammars in industry. In D. Parigot and M. Mernik, editors, Second Workshop on Attribute Grammars and their Applications, WAGA'99, pages 1-16, Amsterdam, The Netherlands, March 1999. INRIA rocquencourt. PDF format. (PostScript, 16 pages, 1688666 bytes)
Are attribute grammars used in industrial applications? Or are attribute grammars just an academic playground? I would like to answer these two ques- tions based on my personal experience. I have been working with attribute grammars for around 17 years now. Around 10 years ago I started creating the Cocktail Toolbox which contains among other tools for compiler construction the attribute grammar tool ag. Five years ago I founded a company named CoCo- Lab which stands for compiler compiler laboratory. The company develops and markets the Cocktail Toolbox as well as parsers generated with Cocktail. We also do project work in the area of compiler construction and programming lan- guages. My first and very spontaneous answers to the above two questions are: Yes, in both cases. Attribute grammars are used in industry and at the same time they can be regarded as academic playground. This does seem contradictory, doesn't it? Therefore let me explain in more detail why I am giving the above answers.

[2]
Aggelos Thanos and George Papakonstantinou. Facilitating the Development of Parallel Implementations of Declarative Programming Languages Using Attribute Grammars. In D. Parigot and M. Mernik, editors, Second Workshop on Attribute Grammars and their Applications, WAGA'99, pages 17-36, Amsterdam, The Netherlands, March 1999. INRIA rocquencourt. PDF format. (PostScript, 20 pages, 350586 bytes)
This paper presents how we can model different control operations on parallel implementations of declarative programming languages. We use a program analysis method based on Attribute Grammar dependency graphs. We present the PAGE framework, which facilitates the development of parallel implementation of declarative languages. As in compiler technology, we use AG as a specification language for the description of the programming paradigms under consideration. Each of the programming paradigms is outlined from a transformation table or a combination of them. These tables consist of transformation actions that have to be applied, under some conditions. The transformations are described in the form of AG semantic rules. With this analysis we can discern a large part of the control of such languages which we can specify in a programmable way. The remain control part is forming a non-programmable layer which is following the restrictions of the underlying hardware architecture of each implementation. In this way we build a layer between the program executed and the control. Using AG technology to specify this control layer is the semantic basis of PAGE. The method can help towards the automation of the development of modern declarative programming languages, such as Concurrent Constraint Logic Programming Languages. The system has been implemented and tested in a wide range of architectures, exhibiting encouraging results.

[3]
Ralf Lämmel and Günter Riedewald. Reconstruction of paradigm shifts. In D. Parigot and M. Mernik, editors, Second Workshop on Attribute Grammars and their Applications, WAGA'99, pages 37-56, Amsterdam, The Netherlands, March 1999. INRIA rocquencourt. PDF format. (PostScript, 20 pages, 361450 bytes)
There are many extensions of the basic attribute grammar formalism intended to improve its pragmatics, e.g.certain modularity concepts, remote access, object-orientation, templates, rule models and higher-order features. In the paper, emph a generic and formal approach to an effective and orthogonal reconstruction of the concepts underlying some extensions is described. The reconstruction is effective in the sense that the reconstructed concepts are presented as executable meta-programs. The approach to reconstruction is formal in the sense that the derived meta-programs modelling certain concepts can be analysed based on properties of the meta-programs, e.g.preservation properties. Furthermore, it is a generic approach because the meta-programming framework can be instantiated not only for attribute grammars but also for several other representatives of the declarative paradigm, e.g.natural semantics and algebraic specification. Thereby, concepts can be imported from and exported to other frameworks. Finally, the reconstructions are derived orthogonally in the sense that potential roles are first unbundled and then particular combinations of the roles can be investigated. The described meta-programming framework has been implemented in the specification framework of LDLand it is used for reusable formal language definition based on attribute grammars and operational semantics.

[4]
Marjan Mernik, Mitja Leni v c, Enis Avdi v cau v  sevi c, and Viljem v  Zumer. Multiple Attribute Grammar Inheritance. In D. Parigot and M. Mernik, editors, Second Workshop on Attribute Grammars and their Applications, WAGA'99, pages 57-76, Amsterdam, The Netherlands, March 1999. INRIA rocquencourt. PDF format. (PostScript, 20 pages, 257543 bytes)
The language design process should be supported by modularity and abstraction in a manner that allows incremental changes as easily as possible. To at least partially fulfill this ambitious goal a new object-oriented attribute grammar specification language which support multiple attribute grammar inheritance is introduced. Multiple attribute grammar inheritance is a structural organization of attribute grammars where the attribute grammar inherits the specifications from ancestor attribute grammars, may add new specifications or may override some specifications from ancestors specifications. With the proposed approach a language designer has the chance to design incrementally a language or reuse some fragments from other programming language specifications. The multiple attribute grammar inheritance is first introduced using an example, and thereafter by a formal model. The proposed approach is successfully implemented in the compiler/interpreter generator tool LISA ver. 2.0.

[5]
Wuu lazybug Yang. A finest partitioning algorithm for attribute grammars. In D. Parigot and M. Mernik, editors, Second Workshop on Attribute Grammars and their Applications, WAGA'99, pages 77-92, Amsterdam, The Netherlands, March 1999. INRIA rocquencourt. PDF format. (PostScript, 16 pages, 214005 bytes)
The attribute dependence graph of a syntax tree may be partitioned into disjoint regions. Attribute instances in different regions are independent of one other. The advantages of partitioning the attribute dependence graph include simplifying the attribute grammar conceptually and allowing the possibility of parallel evaluation. We present a static partitioning algorithm for attribute grammars. The algorithm builds the set of all feasible partitions for every production by analyzing the grammar. After the attributed syntax tree is constructed, one of the feasible partitions is chosen for each production instance in the syntax tree. Gluing together the selected partitions for individual production instances results in a partition of the attribute dependence graph of the syntax tree. No further merging or partitioning is needed at evaluation time. In addition to static partitioning, the algorithm always produces the finest partition of every attribute dependence graph.

[6]
Shin Natori, Katsuhiko Gondow, Takashi Imaizumi, Takeshi Hagiwara, and Takuya Katayama. On Eliminating Type 3 Circularities of Ordered Attribute Grammars. In D. Parigot and M. Mernik, editors, Second Workshop on Attribute Grammars and their Applications, WAGA'99, pages 93-112, Amsterdam, The Netherlands, March 1999. INRIA rocquencourt. PDF format. (PostScript, 20 pages, 714840 bytes)
Ordered attribute grammars (OAGs for short) are a useful class of attribute grammars (AGs). For some attribute grammars, even though they are not circular, OAG circularity test reports that they are not ordered and fails to generate attribute evaluators because of the existence of type 3 circularities. First we discuss that it is sometimes difficult for programmers to eliminate type 3 circularities by hand. Secondly, in order to reduce this difficulty, we propose a new AG class called OAG* that produces less type 3 circularities than OAG while preserving the positive characteristic of OAG. We also show that we obtained good results with our experimental implementation.

[7]
G. Psaila and S. Crespi-Reghizzi. Adding Semantics to XML. In D. Parigot and M. Mernik, editors, Second Workshop on Attribute Grammars and their Applications, WAGA'99, pages 113-132, Amsterdam, The Netherlands, March 1999. INRIA rocquencourt. PDF format. (PostScript, 20 pages, 255287 bytes)
Starting form the analogy between a document tagged by a mark-up language (XML, SGML) and a source string generated by a BNF grammar, we argue that XML parsers should benefit from the addition of semantic attributes and functions. Currently XML only includes initialized lexical attributes. By our approach a XML parser would be extended into a syntax-directed translator. Deep transformations of a document could be specified, sent over the network, and executed within the XML system. For the specification of the semantic attributes and functions we propose a XML Document Type Definition, that is conceptually similar to the metalanguage of a compiler-compiler. By this approach the additions to the XML standard are kept to a minimum.The differences between attribute grammars and attributed XML specifications are discussed, and the system architecture of a semantic evaluator generator is presented.

[8]
Zolt an Alexin, Szilvia Zvada, , and Tibor Gyim othy. Application of AGLEARN on Hungarian Part-of-speech Tagging. In D. Parigot and M. Mernik, editors, Second Workshop on Attribute Grammars and their Applications, WAGA'99, pages 133-152, Amsterdam, The Netherlands, March 1999. INRIA rocquencourt. PDF format. (PostScript, 20 pages, 277488 bytes)
In this paper we present an application of the AGLEARN method to the part-of-speech (POS) tagging of Hungarian sentences. The task of AGLEARN is to infer the semantic functions associated with production. In the learning process the grammar, the background semantic functions and the examples can be used. We applied the AGLEARN method to infer context rules to choose the correct tags. A corpus with about 100 000 pre-tagged words has been used for training and testing. By using AGLEARN method learning data are generated to the C 4.5 attribute value learner. These generated data contain information about the phrase structure of the sentences. A background attribute grammar has been used to determine these sructural information. Our experinces showed that using this structural background information C4.5 learner was able to infer more precise context rules.

[9]
Gorel Hedin. Reference Attributed Grammars. In D. Parigot and M. Mernik, editors, Second Workshop on Attribute Grammars and their Applications, WAGA'99, pages 153-172, Amsterdam, The Netherlands, March 1999. INRIA rocquencourt. PDF format. (PostScript, 503064 bytes)
An extension to canonical attribute grammars is introduced, permitting attributes to be references to arbitrary nodes in the syntax tree, and attributes to be accessed via the reference attributes. Important practical problems such as name and type analysis for object-oriented languages can be expressed concisely in these grammars, and an optimal evaluation algorithm is available. The proposed formalism and algorithm have been implemented in an interactive language development tool.

[10]
Patrik Persson and Görel Hedin. Interactive Execution Time Predictions Using Reference Attributed Grammars. In D. Parigot and M. Mernik, editors, Second Workshop on Attribute Grammars and their Applications, WAGA'99, pages 173-184, Amsterdam, The Netherlands, March 1999. INRIA rocquencourt. PDF format. (PostScript, 12 pages, 657585 bytes)
A central problem for real-time scheduling is to acquire tight but conservative bounds on task execution times. We present a prototype for an environment where such bounds are interactively presented, in terms of source code constructs, to the programmer during development. The prototype is based on the language development tool APPLAB and uses an extended attribute grammar formalism, reference attributed grammars (RAGs), which overcomes some drawbacks of conventional attribute grammars in this context (e.g. description of non-local dependencies). In this paper we show how timing schemata can be implemented as RAGs. Our experience is that the RAG approach allows timing schemata to be implemented in a clear, concise, and modular manner.

[11]
Joao Saraiva and Doaitse Swierstra. Generic Attribute Grammars. In D. Parigot and M. Mernik, editors, Second Workshop on Attribute Grammars and their Applications, WAGA'99, pages 185-204, Amsterdam, The Netherlands, March 1999. INRIA rocquencourt. PDF format. (PostScript, 20 pages, 354396 bytes)
This paper introduces generic attribute grammars which provide a support for genericity, reusability and modularity in attribute grammars. A generic attribute grammar is a component which is easily reused, composed and understood. An attribute grammar based system is constructed out of a set of such generic components. These components can be analysed and compiled separately. Furthermore, deforestated attribute evaluator are derived for each component. As result, redundant intermediate data structures used to glue different components are eliminated.

[12]
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. PDF format. (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).

[13]
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.


Website: http://www-rocq.inria.fr/oscar/waga99.html

Last modified Web page maintained by Didier.Parigot@inria.fr

Back to ETAPS'99 page