An attribute grammar (AG) is a context-free grammar extended to describe the decoration of trees corresponding to sentences defined by that context-free grammar. It provides a declarative specification from which tree computation code can be generated, provided that the AG meets certain conditions. The goal of this paper is to generate code that visits each node of a tree a bounded number of times, and computes a fixed set of attributes on each visit to a node. Unfortunately, generating such code is an NP-complete problem.

Van Binsbergen, Bransen, and Dijkstra base their approach on Kastens’ 1980 paper [1], which develops a polynomial algorithm that generates evaluation code in many cases. Kastens suggested that when his algorithm fails, the user should add one or more artificial dependences and run the process again. This paper describes a mechanism for selecting such dependences automatically.

The paper gives a complete derivation of Kastens’ results, along with a running example to illustrate the process. Kastens’ algorithm fails to find an evaluation order for this example, and the authors show how their mechanism selects an appropriate artificial dependence. This problem has been solved in practical AG processors for decades, and while the authors refer to some of these processors, they give no comparison of their proposed algorithm with those of the systems they reference.

I was disappointed by this paper. Beyond the actual algorithm for selecting artificial dependences, which is written in Haskell, the material is just a restatement of Kastens’ derivation.