Incremental evaluation for attribute grammars with unrestricted movement between tree modifications
type: Item
instance of: scholarly article
title: Incremental evaluation for attribute grammars with unrestricted movement between tree modifications
zbMATH Open document ID: 0645.68089
DOI: 10.1007/BF02737101
published in: Acta Informatica
publication date: 1988-01-01T00:00:00Z
review text: This paper concerns the design of editors that perform checks on a language's context-dependent constraints. Our particular concern is the design of an efficient, incremental analysis algorithm for systems based on the attribute-grammar model of editing. With previous incremental evaluation algorithms for arbitrary noncircular attribute grammars, the editing model required there to be a restriction on the operation that moves the editing cursor: moving the cursor was limited to just a single step in the tree - either to the parent node or to one of the child nodes of the current cursor location. This paper describes a new updating algorithm that can be used when an arbitrary movement of the cursor in the tree is permitted. After an operation that restructures the tree, the tree's attributes can be updated with a cost of \(O((1+| AFFECTED|)\cdot \sqrt{m})\), where m is the size of the tree and AFFECTED is the subset of the tree's attributes that require new values, when the cost is amortized over a sequence of tree modifications. The editing cursor may be moved from its current location to any other node of the tree in a single, unit-cost operation.
Mathematics Subject Classification ID: 68Q55
Mathematics Subject Classification ID: 68Q60
zbMATH DE Number: 4053054
zbMATH Keywords: editing model
zbMATH Keywords: program editors
zbMATH Keywords: compiler generators
zbMATH Keywords: denotational semantics
zbMATH Keywords: incremental evaluation
zbMATH Keywords: noncircular attribute grammars
zbMATH Keywords: tree modifications
zbMATH Keywords: editing cursor
author: Thomas Reps
MaRDI profile type: Publication
cites work: Semantics of context-free languages
cites work: Q3741011
cites work: Sublinear-space evaluation algorithms for attribute grammars
cites work: Q4040974
cites work: Q3707420
cites work: On incremental evaluation of ordered attributed grammars
full work available at URL: https://doi.org/10.1007/bf02737101
OpenAlex ID: W4252107805
description: scientific article; zbMATH DE number 4053054