Syntactic Language Extension via an Algebra of Languages and Transformations

Jacob Andersen, Claus Brabrand

Research output: Journal Article or Conference Article in JournalConference articleResearchpeer-review


We propose an algebra of languages and transformations as a means for extending
languages syntactically. The algebra provides a layer of high-level abstractions
built on top of languages (captured by context-free grammars) and transformations
(captured by constructive catamorphisms).
The algebra is self-contained in that any term of the algebra specifying a transformation
can be reduced to a catamorphism, before the transformation is run. Thus,
the algebra comes "for free" without sacri cing the strong safety and efficiency
properties of constructive catamorphisms.
The entire algebra as presented in the paper is implemented as the Banana Algebra
Tool which may be used to syntactically extend languages in an incremental
and modular fashion via algebraic composition of previously de ned languages and
transformations. We demonstrate and evaluate the tool via several kinds of extensions.

Original languageEnglish
JournalElectronic Notes in Theoretical Computer Science
Issue number7
Pages (from-to)19-35
Publication statusPublished - 2010
EventLanguage Descriptions, Tools, and Applications (LDTA) - York, United Kingdom
Duration: 27 Mar 200928 Mar 2009
Conference number: 9


ConferenceLanguage Descriptions, Tools, and Applications (LDTA)
Country/TerritoryUnited Kingdom


  • Language Algebra
  • Syntactic Extension
  • Context-Free Grammars
  • Constructive Catamorphisms
  • Modular Transformations


Dive into the research topics of 'Syntactic Language Extension via an Algebra of Languages and Transformations'. Together they form a unique fingerprint.

Cite this