Incremental Evaluation for Attribute Grammars
with Unrestricted Movement between Tree Modifications
Thomas Reps
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|) (m**1/2),
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.
CR Categories and Subject Descriptors:
D.2.3 [Software Engineering]: Coding -- program editors;
D.2.6 [Software Engineering]: Programming Environments;
D.3.1 [Programming Languages]: Formal Definitions and Theory -- semantics, syntax;
D.3.4 [Programming Languages]: Processors -- translator writing systems and compiler generators;
F.3.2 [Logics and Meanings of Programs]:
Semantics of Programming Languages -- denotational semantics
General Terms: Algorithms, Design
Additional Key Words and Phrases:
Attribute grammar, incremental attribute evaluation, incremental
context-dependent analysis, language-based editor, editor generator
University of Wisconsin