Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Automated Selective Caching for Reference Attribute Grammars

  • Conference paper
Software Language Engineering (SLE 2010)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 6563))

Included in the following conference series:

Abstract

Reference attribute grammars (RAGs) can be used to express semantics as super-imposed graphs on top of abstract syntax trees (ASTs). A RAG-based AST can be used as the in-memory model providing semantic information for software language tools such as compilers, refactoring tools, and meta-modeling tools. RAG performance is based on dynamic attribute evaluation with caching. Caching all attributes gives optimal performance in the sense that each attribute is evaluated at most once. However, performance can be further improved by a selective caching strategy, avoiding caching overhead where it does not pay off. In this paper we present a profiling-based technique for automatically finding a good cache configuration. The technique has been evaluated on a generated Java compiler, compiling programs from the Jacks test suite and the DaCapo benchmark suite.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Acar, U.A., Blelloch, G.E., Harper, R.: Selective memoization. In: POPL, pp. 14–25. ACM, New York (2003)

    Google Scholar 

  2. Åkesson, J., Ekman, T., Hedin, G.: Implementation of a Modelica compiler using JastAdd attribute grammars. Science of Computer Programming 75(1-2), 21–38 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bellman, R.: Dynamic Programming. Princeton University Press, Princeton (1957)

    MATH  Google Scholar 

  4. Blackburn, S.M., Garner, R., Hoffmann, C., Khang, A.M., McKinley, K.S., Bentzur, R., Diwan, A., Feinberg, D., Frampton, D., Guyer, S.Z., Hirzel, M., Hosking, A., Jump, M., Lee, H., Moss, J.E.B., Moss, B., Phansalkar, A., Stefanović, D., VanDrunen, T., von Dincklage, D., Wiedermann, B.: The DaCapo benchmarks: java benchmarking development and analysis. In: OOPSLA 2006: Proceedings of the 21st Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, pp. 169–190. ACM, New York (2006)

    Chapter  Google Scholar 

  5. Blackburn, S.M., McKinley, K.S., Garner, R., Hoffmann, C., Khan, A.M., Bentzur, R., Diwan, A., Feinberg, D., Frampton, D., Guyer, S.Z., Hirzel, M., Hosking, A.L., Jump, M., Lee, H., Moss, J.E.B., Phansalkar, A., Stefanovic, D., VanDrunen, T., von Dincklage, D., Wiedermann, B.: Wake up and smell the coffee: evaluation methodology for the 21st century. Communications of the ACM 51(8), 83–89 (2008)

    Article  Google Scholar 

  6. Boyland, J.T.: Remote attribute grammars. Journal of the ACM 52(4), 627–687 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  7. Bürger, C., Karol, S., Wende, C.: Applying attribute grammars for metamodel semantics. In: Proceedings of the International Workshop on Formalization of Modeling Languages. ACM Digital Library (2010)

    Google Scholar 

  8. Ekman, T., Hedin, G.: Modular Name Analysis for Java Using JastAdd. In: Lämmel, R., Saraiva, J., Visser, J. (eds.) GTTSE 2005. LNCS, vol. 4143, pp. 422–436. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  9. Ekman, T., Hedin, G.: The Jastadd Extensible Java Compiler. In: 22nd Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2007), pp. 1–18. ACM, New York (2007)

    Google Scholar 

  10. Farrow, R.: Automatic generation of fixed-point-finding evaluators for circular, but well-defined, attribute grammars. In: SIGPLAN 1986: Proceedings of the 1986 SIGPLAN Symposium on Compiler Construction, pp. 85–98. ACM, New York (1986)

    Google Scholar 

  11. Hedin, G.: Reference Attributed Grammars. Informatica (Slovenia) 24(3), 301–317 (2000)

    MATH  Google Scholar 

  12. Hedin, G., Magnusson, E.: JastAdd: an aspect-oriented compiler construction system. Science of Computer Programming 47(1), 37–58 (2003)

    Article  MATH  Google Scholar 

  13. Huang, S.S., Hormati, A., Bacon, D.F., Rabbah, R.M.: Liquid metal: Object-oriented programming across the hardware/Software boundary. In: Ryan, M. (ed.) ECOOP 2008. LNCS, vol. 5142, pp. 76–103. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  14. Ibrahim, A., Jiao, Y., Tilevich, E., Cook, W.R.: Remote batch invocation for compositional object services. In: Drossopoulou, S. (ed.) ECOOP 2009. LNCS, vol. 5653, pp. 595–617. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  15. Jourdan, M.: An optimal-time recursive evaluator for attribute grammars. In: Paul, M., Robinet, B. (eds.) Programming 1984. LNCS, vol. 167, pp. 167–178. Springer, Heidelberg (1984)

    Chapter  Google Scholar 

  16. Jouve, W., Palix, N., Consel, C., Kadionik, P.: A SIP-based programming framework for advanced telephony applications. In: Schulzrinne, H., State, R., Niccolini, S. (eds.) IPTComm 2008. LNCS, vol. 5310, pp. 1–20. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  17. Kastens, U.: Lifetime analysis for attributes. Acta Informatica 24(6), 633–651 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  18. Kats, L.C.L., Sloane, A.M., Visser, E.: Decorated Attribute Grammars: Attribute Evaluation Meets Strategic Programming. In: de Moor, O., Schwartzbach, M.I. (eds.) CC 2009. LNCS, vol. 5501, pp. 142–157. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  19. Knuth, D.E.: Semantics of Context-free Languages. Mathematical Systems Theory 2(2), 127–145 (1968); Correction: Mathematical Systems Theory 5(1), 95–96 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  20. Nilsson-Nyman, E., Ekman, T., Hedin, G., Magnusson, E.: Declarative intraprocedural flow analysis of Java source code. In: Proceedings of the Eight Workshop on Language Description, Tools and Applications (LDTA 2008). Electronic Notes in Theoretical Computer Science, Elsevier B.V., Amsterdam (2008)

    Google Scholar 

  21. Poetzsch-Heffter, A.: Prototyping realistic programming languages based on formal specifications. Acta Informatica 34(10), 737–772 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  22. Rajan, H.: Ptolemy: A language with quantified, typed events (2010), http://www.cs.iastate.edu/~ptolemy/

  23. Saarinen, M.: On constructing efficient evaluators for attribute grammars. In: Ausiello, G., Böhm, C. (eds.) ICALP 1978. LNCS, vol. 62, pp. 382–397. Springer, Heidelberg (1978)

    Chapter  Google Scholar 

  24. Schäfer, M., Ekman, T., de Moor, O.: Sound and Extensible Renaming for Java. In: Kiczales, G. (ed.) 23rd Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2008). ACM Press, New York (2008)

    Google Scholar 

  25. Sloane, A.M., Kats, L.C.L., Visser, E.: A Pure Object-Oriented Embedding of Attribute Grammars. In: Proceedings of the 9th Workshop on Language Descriptions, Tools and Applications, LDTA 2009 (2009)

    Google Scholar 

  26. The DaCapo Project. The DaCapo Benchmarks (2009), http://dacapobench.org

  27. The JastAdd Caching Trac. Performance results for JastAddJ (2010), http://svn.cs.lth.se/trac/jastadd-caching

  28. The Mauve Project. Jacks (Jacks is an Automated Compiler Killing Suite) (2009), http://sources.redhat.com/mauve

  29. Vogt, H., Doaitse Swierstra, S., Kuiper, M.F.: Higher-order attribute grammars. In: PLDI, pp. 131–145 (1989)

    Google Scholar 

  30. Van Wyk, E., Bodin, D., Gao, J., Krishnan, L.: Silver: An extensible attribute grammar system. Science of Computer Programming 75(1-2), 39–54 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  31. Van Wyk, E., Krishnan, L., Bodin, D., Schwerdfeger, A.: Attribute grammar-based language extensions for java. In: Bateni, M. (ed.) ECOOP 2007. LNCS, vol. 4609, pp. 575–599. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Lund University, Sweden

    Emma Söderberg & Görel Hedin

Authors
  1. Emma Söderberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Görel Hedin
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Computer Science Dept., Clemson University, SC 29634, Clemson, USA

    Brian Malloy

  2. Institute for Computer Science, University of Koblenz, P.O.Box 201602, 56016, Koblenz, Germany

    Steffen Staab

  3. Mathematics and Computer Science Dept., Eindhoven University of Technology, Den Dolech 2, 5612 AZ, Eindhoven, The Netherlands

    Mark van den Brand

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Söderberg, E., Hedin, G. (2011). Automated Selective Caching for Reference Attribute Grammars. In: Malloy, B., Staab, S., van den Brand, M. (eds) Software Language Engineering. SLE 2010. Lecture Notes in Computer Science, vol 6563. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19440-5_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-19440-5_2

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-19439-9

  • Online ISBN: 978-3-642-19440-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation