Les containers ASTL

L’Automaton Standard

Template Library est un ensemble de composants logiciels g´en´eriques cod´es en C++. Chacun de ces composants entre dans une cat´egorie bien d´efinie dont l’interface est compl`etement sp´ecifi´ee, y compris les complexit´es de temps de calcul. Une telle conception n´ecessite de d´efinir des abstractions logicielles en rapport avec le domaine consid´er´e, c’est-`a-dire de d´efinir le comportement des objets, ici des containers d’automate et l’´etendue de leur champ d’applications (ce qu’ils doivent savoir faire et ce pour quoi ils ne sont pas faits) en gardant `a l’esprit que les deux buts fondamentaux restent la r´eutilisation et l’efficacit´e. Grˆace `a une utilisation intensive de patron de classe, ASTL fournit un ensemble de structures de donn´ees polymorphes donc interchangeables avec leurs caract´eristiques propres.

Chacune des classes d’automate pr´esente des complexit´es spatiales et temporelles adapt´ees `a des contraintes diff´erentes. Cette vari´et´e d’impl´ementations permet l’adaptation d’une application `a des environnements divers sans avoir `a modifier le reste de l’architecture car l’interface des automates est standardis´ee. 3.1 Structure g´en´erale ASTL se plie aux standards de la programmation g´en´erique en C++ d´efinis par la librairie standard : – Tous les composants sont g´en´eriques, ce sont des patrons (templates) de classe ou de fonction. – L’h´eritage se limite au strict minimum. Il n’y a pas obligatoirement de relation de sous-typage r´eelle entre objets de concepts imbriqu´es. Des sp´ecifications pr´ecises et rigoureuses suffisent `a maintenir un polymorphisme statique. Les composants sont donc interchangeables mais il n’y a pas de m´ethodes virtuelles pour maximiser l’optimisation `a la compilation et pour ´eviter les probl`emes li´es `a leur interaction avec les composants STL [31]. – Les containers ASTL sont des containers STL ou des combinaisons. On acc`ede aux donn´ees grˆace `a des it´erateurs et les s´equences sont d´efinies par des intervalles. – Les algorithmes ne sont pas incorpor´es aux containers. L’utilisateur « branche »l’algo33 Les containers ASTL 34 CHAPITRE 3. LES CONTAINERS ASTL rithme choisi sur la classe d’automate qui satisfait le mieux ses contraintes d’espace et de temps. La communication s’´etablit `a travers les curseurs, accesseurs d’automates ´equivalents aux it´erateurs de s´equences. Les algorithmes g´en´eriques ne s’appliquent jamais directement `a la structure de donn´ees. Dans la section suivante, on d´efinit le type abstrait ou concept d’automate en termes de concepts STL.

Le concept d’automate

Pour une d´efinition math´ematique formelle des automates, de leurs propri´et´es et des termes s’y rapportant se r´ef´erer `a la section 2.2.1 page 24. Les d´efinitions suivantes d´ecrivent un ensemble de concepts dont la combinaison constitue le concept g´en´eral d’automate. 3.2.1 Transitions sortantes L’ensemble δ2(q) = ((σ1, p1), …, (σn, pn)) des transitions sortant d’un ´etat q est stock´e dans un container associatif de paires appel´e Edges (pair associative container) dont les cl´es sont les lettres σ ∈ Σ et les valeurs les couples (σ, p) ∈ Σ × Q. Pour les automates non d´eterministes, ce container associatif est dit `a cl´es multiples, c’est-`a-dire que les cl´es ne sont pas forc´ement uniques : on peut avoir pour i 6= j, σi = σj . Autrement dit, m valeurs peuvent ˆetre associ´ees `a une mˆeme cl´e, ces m transitions ´etant ´etiquet´ees par la mˆeme lettre. Dans le cas d’un automate d´eterministe, le container associatif est dit `a cl´es uniques et les transitions d’un ´etat sont toutes ´etiquet´ees par des lettres diff´erentes.