Re: syntax-directed editing

> I've got an AST representation of a java package/file and a textual
> representation of this file. This file should be editable and the AST
> thus has to be updated at least every time the file is saved. How can
> I manage this rebuilding as little as possible of the AST and how can
> I do it at all? Do you know some introducing papers or other
> materials on this topic?
>
> Thanks in advance.
> Alexander Stippler
> [There was a series of articles in the JCLT on an incremental compiler
> that incrementally updated the parse tree. If the text is stored in a
> tokenized form, I'd guess that reparsing is fast enough that it's
> not worth a lot of work to avoid. -John]


Here's a nice paper I read on it (34 pages). I have the preprint as
PDF, so I don't have the volume, number, pages.


"Efficient and Flexible Incremental Parsing"


ACM Transactions on Programming Languages and Systems


TIM A. WAGNER and SUSAN L. GRAHAM


University of California, Berkeley


ABSTRACT: Previously published algorithms for LR(k) incremental
parsing are inefficient, unnecessarily restrictive, and in some
cases incorrect. We present a simple algorithm based on parsing LR(k)
sentential forms that can incrementally parse an arbitrary number of
textual and/or structural modifications in optimal time and with no
storage overhead. The central role of balanced sequences in achieving
truly incremental behavior from analysis algorithms is described,
along with automated methods to support balancing during parse table
generation and parsing. Our approach extends the theory of
sentential-form parsing to allow for ambiguity in the grammar,
exploiting it for notational convenience, to denote sequences, and to
construct compact abstract syntax trees directly. Combined, these
techniques make the use of automatically generated incremental parsers
in interactive software development environments both practical and
effective. In addition, we address information preservation in these
environments: Optimal node reuse is defined; previous definitions are
shown to be insufficient; and a method for detecting node reuse is
provided that is both simpler and faster than existing techniques. A
program representation based on self-versioning documents is used to
detect changes in the program, generate efficient change reports for
subsequent analyses, and allow the parsing transformation itself to be
treated as a reversible modification in the edit log.


--
Quinn Tyler Jackson


http://qtj.n3.net/~quinn/

Return to the comp.compilers page.
Search the comp.compilers archives again.