MATCHING-BASED INCREMENTAL EVALUATORS FOR HIERARCHICAL ATTRIBUTE GRAMMAR DIALECTS

Although attribute grammars have been very effective for defining indi vidual modules of language translators, they have been rather ineffect ive for specifying large program-transformational systems. Recently, s everal new attribute grammar ''dialects'' have been developed that sup port the modular specification of these systems by allowing modules, e ach described by an attribute grammar, to be composed to form a comple te system. Acceptance of these new hierarchical attribute grammar dial ects requires the availability of efficient batch and incremental eval uators for hierarchical specifications. This paper addresses the probl em of developing efficient incremental evaluators for hierarchical spe cifications. A matching-based approach is taken in order to exploit ex isting optimal change propagation algorithms for nonhierarchical attri bute grammars. A sequence of four new matching algorithms is presented , each increasing the number of previously computed attribute values t hat are made available for reuse during the incremental update.