Generating Language-Based Environments (ACM Doctoral Dissertation Award) by Reps Thomas W. (1984-02-23) Hardcover

by Thomas W. Reps

This book addresses a fundamental software engineering issue, applyingformal techniques and rigorous analysis to a practical problem of great the incorporation of language-specific knowledge in interactiveprogramming environments. It makes a basic contribution in this area by proposing anattribute-grammar framework for incremental semantic analysis and establishing itsalgorithmic foundations. The results are theoretically important while havingimmediate practical utility for implementing environment-generating systems.Thebook's principal technical results an optimal-time algorithm toincrementally maintain a consistent attributed-tree of attribute grammar subclasses, allowing an optimizing environment-generator to select the most efficient applicablealgorithm; a general method for sharing storage among attributes whose values arecomplex data structures; and two algorithms that carry out attribute evaluationwhile reducing the number of intermediate attribute values retained. While othershave worked on this last problem, Reps's algorithms are the first to achievesublinear worst-case behavior. One algorithm is optimal, achieving the log n lowerspace bound in nonlinear time, while the second algorithm uses as much as root n.space but runs in linear time.

Hardcover

First published February 1, 1984