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.
展开▼
