ON THE OPTIMALITY OF CHANGE PROPAGATION FOR INCREMENTAL EVALUATION OFHIERARCHICAL ATTRIBUTE GRAMMARS

Several new attribute grammar dialects have recently been developed, a ll with the common goal of allowing large, complex language translator s to be specified through a modular composition of smaller attribute g rammars'. We refer to the class of dialects as hierarchical attribute grammars. In this short article, we present a characterization of opti mal incremental evaluation that indicates the unsuitability of change propagation as the basis of an optimal incremental evaluator for hiera rchical attribute grammars. This result lends strong support to the us e of incremental evaluators based on more applicative approaches to at tribute evaluation, such as Carle and Pollock's evaluator based on cac hing of partially attributed subtrees, Pugh's evaluator based on funct ion caching of semantic functions, and Swierstra and Vogt's evaluator based on function caching of visit sequences.