Thirty years ago Attribute Grammars were introduced by Knuth [Knu68] and since then they have been widely studied [DJL88, DJ90, AM91]. An Attribute Grammar is a declarative specification that describes how attributes (variables) are computed for rules in a particular syntax (i.e., it is syntax driven). Attribute Grammars were originally introduced as a formalism for describing compilation applications; they were intended to describe how to decorate a tree, and could not be easily thought about in the absence of the structure (tree) representing the program to compile. In this application area, Attribute Grammars were recognized as having these two important qualities:
In spite of that, Attribute Grammar specifications are still not as widely used as they could be. Because of the historical roots of Attribute Grammars in compiler construction, the notion of (physical) tree was considered as the only way to direct computations. This is the main cause for their lack of use and lack of expressiveness. First, there are few application domains, apart from compilation, that naturally provide a tree as the main input. Furthermore, in the absence of such a tree, the computation model is quite weak: you cannot even define the factorial function with a pure, classical Attribute Grammar. This lack of expressiveness and disagreement on basic issues inside the Attribute Grammars community have combined to cast a shadow over the good results that have been accumulated over thirty years regarding Attribute Grammars. Many were led to think that Attribute Grammars are so simple and limited that they were unusable for the development of real applications and methods for their static analysis could not be transposed to other formalisms.
Some works have attempted to respond to this problem by proposing extensions to the classical Attribute Grammar formalism, for instance Higher-Order Attribute Grammars [SV91], Circular Attribute Grammars [Far86] or Multi-Attributed Grammars [Att89]. The main difference between these works and ours is the methodology used to attack the problem. All of them, in a first step, propose a linguistic extension designed to make the expression of a particular application easier (for instance, data-flow analysis for Circular Attribute Grammars) and, in a second step, wondered how this extension could be implemented. In contrast, our approach was, first, to precisely characterize the intrinsic power of the classical formalism and, thereafter, to derive the language extensions that allow to fully exploit this power. The basic observation is that the notion of grammar does not necessarily imply the existence of a (physical) tree.
In fact, our view of the grammar underlying an Attribute Grammar is similar to the grammar describing all the call trees for a given functional program or all the proof trees for a given logic program: the grammar precisely describes the various possible flows of control. In this context, a production describes an elementary recursion scheme [CFZ82] (control flow), whereas the semantic rules describe the computations associated with this scheme (data flow).
It is very important at this point to observe that all the theoretical and practical results on Attribute Grammars, in particular, the algorithms for constructing efficient evaluators, are based only on the abstraction of the control flow by means of a grammar and not at all on how its instances are obtained at run-time. In consequence, we propose two linguistic extensions which comply with this view:
90, JPG93].
The availability of this ``new'' programming language is, however, not the main achievement of our work. Indeed, the actractiveness of a particular language w.r.t. its competitors is a very subjective matter. In our opinion, the justification of our new language is that it is the concrete form for exploiting the static analysis techniques developed for Attribute Grammars, which are of high interest in their own sake. By freeing these results from the narrow frame of traditional Attribute Grammars, we believe that they will find applications in other domains.
The remainder of this article is divided into three sections. In the first of these, the new notions of conditional productions and scheme productions are introduced using some small examples, intentionally taken from outside the compilation area. The next section demonstrates why these extensions do not require modifications to the techniques used for evaluator generation. The last section enumerates the benefits of using extended Attribute Grammar specifications. Most of the presentation is intentionally informal.