Incremental Language Analysis for Ensemble
William Maddox
(Professor S.ÊL. Graham)
(ARPA) MDA972-92-J-1028

We are designing and implementing a static analysis component for
formal documents such as computer programs in the Ensemble multimedia
editing system. We assume that the syntactic structure of the document
has been previously captured and is presented to the analyzer as an
abstract syntax tree.  Since most changes that arise in editing affect
a relatively small portion of the analysis, response time may be
improved by updating the analysis incrementally as changes are made to
the tree. The analyzer is driven by a formal and largely declarative
description of the analysis to be performed, and need not explicitly
take the incremental mode of operation into account.

Incremental attribute grammar evaluation is the traditional approach
taken to this problem by most other researchers, but existing methods
do not exhibit robustly scalable incremental behavior. The Colander
system [1] took an alternate approach based on incremental logic
programming that addressed this problem, but yielded unacceptable
performance for other reasons. Our new approach combines features of
both of these approaches while addressing a number of important
engineering concerns that have been overlooked in previous work, such
as modularity of analysis descriptions and the extension of existing
descriptions.

We have completed the design of the specification language and have
demonstrated a partial implementation. A complete implementation is in
progress.

[1] R. A. Ballance, Syntactic and Semantic Checking in Language-Based
Editing Systems, UC Berkeley Computer Science Division, Report
No. UCB/CSD 89/548, 1989.