Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00175793
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, October 2, 2007 - 2:51:15 PM
Last modification on : Thursday, January 7, 2021 - 4:28:49 PM
Long-term archiving on: : Monday, June 27, 2011 - 4:58:55 PM

Files

RR-6313.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00175793, version 2

Citation

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

Share

Metrics

Record views

222

Files downloads

293