@article{1412294,
      recid = {1412294},
      author = {Reps, Thomas W.},
      title = {Generating language-based environments /},
      publisher = {MIT Press,},
      address = {Cambridge, Mass. ;},
      pages = {1 online resource (138 pages)},
      year = {2012},
      note = {"An MIT Press classic."},
      abstract = {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 n lower space bound  in nonlinear time, while the second algorithm uses as much  as root n. space but runs in linear time.},
      url = {http://library.usi.edu/record/1412294},
}