Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26459
Titel: Attribute (re)evaluation in OPTRAN
Verfasser: Lipps, Peter
Möncke, Ulrich
Olk, Matthias
Wilhelm, Reinhard
Sprache: Englisch
Erscheinungsjahr: 1987
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: 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 zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-51518
hdl:20.500.11880/26515
http://dx.doi.org/10.22028/D291-26459
Schriftenreihe: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Band: 1987/01
SciDok-Publikation: 4-Apr-2013
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
fb14_1987_01.pdf25,74 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.