Generating Language-Based Environments

by Reps, Thomas W.

• ISBN13: 9780262681469
• ISBN10: 0262681463
• Format: Paperback
• Copyright: 1984-02-01
• Publisher: Mit Pr

Summary

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. It makes a basic contribution in this area by proposing an attribute-grammar framework for incremental semantic analysis and establishing its algorithmic foundations. The results are theoretically important while having immediate practical utility for implementing environment-generating systems. The book's principal technical results include: an optimal-time algorithm to incrementally maintain a consistent attributed-tree of attribute grammar subclasses, allowing an optimizing environment-generator to select the most efficient applicable algorithm; a general method for sharing storage among attributes whose values are complex data structures; and two algorithms that carry 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 sublinear worst-case behavior. One algorithm is optimal, achieving the log nlower space bound in nonlinear time, while the second algorithm uses as much as root n. space but runs in linear time.

Table of Contents

Series Foreword	p. v
Preface	p. vii
Acknowledgments	p. ix
Introduction	p. 1
Providing better programming environments	p. 6
Attribute grammars and attribute evaluation	p. 17
Incremental attribute evaluation	p. 29
Optimal-time change propagation	p. 38
Extending the model of editing	p. 49
Space-efficient attribute evaluation	p. 54
Efficient representations of large attributes	p. 81
Incremental evaluation for restricted classes of attribute grammars	p. 88
Some final remarks	p. 107
The Synthesizer Generator Reference Manual	p. 111
The running time of Algorithm 7.8	p. 127
Bibliography	p. 129
Index of symbols	p. 135
Index of Definitions	p. 137
Table of Contents provided by Publisher. All Rights Reserved.