Attribute Grammars and Automatic Complexity Analysis

Decomposable combinatorial structures have been well studied and a systematic manner for determining generating function equations is well known. Attribute grammars have enhanced the study of context-free grammars by giving meaning to constructions. We show that attribute grammars can be defined for the family of decomposable structures and yield multivariate generating function equations. From there, averages and higher moments are easily accessible. This unifies several earlier approaches for the analysis of parameters of combinatorial structures. We give examples of automatic average-case complexity analysis of algorithms using this approach.