Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Implémentation machine d'états en C
Salut,
Je voudrais faire une FSM (Finite State Machine) en C. Je sais qu'il existe une implémentation basée sur des tables de configurations (états - transitions). J'ai fait quelques recherches sur google mais sans succès. Je suis également intéressé par d'autres implémentations. J'ai réalisé le design pattern STATE du GOF en C au lieu de C++ c'est souple d'emploi mais le code n'est pas très joli.
Qu'avez vous à proposer?
Merci
http://emmanuel-delahaye.developpez.com/clib.htmEnvoyé par funtix
Module FSM
cool merci
D'autres implémentations connues ?
Si ça ne te plait pas, fait le toi même...
Pas de probleme, c'est exactement ce que je demandais. C'est basé sur une table de configuration. Je l'utilise dans mon projet. Mais je suis de nature curieuse et j'avais trouvé le design pattern GOF interessant. Donc, je reste ouvert à d'autres solutions...
Je n'en connais pas de plus rapide et de plus simple à mettre en oeuvre.
Je n'arrive pas a modeliser mon système avec cette machine d'état.
Je ne connais pas la theorie qui tourne autour des FSM mais je sais qu'il y a des limites/contraintes à respecter. Quelles sont-elles?
Il existe des astuces pour contourner ces eventuelles limites ?
Fait péter les specs.on va être hors sujet...
Il existe des astuces pour contourner ces eventuelles limites ?Je ne connais pas la theorie qui tourne autour des FSM mais je sais qu'il y a des limites/contraintes à respecter. Quelles sont-elles?
Le F de FSM est lourd de conséquences...
Tu as lu ça ?
http://emmanuel-delahaye.developpez....um.htm#theorie
Si vous n'avez pas peur de faire une "usine à gaz", il existe la possibilité de modéliser la machien d'état en XMLQu'avez vous à proposer?
http://www.w3.org/TR/2005/WD-scxml-20050705/
Ensuite, il est possible de parser cela en langage C.
Pour être honnête, je ne sais pas ce que cela vaut...
utilisation des poiteurs
Tu peux utiliser les pointeurs pour representer ta machine sous forme de graphe
Oui je l'ai bien lu.
Pour ce qui est de la spec, je prepare ca. Ca viendra demain ou ce week end.
Le probleme est le suivant :
1 état (A) peut amener à 2 etats distincts (B et C) suivant une meme transition. C'est logique que l'automate ne puisse pas déterminer lequel d'état (B ou C) il faut choisir.
Pour determiner si c'est B ou C il faut une memoire, un contexte de ce qui s'est passé avant. Il faudrait empiler les états au fur et a mesure de l'evolution du systeme.
Je parlais de contournement, parce que dans la lib, la fonction FSM_engine peut recevoir un pointeur sur des données user (une pile par exemple mais c'est un peu compliqué, j'ai juste besoin de sauvegarder l'etat n-1) et ces données peuvent être exploiter par la suite.
What the frell is that ? Tu travailles sans specs ? Je rêve ?
Alors ce n'est pas la même transition. Point. Revoir l'étude préalable.Le probleme est le suivant :
1 état (A) peut amener à 2 etats distincts (B et C) suivant une meme transition.
Tu me parles réalisation et bidouille. Ca ne m'intéresse pas. Ce que je veux ce sont les specs. Quel problème as-tu à résoudre ? C'est là dessus qu'il faut travailler. Il ne faut pas commencer à bricoler les états dans les transitions, car on ne s'en sort plus.C'est logique que l'automate ne puisse pas déterminer lequel d'état (B ou C) il faut choisir.
Pour determiner si c'est B ou C il faut une memoire, un contexte de ce qui s'est passé avant. Il faudrait empiler les états au fur et a mesure de l'evolution du systeme.
Je parlais de contournement, parce que dans la lib, la fonction FSM_engine peut recevoir un pointeur sur des données user (une pile par exemple mais c'est un peu compliqué, j'ai juste besoin de sauvegarder l'etat n-1) et ces données peuvent être exploiter par la suite.
Je travaille pas sans specmais je ne peux pas les mettre comme ca sur le net
Et puis hors contexte ca risque d'etre dur a comprendre...
Si je me souviens bien, un automate fini déterministe ne peut, et n'a qu'un seul état à la fois. Un Automate fini non-déterministe peut avoir autant d'états qu'il le veut, donc aucun problème.
FYI: Il est possible de "déterminiser" un automate fini non-déterministe de N états en un automate déterministe d'au maximum 2^N (ou 2^N-1, sais plus) états.
SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.
"Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
Apparently everyone. -- Raymond Chen.
Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.
Effectivement, c'est l'idée que j'ai eu hier soir et que j'ai implémenté ce matin.
Le problème : une meme transition peut amener a 2 etats differents. Ce qui permet de choisir entre l'une et l'autre c'est l'etat n-1.
L'idée donc, c'est d'integrer l'etat n-1 dans le systeme a modeliser. Pour ce faire, j'ai creer des etats supplémentaires.
Ainsi mon systeme initial avait 5 états. Avec la modelisation de ce matin, j'ai 12 états (c-a-d 7 etats supplémentaires).
Ca semble fonctionnait.
Il faut que j'ajoute quelques TU pour etre bien sur.
Par contre je ne sais pas dire si mon systeme initial est déterministe ou non. Je ne vois pas ce qu'il y a de non deterministe pour ne pas avoir reussi a le modeliser la premiere fois. Je pense que le systeme etait simplement mal decrit/specifier.
Si ca interesse du monde je pourrais publier les resultats dans les jours a venir...
Merci de votre aide.
ps : Le site cité au départ (que je m'avait été deja donné suite à une question sur la conception en c) est une tres bonne source d'informations.
Euh...
On va remettre ça à plat pour être sûr qu'on parle de la même chose : C'est pour passer de l'état N-1 à l'état N que tu dis ça ou pour passer de l'état N à l'état N+1 ?
Si c'est le premier cas, c'est une erreur de terme. Une transistion n'est pas le message mais l'ensemble (état, message). Et cela, ça donne bien une flèche bien définie, partant d'un état précis vers seul un autre état précis (Sur un AFD) et sur un message précis. Ça, je suppose que c'est déjà géré par l'implémentation d'Emmanuel, car sinon ce ne serait pas une vraie bibliothèque d'AFD...
Si c'est le second cas, alors tu as mal décomposé ta machine: Tu as regroupé à l'état N deux états différents.
SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.
"Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
Apparently everyone. -- Raymond Chen.
Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.
Illustration du problème (L'etat courant est en gras)
e1 e2
Etat1 ----> Etat2 ----> Etat3
e1 e2
Etat1' ----> Etat2 ----> Etat3'
Dans cette exemple, on voit que l'Etat2 peut mener à 2 états differents avec le même évènement (e2).
Pour que l'automate sache dans quel etat il doit aller (Etat3 ou Etat3') il doit regarder l'etat n-1 c'est a dire regarder si l'on vient de Etat1 ou Etat1'.
Pour résoudre ce problème, j'ai crée des états supplémentaires.
Dans la précédente modélisation, les états étaient : Etat1, Etat1', Etat2, Etat3, Etat3'
Dans la nouvelle modélisation, j'ai les états :
Etat1, Etat1', Etat1_Etat2, Etat1'_Etat2, Etat3, Etat3'
On voit que l'état2 est scindé en 2: Selon la provenance.
J'espère que je me suis fait comprendre.
Je pense oui!Si c'est le second cas, alors tu as mal décomposé ta machine: Tu as regroupé à l'état N deux états différents.
Par contre je ne sais pas dire si mon systeme initial est déterministe ou non. Je ne vois pas ce qu'il y a de non deterministe pour ne pas avoir reussi a le modeliser la premiere fois. Je pense que le systeme etait simplement mal decrit/specifier.
Problème de conception. Soit il manque un état (C'est pas Etat2, mais Etat2'),
soit il manque un évènement (mais ça, c'est généralement du ressort de la spécification et non de la conception).
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6e1 e2 Etat1 ----> Etat2 ----> Etat3 e1 e2 Etat1' ----> Etat2'----> Etat3'
Moi ca me parait tout a fait possible. Un evenement intervenant dans 2 etats differents peut tres bien provoquer le passage a un meme etat.
Mais ce n'est pas le même état, puisque pour passer à l'état N+1, tu dois connaitre ce qu'il y avait à l'état N-1. Cela signifie que l'état N est incomplet, donc une erreur.
SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.
"Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
Apparently everyone. -- Raymond Chen.
Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.
Répondre avec citation
Partager