Ce TP va vous faire manipuler deux boîtes à outils fournissant une implémentation efficace des expressions régulières, des automates et des opérations afférentes.
La première boîte à outil s'appelle FSM (Finite State Machine). Elle implémente les automates finis pondérés (chaque arc dispose d'un poids et des opérations permettent de chercher les chemins de poids minimal). L'aspect pondération ne nous intéresse pas (car les automates vus en cours et ceux utilisés pour l'analyse lexicale ne sont pas pondérés). Nous pouvons néanmoins utiliser FSM en ne donnant pas de poids aux arcs.
La deuxième boîte à outil s'appelle Lextools et elle permet de compiler des expressions régulières en des automates FSM. Lextools est un couche au-dessus de FSM permettant d'effectuer des traitements de nature morphologique et lexicale.
FSM et Lextools ont été développés par les AT&T Labs research, un prestigieux institut de recherche du New Jersey. Les exécutables sont librement téléchargeables pour une utilisation non commerciale. Vous pouvez les installer chez vous si vous utilisez linux (FSM fonctionne sous windows, mais pas Lextools).
Par ailleurs, un outil de visualisation graphique appelé graphviz sera utilisé pour obtenir la représentation graphique des automates en un format d'image (par exemple GIF).