Third Workshop on Attribute Grammars and their Applications WAGA'00

Ponte de Lima, Portugal

July 7, 2000

Editors: Didier Parigot and Marjan Mernik

Proceedings

Publisher: INRIA Rocquencourt France


[1]
Katsuhiko Gondow and Takuya Katayama. Attribute grammars as record calculus - a structure-oriented denotational semantics of attribute grammars by using cardelli's record calculus -. Dept. of Information Science, Japan Advanced Inst. of Science and Technology, 1-1 Asahidai Tatsunokuchi Nomi Ishikawa, 923-1292, JAPAN, gondow@jaist.ac.jp. (PostScript, 20 pages, 667486 bytes)
In this paper, we present a new denotational semantics of attribute grammars (AGs) by using Cardelli's record calculus. This new denotational semantics is simple, natural and structure-oriented. AGs have been considered useful in describing interactive programming environments as well as in specifying the semantics of programming languages. Using AGs, interactive programming environments are often described as attributed trees with several AG extensions, e.g., higher-order features, subtree replacements, and remote access. Unfortunately, it was not easy to compare various definitions for these extensions in a formal way. One of the reasons is that previous studies for AG semantics are not structure-oriented, that is, they are based on attribute valuation, not an attributed tree itself. For example, AG semantics based on attribute valuation can not deal directly with program transformation such as a times (b+c) To a times b+a times c. In our new semantics, an attributed tree is represented as a nested record to preserve the structural information of the attributed tree. This enables us to deal directly with attributed trees rather than attribute valuation as AG semantics. We also represent higher-order AGs, recursive AGs and OOAG as record calculus by extending the semantics to show that our semantics can formalize such AG extensions. Both of higher-order AGs and OOAG are computational models to deal with tree transformation depending on attribute values.

[2]
Hiroaki Kameyama Hisashi Nakai, Masataka Sassa and Ikuo Nakata. Incremental attribute evaluation without parse trees. 1-2 Kasuga Tsukuba, 305-8550, Japan, nakai@ulis.ac.jp. (PostScript, 18 pages, 501614 bytes)
The goal of researches for incremental attribute evaluation was to minimize the re-evaluation area for the reconstructed parse tree which is made by an incremental parser or a syntax directed editor. On the other hand, there was no proposal of incremental attribute evaluation based on one-pass-type attribute grammar. In this paper, an incremental attribute evaluation method based on LR-attributed grammar which is a class of one-pass attribute grammar is described. Firstly, we propose a method of incremental attribute evaluation using a parse tree, and then we mention space optimized incremental attribute evaluation method using more compact data structure whose number of nodes is same as tokens. We also describe the optimization to avoid unnecessary re-evaluation, for example, reusing a subtree. Lastly, we describe the implementation of the generator of incremental attribute evaluator by augmenting Rie (an attribute evaluator generator based on ECLR-attributed grammar) and show the results of experiments of executing the incremental attribute evaluators generated. As a result of non-optimized attribute evaluation, each execution time for the re-evaluation is from 40 to 80% of the first evaluations. In the case of the result of optimized attribute evaluation, each the time for re-evaluation is from 5% to 15% of the first evaluation. The results demonstrate the efficiency of incremental re-evaluation.

[3]
Takashi Imaizumi Takeshi Hagiwara, Katsuhiko Gondow and Takuya Katayama. Using object-oriented attribute grammars as odb system generator. Dept. of Information Engineering Faculty of Engineering Niigata University 8050 Ikarashi 2-nocho, Niigata 950-2181, Japan, hagiwara@ie.niigata-u.ac.jp. (PostScript, 20 pages, 929925 bytes)
This paper presents MAGE2 system. It implements a computational model OOAG (Object-Oriented Attribute Grammars) and creates its attributed object trees in object-oriented database (ODB) using persistent object allocation mechanism of object-oriented database management systems (ODBMS). The MAGE2 is a programming support and execution environment for OOAG. The focus of this paper is on an execution system. We indicate core techniques to implement MAGE2, that is, how to execute specifications of OOAG and how to generate an ODB system. We are planning to use MAGE2 to design databases for storing data that have logical structures such as program source files, XML documents and so on. It is to say MAGE2 is a tool for generating ODB system.

[4]
Aino Cornils and Görel Hedin. Tool support for design patterns using specification with reference attributed grammars. Department of Computer science University of Aarhus Aabogade 34 DK-8200 Aarhus N., apaipi@daimi.au.dk. (PostScript, 18 pages, 810552 bytes)
Design patterns are abstract descriptions of solutions to often recurring problems. They are a means to communicate experience in design. Over the past years, along with the increase in popularity of object-oriented design patterns, some problems with the use of them have been identified. One of these lies in documenting software systems using design patterns. Experience has shown that both in the initial design, and especially in later code revisions, it is all too easy for code and documentation to diverge, rendering the documentation misleading and the code inconsistent. In this paper we present a flexible and extensible tool which enables designers to use design patterns in a safe and easy way and which semi-automatically documents and maintains the documentation of a software system. The system is implemented using reference attributed grammars (RAGs) which are capable of describing non-local dependencies. Both the programming language and the design patterns are specified using RAGs, and reference attributes are used for connecting design pattern instances to the corresponding elements in the program code.

[5]
A. G. Manousopoulou and G. Papakonstantinou. A grammatical approach to user model resolution for electronic shopping. Computer Systems Laboratory National Technical University of Athens Iroon Polytechneioy 9 15773 Athens Greece, natasha@cslab.ece.ntua.gr. (PostScript, 8 pages, 900424 bytes)
Electronic shopping is a rapidly expanding market and can reap benefits from the employment of user modeling techniques. In this paper we present a methodology for user modeling that uses attribute grammars to extract a user representation from the navigation of the user inside the electronic shop, and can be applied incrementally.

[6]
Akira Sasaki and Masataka Sassa. Circular attribute grammars with remote attribute references. Dept. of Mathematical and Computing Sciences, Graduate School of Information Science and Engineering, Tokyo Institute of Technology 2-12-1, Ookayama, Meguro-ku, Tokyo, 152-8552, Japan, sasaki@is.titech.ac.jp. (PostScript, 16 pages, 363461 bytes)
Attribute grammar (AG) is a suitable formalism for development of language processing systems. However, for languages including unrestricted labeled jumps, like gotos in C, optimizers in compilers are hard to be written in AG. This is due to two problems which former researches could not deal with simultaneously, i.e., references of attribute values on distant nodes and circularity in attribute dependency. This paper proposes the circular remote attribute grammar (CRAG), an extended AG which allows (1)direct description of relations between two distant attribute instances through pointers referring to other nodes in the derivation tree, and (2)circular dependency under certain conditions including those which arise from remote references. This extension gives AG programmers a natural way to describe language processors and programming environments for languages including any type of labeled jumps. We will also show a way to construct a static evaluator for CRAGs that has efficient run-time performance. The usability of CRAG is also presented by an example application, the SSA translator, which is a part of our compiler for a subset of C language.

[7]
Jörg Harm and Ralf Lämmel. Testing attribute grammars. CWI, P.O. Box 94079, NL-1090 GB Amsterdam, ralf@cwi.nl. (PostScript, 20 pages, 512258 bytes)
Fundamental notions for testing attribute grammars are developed. Two dimensions are explored. The structural dimension focuses on the context-free grammar part of an attribute grammar, whereas the semantic dimension is rather concerned with attributes, attribute types, conditions, and computations. In both dimensions, and also for the combination of them, we are interested in coverage notions, test set criteria, e.g., minimum test sets, and test set generation. The described framework builds upon abstract interpretation technology, certain search algorithms and heuristics. The approach is also applicable to some other representatives of the declarative paradigm, such as logic programming and term rewriting. Examples illustrate that the framework is particularly useful in testing language definitions based on attribute grammar specifications.

[8]
George Economakos, Ioannis Panagopoulos, and George Papakonstantinou. Advances in attribute grammar driven hardware compilation. Mousson 37, GR 145 63, Kifissia GREECE, george@cslab.ece.ntua.gr. (PostScript, 20 pages, 582013 bytes)
High-level or behavioral synthesis of digital circuits offers an effective way to deal with the increasing complexity of digital hardware design. A high-level synthesis tool transforms an abstract algorithmic description into a detailed register transfer level implementation. Since most of the times the algorithmic description is given in textual form, high-level synthesis transformations share common aspects with traditional compiler transformations (the process is also called hardware compilation). As a consequence, hardware compilation can be performed using attribute grammars. However, since modern high-level synthesis transformations are of high complexity, advanced attribute evaluation techniques are required. This paper presents recent advances in hardware compilation under the FNC-2 attribute grammar system. It follows two different approaches. One that decorates the parse tree of the behavioral specification with implementation details, taking advantage of the use of a definition table, and one that constructs and decorates a new tree, which follows the structure of the corresponding data flow graph. Both approaches have been found to be flexible and efficient in supporting future research efforts in the field.


Website: http://www-sop.inria.fr/oasis/WAGA00/waga00.html

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