Skip to Main content Skip to Navigation
Reports

Automates modulaires

Résumé : L'algorithme de Berry-Sethi pour la compilation des expressions régulières en automates est efficace et présenté de manière élégante. Ce rapport fournit une implémentation de cette technique de compilation dans le langage de programmation PidginML avec l'innovation de compiler des expressions régulières que nous avons étendues. Son élégance tient dans son style de programmation purement fonctionnel et son respect de la complexité théorique de l'algorithme. La propriété de localité des automates obtenus est à la base de la modularité d'automates dans la boîte à outils de linguistique computationnelle Zen2. Ce rapport comporte également une justification formelle de la bonne formation des automates compilés, par un développement dans l'assistant de preuves Coq. Il discute également de l'adaptation de la boîte à outils Zen2 au problème classique de recherche de chaînes de caractères dans un texte (commande grep Unix)
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00070233
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 7:37:00 PM
Last modification on : Friday, May 25, 2018 - 12:02:03 PM
Long-term archiving on: : Sunday, April 4, 2010 - 8:41:17 PM

Identifiers

  • HAL Id : inria-00070233, version 1

Collections

Citation

Benoit Razet. Automates modulaires. [Rapport de recherche] RR-5788, INRIA. 2005, pp.43. ⟨inria-00070233⟩

Share

Metrics

Record views

189

Files downloads

322