This book addresses a fundamental software engineering issue, applying formaltechniques and rigorous analysis to a practical problem of great current interest: the incorporationof language-specific knowledge in interactive programming environments. It makes a basiccontribution in this area by proposing an attribute-grammar framework for incremental semanticanalysis and establishing its algorithmic foundations. The results are theoretically important whilehaving immediate practical utility for implementing environment-generating systems.The book'sprincipal technical results include: an optimal-time algorithm to incrementally maintain aconsistent attributed-tree of attribute grammar subclasses, allowing an optimizingenvironment-generator to select the most efficient applicable algorithm; a general method forsharing storage among attributes whose values are complex data structures; and two algorithms thatcarry out attribute evaluation while reducing the number of intermediate attribute values retained.While others have worked on this last problem, Reps's algorithms are the first to achieve sublinearworst-case behavior. One algorithm is optimal, achieving the log n lower space bound in nonlineartime, while the second algorithm uses as much as root n. space but runs in linear time.
This book addresses a fundamental software engineering issue, applying formal techniques and rigorous analysis to a practical problem of great current interest: the incorporation of language-specific knowledge in interactive programming environments.
