Using Cached Functions and Constructors for Incremental Attribute Evaluation

摘要

A technique for the efficient incremental evaluation of attribute grammars ispresented. The applied approach may also be effective in the evaluation of higher-order attribute grammars. The approach is an extension of a simpler algorithm for incremental evaluation, where functions, corresponding to visit sequences, are cached. Attributes are now either found in the cache or they are recomputed, so there is no longer a need to represent the attributed tree explicitly. Common subtrees can be shared. The following change is proposed: instead of explicitly representing the tree and calling visit sequence functions to compute the attributes, the tree is represented through a set of visit functions corresponding to the successive visits. These functions are constituted using the visit sequences as building blocks. This technique has two major advantages. Firstly, a visit function characterizes precisely that part of the tree that would actually be visited in the previous approach, thus increasing the number of cache hits. Secondly, copy rules may be removed during the construction phase. This results in short circuiting the copychains and in minimizing the number of recomputed functions.