Attribute Grammars

Literature references and annotations by Dick Grune, dick@dickgrune.com.
Last update: Fri Sep 06 15:53:24 2024.

These references and annotations were originally intended for personal use and are presented here only in the hope that they may be useful to others. There is no claim to completeness or even correctness. Each annotation represents my understanding of the text at the moment I wrote the annotation.
No guarantees given; comments and content criticism welcome.

John Tang Boyland, Conditional attribute grammars, ACM TOPLAS, vol. 18, #1, Jan. 1996, pp. 73-108.
Many attribute grammars are circular in theory, while the circularity cannot materialize in reality. Often the reason is that repeated conditions on the expressions prevent the circularity but are not detected in the circularity test. The proposed conditional attribute grammars allow conditional groups of attribute definitions rather than groups of conditional attribute definitions. As a result, the condition occurs only once, and the non-circularity can be established. Theoretical properties of the new form are explored, and equivalence classes are defined. Determining whether such an attribute grammar is circular is still NP-hard.

Pei-Chi Wu, Feng-Jian Wang, A worst case of circularity test algorithms for attribute grammars, ACM TOPLAS, vol. 17, #2, March 1995, pp. 228-232.
Presents an attribute grammar of size n with $ O ( 2 sup n ) $ incomparable dependency graphs. The construction consists of two production rules $ X → X $, each with n pairs of derived attributes and with n pairs of inherited attributes. The two productions differ in that one of the pairs of attributes in one production has dependencies different from the corresponding one in the other. A rule $ X → epsilon $ completes the grammar. The paper gives a good pictorial impression of the problem.

Kai Koskimies, Object-orientation in attribute grammars, in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 297-329.
First, object-orientation in context-free grammars is discussed. The non-terminals are divided in two groups: basic nonterminals, which have only one production rule, and superclass nonterminals, which have several production rules, each consisting of a single nonterminal only; all other nonterminals have to be rewritten to the above two forms. The superclass nonterminals give rise to virtual classes, on which other virtual classes and finally some actual classes may be based; the latter correspond to basic nonterminals. The nodes in the AST correspond to actual classes only.
     Next, two object-orientated attribute grammar systems are discussed: Ag and Mjølner/Orm.
     Finally, the author's own system, TOOLS, is explained. It is recognized that inherited attributes are very difficult in object-orientated attribute grammars; TOOLS' solution is to keep them outside the normal attributes in so-called contexts. These contexts are attached to certain nodes in the tree and are consulted and updated by a number of successive depth-first visits, each computing a set of syshthesized attributes.
     The compiler specification is given in a Modula-2-like notation, in which class definitions specify the syntactic structure, the synthesized attributes and the code to be executed for each of the scans. The scans must be activated explicitly: there is no data flow machine. The contexts are also defined as objects, with a somewhat different syntax. The code in them is fixed: table look-up; it is claimed that that is sufficient, and in the examples it is. All this results in a very compact compiler specification; reading it may require some practice, though.

Catherine Julié, Didier Parigot, Space optimization in the FNC-2 attribute grammar system, in Attribute Grammars and their Applications, Lecture Notes in Computer Science #461, 1990, pp. 29-45. Springer-Verlag,
Complicated criteria for allocating attributes in global variables, on stacks and in combinations of both.

J. Engelfriet, W. de Jong, Attribute storage optimization by stacks, Acta Informatica, vol. 27, 1990, pp. 567-581.
Determines statically which attributes can be kept on stacks.

L.G. Jones, Efficient evaluation of circular attribute grammars, ACM TOPLAS, vol. 12, #3, July 1990, pp. 429-462.
Straightforward formulation of some important algorithms, notably those for closures and fixed point, lead to circular attribute grammars. Such AGs cannot be evaluated using the standard evaluation techniques, but still allow consistent assigment of values to all attributes. The problem is to find this assignment in finite time.
     The approach is based on the observation that any directed graph can be considered as a directed acyclic graph, the nodes of which consist of strongly connected components (a strongly connected component SSC of a graph is a subset of the nodes such that from any node you can reach all the others). First the SCCs are ordered according to the acyclic graph and then solved in that order.
     Solving the equations inside a SCC is done by some appropriate fixed-point algorithm, which is not specified precisely in the paper. A sketch is given for a set of attributes, whose values form a lattice of finite height; this will indeed probably cover the most usual cases.
     Two-thirds of the paper is concerned with the complications that arise when we want to do this incrementally.

H.H. Vogt, S.D. Swierstra, M.F. Kuiper, Higher order attribute grammars, in ACM SIGPLAN '89 Conference on Programming Language Design and Implementation, ACM SIGPLAN Notices, vol. 24, #7, July 1989, pp. 131-145.
[ preprint of Lecture Notes in Computer Science #545, June 1991, pp. 256-296? ]

Nigel P. Chapman, Regular attribute grammars and finite state machines, ACM SIGPLAN Notices, vol. 24, #6, June 1989, pp. 97-105.
Regular attribute grammars are a special case of attribute grammars, but the paper is mainly concerned with special cases of regular attribute grammars: deterministic regular attribute grammars and L-attributed regular attribute grammars. The first have attribute evaluation rules that survive the subset algorithm without creating conflicts (in terms of assigning different values to the same attribute), the second do not require the parse tree to be constructed. Details are given. An example is a grammar for checking the correctness of a Hollerith string of the form <number>H<string>, in which the <number> must describe the length of the <string>.

H.K. Haripriyan, Y.N. Srikant, Priti Shankar, A compiler writing system based on affix grammars, Computer Languages, vol. 13, 1988, pp. 1-11.
LR parsing for affix grammars. Improves Pohlmann's algorithm (q.v.) (without explaining it first). High on technical detail, low on explanation.

Uwe. Kastens, Lifetime analysis for attributes, Acta Informatica, vol. 24, 1987, pp. 633-651.
Determines statically which attributes can be allocated globally or even overlaid globally.

Rodney Farrow, Daniel Yellin, A comparison of storage optimizations in automatically generated attribute evaluators, Acta Informatica, vol. 23, 1986, pp. 393-427.
Explains and compares storage optimization techniques of GAG and LINGUIST-86 and proposes a combination.

R. Farrow, Automatic generation of fixed-point-finding evaluators for circular, but well-defined, attribute grammars, in ACM SIGPLAN '86 Symposium on Compiler Construction, ACM SIGPLAN Notices, vol. 21, #7, July 1986, pp. 85-98.
Conditions to be imposed on functions in attribute grammars on which fixed-point-finding algorithms are applied. Main reguirements are that the domains be complete partial orders and allow equality testing and that the functions be monotonic and satisfy ascending-chain conditions. Many examples, and some thoughts about how to test the conditions.

Alan Demers, Anne Rogers, Frank Kenneth Zadeck, Attribute propagation by message passing, ACM SIGPLAN Notices, in ACM SIGPLAN 85 Symposium on Language Issues in Programming Environments, ACM SIGPLAN Notices, vol. 20, #7, July 1985, pp. 43-59.
The attribute evaluation rules are replaced by messages typed with a direction and a destination: inherited ones go down the tree and synthesized ones go up the tree. Messages are passed on by default by all nodes, which simplifies adding new message types, until they are captured and accepted by their destination. When a node accepts a message (in an Ada-like accept-statement) a corresponding piece of code is executed, which may store the value and/or send other messages.
     Part of the paper is very theoretical and is heavy on the formalism, part is practical and gives clear and non-trivial examples.

Martin Jourdan, An optimal-time recursive evaluator for attribute grammars, ed. by M. Paul and B. Robinet, in International Symposium on Programming, Lecture Notes in Computer Science #167, Springer Verlag, Berlin/Heidelberg, 1984, pp. 167-178.
The evaluator is dynamic in the sense that circularities are detected at run time, if they occur. Statically, a set of recursive routines for attribute evaluation is generated from the attribute grammar, one for each attribute in the grammar.
     A routine for a synthesized attribute gets one parameter: a pointer to the node that contains the attribute. When called, it enters the node, computes the value of the attribute from the evaluation rule and the other attributes in the node, stores the value in the node, and returns the value; a second evaluation of the same attribute will just retrieve it from the node. A routine for an inherited attribute gets three parameters: a pointer to the node that contains the attribute, a pointer to its parent in the tree, and the sequence number of the node in the parent. Together these allow the value of the inherited attribute to be evaluated, much in the same way as with synthesized attributes.
     Dynamically, an attributed parse tree is constructed, and the evaluation routine(s) of the top level synthesized attribute(s) are called. This implements lazy evaluation of the attributes, and allows conditionals in attribute rules without causing undue cycles.

Takuya Katayama, Translation of attribute grammars into procedures, ACM Trans. on Programming Languages and Systems, vol. 6, #3, July 1984, pp. 345-369.
First the augmented strong dependency graphs of all attributes of all non-terminals are computed; these are required to be non-circular. These are then used to generate one routine for each synthesized attribute in the grammar. More in particular, the routine for a synthesized attribute s of a rule C is called by its parent P and is passed some inherited attributes of C stored in P plus a pointer to the node C, and returns the value of s. Note that the routine has access to the subtree only; all the information from the supertree has been assembled already in the inherited attributes at this point. Also note that no attributes are stored in nodes: all values reside in the local variables and parameters of the routines. An algorithm is given for generating the routines.
     Often, more than one synthesized attribute can be computed in one call. An algorithm is given to find and implement this optimization. Also, an extension to general non-circular attribute grammars is given.
     When the attributes can be evaluated from left to right (are L-attributes) and the grammar is LL(k), the routines can be simplified further and the program is a recursive descent compiler. It is shown how these routines can be generated.
     The paper is somewhat formal, but has good examples and is easy to read.

Richard K. Jullig, Frank DeRemer, Regular right-part attribute grammars, in ACM SIGPLAN '84 Symposium on Compiler Construction, ACM SIGPLAN Notices, vol. 19, #6, June 1984, pp. 171-178.
Attribute manipulation for extended grammar repetition is introduced by way of six operators: value distribution, in which a single value is distributed over N children, one copy to each child; value construction, in which N children construct a single synthesized attribute for the parent; list distribution, in which the values in a list of N attribute values are distributed over N children as inherited attributes, one to each child; list construction, in which N children construct a list of N synthesized attributes for the parent; bucket brigade left to right, in which an inherited attribute is passed to the first child, which passed it to the second, etc., until the last child passes it as a synthesized attribute back to the parent; bucket brigade right to left, which is like the previous operator except that the information is passed from last child to first.
     The paper gives a formal description and shows that many common data flow patterns can be expressed using these operators.

M. Jourdan, Strongly non-circular attribute grammars and their recursive evaluation, in ACM SIGPLAN '84 Symposium on Compiler Construction, ACM SIGPLAN Notices, vol. 19, #6, June 1984, pp. 81-93.
[ Much more explicit than Martin Jourdan, [ Recursive evaluation for attribute grammars: an implementation, [ in Methods and tools for compiler construction, [ 1984, [ p. 139-163 ]

Rodney Farrow, Sub-protocol-evaluators for attribute grammars, in ACM SIGPLAN '84 Symposium on Compiler Construction, ACM SIGPLAN Notices, vol. 19, #6, June 1984, pp. 70-80.
Improves on Kasten's ordered attribute grammars as follows. Rather than one attributes partition (called "protocol" here) per production rule, a set of them is kept. For each element E of that set for a production rule P, a choice from the protocol sets of the children of P is made to result in a proper visit sequence; it is argued, but not proved, that this can be done for any strictly non-circular AG. For each E, this yields a set of routines to evaluate the attributes of nodes deriving from P of type E, and these routines call evaluation routines of the children, with the protocols that have been decided for them in the choice described above. This results in a large number of routines, each handling a particular protocol segment for a particular production rule.
     Two optimizations are applied. The algorithm to find the sets of protocols is exponential in the number of attributes, and heuristics are given to reduce the cost. Second, there is much repetition in the generated routines, and common subroutine elimination techniques are used to combine segments of them.
     Let's be honest, this is what I understand it says. The paper is not very explicit and assumes considerable knowledge of the higher regions of attribute evaluation.

B. Courcelle, Attribute grammars: definitions, analysis of dependencies, proof methods, in Methods and tools for compiler construction, ed. by B. Lorho, Cambridge University Press, Cambridge, 1984, pp. 80-102.
Very theoretical article.

J. Engelfriet, Attribute grammars: attribute evaluation methods, in Methods and tools for compiler construction, ed. by B. Lorho, Cambridge University Press, Cambridge, 1984, pp. 102-138.
A systematic enumeration of the attribute evaluation methods, based on a very general multi-pass evaluator. Traversal-oriented, visit-oriented, applicative, even a method using coroutines is described. Supplies a practical graphical notation for nodes with inherited and synthesized attributes. Extensive bibliography.

Martin Jourdan, Recursive evaluation for attribute grammars: an implementation, in Methods and tools for compiler construction, ed. by B. Lorho, Cambridge University Press, Cambridge, 1984, pp. 139-163.
Describes two recursive evaluators, one in which a routine is generated for each synthesized attribute, and one in which routines are generated for all attributes. Since the explanation is unclear (how is Asel() constructed?), only the generating algorithms are shown and no examples of resulting code are given, it would require careful analysis of the paper and hand simulation to figure out what exactly is going on. Scientific reporting at its worst.

D.A. Watt, O.L. Madsen, Extended attribute grammars, Computer J., vol. 26, 1983, pp. 142-153.
Summarized from Simonet's thesis:
Rather than having primitive predicates to check metanotions, Prolog-like unification on affixes is defined.

Kari-Jouko Räihä, Mikko Saarinen, Testing attribute grammars for circularity, Acta Informatica, vol. 17, 1982, pp. 185-192.
Since the circularity test for attribute grammars is exponential only in the maximum number of members in a rule, and since the number of members in rules is very limited and for all practical purposes bounded by a small constant, the exponantiality can be replaced by a constant factor, and the circularity test is quite feasible in practice. All tested real-world grammars were proven non-circular within two minutes on a Burroughs B6700.

M. Jazayeri, D. Pozefsky, Space efficient storage management for attribute grammars, ACM TOPLAS, vol. 3, #4, Oct. 1981, pp. 388-404.
Attributes are classified as either one-pass or multi-pass. One-pass attributes can be handled efficiently by putting them on a stack. This reduces the storage requirements greatly.

Ken Kennedy, Jayashree Ramanathan, A deterministic attribute grammar evaluator based on dynamic sequencing, ACM Trans. on Programming Languages and Systems, vol. 1, #1, 1979, pp. 142-160.
Works mainly on the tree and less on the grammar. Basically determines the dependency graph of all attributes in the tree at evaluation time, does a topological sort and produces an evaluation sequence. This sequence is then followed. For each production rule, the steps required to construct the dependency graph are precompiled at compiler generation time into a routine to be added to the compiler. This results in a table of routines, indexed by the node type. Likewise, each attribute evaluation rule is translated into a routine, which is entered into another table. The evaluation sequence is then a list of pairs of indexes in this table and node addresses. The paper derives from the Master's Thesis of S.K. Warren, Rice Univ., April 1975.

R. Cohen, E. Harry / Hany ???, Automatic generation of near-optimal linear-time translators for non-circular attribute grammars, in Sixth ACM Symposium on Principles of Programming Languages, Jan. 1979, San Antonio, Texas, pp. 121-134.
Author's abstract: Attribute grammars are an extension of context-free grammars devised by Knuth as a formalism for specifying the semantics of a context-free language along with the syntax of the language. The syntactic phase of the translation process has been extensively studied and many techniques are available for automatically generating efficient parsers for context-free grammars. Attribute grammars offer the prospect of similarly automating the implementation of the semantic phase. In this paper we present a general method of constructing, for any non-circular attribute grammar, a deterministic translator which will perform the semantic evaluation of each syntax tree of the grammar in time linear with the size of the tree. Each tree is traversed in a manner particularly suited to the shape of the tree, yielding a near optimal evaluation order for that tree. Basically, the translator consists of a finite set of "Local Control Automata", one for each production; these are ordinary finite-state acyclic automata augmented with some special features, which are used to regulate the evaluation process of each syntax tree. With each node in the tree there will be associated the Local Control Automaton of the production applying at the node. At any given time during the translation process all Local Control Automata are inactive, except for the one associated with the currently processed node, which is responsible for directing the next steps taken by the translator until control is finally passed to a neighbour node, reactivating its Local Control Automaton. The Local Control Automata of neighbour nodes communicate with each other.

W.A. Babich, M. Jazayeri, The methods of attributes for data flow analysis -- Part I: exhaustive analysis, Acta Inf., vol. ??, 1978, pp. 245-264.
[ Is critisized by Sonnenschein for presenting a method that is incompatible with standard attribute rules. ]

Ken Kennedy, Scott K. Warren, Automatic generation of efficient evaluators for attribute grammars, in Third ACM Symposium on Principles of Programming Languages, Jan. 1976, pp. 32-49.
Preliminary version of Kennedy & Ramanathan, TOPLAS July 1979.

Donald E. Knuth, Semantics of context-free languages -- correction, Math. Syst. Theory, vol. 5, #1, 1971, pp. 95-96.
Contains the correct algorithm for statically finding cycles in attribute grammars, plus some typo corrections.

Donald E. Knuth, Semantics of context-free languages, Math. Syst. Theory, vol. 2, #2, 1968, pp. 127-145.
Introduces inherited attributes after acknowledging that synthetic attributes were already used by Irons [1961, 1963]. Shows how inherited attributes may simplify language description, mainly by localizing global effects. Gives a formal definition of attribute grammars and shows that they can express any expressible computation on the AST, by carrying around an attribute that represents the entire tree.
     With the introduction of a dual set of attributes comes the danger of circularity of the attribute rules. An algorithm is given to determine that posibility statically (but it is known to be defective).
     Next a simple but non-trivial language for programming a Turing machine called Turingol is defined using an attribute grammar. The full definition fits on one printed page.
     A comparison with other systems (Vienna Definition Language, etc.) concludes the paper.