Question 133

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é.

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 :

• Comment déterminer si ma chaine de caractères est un nombre ?
• Comment créer une TextBox numérique ?