L'automa in questione, appartenente ad una categoria più ampia di FSM, ed avente la sola funzione di riconoscitore, è implementabile tramite una semplice tabella delle transizioni perché:
1) Non compie operazioni negli stati o nelle transizioni (la sola cosa che fa è cambiare stato in risposta ad un evento).
2) L'uscita è data direttamente dallo stato (macchina di Moore)
La tabella delle transizioni comunque non è facilmente leggibile (cioè senza il diagramma non ci si capisce nulla).
La prima cosa da fare è stata associare un simbolo/evento ad un numero da usare come indice di colonna:
Codice: Seleziona tutto
cifre -> 0
punto -> 1
segno -> 2
esponenziale -> 3
altri simboli -> 4
La seconda scrivere un array per ogni stato seguendo il diagramma:
Nello stato iniziale 0 devo transitare al 3 se arriva un numero (evento 0), al 2 se arriva un punto (evento 1), all' 1 se arriva un segno (evento 2), e all'8 (errore) in tutti gli altri casi. In pratica lo stato iniziale "riconosce" che l'inizio corretto di un "valore" può essere solo un segno, una cifra o un punto.
Al giro successivo il nuovo stato fa la stessa cosa. Supponiamo di aver rilevato un segno, siamo quindi nello stato 1, dobbiamo di nuovo decidere quale sarà il prossimo stato per ogni evento, se arriva un numero (evento 0) passiamo in 3, se arriva un punto (evento 1) passiamo in 2, qualsiasi altra cosa è un errore. Lo stato 1 "riconosce" che dopo il segno iniziale può esserci solo una cifra o un punto. Stesso discorso per tutti gli altri stati. Lo stato di errore 8 transita sempre a se stesso per qualsiasi evento, una volta che è stato rilevato un errore qualsiasi altro simbolo non è più importante.
Una stringa è riconosciuta valida se l'automa di ferma negli stati 3 4 o 7, che "leggono" rispettivamente le cifre prima del punto (come in -15), dopo il punto (come in 3.14 o .16) e quelle della parte esponenziale (come in 2E-127), se si ferma in qualche posizione intermedia significa che il valore non è scritto completamente (come 12E o +.), se invece è in errore significa che:
1) è arrivato un simbolo non permesso (16f4 +8.9L4)
2) è arrivato un simbolo permesso ma non nel momento giusto (ad esempio 12.4. ++6 ..)
Una forma più leggibile di automa (che potrebbe anche effettuare operazioni) è invece implementabile tramite uno switch, dove i vari case gestiscono gli stati all'interno dei quali si possono riconoscere gli "eventi" tramite if. Ad esempio l'automa in questione si poteva scrivere nella seguente forma estesa e funzionava nello stesso modo:
Codice: Seleziona tutto
int stat = 0;
while(*s) {
char c = *s++;
switch (stat) {
case 0: // attesa primo carattere
if (c>='0' && c<='9') stat = 3;
else if (c=='.') stat = 2;
else if (c=='+' || c=='-') stat = 1;
else stat = 8;
break;
case 1: // trovato segno iniziale
if (c>='0' && c<='9') stat = 3;
else if (c=='.') stat = 2;
else stat = 8;
break;
ecc ecc ecc
case 8: // errore
break;
}
}
Realizzare un automa con liste collegate? Si, è possibile, più che altro sarebbero nodi interconnessi l'uno all'altro con diversi puntatori ciascuno, basta che vi sia sempre la possibilità di stati e transizioni, e di un percorso sensato tra gli stati realizzato seguendo i puntatori. Probabilmente però si avrebbe solo un aggravio sintattico e nessun beneficio.
In linguaggi ad oggetti come Python un automa si può implementare anche tramite state pattern, in assembly tramite computed goto, ma il principio rimane sempre quello della logica scomposta in tanti piccoli pezzetti (stati) che rappresentano la conoscenza dell'automa in un certo momento, degli eventi che causano le transizioni, e della chiamata ciclica, che nel caso in questione è banalmente il while che itera sulla stringa, ma in un sistema di controllo potrebbe essere il mainloop del programma (in questo ultimo caso si possono eseguire innumerevoli automi contemporaneamente in multitasking cooperativo, soluzione che ho dovuto applicare in tutti i programmi per micro di una qualche utilità pratica (
come l'orologio DCF77 fondo pagina).
