Optimal-Time Incremental Semantic Analysis for Syntax-Directed Editors

Abstract

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 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 recomputes their values. The algorithm is time-optimal, its cost is proportional to the size of AFFECTED.