Advanced

Demand-driven evaluation of collection attributes

Magnusson, Eva LU ; Ekman, Torbjörn LU and Hedin, Görel LU (2009) In Automated Software Engineering 16(2). p.291-322
Abstract
n order to make attribute grammars useful for complicated analysis tasks, a number of extensions to the original Knuth formalism have been suggested. One such extension is the collection attribute mechanism, which allows the value of an attribute to be defined as a combination of contributions from distant nodes in the abstract syntax tree. Another extension that has proven useful is circular attributes, evaluated using fixed-point iteration. In this paper we show how collection attributes and the combined formalism, circular collection attributes, have been implemented in our declarative meta programming system JastAdd, and how they can be used for a variety of applications including devirtualization analysis, metrics and flow analysis. A... (More)
n order to make attribute grammars useful for complicated analysis tasks, a number of extensions to the original Knuth formalism have been suggested. One such extension is the collection attribute mechanism, which allows the value of an attribute to be defined as a combination of contributions from distant nodes in the abstract syntax tree. Another extension that has proven useful is circular attributes, evaluated using fixed-point iteration. In this paper we show how collection attributes and the combined formalism, circular collection attributes, have been implemented in our declarative meta programming system JastAdd, and how they can be used for a variety of applications including devirtualization analysis, metrics and flow analysis. A number of evaluation algorithms are introduced and compared for applicability and efficiency. The key design criterion for our algorithms is that they work well with demand evaluation, i.e., defined properties are computed only if they are actually needed for a particular program. We show that the best algorithms work well on large practical problems including the analysis of large Java programs. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Attribute grammars - Collection attributes - Circular attributes - Fixed-point computations - Source code analysis
in
Automated Software Engineering
volume
16
issue
2
pages
291 - 322
publisher
Springer
external identifiers
  • wos:000265084000005
  • scopus:67349121878
ISSN
1573-7535
DOI
10.1007/s10515-009-0046-z
project
EASE
language
English
LU publication?
yes
id
9d7a662a-49c6-4887-849b-0e857aa7559c (old id 1301564)
date added to LUP
2009-04-16 12:37:24
date last changed
2017-01-01 04:45:08
@article{9d7a662a-49c6-4887-849b-0e857aa7559c,
  abstract     = {n order to make attribute grammars useful for complicated analysis tasks, a number of extensions to the original Knuth formalism have been suggested. One such extension is the collection attribute mechanism, which allows the value of an attribute to be defined as a combination of contributions from distant nodes in the abstract syntax tree. Another extension that has proven useful is circular attributes, evaluated using fixed-point iteration. In this paper we show how collection attributes and the combined formalism, circular collection attributes, have been implemented in our declarative meta programming system JastAdd, and how they can be used for a variety of applications including devirtualization analysis, metrics and flow analysis. A number of evaluation algorithms are introduced and compared for applicability and efficiency. The key design criterion for our algorithms is that they work well with demand evaluation, i.e., defined properties are computed only if they are actually needed for a particular program. We show that the best algorithms work well on large practical problems including the analysis of large Java programs.},
  author       = {Magnusson, Eva and Ekman, Torbjörn and Hedin, Görel},
  issn         = {1573-7535},
  keyword      = {Attribute grammars - Collection attributes - Circular attributes - Fixed-point computations - Source code analysis},
  language     = {eng},
  number       = {2},
  pages        = {291--322},
  publisher    = {Springer},
  series       = {Automated Software Engineering},
  title        = {Demand-driven evaluation of collection attributes},
  url          = {http://dx.doi.org/10.1007/s10515-009-0046-z},
  volume       = {16},
  year         = {2009},
}