Incremental Evaluation for Attribute Grammars with Application to Syntax-directed Editors

Alan Demers, Thomas Reps, and Tim Teitelbaum
Cornell University

A syntax-directed editor is a tool for structured program development. Such an editor can enforce syntactic correctness incrementally by restricting editing operations to legitimate modifications of the program's context-free derivation tree. However, not all language features can be described by the context-free formalism. To build editors that enforce non-context-free correctness, a more powerful specification technique is needed. In this paper we discuss the advantages of attribute grammars as a specification technique for a syntax-directed editing system. We also present an efficient algorithm for incrementally evaluating attributes as a program tree is derived.