State Machine in Ansi C

[Progger (Gast)]

Hi,

ich möchte für ein Softwareprojekt eine State Machine in Ansi C 
programmieren. Wie realisiert man dies in der Programmiersprache Ansi C?
Ich suche dazu ein kleines anschauliches Beispiel. Kann mir jemand sagen 
wo ich dazu Unterlagen im Netz finden kann?

[StinkyWinky (Gast)]

Hier in den Foren gibt es etliche Beiträge.
Im Web kenne ich den:
http://www.embedded.com/columns/technicalinsights/10700829?_requestid=42049

[Progger (Gast)]

Danke für den Link. Hast du eine deutsche Quelle dazu?

[Andreas W. (Gast)]

Vieleicht hilft das ja.
Beitrag "Statemachine, Funktionszeiger oder Variable"

[Progger (Gast)]

Hmmm... aus diesem Beitrag kann ich nichts entnehmen, was ich für mich 
brauchen könnte. Hier wird der Funktionszeiger erwähnt. Kann mir 
trotzdem nicht vorstellen wie das funktionieren soll. Hat dazu jemand 
ein kleines Beispiel mit Funktionszeiger?

[Karl H. (kbuchegg)]

Progger schrieb:
> Hmmm... aus diesem Beitrag kann ich nichts entnehmen, was ich für mich
> brauchen könnte. Hier wird der Funktionszeiger erwähnt. Kann mir
> trotzdem nicht vorstellen wie das funktionieren soll. Hat dazu jemand
> ein kleines Beispiel mit Funktionszeiger?

Für deine erste Statemachine würde ich dir keine Funktionszeiger 
empfehlen, solange du noch danach fragen musst. Du hast sonst zuviele 
Baustellen.

Nimm die klassische Form:

* Es gibt States
* Jeder State hat eine Nummer (die sofort mit einem #define einen
  symbolischen Namen bekommt)
* Der momentan aktive State ist in einer (globalen) Variablen
  gespeichert
* Wird aufgrund irgendwelcher Bedingungen der State gewechselt, dann
  ist das einfach eine Zuweisung an diese Variable
* Die Statemachine wird periodisch aufgerufen und macht ihr Ding
  je nachdem in welchem State (=Zustand) sie ist
* Die eigentliche Statemaschine ist ein

    switch( state ) {

      case ZUSTAND_1:
         // mach irgendwas
         break;

      case ZUSTAND_2:
         // mach was anderes
         break;

      case ZUSTAND_3:
         // und jetzt ganz was anderes

         // der nächste Zustand ist ZUSTAND_2
         state = ZUSTAND_2;
         break;

      case ZUSTAND_4:
         // je nachdem
         if( .... )
           state = ZUSTAND_1;
         else
           state = ZUSTAND_2;
         brea;

       ....

       default:
         // ungültiger Zustand!
         // Sollte eigentlich nie auftreten
    }

Deine erste Statemachine wird noch nicht allzuviele Zustände haben, 
sodass das organisatorisch noch gut zu handhaben ist.
Die Hauptarbeit beim Bau einer Statemachine ist ja auch nicht die 
Programmierung, sondern das Identifizieren welche States es geben soll 
und wie und warum die Statemachine von einem Zustand in einen anderen 
Zustand überwechselt und welche Aktionen dabei ausgeführt werden sollen.

[Klaus W. (mfgkw)]

zu Funktionszeigern:
das nächste C-Buch?

[Klaus W. (mfgkw)]

Der Vollständigkeit halber eine Endlosschleife mit Funktionszeigern:

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



typedef enum
{
  eMotivation_heiss,
  eMotivation_gehtso,
  eMotivation_lau,
  eMotivation_unterirdisch,
  eMotivation_LAST
} eMotivation_t;


// manuelle Variante:

void automat_manuell()
{
  // Zustandsvariable:
  eMotivation_t    MotivationDesFragestellersAnhandSeinerFrage = eMotivation_gehtso;

  while( 69>42 )
  {
    switch( MotivationDesFragestellersAnhandSeinerFrage )
    {
      case eMotivation_heiss:
        printf( "machEineTolleAntwort...\n" );
        break;

      case eMotivation_gehtso:
        printf( "machEineSchnelleAntwort\n" );
        break;

      case eMotivation_lau:
        printf( "machEinePampigeAntwort\n" );
        break;

      case eMotivation_unterirdisch:
        printf( "gehe Bier holen\n" );
        break;

      default :
        fprintf( stderr, "oioioi, das geht ja gar nicht\n" );
        abort();
        break;
    }
  }
}


// Variante mit Sprungtabellen (Funktionszeiger):

// zuerst die Reaktion auf die je einen Zustand jeweils als eine Funktion:
void machEineTolleAntwort()
{
  printf( "machEineTolleAntwort...\n" );
}

void machEineSchnelleAntwort()
{
  printf( "machEineSchnelleAntwort\n" );
}

void machEinePampigeAntwort()
{
  printf( "machEinePampigeAntwort\n" );
}

void saufDirEinenAn()
{
  printf( "gehe Bier holen\n" );
}


void automat_ganztoll()
{
  // Tabelle mit Zeigern auf Funktionen, die jeweils etwas tun:
  void  (*sprungtabelle[eMotivation_LAST])(void) =
    {
      [eMotivation_heiss] = machEineTolleAntwort,
      [eMotivation_gehtso] = machEineSchnelleAntwort,
      [eMotivation_lau] = machEinePampigeAntwort,
      [eMotivation_unterirdisch] = saufDirEinenAn,
    };

  // Zustandsvariable:
  eMotivation_t    MotivationDesFragestellersAnhandSeinerFrage = eMotivation_gehtso;

  while( "Merkel ist doof" )
  {
    if( MotivationDesFragestellersAnhandSeinerFrage<eMotivation_LAST )
    {
      // je nach Zustand die richtige Funktion aufrufen:
      sprungtabelle[MotivationDesFragestellersAnhandSeinerFrage]();
    }
    else
    {
      // sollte nie vorkommen:
      fprintf( stderr, "oioioi, das geht ja gar nicht\n" );
      abort();
    }
  }

}


int main()
{
  automat_manuell();
  //automat_ganztoll();
  return 0;
}

[Karl H. (kbuchegg)]

LOL

  while( "Merkel ist doof" )

You made my day!

[Andreas W. (Gast)]

Hast du dir mal Wikipedia durchgelesen?
http://de.wikipedia.org/wiki/Endlicher_Automat

ist ganz gut beschrieben.

Ganz einfach ist das Beispiel mit der Tür.
Nach tür-öffnen kommt tür-schließen.
tür-schließen bei Tür-zu ist ja irgendwie sinnlos.

[G. O. (aminox86)]

Hier noch eine weitere Methode einer (stark 
vereinfachten)tabellengesteuerten Zustandsmaschine. Die Grundidee stammt 
aus einem Artikel, der ca 1990 im C-Users Journal veröffentlicht wurde.
Das Bemerkenswerte hier ist, dass die Wahrheitstabelle, wie man sie etwa 
auf dem Papier erstellen und optimieren würde, direkt die Maschinentafel 
übernommen wird.
Auf des Grund des strukturierten Datentyps sind beliebige Erweiterungen, 
Verschachtelungen, Abwandlungen usw. der Zustandsmaschine möglich.

Im vorliegenden Programm wird Tastenfolge 'quertz' oder 'querty' 
abgefragt.

#include <stdio.h>
#include <conio.h>

#define FALSE   0
#define TRUE    1
#define TASTE  unsigned char

typedef struct { int okzustand,                    /*nächster gut-zustand*/
                     nokzustand;                   /*nächster schlecht-zustand*/
                void (*okfun)(TASTE t),            /*gut-funktion*/
                     (*nokfun)(TASTE t);           /*fehler-funktion*/
                int (*test_fun)(TASTE t, char c);  /*test-funktion*/
                char test;}FSM;                    /*testwert*/

int compare(TASTE t, char c);
void print_ok(TASTE t), print_nok(TASTE t);
void print_d(TASTE t), print_e(TASTE t);

FSM maschine[]={
/*0*/  {1, 0, print_ok, print_nok, compare, 'q'},
/*1*/  {2, 1, print_ok, print_nok, compare, 'u'},
/*2*/  {3, 2, print_ok, print_nok, compare, 'e'},
/*3*/  {4, 3, print_ok, print_nok, compare, 'r'},
/*4*/  {5, 4, print_ok, print_nok, compare, 't'},
/*5*/  {0, 6, print_d, print_nok, compare, 'z'},
/*6*/  {0, 6, print_e, print_nok, compare, 'y'},};

TASTE get_taste(void);

void main(void)
{  int zustand=0;
  TASTE key;

  clrscr();
  puts("programm mit taste 'x' beenden");
  do
  {  key=get_taste();
    if((*maschine[zustand].test_fun)(key, maschine[zustand].test))
    {   (*maschine[zustand].okfun)(key);
      zustand=maschine[zustand].okzustand;}
    else
    {   (*maschine[zustand].nokfun)(key);
      zustand=maschine[zustand].nokzustand;}}
  while(key!='x');
}

int compare(TASTE t, char test )
{
  return(t==test?TRUE:FALSE);
}

void print_ok(TASTE key)
{
  printf("'%c' %s", key, "erwartete taste betätigt\n");
}

void print_nok(TASTE key)
{
  printf("'%c' %s", key, "diese taste wurde nicht gesucht\n");
}

void print_d(TASTE key)
{
  printf("'%c' %s", key, "deutsche tastenfolge\n");
}

void print_e(TASTE key)
{
  printf("'%c' %s", key, "englische tastenfolge\n");
}

TASTE get_taste(void)
{  TASTE key;

  while(!kbhit());
  return(key=getch());
}

mfg

[Progger (Gast)]

Ich hab nun mal den Code vom obigen Beitrag "Datum: 25.06.2009 15:14 " 
in ein neus Visual Studio 6.0 C++ Projekt eingefügt. Der Compiler spuckt 
mir immer folgende Fehlermeldungen aus:
--------------------Konfiguration: FSM - Win32 Debug--------------------
Kompilierung läuft...
fsm.cpp
Linker-Vorgang läuft...
fsm.obj : error LNK2001: Nichtaufgeloestes externes Symbol "void __cdecl 
print_e(unsigned char)" (?print_e@@YAXE@Z)
fsm.obj : error LNK2001: Nichtaufgeloestes externes Symbol "void __cdecl 
print_d(unsigned char)" (?print_d@@YAXE@Z)
fsm.obj : error LNK2001: Nichtaufgeloestes externes Symbol "int __cdecl 
compare(unsigned char,char)" (?compare@@YAHED@Z)
fsm.obj : error LNK2001: Nichtaufgeloestes externes Symbol "void __cdecl 
print_nok(unsigned char)" (?print_nok@@YAXE@Z)
fsm.obj : error LNK2001: Nichtaufgeloestes externes Symbol "void __cdecl 
print_ok(unsigned char)" (?print_ok@@YAXE@Z)
Debug/FSM.exe : fatal error LNK1120: 5 unaufgeloeste externe Verweise

Hier ist mein C-Code:

#include "fsm.h"
#include <stdio.h>
#include <conio.h>
#include <windows.h>

#define FALSE   0
#define TRUE    1
#define TASTE  unsigned char


typedef struct 
{ 
int okzustand;        /*nächster gut-zustand*/
int nokzustand;        /*nächster schlecht-zustand*/
void (*okfun)(TASTE t);      /*gut-funktion*/
void (*nokfun)(TASTE t);    /*fehler-funktion*/
int (*test_fun)(TASTE t, char c);  /*test-funktion*/
char test;
}FSM;          /*testwert*/


int compare(TASTE t, char c);
void print_ok(TASTE t), print_nok(TASTE t);
void print_d(TASTE t), print_e(TASTE t);

FSM maschine[]={
/*0*/  {1, 0, print_ok, print_nok, compare, 'q'},
/*1*/  {2, 1, print_ok, print_nok, compare, 'u'},
/*2*/  {3, 2, print_ok, print_nok, compare, 'e'},
/*3*/  {4, 3, print_ok, print_nok, compare, 'r'},
/*4*/  {5, 4, print_ok, print_nok, compare, 't'},
/*5*/  {0, 6, print_d, print_nok, compare, 'z'},
/*6*/  {0, 6, print_e, print_nok, compare, 'y'}};


TASTE get_taste(void);


int main(void)
{


  return 0;
}

[Progger (Gast)]

Für den Einstieg bräuchte ich ein lauffähiges Beispielprogramm in AnsiC.
Kennt jemand da eine gute Quelle?

[Daniel (root) (Gast)]

Für den Einstieg wurden genüg Beispiele gezeigt.
Du brauchst keinen Quellcode zum Copy/Reinpasten ;)
Abtippen ist angesagt. Glaub mir :)

Was FSM angeht, so gibt es viele Möglichkeiten denkbar.

a) Eine uC timer interrupt routine, die regelmässig aufwacht,
ihre inputs (Pins zB) checkt, dann neuen Zustand berechnet und
neue Ausgaben (Pins zB beschreibt). => Input kommt aus Jetzt!
=> reaktives System

b) Compiler kann als FSM betrachtet werden. Tokens, also Input,
wird Zeichen oder Tokenweise aus einer bereits stehenden Quelle(Datei)
geholt. => Input kommt Stückweise, aber an sich aus einem Guss.

c) wenn Software auf mehrere Threads verteilt ist, so ist die
Situation ähnlich Punkt a). Inputs stammen aber aus anderen Thread.
Der Thread mit FSM kann zb blockierd warten. => siehe zB Kernel.

Falls jemand noch etwas einfällt bitte eintragen.
Ich denke das meiste ist damit erschlagen ;)

[G. O. (aminox86)]

@progger,
der Linker beschwert sich, weil er einige Objekte in deinem
(Programm)-Fragment nicht finden kann. Kann ich ihm nachfühlen, denn der 
Quelltext, so wie in deinem Beitrag abgebildet, ist nicht vollständig 
übernommen bzw verstümmelt.
Bitte daran denken, dass das Beispiel unter Windows als 
'Konsole-Anwendung'(Dos läßt grüßen) laufen sollte.
mfg

[Klaus W. (mfgkw)]

Was soll man da noch machen?

Das obige Beispiel von G.O.
(Beitrag "Re: State Machine in Ansi C")
IST lauffähig unter VC++ 6.0 (zumindest wenn man den Aufruf von
clrscr() entfernt, ein echter "Progger" schafft das, und sogar
ich als Maschinenbauer habe es hinbekommen).
Auch wenn man es genau so nicht übersetzt bekommt, könnte man
mit etwas gutem Willen daran sehen, wie ein Automat funktionieren
kann - deiner wird sowieso etwas anderes machen müssen als Tasten
abzufragen.


Progger schrieb:
> Für den Einstieg bräuchte ich ein lauffähiges Beispielprogramm in AnsiC.

ANSI-C und Visual C++ 6.0 sind zwei verschiedene Dinge.
Das obige Beispiel ist wie gesagt lauffähig (vom clrscr() abgesehen).
Wenn du es nicht schaffst, das zu übernehmen, ohne es zu verhunzen,
kann ich dir ein günstiges Angebot machen, vor Ort den Quelltext
in deinen Editor zu kopieren. Spesen gehen extra.

> Kennt jemand da eine gute Quelle?

Ja.

BTW:
Wofür steht eigentlich der schöne Name "Progger"?

[Karl H. (kbuchegg)]

Progger schrieb:
> Ich hab nun mal den Code vom obigen Beitrag "Datum: 25.06.2009 15:14 "
> in ein neus Visual Studio 6.0 C++ Projekt eingefügt. Der Compiler spuckt
> mir immer folgende Fehlermeldungen aus:

Die sollte mann dann auch lesen und wenigstens versuchen zu verstehen. 
So schwer ist das nicht.
Der Linker (nicht der Compiler) beschwert sich, dass er print_e nicht 
finden kann. Also vergleichst du einfach mal wo in deinem Programm 
print_e vorkommt und wo in deiner Vorlage print_e vorkommt.

Ich habe nichts gegen copy&paste Programmierung. Ab und an braucht man 
einfach eine Vorlage, die man studieren kann. Aber dann sollte man 
wenigstens in der Lage sein, die Vorlage komplett zu kopieren!

Und ob du bei derartigen Problemen eine Statemachine, die auf 
Funktionspointern beruht in Eigenregie zum laufen kriegst, da hab ich so 
meine Zweifel.

[Progger (Gast)]

Sorry wenn ich nochmals nerve. Ich verstehe nicht woran dies liegen 
könnte.

FSM maschine[]={
/*0*/  {1, 0, print_ok, print_nok, compare, 'q'},
/*1*/  {2, 1, print_ok, print_nok, compare, 'u'},
/*2*/  {3, 2, print_ok, print_nok, compare, 'e'},
/*3*/  {4, 3, print_ok, print_nok, compare, 'r'},
/*4*/  {5, 4, print_ok, print_nok, compare, 't'},
/*5*/  {0, 6, print_d, print_nok, compare, 'z'},
/*6*/  {0, 6, print_e, print_nok, compare, 'y'}};

[Progger (Gast)]

Ich hab meinen Fehler gefunden. Ich danke euch viel mals.

[G. O. (aminox86)]

@Progger
Na dann funktionierts ja wohl.

@Karl heinz Buchegger
Nicht so streng, jeder hat 'mal angefangen.

An dieser Stelle soll noch der erwähnte Artikel nachgereicht werden:
Alan Cline: Build Applications Faster with State Transition Automatons, 
erschienen Dezember 1992 ab Seite 93 im 'C Users Journal'. Der Quellcode 
war oder ist im Rahmen der Wal-Nut-Creek Cd-Rom im Internet verfügbar.

Ich finde Clines Konzept einfach genial. Von allen Methoden 
Zustandsmaschinen zu konstruieren, ist diese die einfachste und 
flexibelste, die ich kenne. Mit ihr lassen sich besonders gut Tokeniser, 
Parser, Protokollstack(zB Carson: PPP Design, Implementation and 
Debugging (!mehrdimensionale Maschinentafel!)) usw. aufbauen. Ich 
verwende sie hauptsächlich für die Programmierung umfangreicher 
Menüstrukturen (Wettbewerbsbeitrag 2008: Tinykon).
mfg

[Peter Mueller (Gast)]

Hallo,

schau mal hier: www.sinelabore.com

Gruß,
Peter Mueller

[Vaclav Cechticky (Gast)]

Hi,

Have a look here: http://code.google.com/p/fwprofile/

It's an open source version (GNU GPLv3) of the state machine implemented 
in C. The concept and implementation is well-suited for use in 
mission-critical applications. There are deployments in industrial 
applications.

Regards
Vaclav

[Rufus Τ. F. (rufus)]

We're not really keen on digging up threads that have been dead or 
dormant for a long time. You've just managed to do so with a thread 
three years old.
Do you really think that the participants were sitting in front of their 
computers for three years, waiting for your contribution to arrive?

So, please refrain from attempts to rise the un-dead.

[Anton (Gast)]

Yes, someone is still redanig it  The point is, though, that currently 
we have 2 different  editions . One with full Unicode capabilities and 
one with ANSI only. ANSI is also always slower, because all the ANSI 
APIs on Windows NT and later convert the string to Unicode anyway (well, 
as much as a mapping is possible). 64bit and ANSI is pointless. But 
should we drop ANSI ultimately (not necessarily the option to get back 
to it, but cease to develop that branch, so to speak   or should we 
continue ANSI +  Unicode 32bit + Unicode 64bit.BTW: The performance 
impact on WOW64 programs is minimal. Has to do with how the stuff is 
passed to the kernel. And depending on what you consider low-level, I 
cannot really see what information is hidden from WDS that would be 
interesting for this kind of application

[Rufus Τ. F. (rufus)]

Anton schrieb:
> (well, as much as a mapping is possible)

Are you really sure that you know what you're writing about?

[Johann L. (gjlayde)]

Progger schrieb:
> Für den Einstieg bräuchte ich ein lauffähiges Beispielprogramm in AnsiC.

Das ist schon mal kein ANSI-C

#include <conio.h>
#include <windows.h>

> Kennt jemand da eine gute Quelle?

Die besten Quellen die ich kenne sind meine eigenen :-))

[Rufus Τ. F. (rufus)]

Noch mal ein DEUTLICHER HINWEIS:

Dieser Thread ist seit drei Jahren verwaist.