T5 - Application Domain 3: Attribute Grammars

Attribute grammars (AGs) are widely used to specify complex transformations from a source program/language into a target one. One well-known and natural application is to define language-based editors: the user edits a source program and the editor (incrementally) computes the target program [34]. These editors, however, do not provide bidirectional transformations, since they are not able to synchronize the source program after a change in the target.

Surprisingly no work has been done in bidirectionalization for AGs directly or in applying existing bidirectional transformation results to AGs, excepting [6]. This work used strings and is not applicable to the hierarchical structures nor the non-hierarchical structures of interest here. Modern extensions to AGs include references attributes; these allow graphs (non-hierarchical models) to be specified in addition to the traditional syntax trees (hierarchical models). Thus, results from task 2 for non-hierarchical bidirectional transformations will be applicable to graphs used in AG with reference attributes. This will enable the envisioned bidirectional language-based environments. Furthermore, because reference attributes are typically used to impose a non-hierarchical structure on top of an existing hierarchical one (the syntax tree) these may form a restricted yet still useful and interesting sub-class of non-hierarchical models that may provide application-based feedback to the theoretical work of task 2.

A main objective of this task is to study and develop techniques to incorporate all recent advances in bidirectional transformations into modern extensions of AG. Thus, we will study the foundations of bidirectionalization in modern AG extensions. Furthermore, we will study how to derive the attribute grammar specification of a backward transformation from the specification of the forward transformation. Finally, we will study how to adapt techniques to produce highly optimized implementations for AG, in order to efficiently and incrementally execute bidirectional transformations. Finally, we will incorporate these techniques into a bidirectional attribute grammar (BAG) based system.

Two senior team members have done some initial investigations together into BAGs and a research paper has been submitted. We will build on these results to create a comprehensive, rigorous approach to bidirectional programming in AG.

The team members have extensive experience in building AG-related artifacts, namely: AG extensions [21], tools [5, 34], optimization/implementation techniques [33,35], AG-based libraries [33] and incremental language-based tools [34]. We will adapt the common framework developed in task 2 to work in an AG setting, specifically as an extension to Silver [5]. Furthermore, the task leader Van Wyk is currently on sabbatical leave at the University of Minho working on bidirectional transformations. This work relates to two existing NSF funded projects that use AGs to build extensible languages tailored to developing high performance programs in data mining and materials science simulations. Since the work proposed here relates directly to the work on these projects Van Wyk will be requesting supplemental funding through the NSF Office of International Science and Engineering for other members of his research group to visit Minho University and actively participate in this project. A BI grant is being requested to support tool implementation.

The expected deliverables of this task are:

• A set of techniques and tools that will help programmers to specify powerful transformations in the elegant and concise AG formalism, and to efficiently execute such transformations in advanced BT environments that are automatically generated from an AG.
• A master thesis detailing the implementation of such tools.
• Two international conference papers and a journal paper describing the achieved results.

Team

• Eric Van Wyk [Task Leader]
• João Paulo Fernandes
• João Saraiva
• Jácome Cunha
• BI5