Semantic values in a hierarchical attribute grammar can be defined by composing other attribute grammars. Two techniques make this possible. First, the attribute values are maintained separately from the syntax tree being evaluated, in an auxiliary data structure called the attribute tree. Second, the various grammars and their evaluations must share the document’s underlying internal representation (IR).

This paper explains hierarchical attribute grammars, critiques previously published algorithms, and defines a new family of evaluation algorithms. A critical assumption is that the actual changes to the IR that occur between attribute value updates are not available a priori, but must be constructed algorithmically. The givens include the previous state of the IR, the IR as currently constituted, and the attribute tree after the last evaluation cycle. From these, an updated attribute tree is constructed. The new tree retains previously computed values wherever possible. Retaining values is critical to incremental attribute evaluation. Several algorithms are presented along with their complexity bounds. All aggressively trade space for time. Practical experience is not discussed.

The paper’s primary audience is those directly involved with language-based tools. A secondary audience is those who are interested in document differencing algorithms. Structural differencing is an interesting problem in its own right, for example in document management or source code control systems. I found the paper most interesting when considering ways to adapt the algorithms to other problem domains.