[C] Automi a stati finiti

[gila75]

OK grazie
Oggi se riesco provo a implementate il compilatore automatico dell`array in
Modo tale che ci disegnano il grafico e non ci dobbiamo preoccupare dei collegamenti

[gila75]

Ecco, pensavo a una cosa così: ci disegnamo carta e penna il grafico, e assegnamo il nome degli eventi, poi tramite input il programma crea l'array,
poi analizza la stringa:

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#define R 50
#define C 50
#define DEBUG 1
//-------------------------------------------------------------

void compila(char table[R][C]);
int isvalue(char* s,char table[R][C]);

void compila(char table[R][C])
{
    int nodi,row,col,event_err,i,nodo,evento;

    printf ("immetti numero nodi (0 to x) ");
    scanf ("%d",&nodi);
    puts("");
    event_err=nodi+1;
    
     //------------------------------------------------------
    // inizializza tutta la tavola a errore
    for (row=0; row<R; row++)
    {
        for (col=0; col<C; col++)
        {
            table[row][col]=event_err;
        }
        
    }
  //------------------------------------------------------
    
    

    for (i=0; i<=nodi; i++)
    {
        while(1)
        {
            printf ("collega nodo [%d] a nodo ? (-1 for exit) ",i);
            scanf  ("%d",&nodo);
            if (nodo==-1)
                break;
            printf ("collega nodo [%d] a nodo--->[%d] tramite evento ? ", i,nodo);
            scanf("%d", &evento);
            table[i][evento]=evento;
           
        }
        puts("");
    }

    #if DEBUG
    // mostra tavola automa
    for (row=0; row<=nodi; row++)
    {
        for (col=0; col<=event_err; col++)
        {
           
            printf ("%d ", table[row][col]);
        }
        puts("");
    }
   #endif 
    
}

int isvalue(char* s,char table[R][C])
{              
                           
    int event;
    int stat = 0;
    int err=0;
    while(*s!='\0')
    {
        
        if      ( *s>='a' && *s<='z')   event = 0;
        else if (*s=='.' || *s=='*')    event = 1;
        else                            event = 2;
        stat = table[stat][event];   
       
        if (stat==2)
        {   
            printf ("errore in pos s[%d] %c\n",err,*s);
            return 0;
        }
        s++;
        ++err;
    }       
    
    return stat==0;
}



//--------------------------------------------------------------------
int  main(void)
{
    char st[128] = "8ncdefghil*a.bgt**aaa";
    char table[R][C];
    compila(table);
    printf("ris= %d\n", isvalue(st,table));
    return 0;
}

input\output:

Codice: Seleziona tutto

immetti numero nodi (0 to x) 1

collega nodo [0] a nodo ? (-1 for exit) 0
collega nodo [0] a nodo--->[0] tramite evento ? 0
collega nodo [0] a nodo ? (-1 for exit) 1
collega nodo [0] a nodo--->[1] tramite evento ? 1
collega nodo [0] a nodo ? (-1 for exit) -1

collega nodo [1] a nodo ? (-1 for exit) 0
collega nodo [1] a nodo--->[0] tramite evento ? 0
collega nodo [1] a nodo ? (-1 for exit) -1

0 1 2 
0 2 2 
errore in pos s[0] 8
ris= 0

la tavola si può visualizzare o meno a seconda si attivi DEBUG.
Per ora ho implementato come test dei rozzi scanf(), ma saranno da sostituire.
Credo sia comodo lasciar "smazzare" al pc il noioso compito di preparare l'array.
Spero non ci siano bug

EDIT: purtroppo ci sono i bug...pazienza con calma sistemo.
Alla fine mi sono però reso conto che è facile sbagliare anche così.
Credevo semplificasse, ma invece...

[gila75]

Ho corretto e risolto il bug.
Mi posso comporre il grafico in modo interattivo senza dover compilare l'array a mano (dove è facile sbagliare)
Prendo come esempio questo:
Questo è il codice:

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define R 50
#define C 50

//-------------------------------------------------------------

void compila(char table[R][C]);
int isvalue(char s[] ,char table[R][C]);
void input (char str[]);


void input (char str[])
{
    int len_str;
    len_str=strlen(str);
    str[len_str-1]='\0';
    
}



void compila(char table[R][C])
{
    int nodi,row,col,event_err,i,nodo,evento,num_eventi;
    char buff[10];

    printf ("immetti numero nodi (0 to x) ");
    fgets(buff,10,stdin);
    input(buff);
    nodi=atoi(buff);
    nodi++;
    puts("");

    printf ("immetti numero eventi (err escluso) " );
    fgets(buff,10,stdin);
    input(buff);
    num_eventi=atoi(buff);
    num_eventi++;
    event_err=nodi;
    
     //------------------------------------------------------
    // inizializza tutta la tavola a errore
    for (row=0; row<=nodi; row++)
    {
        for (col=0; col<num_eventi; col++)
        {
            table[row][col]=event_err;
            printf ("%d ",table[row][col]);
        }
        puts("");
    }
  //------------------------------------------------------
    
    

    for (i=0; i<nodi; i++)
    {
            
        for(;;)
        {
            printf ("collega nodo [%d] a nodo ? (-1 for exit)",i);
            fgets(buff,10,stdin);
            input(buff);
            nodo=atoi(buff);

            if (nodo==-1 )
                break;
            
            printf ("collega nodo [%d] a nodo--->[%d] tramite evento ?", i,nodo);
            fgets(buff,10,stdin);
            input(buff);
            evento=atoi(buff);  
            table[i][evento]=nodo;
                         
        }
        
       printf ("fatti tutti i collegamenti di nodo [%d]\n",i );
       puts("--------------------------------------------------");
    }

    for (row=0; row<=nodi; row++)
    {
        for (col=0; col<num_eventi; col++)
        {
           
            printf ("%d ", table[row][col]);
        }
        puts("");
    }  
}


int isvalue(char* s,char table[R][C])
{
    
    int event;
    int stat = 0;
    while(*s)
    {
        char c = *s++;
        if      (c>='0' && c<='9') event = 0;
        else if (c=='.')           event = 1;
        else if (c=='+' || c=='-') event = 2;
        else if (c=='e' || c=='E') event = 3;
        else                       event = 4;
        stat = table[stat][event];  

        
    }
    return stat==3 || stat==4 || stat==7;
}



//--------------------------------------------------------------------
int  main(void)
{
    char st[128];
    char table[R][C];
    
    compila(table);
    while(1)
    {   printf("input esperssione ");
        fgets(st,128,stdin);
        input(st);
        printf("ris= %d\n", isvalue(st,table));
    }
    return 0;
}

input\output:

Codice: Seleziona tutto

gila@ubuntu:~/Scrivania$ ./xx
immetti numero nodi (0 to x) 7

immetti numero eventi (err escluso) 4
8 8 8 8 8 
8 8 8 8 8 
8 8 8 8 8 
8 8 8 8 8 
8 8 8 8 8 
8 8 8 8 8 
8 8 8 8 8 
8 8 8 8 8 
8 8 8 8 8 
collega nodo [0] a nodo ? (-1 for exit)1
collega nodo [0] a nodo--->[1] tramite evento ?2
collega nodo [0] a nodo ? (-1 for exit)2
collega nodo [0] a nodo--->[2] tramite evento ?1
collega nodo [0] a nodo ? (-1 for exit)3
collega nodo [0] a nodo--->[3] tramite evento ?0
collega nodo [0] a nodo ? (-1 for exit)-1
fatti tutti i collegamenti di nodo [0]
--------------------------------------------------
collega nodo [1] a nodo ? (-1 for exit)2
collega nodo [1] a nodo--->[2] tramite evento ?1
collega nodo [1] a nodo ? (-1 for exit)3
collega nodo [1] a nodo--->[3] tramite evento ?0
collega nodo [1] a nodo ? (-1 for exit)-1
fatti tutti i collegamenti di nodo [1]
--------------------------------------------------
collega nodo [2] a nodo ? (-1 for exit)4
collega nodo [2] a nodo--->[4] tramite evento ?0
collega nodo [2] a nodo ? (-1 for exit)-1
fatti tutti i collegamenti di nodo [2]
--------------------------------------------------
collega nodo [3] a nodo ? (-1 for exit)3
collega nodo [3] a nodo--->[3] tramite evento ?0
collega nodo [3] a nodo ? (-1 for exit)4
collega nodo [3] a nodo--->[4] tramite evento ?1
collega nodo [3] a nodo ? (-1 for exit)5
collega nodo [3] a nodo--->[5] tramite evento ?3
collega nodo [3] a nodo ? (-1 for exit)-1
fatti tutti i collegamenti di nodo [3]
--------------------------------------------------
collega nodo [4] a nodo ? (-1 for exit)4
collega nodo [4] a nodo--->[4] tramite evento ?0
collega nodo [4] a nodo ? (-1 for exit)5
collega nodo [4] a nodo--->[5] tramite evento ?3
collega nodo [4] a nodo ? (-1 for exit)-1
fatti tutti i collegamenti di nodo [4]
--------------------------------------------------
collega nodo [5] a nodo ? (-1 for exit)6
collega nodo [5] a nodo--->[6] tramite evento ?2
collega nodo [5] a nodo ? (-1 for exit)7
collega nodo [5] a nodo--->[7] tramite evento ?0
collega nodo [5] a nodo ? (-1 for exit)-1
fatti tutti i collegamenti di nodo [5]
--------------------------------------------------
collega nodo [6] a nodo ? (-1 for exit)7
collega nodo [6] a nodo--->[7] tramite evento ?0
collega nodo [6] a nodo ? (-1 for exit)-1
fatti tutti i collegamenti di nodo [6]
--------------------------------------------------
collega nodo [7] a nodo ? (-1 for exit)7
collega nodo [7] a nodo--->[7] tramite evento ?0
collega nodo [7] a nodo ? (-1 for exit)-1
fatti tutti i collegamenti di nodo [7]
--------------------------------------------------
3 2 1 8 8 
3 2 8 8 8 
4 8 8 8 8 
3 4 8 5 8 
4 8 8 5 8 
7 8 6 8 8 
7 8 8 8 8 
7 8 8 8 8 
8 8 8 8 8 
input esperssione 12.33
ris= 1
input esperssione 12e12
ris= 1
input esperssione 12E12
ris= 1
input esperssione 12..3
ris= 0
input esperssione .3
ris= 1
input esperssione -.3
ris= 1
input esperssione .-3
ris= 0
input esperssione -.33e12
ris= 1
input esperssione +12.33e2
ris= 1
input esperssione +12-
ris= 0
input esperssione +12.35e
ris= 0
input esperssione 12e
ris= 0
input esperssione 12e2
ris= 1

che ne pensate ?

EDIT: volevo il grafico sopra, ma non so bene come si fa. Posto immagini raramente...pazienza

[gila75]

Nessun parere se può essere utile la compilazione automatica ?

[vbextreme]

@gila ti consiglio di comprare il "little languages", parla proprio di automi e di come costruirli. è ben fatto, non ha molte pagine e tante sono solo di codice.
L'inglese usato è abbastanza semplice, non ci sono molti paroloni tecnici da decifrare, il succo del libro è quello di creare un linguaggio elementare e illustra come farlo sia senza lexer e yacc che con.
Richiede però una buona infarinatura su tutto l'argomento perchè non spreca troppe parole, cosi mi sono ritrovato che dopo 4 giorni sono fermo solo a pagina 116, devo rileggere i capitoli 2/3 volte perchè nonostante le poche parole usate è intriso di significato, fortuna che i ricchi schemi semplificano non poco l'apprendimento.
Lo puoi trovare a circa 20€ usato.
Che dire, meglio di cosi non si può.

[M_A_W_ 1968]

Nessun parere se può essere utile la compilazione automatica ?

Esistono da decenni ambienti sofisticatissimi come Statemate che costano migliaia di dollari e servono esattamente a progettare e simulare FSM di ogni dimensione ed a generare direttamente l'intero codice sorgente corrispondente alla state change table... la generazione automatica non è semplicemente utile, ma indispensabile per evitare ogni sorta di errori, soprattutto quando la FSM in questione non è un balocco.

Tra l'altro ho già indicato in questo stesso thread questo articolo nel quale si descrive quello che è in pratica l'unico (e comunque il migliore) ambiente gratuito usato per la progettazione grafica e la generazione di codice da FSM, con un intero framework di supporto e versioni per i più diffusi RTOS (incluso FreeRTOS, che non è poi così diffuso in realtà, ma tant'è).


Riguardo ai "Little Languages" di Kaplan, purtroppo ci sono libri ignobili, fuorvianti e senza alcun valore che finiscono nelle mani di un numero spropositato di sprovveduti (inutile elencarli ancora), ma al contrario testi come quello sono delle vere e proprie gemme che valgono tanto oro quanto pesano. E ovviamente, se non fosse per persone come il sottoscritto che rubano tempo al riposo e ad altre attività primarie solo per aiutare e indirizzare il prossimo con una profonda conoscenza di quel poco che vale in mezzo al ciarpame editoriale e online, non li studierebbe praticamente nessuno, tranne forse qualche raro studente svogliato obbligato dal professore di turno.

[vbextreme]

@maw il link "framework opensource" non funziona

[M_A_W_ 1968]

@maw il link "framework opensource" non funziona

Ora sì.

[vbextreme]

forse non mi sono spiegato, nel tuo blog il link "framework opensource" e "testo di riferimento" non vanno, Quantum si.

Rettifico, non va nessun link di quel blog

[M_A_W_ 1968]

Rettifico, non va nessun link di quel blog

Link? Quali link?

Dato che questi si divertono a riorganizzare il sito ogni tre per due seguendo le mode del momento, ho eliminato tutti i deep links. Credo che le pagine dei downloads e della documentazione sappiate trovarvele da soli.
Quello che mi interessa è solo farvi capire la superiore qualità del progetto, dei tools e dell'approccio. Rarissimo da trovarsi a costo zero.

[gila75]

@gila ti consiglio di comprare il "little languages", parla proprio di automi e di come costruirli. è ben fatto, non ha molte pagine e tante sono solo di codice.

Mannaggia VB: il tempo...e l'inglese. Ok ce la potrei fare a capire però...sono fermo al pessimo inglese delle superiori.
Qualcosa ho aggiunto spulciando i datasheet ai tempi dei pic e dei componenti elettronici...però.
Che te ne pare il programmino che ho postato?
Sarebbe bello implementare anche gli eventi a input.
Che so a terminale dire (tramite input) event 0=n , evento 1=. ecc...

[vbextreme]

il mio inglese è messo sicuramente peggio.Ma se riesco io allora sono sicuro che riesci pure te!
5 minuti prima di dormire, tanto non abbiamo un termine....

Non ho molto tempo, vorrei provare anche io a creare un "automata" ma ho mille e uno impegni.
Ho anche uno scheduler da finire, una board da sviluppare...ah già! una moglie e un figlio

[gila75]

ah già! una moglie e un figlio

Bhè dai il programma funziona, più che altro mi perdo parecchio a disegnare il grafico.
Ho capito la teoria, ma devo prenderci su bene la mano.
Il grafico disegnato da Claudio...non credo proprio che sarei stato in grado di pensarlo.
a vederlo ora sembra semplice ma...quando lo fanno gli altri tutto è semplice.
Sul libro "algoritimi in C" che ho c'è un sacco di materiale, ma è davvero difficile, in più quasi tutti gli esempi ù
sono con liste concatenate e ricorsione...una seccatura.
MAW dice che l'autore è un mostro sacro, non discuto,ma cavolo capire certe cose alla sera da stanco....mannaggia!!!!

[gila75]

Ai tempi che giocherellavo con i pic, mi sono trovato di fronte il problema della stampa su lcd.
Il problema degli zeri non significativi es:
12 veniva stampato 00000012
Con una serie assurda di if (in asm se non ricordo male erano xor e btfss) testavo il tutto.
La stampa risultava corretta, ma mi rendo conto solo ora che nonostante i mie vecchi progetti funzionassero,
ero ben lontano da quello che viene definito un buon programma.
Non conoscevo\conosco molte cose.
Mi chiedevo se per risolvere questo problema, un automa non si presti per il caso:
12.01 ok
12.00 no=12
012 no=12
e via dicendo.
Purtroppo ho ancora problemi nella stesura dei grafici.
Questo l'ho solo abbozzato.
Visto che è giusto ragionare con le proprie forze, ma non è bello perdere troppo tempo, impuntandosi,
chiedo se qualcuno ha voglia di darmi una dritta.
Testerei ogni singolo passaggio dell'automa, e se da esito positivo copio in un secondo array, altrimenti salto.
Alla fine ci metto il '\0'
es:
00012.000
dovrà diventare 12
Credo che sia più difficile eliminare gli zeri non significativi dopo il decimale che non quelli prima.
I primi basta dire: entra uno 0, mi aspetto solo un punto . Se arriva il punto lo zero è ok, se entra la cifra, salta lo
zero nella copia del secondo array.
Nel caso dopo i decimali però la faccenda si complica:
12.003
come faccio a sapere se stampare i 2 zeri se non ho ancora incontrato l'ultima cifra?
Non so ancora molto (in verità niente) degli automi...quindi chiedo.
E dovrei leggere testi...ok l'impegno e magari un po' d'intuito...ma è un po' dura risolvere da solo cose
sviluppate in decenni

[Claudio_F]

12.003
come faccio a sapere se stampare i 2 zeri se non ho ancora incontrato l'ultima cifra?

Credo che un semplice automa riconoscitore non sia più sufficiente, occorre come minimo un automa traduttore: gli eventi non producono solo un cambio di stato ma anche un valore di uscita. Ad esempio il seguente automa trasforma gli 0 in 1 e viceversa, e va in errore per qualsiasi cosa non sia 0 o 1 (in quel caso continua a fornire E). I simboli neri sono l'evento in ingresso e quelli rossi sono l'uscita prodotta.



Il valore di uscita potrebbe essere qualcosa di più complesso di un semplice carattere, magari una stringa completa costruita in un buffer interno che esce solo in una certa condizione.

L'interpretazione delle cifre dopo il punto mi sembra debba richiedere per forza un buffer e delle ulteriori "azioni" da compiere... mi è venuto fuori questo anche se mi sembra un po' complesso per il compito da svolgere. L'automa ad ogni simbolo in ingresso fornito con 't_push' scrive nel suo buffer interno i simboli rossi. Alla fine va chiamata la funzione 't_done' con cui l'automa completa eventuali "pendenze" e il risultato si trova nel suo buffer interno. La struct contiene i dati di lavoro dell'automa. Le funzioni 't_reset' 't_push' 't_done' sono "i comandi" che si possono dare all'automa (in un linguaggio OOP sarebbero i metodi di un oggetto automa). Lo stato 6 è quello di errore.

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//--------------------------------------------------------------------

typedef struct { char buffer[256]; int i; int stat; } t_data;

void t_reset(t_data* this) { this->i = 0; this->stat = 0; }

void t_add(t_data* this, char c) { this->buffer[this->i++] = c; }


void t_push(t_data* this, char c) {
    int number = c >= '1' && c <= '9';
    int zero   = c == '0';
    int point  = c == '.';
    switch (this->stat) {
        case 0:
            if (zero)            this->stat = 1;
            else if (number)    {t_add(this, c); this->stat = 2;}
            else if (point)      this->stat = 5;
            else                 this->stat = 6;
            break;
        case 1:
            if (zero)            ;
            else if (number)    {t_add(this, c); this->stat = 2;}
            else if (point)     {t_add(this, '0');
                                 t_add(this, '.'); this->stat = 3;}
            else                 this->stat = 6;
            break;
        case 2:
            if (zero || number)  t_add(this, c);
            else if (point)     {t_add(this, c); this->stat = 3;}
            else                 this->stat = 6;
            break;
        case 3:
            if (zero)            t_add(this, c);
            else if (number)    {t_add(this, c); this->stat = 4;}
            else                 this->stat = 6;
            break;
        case 4:
            if (zero)           {t_add(this, c); this->stat = 3;}
            else if (number)     t_add(this, c);
            else                 this->stat = 6;
            break;
        case 5:
            if (zero)           {t_add(this, '0'); t_add(this, '.'); 
                                 t_add(this, c);  this->stat = 3;}
            else if (number)    {t_add(this, '0'); t_add(this, '.'); 
                                 t_add(this, c);  this->stat = 4;}
            else                 this->stat = 6;
            break;
    }
}


void t_done(t_data* this) {
    switch (this->stat) {
        case 0:
            t_add(this, '0');
            t_add(this, '\0');
            break;
        case 1:
            t_add(this, '0');
            t_add(this, '\0');
            break;
        case 2:
            t_add(this, '\0');
            break;
        case 3:
            while (this->i--){
                if (this->buffer[this->i] == '.')  break;
                if (this->buffer[this->i] != '0') {this->i++; break;}
            }
            t_add(this, '\0');
            break;
        case 4:
            t_add(this, '\0');
            break;
        case 5:
            strcpy(this->buffer, "ERROR");
            break;
        case 6:
            strcpy(this->buffer, "ERROR");
    }
}

//--------------------------------------------------------------------

void main(void) {
    // init dati
    t_data tr;
    t_reset(&tr);

    // fornisco un carattere alla volta
    char* st = "0000000012.010000000";
    int i;
    for (i=0; i<strlen(st); i++)
        t_push(&tr, st[i]);

    // fine lavoro
    t_done(&tr);

    // stampo risultato
    printf("%s\n", tr.buffer);
    printf("Stato finale: %d\n\n", tr.stat);
}

PS: meglio non quotare tutto il codice o i disegni, così se mi accorgo di errori li posso correggere.

[gila75]

Grazie Claudio, devo leggere,leggere, capire e poi ancora riflettere. Non è per nulla semplice

[gila75]

Per ora voglio provare solo la parte iniziale:00012=12
00.12=0.12
Con un automa.
Riflettendo,la parte dopo(12.000=12),la si può fare benissimo con un if e un cast:
If
Float(x)-int(x)==0
Stampa un int
Giusto?

[gila75]

Non avevo visto il grafico!!!!!
Io solo per i decimali dopo lo zero ,stavo risolvendo così:

Ma è solo una prova sommaria. per ora accetta solo lo 0 prima del punto...ripeto è una prova. Però funziona.
Ecco l'output:

Codice: Seleziona tutto

input esperssione 0.33
ris= 1
input esperssione 0.3000
ris= 0
input esperssione 0.301
ris= 0
input esperssione 0.003
ris= 1
input esperssione 0.000
ris= 0
input esperssione 0.250
ris= 0
input esperssione 0.00012
ris= 1
input esperssione 0.120
ris= 0

Grazie ancora del programma e del codice...ci studio sopra.
Intanto mi dici se è valida come idea la mia?
Al limite posto il programma con la tabella...così compili e basta.
è semplice ma credo possa essere un'idea: dopo il punto con lo stato 2 creo un loop infinito per lo zero: si può uscire solo
se si passa in 3 (1-9)
Non so se così facendo e mettendo tutto il resto ho problemi, magari "vado in un vicolo cieco" non so.
tempo permettendo lo amplio, anche se sicuramente il tuo sarà migliore.
Su queste cose logiche ho notato già da molto che sei davvero tosto...complimenti!
La tabella comunque risulta così:

Codice: Seleziona tutto

1 4 4 4 
4 2 4 4 
2 4 3 4 
4 4 3 4 
4 4 4 4 

[gila75]

@claudio... mi manca poco per finire la mia versione.
C'è da correggere nel punto 4 perchè stampa 0000.3
e non dovrebbe, il resto ho un output corretto:
012 no
12.3 si
13.00001 si
13.00000 no
Ecco il grafico (scusami fa schifo, non sono tanto pratico...e la mia compagna mi tallona!!! )

Edit: il punto 1 si chiude in se stsso con l'evento 1-9 mi sono dimenticato. E il punto 4 per errore ci sono 2 archi.
Che ne pensi?
Edit: ho cantato vittoria troppo in fretta alcuni bug...
va bhè...leggerò con cura il tuo grafico

[ubuntumate]

Materiale sugli automi a stati finiti? Intendo libri,non dispensine ridicole. Se ne avete da consigliare fatemi sapere e vi sarò mooolto grato