Please use this identifier to cite or link to this item: doi:10.22028/D291-26459
Title: Attribute (re)evaluation in OPTRAN
Author(s): Lipps, Peter
Möncke, Ulrich
Olk, Matthias
Wilhelm, Reinhard
Language: English
Year of Publication: 1987
DDC notations: 004 Computer science, internet
Publikation type: Report
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.
Link to this record: urn:nbn:de:bsz:291-scidok-51518
Series name: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Series volume: 1987/01
Date of registration: 4-Apr-2013
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
fb14_1987_01.pdf25,74 MBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.