## Abstract

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 language | English |
---|---|

Journal | Electronic Notes in Theoretical Computer Science |

Volume | 253 |

Issue number | 7 |

Pages (from-to) | 19-35 |

ISSN | 1571-0661 |

Publication status | Published - 2010 |

Event | Language Descriptions, Tools, and Applications (LDTA) - York, United Kingdom Duration: 27 Mar 2009 → 28 Mar 2009 Conference number: 9 |

### Conference

Conference | Language Descriptions, Tools, and Applications (LDTA) |
---|---|

Number | 9 |

Country/Territory | United Kingdom |

City | York |

Period | 27/03/2009 → 28/03/2009 |

## Keywords

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