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)