Attribute (re)evaluation in OPTRAN

Abstract

A transformation of a tree decorated according to some attribute grammar may leave the tree containing attribute inconsistencies. An attribute reevaluation algorithm computes new attribute values for affected attribute instances. It has to guarantee, that never an inconsistent attribute value is accessed. Reps´ algorithm performs this task in time O(|affected region|). It is data driven as changed values trigger recomputations of attribute instances dependent on them. After each transformation, a complete update of the effected instances is performed. Reps´ algorithm is compared with the data driven reevaluation scheme used in OPTRAN. It uses the same strategic information in the initial attribute evaluation and the reevaluation process. Furthermore, we present a demand driven scheme for attribute reevaluation. It does not have the linear time complexity for each update after one transformation but, depending on the situation, often compares favourably with the data driven scheme for series of transformations. In addition, the linear time complexity of the data driven reevaluation algorithm needs fast convergence using an equality test between old and new attribute values. It is thus necessary, to keep the attribute values at (almost) all instances. The demand driven reevaluator does not need all the old attribute values. It can flexibly trade time for space. We also describe the handling of space consuming attributes, e.g. tables, lists and trees, in the reevaluation algorithm. An integrated version of data driven and demand driven reevaluation using these features has been implemented in the OPTRAN system.