Attribute Grammars
Literature references and annotations by Dick Grune, dick@dickgrune.com.
Last update: Tue Nov 29 11:13:42 2022.
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. 73108.
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 noncircularity 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
NPhard.
PeiChi Wu,
FengJian Wang,
A worst case of circularity test algorithms for attribute grammars,
ACM TOPLAS,
vol. 17,
#2,
March 1995,
pp. 228232.
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,
Objectorientation in attribute grammars,
in Attribute Grammars, Applications and Systems,
ed. by H. Alblas & B. Melichar,
Lecture Notes in Computer Science #545,
SpringerVerlag,
Berlin,
June 1991,
pp. 297329.
First, objectorientation in contextfree grammars is discussed.
The nonterminals 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 objectorientated 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
objectorientated attribute grammars; TOOLS' solution is to keep them
outside the normal attributes in socalled contexts.
These contexts are attached to certain nodes in the tree and are
consulted and updated by a number of successive depthfirst visits, each
computing a set of syshthesized attributes.
The compiler specification is given in a Modula2like 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 lookup; 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 FNC2 attribute grammar system,
in Attribute Grammars and their Applications,
Lecture Notes in Computer Science #461,
1990,
pp. 2945.
SpringerVerlag,
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. 567581.
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. 429462.
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
fixedpoint 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.
Twothirds 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,
pp. 131145.
July 1989,
[ preprint of Lecture Notes in Computer Science #545, June 1991, pp. 256296? ]
Nigel P. Chapman,
Regular attribute grammars and finite state machines,
ACM SIGPLAN Notices,
vol. 24,
#6,
pp. 97105.
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 Lattributed
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,
pp. 111.
1988,
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. 633651.
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. 393427.
Explains and compares storage optimization techniques of GAG and
LINGUIST86 and proposes a combination.
R. Farrow,
Automatic generation of fixedpointfinding evaluators for circular, but welldefined, attribute grammars,
in ACM SIGPLAN '86 Symposium on Compiler Construction,
ACM SIGPLAN Notices,
vol. 21,
#7,
July 1986,
pp. 8598.
Conditions to be imposed on functions in attribute grammars on which
fixedpointfinding 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
ascendingchain 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,
pp. 4359.
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 Adalike acceptstatement) 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 nontrivial examples.
Martin Jourdan,
An optimaltime 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. 167178.
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. 345369.
First the augmented strong dependency graphs of all attributes of all
nonterminals are computed; these are required to be noncircular.
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 noncircular attribute grammars is given.
When the attributes can be evaluated from left to right (are
Lattributes) 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 rightpart attribute grammars,
in ACM SIGPLAN '84 Symposium on Compiler Construction,
ACM SIGPLAN Notices,
vol. 19,
#6,
June 1984,
pp. 171178.
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 noncircular attribute grammars and their recursive evaluation,
in ACM SIGPLAN '84 Symposium on Compiler Construction,
ACM SIGPLAN Notices,
vol. 19,
#6,
June 1984,
pp. 8193.
[ Much more explicit than Martin Jourdan,
[ Recursive evaluation for attribute grammars: an implementation,
[ in Methods and tools for compiler construction,
[ 1984,
[ p. 139163 ]
Rodney Farrow,
Subprotocolevaluators for attribute grammars,
in ACM SIGPLAN '84 Symposium on Compiler Construction,
ACM SIGPLAN Notices,
vol. 19,
#6,
June 1984,
pp. 7080.
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 noncircular 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. 80102.
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. 102138.
A systematic enumeration of the attribute evaluation methods, based on a
very general multipass evaluator.
Traversaloriented, visitoriented, 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. 139163.
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,
pp. 142153.
1983,
Summarized from Simonet's thesis:
Rather than having primitive predicates to check metanotions, Prologlike
unification on affixes is defined.
KariJouko Räihä,
Mikko Saarinen,
Testing attribute grammars for circularity,
Acta Informatica,
vol. 17,
pp. 185192.
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 realworld grammars were proven noncircular 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. 388404.
Attributes are classified as either onepass or multipass.
Onepass 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. 142160.
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 nearoptimal lineartime translators for noncircular attribute grammars,
in Sixth ACM Symposium on Principles of Programming Languages,
Jan. 1979,
San Antonio, Texas,
pp. 121134.
Author's abstract:
Attribute grammars are an extension of contextfree grammars devised by Knuth
as a formalism for specifying the semantics of a contextfree 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 contextfree
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 noncircular 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 finitestate 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. 245264.
[ 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,
ACM,
Jan. 1976,
pp. 3249.
Preliminary version of Kennedy & Ramanathan, TOPLAS July 1979.
Donald E. Knuth,
Semantics of contextfree languages  correction,
Math. Syst. Theory,
vol. 5,
#1,
pp. 9596.
1971,
Contains the correct algorithm for statically finding cycles in
attribute grammars, plus some typo corrections.
Donald E. Knuth,
Semantics of contextfree languages,
Math. Syst. Theory,
vol. 2,
#2,
1968,
pp. 127145.
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 nontrivial 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.
