Attribute Grammars and Automatic Complexity Analysis

Marni Mishna

Algorithms Project, INRIA Rocquencourt

Algorithms Seminar

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

Abstract
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 automatically.



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 [5]. 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:
B=F1(B11,...,B
1
 
k1
)|...|Fn(B1n,...,B
n
 
kn
).     (1)
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
Fi(B)=
 
È
1£ m £ n
f æ
ç
ç
è		 dim+
 
å
j,k
ai,jmFj ( Bkm ) ö
÷
÷
ø		 +gi
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 partition.

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
B(z0,...,zk)=
 
å
b Î B
z0|b|z
F1(b)
 
1
... z
Fk(b)
 
k
.     (2)
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 following notations: zd=(z1d1,..., zkdk) and za=(z1a1,1... zka1,k,..., z1a1,k... zkak,k). This allows us to state the Attribute Grammars Generating Function theorem.
Theorem 1   [6] Given the grammar specification B=F1(B11,...,Bk11)|...|Fn(B1n,...,Bknn) where each Fi is a grammar constructor or a terminal and given the set of attribute productions Fi(B)=È1£ m £ n f(dim+ åj,kai,jmFj(Bkm))+gi the multivariate generating function B(z) satisfies
B(z )=
 
å
m
z
gm
 
G
 
Fm
æ
è		 z
dm
 
Bkm(z
am
 
) ö
ø
where GFm is the classical generating function transformation on structures.

Proof. 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
B(z )=
 
å
b Î B
z
F1(b)
 
1
... z
Fk(b)
 
k
.
By replacing with the definition of Fi, i.e., Fi(B)=f(di+åj,kai,jFj(Bk))+gi, we obtain
B(z )=
 
å
b Î B
 
Õ
l
z
gl
 
l
.
 
Õ
a Î b
 
Õ
i
z
di+
k
å
j=1
aijFj(b)
 
i
,     (3)
which simplifies into
B(z)=z
g
 
 
å
b Î B
z
d
 
 
Õ
a Î b
 
Õ
j
æ
ç
ç
è
 
Õ
i
z
aij
 
i
ö
÷
÷
ø
Fj(b)
 
.
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
B(z)=z
g
 
G
 
F
æ
è		 z
d
 
C(z
a
 
) ö
ø		 .
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 encompassed by the attribute grammar system. The attribute grammars are well implemented and will be in the combstruct package soon. For example it is possible to compute the cost of differentiating 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 increasing trees.

Figure 1: The binary search tree and increasing tree associated with [521634].

To describe increasing trees with attribute grammars, we need to introduce the Greene operator also called box operator [4]. In a labelled 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:
T(z)= ó
õ
z


0
T2(x)
N(x)
x
  dx.
It is now possible to define the internal path length as an attribute on the increasing tree structure by the relation
ipl(T)=0|ipl(T1)+size(T1)+ipl(T2)+size(T2),
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
T(z,u)=1+ ó
õ
z


0
æ
ç
ç
è
x
x ö
÷
÷
ø		 T(xu,u)2 dx.
The average is therefore
[zn]Tu(z,u)|u=1
[zn]T(z,1)
=2Hn-3+
Hn
n
  with   T(z,1)=
1
1-z
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, 
            F(A)=Union(b_1*F_1(B)+...+b_k*F_k(B),c_1*F_1(C)+...+c_k*F_k(C))
                       + a_1*F_1(A)+...+a_k*F_k(A)+a_0.
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 can 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.

References

[1]
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).

[2]
Dutour (I.) and Fédou (J. M.). -- Object grammars and random generation. Discrete Mathematics and Theoretical Computer Science, vol. 2, 1998, pp. 47--61.

[3]
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.

[4]
Green (D.). -- Formal languages and their uses. -- Ph. D. Thesis, Stanford University, 1985.

[5]
Knuth (D. E.). -- Semantics of context-free languages. Mathematical Systems Theory, vol. 2, n°2, 1968, pp. 127--145.

[6]
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.

[7]
Zimmermann (P.). -- Series génératrices et analyse automatique d'algorithmes. -- Ph. D. Thesis, École polytechnique, Palaiseau, 1991.
This document was translated from LATEX by HEVEA.