Article

Decorated Attribute Grammars: Attribute Evaluation Meets Strategic Programming

Authors:

Lennart C. L. Kats,

Anthony M. Sloane,

Eelco VisserAuthors Info & Claims

CC '09: Proceedings of the 18th International Conference on Compiler Construction: Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009

Pages 142 - 157

https://doi.org/10.1007/978-3-642-00722-4_11

Published: 27 March 2009 Publication History

Abstract

Attribute grammars are a powerful specification formalism for tree-based computation, particularly for software language processing. Various extensions have been proposed to abstract over common patterns in attribute grammar specifications. These include various forms of copy rules to support non-local dependencies, collection attributes, and expressing dependencies that are evaluated to a fixed point. Rather than implementing extensions natively in an attribute evaluator, we propose <em>attribute decorators</em> that describe an abstract evaluation mechanism for attributes, making it possible to provide such extensions as part of a library of decorators. Inspired by strategic programming, decorators are specified using generic traversal operators. To demonstrate their effectiveness, we describe how to employ decorators in name, type, and flow analysis.

References

[1]

Aster project home page, http://strategoxt.org/Stratego/Aster

[2]

Baars, A., Swierstra, D., Löh, A.: UU AG System User Manual. Department of Computer Science, Utrecht University (September 2003).

[3]

Bird, R.: Using circular programs to eliminate multiple traversals of data. Acta Informatica 21(3), 239-250 (1984).

[4]

Boyland, J.: Descriptional Composition of Compiler Components. PhD thesis (1996).

[5]

Boyland, J.: Remote attribute grammars. Journal of the ACM(JACM) 52(4), 627-687 (2005).

[6]

Boyland, J., Graham, S.L.: Composing tree attributions. In: POPL 1994, pp. 375-388. ACM, New York (1994).

[7]

van den Brand, M.G.J., de Jong, H., Klint, P., Olivier, P.: Efficient annotated terms. Software, Practice & Experience 30(3), 259-291 (2000).

[8]

Bravenboer, M., Kalleberg, K.T., Vermaas, R., Visser, E.: Stratego/XT 0.17. A language and toolset for program transformation. Science of Computer Programming 72(1-2), 52-70 (2008).

[9]

Ekman, T., Hedin, G.: Rewritable reference attributed grammars. In: Odersky, M. (ed.) ECOOP 2004. LNCS, vol. 3086, pp. 144-169. Springer, Heidelberg (2004).

[10]

Farnum, C.: Pattern-based tree attribution. In: POPL 1992, pp. 211-222 (1992).

[11]

Gamma, E., Helm, R., Johnson, R., Vlissides, J.: Design patterns: elements of reusable object-oriented software. Addison-Wesley Professional, Reading (1995).

[12]

Hedin, G.: Reference attributed grammars. Informatica (Slovenia) 24(3), 301-317 (2000).

[13]

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

[14]

Jalili, F.: A general linear time evaluator for attribute grammars. ACM SIGPLAN Notices 18(9), 35-44 (1983).

[15]

Kastens, U., Waite, W.M.: Modularity and reusability in attribute grammars. Acta Informatica 31(7), 601-627 (1994).

[16]

Kats, L.C.L., Kalleberg, K.T., Visser, E.: Generating editors for embedded languages. Integrating SGLR into IMP. In: LDTA 2008 (April 2008).

[17]

Kats, L.C.L., Sloane, A.M., Visser, E.: Decorated attribute grammars - Attribute evaluation meets strategic programming. Extended technical report TUD-SERG-2008-038a. Software Engineering Research Group, Delft University of Technology (2008), http://swerl.tudelft.nl/bin/view/Main/TechnicalReports#2008-038

[18]

Kiczales, G., et al.: Aspect-oriented programming. In: Aksit, M., Matsuoka, S. (eds.) ECOOP 1997. LNCS, vol. 1241, pp. 220-242. Springer, Heidelberg (1997).

[19]

Knuth, D.E.: Semantics of context-free languages. Math. Syst. Theory 2(2), 127-145 (1968).

[20]

Laemmel, R., Visser, E., Visser, J.: Strategic programming meets adaptive programming. In: Proceedings of Aspect-Oriented Software Development (AOSD 2003), Boston, USA, pp. 168-177. ACM Press, New York (2003).

[21]

Lämmel, R.: Typed generic traversal with term rewriting strategies. Journal of Logic and Algebraic Programming 54(1), 1-64 (2003).

[22]

Magnusson, E., Ekman, T., Hedin, G.: Extending attribute grammars with collection attributes - evaluation and applications. In: Proc. of the Int. Working Conference on Source Code Analysis and Manipulation, pp. 69-80 (2007).

[23]

Magnusson, E., Hedin, G.: Circular reference attributed grammars - their evaluation and applications. Science of Computer Programming 68(1), 21-37 (2007).

[24]

de Moor, O., Backhouse, K., Swierstra, S.: First-class attribute grammars. Informatica 24(3), 329-341 (2000).

[25]

Nilsson-Nyman, E., Ekman, T., Hedin, G., Magnusson, E.: Declarative intraprocedural flow analysis of Java source code. In: LDTA 2008 (2008).

[26]

Paakki, J.: Attribute grammar paradigms - a high-level methodology in language implementation. ACM Computing Surveys (CSUR) 27(2), 196-255 (1995).

[27]

van Rossum, G.: Python Reference Manual. iUniverse (2000).

[28]

Steele, G.: Growing a language. Higher Order Symb. Comp. 12(3), 221-236 (1999).

[29]

Van Wyk, E., Bodin, D., Gao, J., Krishnan, L.: Silver: an extensible attribute grammar system. In: LDTA 2007. ENTCS, vol. 203, pp. 103-116. Elsevier Science, Amsterdam (2008).

[30]

Van Wyk, E., de Moor, O., Backhouse, K., Kwiatkowski, P.: Forwarding in attribute grammars for modular language design. In: Horspool, R.N. (ed.) CC 2002. LNCS, vol. 2304, pp. 128-142. Springer, Heidelberg (2002).

[31]

Van Wyk, E., Krishnan, L., Bodin, D., Johnson, E.: Adding domain-specific and general purpose language features to Java with the Java language extender. In: Companion to OOPSLA 2006, pp. 728-729. ACM, New York (2006).

[32]

Visser, E.: Meta-programming with concrete object syntax. In: Batory, D., Consel, C., Taha, W. (eds.) GPCE 2002. LNCS, vol. 2487, pp. 299-315. Springer, Heidelberg (2002).

[33]

Visser, E., Benaissa, Z.-e.-A., Tolmach, A.: Building program optimizers with rewriting strategies. In: International Conference on Functional Programming (ICFP 1998), pp. 13- 26. ACM, New York (1998).

Cited By

Macedo JViera MSaraiva J(2022)Zipping Strategies and Attribute GrammarsFunctional and Logic Programming10.1007/978-3-030-99461-7_7(112-132)Online publication date: 10-May-2022
https://dl.acm.org/doi/10.1007/978-3-030-99461-7_7
Kramer LVan Wyk ELämmel RTratt Lde Lara J(2020)Strategic tree rewriting in attribute grammarsProceedings of the 13th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3426425.3426943(210-229)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.1145/3426425.3426943
Fors NSöderberg EHedin GLämmel RTratt Lde Lara J(2020)Principles and patterns of JastAdd-style reference attribute grammarsProceedings of the 13th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3426425.3426934(86-100)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.1145/3426425.3426934
Show More Cited By

Decorated Attribute Grammars: Attribute Evaluation Meets Strategic Programming
1. Theory of computation
  1. Formal languages and automata theory
  2. Semantics and reasoning

Recommendations

The formal power of one-visit attribute grammars

An attribute grammar is one-visit if the attributes can be evaluated by walking through the derivation tree in such a way that each subtree is visited at most once. One-visit (1V) attribute grammars are compared with one-pass left-to-right (L) attribute ...
Indexical attribute grammars
A Classification of Noncircular Attribute Grammars Based on the Look-Ahead Behavior

We propose a family of static evaluators for subclasses of the well-defined (i.e., noncircular) attribute grammars. These evaluators augment the evaluator for the absolutely noncircular attribute grammars with look-ahead behaviors. Because this family ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CC '09: Proceedings of the 18th International Conference on Compiler Construction: Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009

March 2009

280 pages

ISBN:9783642007217

Editors:
Oege Moor
Computing Laboratory, Oxford University, Oxford, UK OX1 3QD
,
Michael I. Schwartzbach
Department of Computer Science, Aarhus University, Aarhus N., Denmark 8200

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 27 March 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Macedo JViera MSaraiva J(2022)Zipping Strategies and Attribute GrammarsFunctional and Logic Programming10.1007/978-3-030-99461-7_7(112-132)Online publication date: 10-May-2022
https://dl.acm.org/doi/10.1007/978-3-030-99461-7_7
Kramer LVan Wyk ELämmel RTratt Lde Lara J(2020)Strategic tree rewriting in attribute grammarsProceedings of the 13th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3426425.3426943(210-229)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.1145/3426425.3426943
Fors NSöderberg EHedin GLämmel RTratt Lde Lara J(2020)Principles and patterns of JastAdd-style reference attribute grammarsProceedings of the 13th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3426425.3426934(86-100)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.1145/3426425.3426934
Smits JVisser ECombemale BMernik MRumpe B(2017)FlowSpec: declarative dataflow analysis specificationProceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3136014.3136029(221-231)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3136014.3136029
Bürger CPaige RDi Ruscio DVölter M(2015)Reference attribute grammar controlled graph rewriting: motivation and overviewProceedings of the 2015 ACM SIGPLAN International Conference on Software Language Engineering10.1145/2814251.2814257(89-100)Online publication date: 26-Oct-2015
https://dl.acm.org/doi/10.1145/2814251.2814257
Krijnen JSwierstra DViera M(2014)ExpandProceedings of the 16th International Symposium on Practical Aspects of Declarative Languages - Volume 832410.1007/978-3-319-04132-2_14(200-215)Online publication date: 20-Jan-2014
https://dl.acm.org/doi/10.1007/978-3-319-04132-2_14
LäMmel RThompson SKaiser M(2013)Programming errors in traversal programs over structured dataScience of Computer Programming10.1016/j.scico.2011.11.00678:10(1770-1808)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1016/j.scico.2011.11.006
Sloane AKats LVisser E(2013)A pure embedding of attribute grammarsScience of Computer Programming10.1016/j.scico.2011.11.00578:10(1752-1769)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1016/j.scico.2011.11.005
de Jonge MKats LVisser ESöderberg E(2012)Natural and Flexible Error Recovery for Generated Modular Language EnvironmentsACM Transactions on Programming Languages and Systems10.1145/2400676.240067834:4(1-50)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1145/2400676.2400678
Söderberg EHedin G(2010)Automated selective caching for reference attribute grammarsProceedings of the Third international conference on Software language engineering10.5555/1964571.1964575(2-21)Online publication date: 12-Oct-2010
https://dl.acm.org/doi/10.5555/1964571.1964575
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten