Comment valider des données complexes?
Les automates à états finis sont un moyen classique et très élégant
pour résoudre un grand nombre de problèmes, notamment pour écrire des
parseurs ou des validateurs de toutes sortes. Ils sont particulièrement
adaptés à la validation de données complexes, à la vérification de formats,
à la vérification de syntaxe, etc.
Comment ça marche?
Les automates sont basés sur 2 concepts : les états et les transitions.
Un automate admet un état initial et un ou des états finaux, plus des
états intermédiaires. Une transition est simplement une condition
permettant de passer d'un état à un autre.
Voici la description d'un automate (simple) permettant de valider qu'une
chaîne de caractères est un nombre, en écriture décimale. On pourrait aisément
l'étendre pour valider aussi une écriture au format scientifique, en hexadécimal, etc.
- l'expression peut commencer par un chiffre, le signe moins, le signe plus ou un point
- si l'expression commence par un signe moins ou un signe plus, le prochain caractère doit être un point ou un chiffre
- si l'expression commence par un point, le caractère suivant doit être un chiffre
- si l'expression commence par un chiffre, le caractère suivant doit être un chiffre ou un point
- après un point, il faut au moins un chiffre, et plus jamais de points
- après un chiffre, on peut trouver un autre chiffre ou un point, pour autant que ce soit le premier point rencontré.
Voici un petit diagramme de l'automate correspondant :
Les états sont représentés par des numéros : 0, 1, 2, 3, 4, 5
Les transitions sont les flèches qui partent des états. La condition de
transition est indiquée au dessus ou à coté de la flèche.
Sur ce graphe, l'état initial est l'état 0 (zéro).
Les états terminaux sont les états 1 et 4. L'état 5 est particulier,
c'est un état qui n'a pas de transition sortante. Il est terminal de
fait, mais invalide.
L'automate lit donc la chaîne caractère par caractère, et selon l'état dans
lequel on se trouve, on regarde les transitions possibles. Si on trouve
une transition possible, on passe dans l'état correspondant.
Quand il n'y a plus de caractères, il suffit de regarder dans quel état
de l'automate on se trouve. Si on est dans un état final et valide (1 ou
4 dans cet exemple), alors la réponse pour le problème est "VRAI", sinon
la réponse est "FAUX".
Maintenant, le plus sympathique : une fois que la modélisation est faite, le
codage est trivial et carrément mécanique; on peut même écrire
des générateurs de code qui en partant d'une description d'un automate
génèrent le code correspondant, en n'importe quel langage.
L'écriture d'un tel générateur n'est pas très compliquée mais déborde le cadre
de cet article.
Voici pour finir une implémentation de cet automate en VB. L'automate est dans la fonction principale (MyIsNumeric),
les autres fonctions étant les fonctions de transitions.
Option Explicit
Function MyIsNumeric(s As String) As Boolean
Dim etat As Integer
Dim car As String
Dim l As Long
Dim i As Long
Dim validStates As String
validStates = "1,4,"
l = Len(s) ' longueur de la chaine d'entrée
If l > 0 Then ' si chaine pas vide
For i = 1 To l ' puis on avance caractere par caractere
car = Mid$(s, i, 1)
Select Case etat ' et on suit l'automate
Case 0
If IsDigit(car) Then
etat = 1
ElseIf IsMinusSign(car) Then
etat = 2
ElseIf IsPlusSign(car) Then
etat = 2
ElseIf IsDot(car) Then
etat = 3
Else
etat = 5 ' fini
End If
Case 1
If IsDigit(car) Then
etat = 1
ElseIf IsDot(car) Then
etat = 3
Else
etat = 5 ' fini
End If
Case 2
If IsDigit(car) Then
etat = 1
ElseIf IsDot(car) Then
etat = 3
End If
Case 3
If IsDigit(car) Then
etat = 4
End If
Case 4
If IsDigit(car) Then
etat = 4
Else
etat = 5 ' fini
End If
Case 5
' etat invalide, pas de transitions
' on peut quitter ici si on veut
End Select
Next i
End If
If InStr(validStates, Trim$(Str$(etat)) & ",") > 0 Then
MyIsNumeric = True
Else
MyIsNumeric = False
End If
End Function
Private Function IsDigit(car As String) As Boolean
If car >= "0" And car <= "9" Then
IsDigit = True
End If
End Function
Private Function IsMinusSign(car As String) As Boolean
If car = "-" Then
IsMinusSign = True
End If
End Function
Private Function IsPlusSign(car As String) As Boolean
If car = "+" Then
IsPlusSign = True
End If
End Function
Private Function IsDot(car As String) As Boolean
If car = "." Then
IsDot = True
End If
End Function
Voir aussi : |
Top