Attribute Grammars and Automatic Complexity Analysis
Algorithms Project, INRIA Rocquencourt
June 19, 2000
[summary by Marianne Durand]
A properly typeset version of this document is available in postscript
and in pdf
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Starting from combinatorial structures, one can study some of their
characteristics by means of attribute grammars [1, 2].
This leads to multivariate generating functions that permit us to
study the distribution of these characteristics, part of it
1 Attribute Grammars
The grammars considered here are built from atoms, Z, Z1,...of
weight 1 and from an e of weight 0. The production rules are
described in terms of a few constructors: union, cartesian product,
set, sequence and cycle. These constructors can take place in a
labelled world (permutations) or unlabelled (trees) and they are
already present in the combstruct package. A grammar is composed
of production rules of the type T=F(T1,...,Tn); T is said
to be an ancestor of each Ti and each Ti is a descendant
of T. The attributes on these grammars are values on the objects
produced by the grammar, here on combinatorial structures, like for
example the size or the internal path length on a binary search tree.
An attribute is synthesized if it is a function of his
descendants (size of a tree) and inherited if it is a function
of his ancestors. An example of an inherited attribute is the depth of
a tree. The depth is defined by : the depth of the root is zero and
the depth of a subtree is the depth of its father plus one. An
attribute is well-defined if there are no circular
dependencies amongst the attributes, which can be checked
algorithmically . The attribute is linear if it
is a linear function of the attributes of the descendants. The size of
a tree is a linear attribute, but the height of a tree defined by the
maximum of the height of the subtrees plus one is not.
We now consider linear synthesized and well-defined attributes. The general
specification of a structure is:
where Fi is a standard constructor, like cartesian product, set,
sequence, or cycle, or a terminal. The general form of the definition
of an attribute Fi then is
where lower case indexed greek letters indicate integer constants, and
Fj corresponds to other attributes. The letter f stands for a
general iterative operator coding the fact that all the subelements of
the structure are considered. For example if F is the sequence
constructor, each element of the sequence is considered recursively.
The non-planar trees are defined by T=N · Set(T) and there
the internal path length is specified by ipl(T)=f(size(T)+ipl(T)). Other examples are the area below Dyck paths,
the number of cycles in a permutation or the number of parts in a
All these attributes can be encoded in multivariate generating functions as
follows. If the attributes are named Fi and the structure is defined as in
equation (1), the generating function in an unlabelled world is
Let z be the vector (z1,...,zk), am be the matrix
[ai,jm], gm and dm be vectors, where m is an
index indicating the related constructor Fm. We use the
zd=(z1d1,..., zkdk) and
This allows us to state the Attribute Grammars Generating Function theorem.
|Theorem 1 
Given the grammar specification
where each Fi is a grammar constructor or a terminal and given the set
of attribute productions Fi(B)=È1£ m £ n
multivariate generating function B(z) satisfies
where GFm is the classical generating function transformation
The proof requires a study of each constructor. We give here a
simplified proof where B=F(C). As in equation (2) the
generating function is defined by
By replacing with the definition of Fi, i.e.,
which simplifies into
In view of
C(z)=åc Î CÕj zjFj(c) and
B(z)=åb Î BÕa Î bz|b|= G(B(z)),
we now have the final result
We obtain a simple formula to express the generating function of a structure
given the type of its attributes.
2 Automatic Complexity Analysis
The idea of working on combinatorial properties is not new, it has already
been exploited in LUO [3, 7], part of which is implemented
in the combstruct package.
Given a combinatorial structure and a class of algorithms based on
programming primitives like sequence of programs, test on unions, partial
program descent and full component iteration, LUO returns the asymptotic
value of the cost of the program on all structures of size n. It is
then possible to get the average value of the cost of the considered program.
The programs analysed by LUO can be viewed as attributes on a grammar
corresponding to the structure. In fact the expressivity of LUO is
by the attribute grammar system.
The attribute grammars are well implemented and will be in
package soon. For example it is possible to compute the cost of
a regular expression based on plus, times and exp and to get the average and
the variance of this cost, which is not possible in LUO.
These techniques can also be applied to other constructors, if their
translation into generating function is known. For instance the
Quicksort algorithm can be studied using attribute grammars. The
Quicksort algorithm takes as input a random permutation, chooses a
pivot, sorts the elements according to their position with respect to
the pivot and then sorts recursively the two subarrays. The run of the
algorithm can be visualised by a binary search tree, the root being
the pivot, and the two sons being the two subarrays. The complexity
is the number of comparisons done, which corresponds to the internal
path length of the binary search tree. This correspondance between
executions of the algorithm and binary search trees is not a
bijection, because the inputs 231 and 213 yield the same tree. The
solution to this problem is to keep the shape of the tree and to label
it with the order in which the nodes are filled, as shown on Figure
1. This gives a bijection between runs of Quicksort and
To describe increasing trees with attribute grammars, we need to introduce
the Greene operator also called box operator . In
structure, the Greene operator specifies where the minimum label is to be.
For example the increasing trees are defined by
T=e| T1·Min(N)· T2
which specifies that the minimum is in the root N.
The generating function has been determined by Greene:
It is now possible to define the internal path length as an attribute on
the increasing tree structure by the relation
Figure 1: The binary search tree and increasing tree associated with .
assuming that the internal path length of a node is 0, which is coherent with
the complexity model of the number of comparisons.
The multivariate generating function is
The average is therefore
where Hn is the nth harmonic number.
All this work has been implemented in Maple in such a way that the
syntax of attributes grammars use the same basic functions as combstruct. For example if a grammar rule is A=B| C then an
attribute for A follows the equation, in combstruct syntax,
Similar rules apply for product and set. Since combstruct can
verify if a grammar is well defined, the same algorithm can tell if an
attribute grammar is linear and synthetic. For example if one looks
again at the internal path length but this time of a binary Catalan
tree, using two lines to define the grammar (B=e +zB2) and
the attribute coding internal path length (ipl=size(B)+ipl(B1)+ipl(B2)) and five to compute the
generating functions and the first moments, one gets automatically
that the average equals (p)1/2n3/2+O(n) and the variance
equals (10/3-p)n3+O(n5/2). This computation can also be done
on examples like the grammar defining the expressions based on zero,
one, x, sum, product and exponentiation. It is possible to define
the attribute coding the size of an expression after
differentiation. This leads to an automatic proof that on average
differentiating an expression of size n yields an expression of
size 0.8 n3/2.
Attribute grammars provide a good way of describing recursive properties
of decomposable structures; a structure is decomposable if it can be
expressed with basic atoms (e, Z) and basic constructors (union,
product, set, sequence, ...). The work that has been done on this subject
be used to obtain algorithms for random generation of structures
with given attribute value, and also to obtain the distribution of the
attribute. It can be continued on other attribute types for example
heads or tails of sequences.
From the aspect of attribute grammar research, some theory has been
developed on the idea of coupling grammars. This simulates repeated
application of a function. This, for example, would allow a simple
analysis of repeated differentiation, and other composed
functions. This requires a system where the attributes may be more
than constants, but rather further structures.
Delest (M.-P.) and Fedou (J. M.). --
Attribute grammars are useful for combinatorics. Theoretical
Computer Science, vol. 98, n°1, 1992, pp. 65--76. --
Second Workshop on Algebraic and Computer-theoretic Aspects of Formal
Power Series (Paris, 1990).
Dutour (I.) and Fédou (J. M.). --
Object grammars and random generation. Discrete Mathematics and
Theoretical Computer Science, vol. 2, 1998, pp. 47--61.
Flajolet (P.), Salvy (B.), and Zimmermann (P.). --
Lambda-Upsilon-Omega: the 1989 cookbook. --
Research Report n°1073, Institut National de Recherche en
Informatique et en Automatique, August 1989. 116 pages.
Green (D.). --
Formal languages and their uses. --
Ph. D. Thesis, Stanford University, 1985.
Knuth (D. E.). --
Semantics of context-free languages. Mathematical Systems
Theory, vol. 2, n°2, 1968, pp. 127--145.
Mishna (Marni). --
Attribute grammars and automatic complexity analysis. --
Research Report n°4021, Institut National de Recherche en
Informatique et en Automatique, October 2000. 20 pages.
Zimmermann (P.). --
Series génératrices et analyse automatique
Ph. D. Thesis, École polytechnique, Palaiseau,
This document was translated from LATEX by