Attribute Grammars

Literature references and annotations by Dick Grune, dick@dickgrune.com. Last update: Sat Sep 19 08:18:32 2009.
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.

* Eric Van Wyk, Oege de Moor, Kevin Backhouse, Paul Kwiatkowski, "Forwarding in attribute grammars for modular language design", in Compiler Construction, Lecture Notes in Computer Science #2304, pp. 128-142. 2002,

* John Tang Boyland, "Conditional attribute grammars", ACM TOPLAS, 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.

* Alan Carle, Lori Pollock, "Matching-based incremental evaluators for hierarchical attribute grammar dialects", ACM TOPLAS, 17, #2, March 1995, pp. 394-429.

* Pei-Chi Wu, Feng-Jian Wang, "A worst case of circularity test algorithms for attribute grammars", ACM TOPLAS, 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.

* Josephine Micallef, Gail E. Kaiser, "Extending attribute grammars to support programming-in-the-large", ACM TOPLAS, 16, #5, Sept. 1994, pp. 1572-1612.

* Tibor Gyimóthy, Zoltán Alezin, Róbert Szücs, "Integrated graphic environment to develop applications based on attribute grammars", in Compiler Construction, 4th International Conference, CC'92, ed. by U. Kastens and P. Pfahler, Lecture Notes in Computer Science #641, Springer-Verlag, Oct. 1992, pp. 51-58.

* Beate Baum, "Another kind of modular attribute grammars", in Compiler Construction, 4th International Conference, CC'92, ed. by U. Kastens and P. Pfahler, Lecture Notes in Computer Science #641, Springer-Verlag, Oct. 1992, pp. 44-50.

* Scott E. Hudson, "Incremental attribute evaluation: A flexible algorithm for lazy update", ACM TOPLAS, 13, #3, July 1991, pp. 315-341.

* Uwe Kastens, "Attribute grammars as a specification method", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 16-47.

* Henk Alblas, "Attribute evaluation methods", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 48-113.

* Uwe Kastens, "Implementation of visit-oriented attribute evaluators", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 114-139.

* Rieks op den Akker, Erik Sluiman, "Storage allocation for attribute evaluators using stacks and queues", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 140-150.

* Ulrich Möncke, Reinhard Wilhelm, "Grammar flow analysis", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 151-186.

* Rieks op den Akker, Bo\(vrivoj Melichar, Jorma Tarhio, "Attribute evaluation and parsing", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 187-214.

* Henk Alblas, "Incremental attribute evaluation", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 215-233.

* Martin Jourdan, "A survey of parallel attribute evaluation methods", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 234-254.

* Doaitse Swierstra, Harald Vogt, "Higher order 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. 256-296.

* Jan Maluszy\('nski, "Attribute grammars and logic programs: a comparison of concepts", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 330-357.

* Kees Koster, "Affix grammars for programming", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 358-373.

* Görel Hedin, "Incremental static-semantic analysis for object-oriented languages using Door 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. 374-378.

* Uwe Kastens, "Attribute grammars in a compiler construction environment", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 380-400.

* Günter Riedewald, "Prototyping by using an attribute grammar as a logic program", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 401-437.

* Peter Forbrig, "Using the generative aspect of attribute grammars in a knowledge based way", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 438-459.

* Tibor Gyimóthy, "Natural language interface construction using 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. 460-468.

* Kees Koster, "Affix grammars for natural languages", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 469-483.

* Martin Jourdan, Didier Parigot, "Internals and externals of the FNC-2 attribute grammar system", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 485-504.

* Peter Lipps, Ulrich Möncke, Reinhard Wilhelm, "An overview of the OPTRAN system", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 505-506.

* Reinhard Wilhelm, "Attribute reevaluation in OPTRAN", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 507-507.

* Ralf Lämmel, "The translator writing system RUEGEN - KS", in Attribute Grammars, Applications and Systems, ed. by H. Alblas & B. Melichar, Lecture Notes in Computer Science #545, Springer-Verlag, Berlin, June 1991, pp. 508-???.

* H. Alblas, "Introduction to 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. 1-15.

* 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.

* U. Kastens, "An Attribute Grammar System in a Compiler Construction Environment", in International Summer School on Attribute Grammars, Application and Systems, Prague, 1991,

* U. Kastens, W.M. Waite, "Modularity and reusability in attribute grammars", Acta Inf., 31, #7, pp. 601-627. 1994,

* H. Alblas, "Concurrent incremental attribute evaluation", in Attribute Grammars and their Applications, ed. by P. Deransart and M. Jourdan, Lecture Notes in Computer Science #461, 1990, pp. 343-358. Springer-Verlag,

* A. Feng, T. Kikuno, K. Torii, "Incremental attribute evaluation for multiple subtree replacements in structure-oriented environments", in Attribute Grammars and their Applications, ed. by P. Deransart, M. Jourdan, Lecture Notes in Computer Science #461, 1990, pp. ??-??. Springer-Verlag,

* 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.

* A. Feng, R. op den Akker, B. Melichar, J. Tarhio, "The hierarchy of LR-attributed grammars", in Attribute Grammars and their Applications, ed. by P. Deransart and M. Jourdan, Lecture Notes in Computer Science #461, Springer-Verlag, Berlin, 1990, pp. 13-28.

* S.B. Peckham, "Globally partitionable attribute grammars", in Attribute Grammars and their Applications, ed. by P. Deransart, M. Jourdan, Lecture Notes in Computer Science #461, 1990, pp. 327-342. Springer-Verlag,

* A. Vorthmann, "Coordinated incremental attribute evaluation on a DR-threaded tree", in Attribute Grammars and their Applications, ed. by P. Deransart, M. Jourdan, Lecture Notes in Computer Science #461, 1990, pp. 207-221. Springer-Verlag,

* J. Grosch, "Object-Oriented Attribute Grammars", in Fifth International Symposium on Computer and Information Sciences, ISCIS V, ed. by A.E. Harmanci and E. Gelenbe (ed.), Nevsehir, Cappadocia, Turkey, Oct. 1990, pp. 807-816.

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

* Martin Jourdan, Didier Parigot, Catherine Julié, Olivier Durin, Carole Le Bellec, "Design, Implementation and Evaluation of the FNC-2 Attribute Grammar System", in '90 Symposium on Programming Languages Design and Implementation, ACM SIGPLAN Notices, 1990, pp. 209-222.

* L.G. Jones, "Efficient evaluation of circular attribute grammars", ACM TOPLAS, 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.

* J. Tarhio, "Uncle-attributed grammars", BIT, 30, 1990, pp. 437-449.

* Arvind M. Murching, Y.N. Srikant, "Incremental attribute evaluation through recursive procedures", Computer Languages, 14, #4, pp. 225-237. 1989,

* J. Tarhio, "A compiler generator for attribute evaluation during LR parsing", in Compiler Compilers and High Speed Compilation, ed. by D. Hammer, Lecture Notes in Computer Science #371, Springer-Verlag, Berlin, 1989,

* D.A. Watt, "Rule splitting and attribute-directed parsing", in Semantics-Directed Compiler Generation, ed. by N.D. Jones, Lecture Notes in Computer Science #94, 1989, Springer-Verlag, pp. 363-392.

* 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, 24, #7, pp. 131-145. July 1989,
[ 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, 24, #6, pp. 97-105. June 1989,
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. Alblas, "Attributed tree transformations with delayed and smart re-evaluation", in Compiler Compilers and High Speed Compilation, ed. by D. Hammer, Lecture Notes in Computer Science #371, 1989, pp. 160-174. Springer-Verlag,

* H. Alblas, "Iteration of transformation passes over attributed program trees", Acta Informatica, 27, 1989, pp. 1-40.

* H. Alblas, "Optimal incremental simple multi-pass attribute evaluation", Information Processing Letters, 32, pp. 289-295. 1989,

* P. Deransart, M. Jourdan, B. Lorho, "Attribute Grammars: Definitions, Systems and Bibliography", Lecture Notes in Computer Science #323, Springer-Verlag, Berlin, 1988,

* R. Giegerich, "Composition and evaluation of attribute coupled grammars", Acta Informatica, 25, pp. 355-423. 1988,

* P. Lipps, U. Möncke, M. Olk, R. Wilhelm, "Attribute (re-)evaluation in OPTRAN", Acta Informatica, 26, pp. 213-239. 1988,

* T. Reps, "Incremental evaluation for attribute grammars with unrestricted movement between tree modifications", Acta Informatica, 25, pp. 155-178. 1988,

* D. Yeh, U. Kastens, "Improvements on an incremental evaluation algorithm for ordered attribute grammars", ACM SIGPLAN Notices, 13, #12, pp. 45-50. 1988,

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

* G. Filè, "Classical and incremental attribute evaluation by means of recursive procedures", Theoretical Computer Science, 53, 1987, pp. 25-65.

* M.L. Hall, "The Optimization of Automatically Generated Compilers", Department of Computer Science, University of Colorado, Ph.D. Thesis, Boulder, CO, 1987,

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

* M. Sassa, H. Ishizuka, I. Nakata, "ECLR-attributed grammars: a practical class of LR-attributed grammars", Information Processing Letters, 24, 1987, pp. 31-41.

* H. Alblas, "One-pass transformations of attributed program trees", Acta Informatica, 24, pp. 299-3??. 1987,

* H. Alblas, "Pass-oriented attribute evaluation and attributed tree transformations", PhD. Thesis, University of Twente, 1987,

* H. Alblas, "Incremental simple multi-pass attribute evaluation", in NGI-SION 1986 Symposion, pp. 319-342. 1986,

* Rodney Farrow, Daniel Yellin, "A comparison of storage optimizations in automatically generated attribute evaluators", Acta Informatica, 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, 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.

* R. Hoover, T. Teitelbaum, "Efficient incremental evaluation of aggregate values in attribute grammars", in ACM SIGPLAN '86 Symposium on Compiler Construction, ACM SIGPLAN Notices, pp. 39-50. July 1986,

* R. Hoover, "Dynamically bypassing copy rule chains in attribute grammars", in Thirteenth ACM Symposium on Principles of Programming Languages, pp. 14-25. 1986,

* T. Reps, C. Marceau, T. Teitelbaum, "Remote attribute updating for language-based editors", in Thirteenth ACM Symposium on Principles of Programming Languages, pp. 1-13. 1986,

* S.M. Kaplan, G.E. Kaiser, "Incremental attribute evaluation in distributed language environments", in Fifth Annual ACM Symposium on Principles of Distributed Computing, pp. 121-130. 1986,

* I. Nakata, M. Sassa, "L-attributed LL(1)-grammars are LR(1)-attributed", Information Processing Letters, 23, 1986, pp. 325-328.

* M. Sassa, H. Ishizuka, I. Nakata, "A contribution to LR-attributed grammars", J. Information Processing, 8, 1985, pp. 196-206.

* M. Sonnenschein, "Global storage cells for attributes in an attribute grammar", Acta Informatica, 22, 1985, pp. 397-420.

* 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, 20, #7, pp. 43-59. July 1985,
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.

* H. Alblas, "Finding minimal pass sequences for attribute grammars", SIAM J. on Computing, 14, 1985, pp. 889-914.

* 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, 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, 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.

* H. Ganzinger, R. Giegerich, "Attribute coupled grammars", in ACM SIGPLAN '84 Symposium on Compiler Construction, ACM SIGPLAN Notices, 19, #6, pp. 157-170. June 1984,

* M. Jourdan, "Strongly non-circular attribute grammars and their recursive evaluation", in ACM SIGPLAN '84 Symposium on Compiler Construction, ACM SIGPLAN Notices, 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, 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.

* P. Deransart, M. Jourdan, B. Lorho, "Speeding up circularity tests for attribute grammars", Acta Inf., 21, #4, Nov. 1984, pp. 375-391.

* G. Filè, "The theory of attribute grammars", Doctoral dissertation, Twente University of Technology, Enschede, The Netherlands, 1983,

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

* J. Lewi, K. De Vlaeminck, J. Huens, E. Steegmans, "The language implementation laboratory LILA -- an overview", in Microcomputers; developments in industry, business and education, ed. by D. Wilson and C. van Spronsen, Elsevier, 1983, pp. 11-21.

* T. Reps, T. Teitelbaum, A. Demers, "Incremental context-dependent analysis for language based editors", ACM Trans. Programming Languages and Systems, 5, pp. 449-477. 1983,

* H. Riis Nielson, "Computation sequences: a way to characterize classes of attribute grammars", Acta Informatica, 19, 1983, pp. 255-268.

* D. Yeh, "On incremental evaluation of ordered attribute grammars", BIT, 23, pp. 308-320. 1983,

* B. Courcelle, P. Franchi-Zannettacci, "Attribute grammars and recursive program schemes", Theoretical Computer Science, 17, 1982, pp. 163-191,235-257.

* J. Engelfriet, G. Filè, "Simple multi-visit attribute grammars", J. Computer and System Sciences, 24, 1982, pp. 283-314.

* R. Farrow, "Experience with an attribute grammar based compiler", in Ninth ACM Symposium on Principles of Programming Languages, 1982, pp. 95-107.

* U. Möncke, R. Wilhelm, "Iterative algorithms on grammar graphs", in Eighth Conference on Graph-theoretic Concepts in Computer Science, ed. by H. Goettler, pp. 177-194. Hanser-Verlag, 1982,

* Kari-Jouko Räihä, Mikko Saarinen, "Testing attribute grammars for circularity", Acta Informatica, 17, pp. 185-192. 1982,
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.

* V. Serebryakov, "Principal features of the input language and implementation of the translator design system SUPER", Prog. and Comput. Softw., 8, #1, 1982, pp. 52-56.

* J. Uhl, S. Drossopoulos, G. Persch, G. Go??, M. Daussmann, G. Winterstein, W. Kirchg???ssner, "An attributed grammar for the semantic analysis of ADA", Lecture Notes in Computer Science #139, Springer-Verlag, Berlin, 1982,

* A. Demers, T. Reps, T. Teitelbaum, "Incremental evaluation for attribute grammars and application to syntax-directed editors", in Eighth ACM Symposium on Principles of Programming Languages, pp. 105-116. 1981,

* M. Jazayeri, "A simpler construction for showing the intrinsically exponential complexity of the circularity problem for attribute grammars", J. ACM, 28, #??, pp. 715-720. 1981,

* J. Engelfriet, G. Filè, "Passes and paths of attribute grammars", Information and Control, 49, 1981, pp. 125-169.

* J. Engelfriet, G. Filè, "Passes, sweeps and visits in attribute grammars", in Eighth ICALP, Lecture Notes in Computer Science #115, 1981, Springer-Verlag, pp. 193-207.

* J. Engelfriet, G. Filè, "The formal power of one-visit attribute grammars", Acta Informatica, 16, 1981, pp. 275-302.

* K.J. Räihä, "A space management technique for multi-pass attribute evaluators", Dept. of Comp. Sc., University of Helsinki, Finland, 1981,

* K.-J. Räihä, E. Ukkonen, "Minimizing the number of evaluation passes for attribute grammars", SIAM J. on Computing, 10, 1981, pp. 772-786.

* H. Riis, S. Skyum ??, "k-visit attribute grammars", Math. Systems Theory, 15, 1981, pp. 17-28.

* M. Jazayeri, D. Pozefsky, "Space efficient storage management for attribute grammars", ACM TOPLAS, 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.

* H. Alblas, "A characterization of attribute evaluation in passes", Acta Informatica, 16, 1981, pp. 427-464.

* K.S. Chebotar, "Some modifications of Knuth's algorithm for verifying cyclicity of attribute grammars", Program. Comput. Softw., 7, #1, Feb. 1981, pp. 58-61.

* U. Kastens, "Ordered Attribute Grammars", Acta Inf., 13, #3, 1980, pp. 229-256.

* N. Jones, C.M. Madsen, "Attribute-influenced LR parsing", in Aarhus Workshop on Semantics-Directed Compiler Generation, ed. by N.D. Jones, Springer-Verlag, 1980, pp. 393-407.

* K.-J. Räihä, E. Ukkonen, "On the optimal assignment of attributes to passes in multi-pass attribute evaluators", in Seventh ICALP, ed. by J. de Bakker and J. van Leeuwen, Lecture Notes in Computer Science #85, Springer-Verlag, 1980, pp. 500-511.

* K.J. Räihä, "Bibliography on attribute grammars", ACM SIGPLAN Notices, 15, #3, pp. 35-44. March 1980,

* Ken Kennedy, Jayashree Ramanathan, "A deterministic attribute grammar evaluator based on dynamic sequencing", ACM Trans. on Programming Languages and Systems, 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.

* D.A. Watt, "An extended attribute grammar for Pascal", ACM SIGPLAN notices, 14, #2, pp. 60-74. 1979,

* R. Wilhelm, "Attributierte Grammatiken", Informatik Spektrum, 2, pp. 123-130. 1979,

* D. Milton, C. Fischer, "LL(k) parsing for attributed grammars", in Automata, language and programming, Lecture notes in Computer Science #7, Springer-Verlag, pp. 424-430. 1979,

* H. Ganzinger, "On storage optimization for automatically generated compilers", in Fourth GI Conference on Theoretical Computer Science, ed. by K. Weihrauch, ed., Lecture Notes in Computer Science #67, Springer-Verlag, March 1979, pp. 132-141.

* K. Räihä, "Dynamic allocation of space for attribute instances in multi-pass evaluators of attribute grammars", ACM SIGPLAN Notices, 14, Aug. 1979, pp. 26-38.

* R. Wilhelm, "Computation and use of data flow information in optimizing compilers", Acta Informatica, 12, pp. 209-225. 1979,

* 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.

* M. Saarinen, "On constructing efficient evaluators for attribute grammars", in Automata, Languages and Programming: 5th Colloquium, Lecture Notes in Computer Science #62, ed. by C. Ausiello and C. Bohm, New York, Springer-Verlag, 1978, pp. 382-396(397?).

* W.A. Babich, M. Jazayeri, "The methods of attributes for data flow analysis -- Part II: demand analysis", Acta Inf., ??, 1978, pp. 265-272.

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

* G.V. Bochmann, P. Ward, "Compiler writing systems for attribute grammars", Computer J., 21, 1978, pp. 144-148.

* R. Giegerich, R. Wilhelm, "Counter one-pass features in one-pass compilation: a formalization using attribute grammars", Information Processing Letters, 7, 1978, pp. 279-284.

* R. Giegerich, R. Wilhelm, "Attribute evaluation", in Le point sur la compilation, IRIA, Le Chesnay, France, 1978, pp. 337-365.

* K.-J. Räihä, M. Saarinen, "An optimization of the alternating semantic evaluator", Information Processing Letters, 6, pp. 97-100. 1977,

* B. Lorho, "Semantic attribute processing in the system DELTA", in Methods of Algorithm Language Implementation, ed. by Ershov & Koster, LNCS #47, Springer Verlag, Berlin, 1977, pp. 21-40.

* H. Ganzinger, K. Ripken, R. Wilhelm, "MUG1 - an incremental compiler-compiler", in ACM 1976 Annual Conference, 1976, pp. 415-418.

* R. Wilhelm, K. Ripken, H. Ciesinger, W. Lahner, R.D. Nollman, "Design evaluation of the compiler generating system MUG1", in Second International Conference on Software Engineering, 1976, pp. 571-576.

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

* G.V. Bochmann, "Semantic evaluation from left to right", Commun. ACM, 19, 1976, pp. 55-62.

* M. Jazayeri, W. Ogden, W. Rounds, "The intrinsically exponential complexity of the circularity problem for attribute grammars", Commun. ACM, 18, #12, Dec. 1975, pp. 697-706.

* P.M. Lewis, D.J. Rosenkrantz, R.E. Stearns, "Attributed translations", J. Computer Syst. Sci., 9, pp. 279-307. 1974,

* F.L. DeRemer, "Transformational grammars", in Compiler Construction: An Advanced Course, ed. by F.L. Bauer and J. Eickel, Lecture Notes in Computer Science #21, Springer-Verlag, New York, 1974, pp. 121-145.

* Donald E. Knuth, "Semantics of context-free languages -- correction", Math. Syst. Theory, 5, #1, pp. 95-96. 1971,
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, 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.

* Edgar T. Irons, "Towards more versatile mechanical translators", in Fifteenth Symposium on Applied Mathematics, , American Math. Soc., 1963, pp. 41-50.