Efficient Incremental Evaluation of Higher Order Attribute Grammars

摘要

A new algorithm for the incremental evaluation of Ordered Attribute Grammars(OAGs), which also solves the problem of the incremental evaluation of Ordered Higher order Attribute Grammars (OHAGs) is presented. Two new approaches are used in the algorithm. First, instead of caching all results of semantic functions in the grammar, all results of visits to trees are caught. There are no attributed trees, because all attributes are stored in the cache. Trees are built using hash consing, thus sharing multiple instances of the same tree and avoiding repeated attributions of the same tree with the same inherited attributes. Second, each visit computes not only synthesized attributes but also bindings for subsequent visits. Bindings, which contain attribute values computed in one visit and used in subsequent visits, are also stored in the cache. As a result, second and further visits get a subtree containing only all necessary earlier computer values (the bindings) as a parameter. The algorithm runs in O((Affected) + (paths-to-roots)) steps after modifying subtrees, where paths-to-roots is the sum of the lengths of all paths from the root to all modified subtrees.