Re: How to translate a state/transition diagram into C-language?

Warwick Molloy - Software Engineer <wmolloy@netspace.net.au>
14 Apr 2000 23:39:19 -0400

          From comp.compilers

Related articles
How to translate a state/transition diagram into C-language? b_thiel@online.de (Bruno Thiel) (2000-03-23)
Re: How to translate a state/transition diagram into C-language? wmolloy@netspace.net.au (Warwick Molloy - Software Engineer) (2000-04-14)
| List of all articles for this month |

From: Warwick Molloy - Software Engineer <wmolloy@netspace.net.au>
Newsgroups: comp.compilers
Date: 14 Apr 2000 23:39:19 -0400
Organization: A customer of Netspace Internet.
References: 00-03-109
Keywords: lex

Hi Bruno,


Actually, there's a very simple technique for converting a
state-transition diagram into C.


Basically, the technique requires that you convert your diagram into a
state-transition table and then implement this as a pair of arrays.


For instance, say you have a simple S.T. diagram like this:


      "/ignore "/end
    (0) --> (1) --> (2)
                  /|\ |
                    | |
                    ----
                    not (") / store


The events are quotes (") and non-quotes on an incoming character
stream.


The actions are ignore, store and end.


There are three states: 0, 1 and 2.


S.T. Table is something like this:


Current Event Next Action
State State
q q'
-------------------------------
0 not " 0 ignore (implied)
0 " 1 ignore
1 not " 1 store
1 " 2 end




C code should look like this:


#define QUOTE 0
#define NONQUOTE 1


int fsm[2][2]={
/* " not " */
  {1, 0}, /* state 0 */
  {2, 1} /* state 1 */
};


#define IGNORE 10
#define STORE 20
#define END 30


int actions[2][2]={
/* " not " */
{10, 10 },
{ 30, 20}
};


void scanner( void )
{
        char ch;
        int state=0, next, event;
        int action;


        while (action != END)
        {
                ch = getchar(); /* or wherever input comes from :) */
                if (ch == 34) event = QUOTE; /* " */
                else event = NONQUOTE;


                next = fsm[ state][ event];
                action = actions[ state ][ event];
                switch( action ) {
                        /* do something */
                }
        }
}




Anyway, this is a rough example. Hope its useful.


Regards,
Warwick


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.