Incremental Context-Dependent Analysis for Language-Based Editors

Thomas Reps, Tim Teitelbaum, and Alan Demers
Cornell University

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