Incremental Attribute Evaluation and Multiple Subtree Replacements

Peckham, Stephen B.

Incremental Attribute Evaluation and Multiple Subtree Replacements

Abstract

The standard model for incremental attribute evaluation allows single subtree replacements followed by attribute reevaluation to restore consistency to a derivation tree. This thesis advocates an extended model that allows multiple subtree replacements. A static (tree-walking) algorithm for performing incremental updating after such changes is developed. The algorithm cannot be used with all attribute grammars, but is restricted to grammars contained in the new class of "globally partitionable attributer grammars" (GPAGs). A test for determining whether an attribute grammar is GPAG is described. The multiple subtree replacement algorithm (GPAG-evaluate) in this thesis improves on two shortcomings of existing algorithms. First, many evaluators have a running time that depends linearly on the size of the derivation tree of on the number of concurrent subtree replacements. GPAG-evaluate has a running time of $O$(log $n \cdot$ |AFFECTED|), where $n$ is the number of nodes in the derivation tree and AFFECTED is the set of attributes needing reevaluation. Second, experience with incremental, attribute grammar-based environments demonstrates that dynamic evaluators are noticeably slower than static evaluators because they require time-consuming data structure manipulations. Most existing algorithms for multiple subtree replacements are dynamic, but GPAG-evaluate is static. A second problem treated in this thesis is asynchronous subtree replacements, that is, allowing changes to be made while propagation continues after previous changes. A method for analyzing the efficiency of asynchronous subtree replacement algorithms is presented. An asynchronous evaluator (ASYNCH-evaluate) is described that, like GPAG-evaluate, guarantees that no attributes will be evaluated unnecessarily. Under some restrictions, ASYNCH-evaluate is as efficient as GPAG-evaluate. In particular, propagation in trees containing dynamically generated, nonlocal dependency edges can be supported. Both GPAG-evaluate and ASYNCH-evaluate must find lowest common ancestors of nodes in a tree where subtree replacements were made. A simple technique performs this operation in time $O(n)$. To make the evaluators more efficient, this thesis describes an algorithm that uses self-adjusting binary trees to perform the necessary operations in amortized $O$(log $n$) time. These operations are not restricted to attributed derivation trees, but can be used for any application using trees.

Date Issued

1990-02

Publisher

Cornell University

Keywords

computer science; technical report

Previously Published As

http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1093

Types

technical report