Incremental evaluation for attribute grammars with unrestricted movement between tree modifications (Q1103412)

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.