OpenGRM permet de compiler des expressions régulières en automates finis OpenFST (forme compilée). Un fichier source de OpenGRM comporte une succession de définitions d'expressions régulières.
Voyons un premier exemple que nous mettons dans un fichier
exemple-3.grm.
export automate_1 = "a" "b"* "c"+;
export automate_2 = ("xz"|"yy")*;
espace = " ";
export automate_3 = automate_1 espace+ automate_2;
export automate_3_opt = Optimize[ automate_3 ];
Chaque ligne définit une expression régulière et lui donne un nom. La ligne 3
ne commence pas par export: cela signifie que l'automate appelé espace
sera calculé mais ne sera pas conservé. Il sera juste utilisé dans la
définition de automate_3.
Pour compiler ces expressions régulières en automates, il faut utiliser les commandes suivantes:
> thraxmakedep exemple-3.grm > make thraxcompiler --input_grammar=exemple-3.grm --output_far=exemple-3.far Evaluating rule: automate_1 Evaluating rule: automate_2 Evaluating rule: espace Evaluating rule: automate_3 Evaluating rule: automate_3_opt
Le résultat de la compilation est un unique fichier exemple-3.far qui
est une archive (une sorte de .zip) contenant les quatre automates finis
calculés. Si on veut avoir accès individuellement à chacun des quatre
automates, il faut les extraire de l'archive avec la commande:
farextract exemple-3.far
Les quatre fichiers extraits n'ont pas d'extension: ils s'appelent
respectivement automate_1,
automate_2, automate_3 et automate_3_opt. Ce sont des
fichiers openfst binaires (forme compilée).
On peut utiliser les commandes openfst pour étudier ces automates, par exemple:
> fstinfo automate_2 fst type vector arc type standard input symbol table none output symbol table none # of states 7 # of arcs 8 initial state 6 # of final states 3 # of input/output epsilons 4 # of input epsilons 4 # of output epsilons 4 # of accessible states 7 # of coaccessible states 7 # of connected states 7 # of connected components 1 # of strongly conn components 2 input matcher n output matcher n input lookahead n output lookahead n expanded y mutable y error n acceptor y input deterministic y output deterministic y input/output epsilons y input epsilons y output epsilons y input label sorted n output label sorted n weighted n cyclic y cyclic at initial state n top sorted n accessible y coaccessible y string n 6 0 0 6 0 1 120 0 3 0 1 2 122 2 0 0 2 3 4 121 4 5 121 5 0 0 5
OpenGRM utilise par défaut le codage ascii pour les caractères. Si l'on veut afficher les symboles eux-mêmes et non leur code ascii, il faut utiliser le fichier de symboles à télécharger: ascii.syms.
6 0 <epsilon> 6 0 1 x 0 3 <epsilon> 1 2 z 2 0 <epsilon> 2 3 4 y 4 5 y 5 0 <epsilon> 5
On peut également créer la représentation graphique:
fstdraw --portrait --acceptor --isymbols=ascii.syms automate_2 > automate_2.dot dot -Tpng automate_2.dot > automate_2.png display automate_2.png
La commande Optimize utilisée sur la dernière ligne du fichier
exemple-3.grm est une commande qui enchaîne élimination des
epsilon-transitions, déterminisation et minimisation.
Pour afficher le langage d'un automate sous forme d'une suite de chaîne, on
peut utiliser la commande fst_printstrings. Cette commande ne fait pas
partie de la boîte à outils: c'est un programme c++ écrit par le prof pour ce
TP.
La commande fst_printstrings affiche toutes les chaînes du langage d'un
automate si c'est un langage fini. Sinon, cela provoque une erreur, sauf à
donner les options qui permettent de limiter le nombre de chaînes à afficher.
> fst_printstrings --byte --acceptor automate_2 FATAL: The machine is cyclic: automate_2 > fst_printstrings --byte --acceptor --shortest=3 automate_2 yy xz xzxz
L'option --shortest=n permet de sélectionner les n plus courts
chemins. L'option --random=n permet de sélectionner n chemins au
hasard (pas forcément différents).
L'option --byte permet d'afficher les chaînes des machines crées via
opengrm. Pour celles qui sont créés directement par openfst, on peut les
afficher en spécifiant le fichier de symboles: --isymbols=symbols.lab
et en ne mettant pas l'option --byte.
Vous pouvez voir les opérations disponibles pour spécifier les machines finies dans cette page web.