HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Modular Grammars and Splitting of Catamorphisms

Eric Badouel 1 Rodrigue Djeumen 1
1 S4 - System synthesis and supervision, scenarios
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : An abstract context-free grammar can be viewed as a system of polynomial functors. The initial algebra of this functor coincides with its least fixed-point; and this fixed-point can be computed by a method of substitution using Bek\`{\i}c theorem. By doing so the system of polynomial functors is transformed into a related system of regular functors. We introduce a splitting operation on algebras producing an algebra for the resulting system of regular functors from an algebra of the original system of polynomial functors. This transformation preserves the interpretation function (catamorphism). The end result is a class of (extended) abstract context-free grammars, associated with regular functors. This class seems to be well-adapted to the modular design of domain-specific embedded languages.
Document type :
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, October 2, 2007 - 2:51:15 PM
Last modification on : Friday, February 4, 2022 - 3:24:55 AM
Long-term archiving on: : Monday, June 27, 2011 - 4:58:55 PM


Files produced by the author(s)


  • HAL Id : inria-00175793, version 2


Eric Badouel, Rodrigue Djeumen. Modular Grammars and Splitting of Catamorphisms. [Research Report] RR-6313, INRIA. 2007, pp.17. ⟨inria-00175793v2⟩



Record views


Files downloads