Optimal-time Incremental Semantic Analysis for Syntax-directed Editors
Thomas Reps
Attribute grammars permit the specification of static semantics in an
applicative and modular fashion, and thus are a good basis for
syntax-directed editors. Such editors represent programs as
attributed trees, which are modified by operations such as subtree
pruning and grafting. After each modification, a subset of
attributes, AFFECTED, requires new values. Membership in AFFECTED is
not known a priori; this paper presents an algorithm that identifies
attributes in AFFECTED and computes their new values. The algorithm
is time-optimal, its cost is proportional to the size of AFFECTED.
Cornell University