Un exemple Lextools pas à pas

Lextools permet de compiler une expression régulière en un automate FSM. Il faut commencer par décrire le vocabulaire (les lettres du vocabulaire) dans un format différent de FSM. Il y a une notion de classes de symboles. Sur chaque ligne du fichier, on déclare une classe (avec son nom), suivie des symboles qu'elle contient. Les mêmes symboles peuvent apparaître dans plusieurs classes.

Exemple: fichier lexsym.sym:

lettres a b c d e f g h i j k
voyelles a e i
consonnes b c d f g h j k

On compile ce fichier avec la commande suivante:

> lexmakelab lexsym

Cela crée deux fichiers: lexsym.lab et lexsym.scl. Le premier est un fichier de symboles au format FSM:

> cat lexsym.lab
<epsilon>       0
a       1
b       2
c       3
d       4
e       5
f       6
g       7
h       8
i       9
j       10
k       11

Le second décrit les classes de symboles:

> cat lexsym.scl
consonnes       2
consonnes       3
consonnes       4
consonnes       6
consonnes       7
consonnes       8
consonnes       10
consonnes       11
voyelles        1
voyelles        5
voyelles        9
<sigma> 1
<sigma> 2
<sigma> 3
<sigma> 4
<sigma> 5
<sigma> 6
<sigma> 7
<sigma> 8
<sigma> 9
<sigma> 10
<sigma> 11
lettres 1
lettres 2
lettres 3
lettres 4
lettres 5
lettres 6
lettres 7
lettres 8
lettres 9
lettres 10
lettres 11

On peut ensuite compiler des expressions régulières:

> lexcompre -l lexsym.lab -S lexsym.scl -s '(a*|b*)' > exp1.fsm
> fsmdraw -i lexsym.lab exp1.fsm | dot -Tgif > exp1.gif

On peut également compiler une expression régulière ou l'union des expressions régulières contenues dans un fichier. Et l'on peut utiliser les classes pour écrire plus facilement les expressions.

Exemple: exp2.lex:

([voyelles]^3)gh?jee([consonnes]+)

Compilation:

> lexcomplex -l lexsym.lab -S lexsym.scl exp2.lex > exp2.fsm
> fsmdraw -i lexsym.lab exp2.fsm | dot -Tgif > exp2.gif

A noter: les exemples que nous avons vus sont relativement petits, mais il est parfaitement possible d'utiliser FSM et Lextools pour de gros automates (plusieurs centaines de milliers d'états). Pour de gros automates, l'affichage graphique n'a aucun intérêt et certaines opérations (intersection, déterminisation, minimisation) peuvent être longues.