Knowledge of a programming language's grammar allows language-based editors to enforce syntactic correctness at all times during development by restricting editing operations to legitimate modifications of the program's context-free derivation tree; however, not all language constraints can be enforced in this way because not all features can be described by the context-free formalism. Attribute grammars permit context-dependent language features to be expressed in a modular, declarative fashion, and thus are a good basis for specifying language-based editors. Such editors represent programs as attributed trees, which are modified by operations such as subtree pruning and grafting. Incremental analysis is performed by updating attribute values after every modification. This paper discusses how updating can be carried out, and presents several algorithms for the task, including one that is asymptotically optimal in time.

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

General Terms: Algorithms, Design

Additional Key Words and Phrases: attribute grammars, incremental attribute evaluation, incremental semantic analysis, editor generators

[ACM Author-Izer Link.]

Corrigenda, ACM Transactions on Programming Languages and Systems 5, 4 (October 1983). [ACM Author-Izer Link.]