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.
Type de document :
Rapport
[Research Report] RR-6313, INRIA. 2007, pp.17
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00175793
Contributeur : Rapport de Recherche Inria <>
Soumis le : mardi 2 octobre 2007 - 14:51:15
Dernière modification le : mercredi 16 mai 2018 - 11:23:04
Document(s) archivé(s) le : lundi 27 juin 2011 - 16:58:55

Fichiers

RR-6313.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

190

Téléchargements de fichiers

217