A pure embedding of attribute grammars

Anthony M. Sloane*, Lennart C L Kats, Eelco Visser

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)


Attribute grammars are a powerful specification paradigm for many language processing tasks, particularly semantic analysis of programming languages. Recent attribute grammar systems use dynamic scheduling algorithms to evaluate attributes on demand. In this paper, we show how to remove the need for a generator, by embedding a dynamic approach in a modern, object-oriented and functional programming language. The result is a small, lightweight attribute grammar library that is part of our larger Kiama language processing library. Kiama's attribute grammar library supports a range of advanced features including cached, uncached, higher order, parameterised and circular attributes. Forwarding is available to modularise higher order attributes and decorators abstract away from the details of attribute value propagation. Kiama also implements new techniques for dynamic extension and variation of attribute equations. We use the Scala programming language because of its support for domain-specific notations and emphasis on scalability. Unlike generators with specialised notation, Kiama attribute grammars use standard Scala notations such as pattern-matching functions for equations, traits and mixins for composition and implicit parameters for forwarding. A benchmarking exercise shows that our approach is practical for realistic language processing.

Original languageEnglish
Pages (from-to)1752-1769
Number of pages18
JournalScience of Computer Programming
Issue number10
Publication statusPublished - 1 Oct 2013


Dive into the research topics of 'A pure embedding of attribute grammars'. Together they form a unique fingerprint.

Cite this